2
This code is derived from jgit (http://eclipse.org/jgit).
3
Copyright owners are documented in jgit's IP log.
5
This program and the accompanying materials are made available
6
under the terms of the Eclipse Distribution License v1.0 which
7
accompanies this distribution, is reproduced below, and is
8
available at http://www.eclipse.org/org/documents/edl-v10.php
12
Redistribution and use in source and binary forms, with or
13
without modification, are permitted provided that the following
16
- Redistributions of source code must retain the above copyright
17
notice, this list of conditions and the following disclaimer.
19
- Redistributions in binary form must reproduce the above
20
copyright notice, this list of conditions and the following
21
disclaimer in the documentation and/or other materials provided
22
with the distribution.
24
- Neither the name of the Eclipse Foundation, Inc. nor the
25
names of its contributors may be used to endorse or promote
26
products derived from this software without specific prior
29
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30
CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
45
using System.Collections.Generic;
54
/// Specialized variant of an ArrayList to support a
55
/// <code>RefDatabase</code>
58
/// This list is a hybrid of a Map<String,Ref> and of a List<Ref>. It
59
/// tracks reference instances by name by keeping them sorted and performing
60
/// binary search to locate an entry. Lookup time is O(log N), but addition and
61
/// removal is O(N + log N) due to the list expansion or contraction costs.
63
/// This list type is copy-on-write. Mutation methods return a new copy of the
66
/// unmodified. As a result we cannot easily implement
68
/// <see cref="System.Collections.IList{E}">System.Collections.IList<E></see>
69
/// interface contract.
72
public class RefList<T> : Iterable<Ref> where T:Ref
74
private static readonly NGit.Util.RefList<Ref> EMPTY = new NGit.Util.RefList<Ref>
77
/// <returns>an empty unmodifiable reference list.</returns>
79
public static NGit.Util.RefList<T> EmptyList<T>() where T:Ref
81
return new RefList<T>(new Ref[0], 0);
84
public static NGit.Util.RefList<Ref> EmptyList()
86
return RefList<T>.EMPTY;
89
private readonly Ref[] list;
91
private readonly int cnt;
93
internal RefList(Ref[] list, int cnt)
99
/// <summary>Initialize this list to use the same backing array as another list.</summary>
100
/// <remarks>Initialize this list to use the same backing array as another list.</remarks>
101
/// <param name="src">the source list.</param>
102
protected internal RefList(NGit.Util.RefList<T> src)
104
this.list = src.list;
108
public override Sharpen.Iterator<Ref> Iterator()
110
return new _Iterator_104(this);
113
private sealed class _Iterator_104 : Sharpen.Iterator<Ref>
115
public _Iterator_104(RefList<T> _enclosing)
117
this._enclosing = _enclosing;
122
public override bool HasNext()
124
return this.idx < this._enclosing.cnt;
127
public override Ref Next()
129
if (this.idx < this._enclosing.cnt)
131
return this._enclosing.list[this.idx++];
133
throw new NoSuchElementException();
136
public override void Remove()
138
throw new NotSupportedException();
141
private readonly RefList<T> _enclosing;
145
/// this cast as an immutable, standard
146
/// <see cref="System.Collections.IList{E}">System.Collections.IList<E></see>
149
public IList<Ref> AsList()
151
IList<Ref> r = Arrays.AsList(list).SubList(0, cnt);
152
return Sharpen.Collections.UnmodifiableList(r);
155
/// <returns>number of items in this list.</returns>
161
/// <returns>true if the size of this list is 0.</returns>
162
public bool IsEmpty()
167
/// <summary>Locate an entry by name.</summary>
168
/// <remarks>Locate an entry by name.</remarks>
169
/// <param name="name">the name of the reference to find.</param>
171
/// the index the reference is at. If the entry is not present
172
/// returns a negative value. The insertion position for the given
173
/// name can be computed from
174
/// <code>-(index + 1)</code>
177
public int Find(string name)
187
int mid = (int)(((uint)(low + high)) >> 1);
188
int cmp = RefComparator.CompareTo(list[mid], name);
209
/// <summary>Determine if a reference is present.</summary>
210
/// <remarks>Determine if a reference is present.</remarks>
211
/// <param name="name">name of the reference to find.</param>
212
/// <returns>true if the reference is present; false if it is not.</returns>
213
public bool Contains(string name)
215
return 0 <= Find(name);
218
/// <summary>Get a reference object by name.</summary>
219
/// <remarks>Get a reference object by name.</remarks>
220
/// <param name="name">the name of the reference.</param>
221
/// <returns>the reference object; null if it does not exist in this list.</returns>
222
public T Get(string name)
224
int idx = Find(name);
225
return 0 <= idx ? Get(idx) : default(T);
228
/// <summary>Get the reference at a particular index.</summary>
229
/// <remarks>Get the reference at a particular index.</remarks>
230
/// <param name="idx">
231
/// the index to obtain. Must be
232
/// <code>0 <= idx < size()</code>
235
/// <returns>the reference value, never null.</returns>
236
public T Get(int idx)
241
internal static RefList<Ref> Copy<U>(RefList<U> other) where U: Ref
243
return new RefList<Ref>(other.list, other.cnt);
247
/// Obtain a builder initialized with the first
253
/// elements from this list into a new builder,
254
/// which can be used by the caller to add additional elements.
256
/// <param name="n">the number of elements to copy.</param>
258
/// a new builder with the first
260
/// elements already added.
262
public RefListBuilder<T> Copy(int n)
264
RefListBuilder<T> r = new RefListBuilder<T>(Math.Max(16, n));
265
r.AddAll(list, 0, n);
269
/// <summary>Obtain a new copy of the list after changing one element.</summary>
271
/// Obtain a new copy of the list after changing one element.
273
/// This list instance is not affected by the replacement. Because this
274
/// method copies the entire list, it runs in O(N) time.
276
/// <param name="idx">index of the element to change.</param>
277
/// <param name="ref">the new value, must not be null.</param>
279
/// copy of this list, after replacing
285
public NGit.Util.RefList<T> Set(int idx, T @ref)
287
Ref[] newList = new Ref[cnt];
288
System.Array.Copy(list, 0, newList, 0, cnt);
290
return new NGit.Util.RefList<T>(newList, cnt);
293
/// <summary>Add an item at a specific index.</summary>
295
/// Add an item at a specific index.
297
/// This list instance is not affected by the addition. Because this method
298
/// copies the entire list, it runs in O(N) time.
300
/// <param name="idx">
301
/// position to add the item at. If negative the method assumes it
302
/// was a direct return value from
303
/// <see cref="RefList{T}.Find(string)">RefList<T>.Find(string)</see>
305
/// adjust it to the correct position.
307
/// <param name="ref">the new reference to insert.</param>
309
/// copy of this list, after making space for and adding
313
public NGit.Util.RefList<T> Add(int idx, T @ref)
319
Ref[] newList = new Ref[cnt + 1];
322
System.Array.Copy(list, 0, newList, 0, idx);
327
System.Array.Copy(list, idx, newList, idx + 1, cnt - idx);
329
return new NGit.Util.RefList<T>(newList, cnt + 1);
332
/// <summary>Remove an item at a specific index.</summary>
334
/// Remove an item at a specific index.
336
/// This list instance is not affected by the addition. Because this method
337
/// copies the entire list, it runs in O(N) time.
339
/// <param name="idx">position to remove the item from.</param>
341
/// copy of this list, after making removing the item at
345
public NGit.Util.RefList<T> Remove(int idx)
349
return EmptyList<T>();
351
Ref[] newList = new Ref[cnt - 1];
354
System.Array.Copy(list, 0, newList, 0, idx);
358
System.Array.Copy(list, idx + 1, newList, idx, cnt - (idx + 1));
360
return new NGit.Util.RefList<T>(newList, cnt - 1);
363
/// <summary>Store a reference, adding or replacing as necessary.</summary>
365
/// Store a reference, adding or replacing as necessary.
367
/// This list instance is not affected by the store. The correct position is
368
/// determined, and the item is added if missing, or replaced if existing.
369
/// Because this method copies the entire list, it runs in O(N + log N) time.
371
/// <param name="ref">the reference to store.</param>
372
/// <returns>copy of this list, after performing the addition or replacement.</returns>
373
public NGit.Util.RefList<T> Put(T @ref)
375
int idx = Find(@ref.GetName());
378
return Set(idx, @ref);
380
return Add(idx, @ref);
383
public override string ToString()
385
StringBuilder r = new StringBuilder();
390
for (int i = 1; i < cnt; i++)
401
/// <summary>Builder to facilitate fast construction of an immutable RefList.</summary>
402
/// <remarks>Builder to facilitate fast construction of an immutable RefList.</remarks>
404
public class RefListBuilder<T> where T:Ref
410
/// <summary>Create an empty list ready for items to be added.</summary>
411
/// <remarks>Create an empty list ready for items to be added.</remarks>
412
public RefListBuilder() : this(16)
416
/// <summary>Create an empty list with at least the specified capacity.</summary>
417
/// <remarks>Create an empty list with at least the specified capacity.</remarks>
418
/// <param name="capacity">the new capacity.</param>
419
public RefListBuilder(int capacity)
421
list = new Ref[capacity];
424
/// <returns>number of items in this builder's internal collection.</returns>
425
public virtual int Size()
430
/// <summary>Get the reference at a particular index.</summary>
431
/// <remarks>Get the reference at a particular index.</remarks>
432
/// <param name="idx">
433
/// the index to obtain. Must be
434
/// <code>0 <= idx < size()</code>
437
/// <returns>the reference value, never null.</returns>
438
public virtual T Get(int idx)
443
/// <summary>Remove an item at a specific index.</summary>
444
/// <remarks>Remove an item at a specific index.</remarks>
445
/// <param name="idx">position to remove the item from.</param>
446
public virtual void Remove(int idx)
448
System.Array.Copy(list, idx + 1, list, idx, size - (idx + 1));
452
/// <summary>Add the reference to the end of the array.</summary>
454
/// Add the reference to the end of the array.
456
/// References must be added in sort order, or the array must be sorted
457
/// after additions are complete using
458
/// <see cref="Builder{T}.Sort()">Builder<T>.Sort()</see>
461
/// <param name="ref"></param>
462
public virtual void Add(T @ref)
464
if (list.Length == size)
466
Ref[] n = new Ref[size * 2];
467
System.Array.Copy(list, 0, n, 0, size);
473
/// <summary>Add all items from a source array.</summary>
475
/// Add all items from a source array.
477
/// References must be added in sort order, or the array must be sorted
478
/// after additions are complete using
479
/// <see cref="Builder{T}.Sort()">Builder<T>.Sort()</see>
482
/// <param name="src">the source array.</param>
483
/// <param name="off">
486
/// to start copying from.
488
/// <param name="cnt">
489
/// number of items to copy from
493
public virtual void AddAll(Ref[] src, int off, int cnt)
495
if (list.Length < size + cnt)
497
Ref[] n = new Ref[Math.Max(size * 2, size + cnt)];
498
System.Array.Copy(list, 0, n, 0, size);
501
System.Array.Copy(src, off, list, size, cnt);
505
/// <summary>Replace a single existing element.</summary>
506
/// <remarks>Replace a single existing element.</remarks>
507
/// <param name="idx">index, must have already been added previously.</param>
508
/// <param name="ref">the new reference.</param>
509
public virtual void Set(int idx, T @ref)
514
/// <summary>Sort the list's backing array in-place.</summary>
515
/// <remarks>Sort the list's backing array in-place.</remarks>
516
public virtual void Sort()
518
Arrays.Sort(list, 0, size, RefComparator.INSTANCE);
521
/// <returns>an unmodifiable list using this collection's backing array.</returns>
522
public virtual RefList<T> ToRefList()
524
return new RefList<T>(list, size);
527
public override string ToString()
529
return ToRefList().ToString();
533
internal class RefList : RefList<Ref>
536
public RefList() : base(new Ref[0], 0)
added
removed
contrib/NGit/NGit.Util/RefList.cs
