1
|
/*
|
2
|
Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
|
3
|
Permission is hereby granted, free of charge, to any person obtaining a copy
|
4
|
of this software and associated documentation files (the "Software"), to deal
|
5
|
in the Software without restriction, including without limitation the rights
|
6
|
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
7
|
copies of the Software, and to permit persons to whom the Software is
|
8
|
furnished to do so, subject to the following conditions:
|
9
|
|
10
|
The above copyright notice and this permission notice shall be included in
|
11
|
all copies or substantial portions of the Software.
|
12
|
|
13
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
14
|
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
15
|
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
16
|
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
17
|
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
18
|
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
|
19
|
SOFTWARE.
|
20
|
*/
|
21
|
|
22
|
using System;
|
23
|
using System.Diagnostics;
|
24
|
using SCG = System.Collections.Generic;
|
25
|
namespace C5
|
26
|
{
|
27
|
/// <summary>
|
28
|
/// A collection class implementing a sorted dynamic array data structure.
|
29
|
/// </summary>
|
30
|
[Serializable]
|
31
|
public class SortedArray<T> : ArrayBase<T>, IIndexedSorted<T>
|
32
|
{
|
33
|
#region Features
|
34
|
/// <summary>
|
35
|
/// A debugging artifact. To be removed.
|
36
|
/// </summary>
|
37
|
[Flags]
|
38
|
public enum Feature : short
|
39
|
{
|
40
|
/// <summary>
|
41
|
/// A debugging artifact. To be removed.
|
42
|
/// </summary>
|
43
|
Standard = 0
|
44
|
}
|
45
|
|
46
|
|
47
|
static Feature features = Feature.Standard;
|
48
|
|
49
|
|
50
|
/// <summary>
|
51
|
/// A debugging artifact. To be removed.
|
52
|
/// </summary>
|
53
|
/// <value></value>
|
54
|
public static Feature Features { get { return features; } }
|
55
|
|
56
|
#endregion
|
57
|
|
58
|
#region Events
|
59
|
|
60
|
/// <summary>
|
61
|
///
|
62
|
/// </summary>
|
63
|
/// <value></value>
|
64
|
public override EventTypeEnum ListenableEvents { get { return EventTypeEnum.Basic; } }
|
65
|
|
66
|
#endregion
|
67
|
|
68
|
#region Fields
|
69
|
|
70
|
SCG.IComparer<T> comparer;
|
71
|
|
72
|
#endregion
|
73
|
|
74
|
#region Util
|
75
|
/// <summary>
|
76
|
///
|
77
|
/// </summary>
|
78
|
/// <param name="item">The item to search for</param>
|
79
|
/// <param name="mid">The least index, mid, for which array[mid] >= item</param>
|
80
|
/// <returns>True if item found</returns>
|
81
|
private bool binarySearch(T item, out int mid)
|
82
|
{
|
83
|
int bot = 0, top = size;
|
84
|
|
85
|
mid = top / 2;
|
86
|
while (top > bot)
|
87
|
{
|
88
|
int c;
|
89
|
|
90
|
if ((c = comparer.Compare(array[mid], item)) == 0)
|
91
|
return true;
|
92
|
|
93
|
if (c > 0)
|
94
|
{ top = mid; }
|
95
|
else
|
96
|
{ bot = mid + 1; }
|
97
|
|
98
|
mid = (bot + top) / 2;
|
99
|
}
|
100
|
|
101
|
return false;
|
102
|
}
|
103
|
|
104
|
private int indexOf(T item)
|
105
|
{
|
106
|
int ind;
|
107
|
|
108
|
if (binarySearch(item, out ind))
|
109
|
return ind;
|
110
|
|
111
|
return ~ind;
|
112
|
}
|
113
|
|
114
|
#endregion
|
115
|
|
116
|
#region Constructors
|
117
|
|
118
|
/// <summary>
|
119
|
/// Create a dynamic sorted array with a natural comparer
|
120
|
/// (and item equalityComparer, assumed compatible)
|
121
|
/// </summary>
|
122
|
/// <exception cref="NotComparableException">If <code>T</code> is not comparable.
|
123
|
/// </exception>
|
124
|
public SortedArray() : this(8) { }
|
125
|
|
126
|
|
127
|
/// <summary>
|
128
|
/// Create a dynamic sorted array with a natural comparer
|
129
|
/// (and item equalityComparer, assumed compatible)
|
130
|
/// and prescribed initial capacity.
|
131
|
/// </summary>
|
132
|
/// <exception cref="NotComparableException">If <code>T</code> is not comparable.
|
133
|
/// </exception>
|
134
|
/// <param name="capacity">The capacity</param>
|
135
|
public SortedArray(int capacity)
|
136
|
: this(capacity, Comparer<T>.Default, EqualityComparer<T>.Default) { }
|
137
|
|
138
|
|
139
|
/// <summary>
|
140
|
/// Create a dynamic sorted array with an external comparer.
|
141
|
/// <para>The itemequalityComparer will be compatible
|
142
|
/// <see cref="T:C5.ComparerZeroHashCodeEqualityComparer`1"/> since the
|
143
|
/// default equalityComparer for T (<see cref="P:C5.EqualityComparer`1.Default"/>)
|
144
|
/// is unlikely to be compatible with the external comparer. This makes the
|
145
|
/// array inadequate for use as item in a collection of unsequenced or sequenced sets or bags
|
146
|
/// (<see cref="T:C5.ICollection`1"/> and <see cref="T:C5.ISequenced`1"/>)
|
147
|
/// </para>
|
148
|
/// </summary>
|
149
|
/// <param name="comparer">The comparer</param>
|
150
|
public SortedArray(SCG.IComparer<T> comparer)
|
151
|
: this(8, comparer) { }
|
152
|
|
153
|
/// <summary>
|
154
|
/// Create a dynamic sorted array with an external comparer
|
155
|
/// and prescribed initial capacity.
|
156
|
/// <para>The itemequalityComparer will be a compatible
|
157
|
/// <see cref="T:C5.ComparerZeroHashCodeEqualityComparer`1"/> since the
|
158
|
/// default equalityComparer for T (<see cref="P:C5.EqualityComparer`1.Default"/>)
|
159
|
/// is unlikely to be compatible with the external comparer. This makes the
|
160
|
/// sorted array inadequate for use as item in a collection of unsequenced or sequenced sets or bags
|
161
|
/// (<see cref="T:C5.ICollection`1"/> and <see cref="T:C5.ISequenced`1"/>)
|
162
|
/// </para>
|
163
|
/// </summary>
|
164
|
/// <param name="capacity">The capacity</param>
|
165
|
/// <param name="comparer">The comparer</param>
|
166
|
public SortedArray(int capacity, SCG.IComparer<T> comparer)
|
167
|
: this(capacity, comparer, new ComparerZeroHashCodeEqualityComparer<T>(comparer)) { }
|
168
|
|
169
|
/// <summary>
|
170
|
/// Create a dynamic sorted array with an external comparer, an external item equalityComparer
|
171
|
/// and prescribed initial capacity. This is the constructor to use if the collection
|
172
|
/// will be used as item in a hash table based collection.
|
173
|
/// </summary>
|
174
|
/// <param name="capacity">The capacity</param>
|
175
|
/// <param name="comparer">The item comparer</param>
|
176
|
/// <param name="equalityComparer">The item equalityComparer (assumed compatible)</param>
|
177
|
public SortedArray(int capacity, SCG.IComparer<T> comparer, SCG.IEqualityComparer<T> equalityComparer)
|
178
|
: base(capacity, equalityComparer)
|
179
|
{
|
180
|
if (comparer == null)
|
181
|
throw new NullReferenceException("Comparer cannot be null");
|
182
|
this.comparer = comparer;
|
183
|
}
|
184
|
|
185
|
#endregion
|
186
|
|
187
|
#region IIndexedSorted<T> Members
|
188
|
|
189
|
/// <summary>
|
190
|
/// Determine the number of items at or above a supplied threshold.
|
191
|
/// </summary>
|
192
|
/// <param name="bot">The lower bound (inclusive)</param>
|
193
|
/// <returns>The number of matcing items.</returns>
|
194
|
[Tested]
|
195
|
public int CountFrom(T bot)
|
196
|
{
|
197
|
int lo;
|
198
|
|
199
|
binarySearch(bot, out lo);
|
200
|
return size - lo;
|
201
|
}
|
202
|
|
203
|
|
204
|
/// <summary>
|
205
|
/// Determine the number of items between two supplied thresholds.
|
206
|
/// </summary>
|
207
|
/// <param name="bot">The lower bound (inclusive)</param>
|
208
|
/// <param name="top">The upper bound (exclusive)</param>
|
209
|
/// <returns>The number of matcing items.</returns>
|
210
|
[Tested]
|
211
|
public int CountFromTo(T bot, T top)
|
212
|
{
|
213
|
int lo, hi;
|
214
|
|
215
|
binarySearch(bot, out lo);
|
216
|
binarySearch(top, out hi);
|
217
|
return hi > lo ? hi - lo : 0;
|
218
|
}
|
219
|
|
220
|
|
221
|
/// <summary>
|
222
|
/// Determine the number of items below a supplied threshold.
|
223
|
/// </summary>
|
224
|
/// <param name="top">The upper bound (exclusive)</param>
|
225
|
/// <returns>The number of matcing items.</returns>
|
226
|
[Tested]
|
227
|
public int CountTo(T top)
|
228
|
{
|
229
|
int hi;
|
230
|
|
231
|
binarySearch(top, out hi);
|
232
|
return hi;
|
233
|
}
|
234
|
|
235
|
|
236
|
/// <summary>
|
237
|
/// Query this sorted collection for items greater than or equal to a supplied value.
|
238
|
/// </summary>
|
239
|
/// <param name="bot">The lower bound (inclusive).</param>
|
240
|
/// <returns>The result directed collection.</returns>
|
241
|
[Tested]
|
242
|
public IDirectedCollectionValue<T> RangeFrom(T bot)
|
243
|
{
|
244
|
int lo;
|
245
|
|
246
|
binarySearch(bot, out lo);
|
247
|
return new Range(this, lo, size - lo, true);
|
248
|
}
|
249
|
|
250
|
|
251
|
/// <summary>
|
252
|
/// Query this sorted collection for items between two supplied values.
|
253
|
/// </summary>
|
254
|
/// <param name="bot">The lower bound (inclusive).</param>
|
255
|
/// <param name="top">The upper bound (exclusive).</param>
|
256
|
/// <returns>The result directed collection.</returns>
|
257
|
[Tested]
|
258
|
public IDirectedCollectionValue<T> RangeFromTo(T bot, T top)
|
259
|
{
|
260
|
int lo, hi;
|
261
|
|
262
|
binarySearch(bot, out lo);
|
263
|
binarySearch(top, out hi);
|
264
|
|
265
|
int sz = hi - lo;
|
266
|
|
267
|
return new Range(this, lo, sz, true);
|
268
|
}
|
269
|
|
270
|
|
271
|
/// <summary>
|
272
|
/// Query this sorted collection for items less than a supplied value.
|
273
|
/// </summary>
|
274
|
/// <param name="top">The upper bound (exclusive).</param>
|
275
|
/// <returns>The result directed collection.</returns>
|
276
|
[Tested]
|
277
|
public IDirectedCollectionValue<T> RangeTo(T top)
|
278
|
{
|
279
|
int hi;
|
280
|
|
281
|
binarySearch(top, out hi);
|
282
|
return new Range(this, 0, hi, true);
|
283
|
}
|
284
|
|
285
|
|
286
|
/// <summary>
|
287
|
/// Create a new indexed sorted collection consisting of the items of this
|
288
|
/// indexed sorted collection satisfying a certain predicate.
|
289
|
/// </summary>
|
290
|
/// <param name="f">The filter delegate defining the predicate.</param>
|
291
|
/// <returns>The new indexed sorted collection.</returns>
|
292
|
[Tested]
|
293
|
public IIndexedSorted<T> FindAll(Fun<T, bool> f)
|
294
|
{
|
295
|
SortedArray<T> res = new SortedArray<T>(comparer);
|
296
|
int j = 0, rescap = res.array.Length;
|
297
|
|
298
|
for (int i = 0; i < size; i++)
|
299
|
{
|
300
|
T a = array[i];
|
301
|
|
302
|
if (f(a))
|
303
|
{
|
304
|
if (j == rescap) res.expand(rescap = 2 * rescap, j);
|
305
|
|
306
|
res.array[j++] = a;
|
307
|
}
|
308
|
}
|
309
|
|
310
|
res.size = j;
|
311
|
return res;
|
312
|
}
|
313
|
|
314
|
|
315
|
/// <summary>
|
316
|
/// Create a new indexed sorted collection consisting of the results of
|
317
|
/// mapping all items of this list.
|
318
|
/// <exception cref="ArgumentException"/> if the map is not increasing over
|
319
|
/// the items of this collection (with respect to the two given comparison
|
320
|
/// relations).
|
321
|
/// </summary>
|
322
|
/// <param name="m">The delegate definging the map.</param>
|
323
|
/// <param name="c">The comparion relation to use for the result.</param>
|
324
|
/// <returns>The new sorted collection.</returns>
|
325
|
[Tested]
|
326
|
public IIndexedSorted<V> Map<V>(Fun<T, V> m, SCG.IComparer<V> c)
|
327
|
{
|
328
|
SortedArray<V> res = new SortedArray<V>(size, c);
|
329
|
|
330
|
if (size > 0)
|
331
|
{
|
332
|
V oldv = res.array[0] = m(array[0]), newv;
|
333
|
|
334
|
for (int i = 1; i < size; i++)
|
335
|
{
|
336
|
if (c.Compare(oldv, newv = res.array[i] = m(array[i])) >= 0)
|
337
|
throw new ArgumentException("mapper not monotonic");
|
338
|
|
339
|
oldv = newv;
|
340
|
}
|
341
|
}
|
342
|
|
343
|
res.size = size;
|
344
|
return res;
|
345
|
}
|
346
|
|
347
|
#endregion
|
348
|
|
349
|
#region ISorted<T> Members
|
350
|
|
351
|
/// <summary>
|
352
|
/// Find the strict predecessor of item in the sorted array,
|
353
|
/// that is, the greatest item in the collection smaller than the item.
|
354
|
/// </summary>
|
355
|
/// <param name="item">The item to find the predecessor for.</param>
|
356
|
/// <param name="res">The predecessor, if any; otherwise the default value for T.</param>
|
357
|
/// <returns>True if item has a predecessor; otherwise false.</returns>
|
358
|
public bool TryPredecessor(T item, out T res)
|
359
|
{
|
360
|
int lo;
|
361
|
binarySearch(item, out lo);
|
362
|
if (lo == 0)
|
363
|
{
|
364
|
res = default(T);
|
365
|
return false;
|
366
|
}
|
367
|
else
|
368
|
{
|
369
|
res = array[lo - 1];
|
370
|
return true;
|
371
|
}
|
372
|
}
|
373
|
|
374
|
|
375
|
/// <summary>
|
376
|
/// Find the strict successor of item in the sorted array,
|
377
|
/// that is, the least item in the collection greater than the supplied value.
|
378
|
/// </summary>
|
379
|
/// <param name="item">The item to find the successor for.</param>
|
380
|
/// <param name="res">The successor, if any; otherwise the default value for T.</param>
|
381
|
/// <returns>True if item has a successor; otherwise false.</returns>
|
382
|
public bool TrySuccessor(T item, out T res)
|
383
|
{
|
384
|
int hi;
|
385
|
if (binarySearch(item, out hi))
|
386
|
hi++;
|
387
|
if (hi >= size)
|
388
|
{
|
389
|
res = default(T);
|
390
|
return false;
|
391
|
} else {
|
392
|
res = array[hi];
|
393
|
return true;
|
394
|
}
|
395
|
}
|
396
|
|
397
|
|
398
|
/// <summary>
|
399
|
/// Find the weak predecessor of item in the sorted array,
|
400
|
/// that is, the greatest item in the collection smaller than or equal to the item.
|
401
|
/// </summary>
|
402
|
/// <param name="item">The item to find the weak predecessor for.</param>
|
403
|
/// <param name="res">The weak predecessor, if any; otherwise the default value for T.</param>
|
404
|
/// <returns>True if item has a weak predecessor; otherwise false.</returns>
|
405
|
public bool TryWeakPredecessor(T item, out T res)
|
406
|
{
|
407
|
int lo;
|
408
|
|
409
|
if (!binarySearch(item, out lo))
|
410
|
lo--;
|
411
|
|
412
|
if (lo < 0)
|
413
|
{
|
414
|
res = default(T);
|
415
|
return false;
|
416
|
}
|
417
|
else
|
418
|
{
|
419
|
res = array[lo];
|
420
|
return true;
|
421
|
}
|
422
|
}
|
423
|
|
424
|
|
425
|
/// <summary>
|
426
|
/// Find the weak successor of item in the sorted array,
|
427
|
/// that is, the least item in the collection greater than or equal to the supplied value.
|
428
|
/// </summary>
|
429
|
/// <param name="item">The item to find the weak successor for.</param>
|
430
|
/// <param name="res">The weak successor, if any; otherwise the default value for T.</param>
|
431
|
/// <returns>True if item has a weak successor; otherwise false.</returns>
|
432
|
public bool TryWeakSuccessor(T item, out T res)
|
433
|
{
|
434
|
int hi;
|
435
|
|
436
|
binarySearch(item, out hi);
|
437
|
if (hi >= size)
|
438
|
{
|
439
|
res = default(T);
|
440
|
return false;
|
441
|
}
|
442
|
else
|
443
|
{
|
444
|
res = array[hi];
|
445
|
return true;
|
446
|
}
|
447
|
}
|
448
|
|
449
|
|
450
|
/// <summary>
|
451
|
/// Find the strict predecessor in the sorted collection of a particular value,
|
452
|
/// i.e. the largest item in the collection less than the supplied value.
|
453
|
/// </summary>
|
454
|
/// <exception cref="NoSuchItemException"> if no such element exists (the
|
455
|
/// supplied value is less than or equal to the minimum of this collection.)</exception>
|
456
|
/// <param name="item">The item to find the predecessor for.</param>
|
457
|
/// <returns>The predecessor.</returns>
|
458
|
[Tested]
|
459
|
public T Predecessor(T item)
|
460
|
{
|
461
|
int lo;
|
462
|
|
463
|
binarySearch(item, out lo);
|
464
|
if (lo == 0)
|
465
|
throw new NoSuchItemException();
|
466
|
|
467
|
return array[lo - 1];
|
468
|
}
|
469
|
|
470
|
|
471
|
/// <summary>
|
472
|
/// Find the strict successor in the sorted collection of a particular value,
|
473
|
/// i.e. the least item in the collection greater than the supplied value.
|
474
|
/// </summary>
|
475
|
/// <exception cref="NoSuchItemException"> if no such element exists (the
|
476
|
/// supplied value is greater than or equal to the maximum of this collection.)</exception>
|
477
|
/// <param name="item">The item to find the successor for.</param>
|
478
|
/// <returns>The successor.</returns>
|
479
|
[Tested]
|
480
|
public T Successor(T item)
|
481
|
{
|
482
|
int hi;
|
483
|
|
484
|
if (binarySearch(item, out hi)) hi++;
|
485
|
|
486
|
if (hi >= size)
|
487
|
throw new NoSuchItemException();
|
488
|
|
489
|
return array[hi];
|
490
|
}
|
491
|
|
492
|
|
493
|
/// <summary>
|
494
|
/// Find the weak predecessor in the sorted collection of a particular value,
|
495
|
/// i.e. the largest item in the collection less than or equal to the supplied value.
|
496
|
/// <exception cref="NoSuchItemException"/> if no such element exists (the
|
497
|
/// supplied value is less than the minimum of this collection.)
|
498
|
/// </summary>
|
499
|
/// <param name="item">The item to find the weak predecessor for.</param>
|
500
|
/// <returns>The weak predecessor.</returns>
|
501
|
[Tested]
|
502
|
public T WeakPredecessor(T item)
|
503
|
{
|
504
|
int lo;
|
505
|
|
506
|
if (!binarySearch(item, out lo)) lo--;
|
507
|
|
508
|
if (lo < 0)
|
509
|
throw new NoSuchItemException();
|
510
|
|
511
|
return array[lo];
|
512
|
}
|
513
|
|
514
|
|
515
|
/// <summary>
|
516
|
/// Find the weak successor in the sorted collection of a particular value,
|
517
|
/// i.e. the least item in the collection greater than or equal to the supplied value.
|
518
|
/// </summary>
|
519
|
/// <exception cref="NoSuchItemException"> if no such element exists (the
|
520
|
/// supplied value is greater than the maximum of this collection.)</exception>
|
521
|
/// <param name="item">The item to find the weak successor for.</param>
|
522
|
/// <returns>The weak successor.</returns>
|
523
|
[Tested]
|
524
|
public T WeakSuccessor(T item)
|
525
|
{
|
526
|
int hi;
|
527
|
|
528
|
binarySearch(item, out hi);
|
529
|
if (hi >= size)
|
530
|
throw new NoSuchItemException();
|
531
|
|
532
|
return array[hi];
|
533
|
}
|
534
|
|
535
|
|
536
|
/// <summary>
|
537
|
/// Perform a search in the sorted collection for the ranges in which a
|
538
|
/// non-increasing (i.e. weakly decrerasing) function from the item type to
|
539
|
/// <code>int</code> is
|
540
|
/// negative, zero respectively positive. If the supplied cut function is
|
541
|
/// not non-increasing, the result of this call is undefined.
|
542
|
/// </summary>
|
543
|
/// <param name="c">The cut function <code>T</code> to <code>int</code>, given
|
544
|
/// as an <code>IComparable<T></code> object, where the cut function is
|
545
|
/// the <code>c.CompareTo(T that)</code> method.</param>
|
546
|
/// <param name="low">Returns the largest item in the collection, where the
|
547
|
/// cut function is positive (if any).</param>
|
548
|
/// <param name="lowIsValid">True if the cut function is positive somewhere
|
549
|
/// on this collection.</param>
|
550
|
/// <param name="high">Returns the least item in the collection, where the
|
551
|
/// cut function is negative (if any).</param>
|
552
|
/// <param name="highIsValid">True if the cut function is negative somewhere
|
553
|
/// on this collection.</param>
|
554
|
/// <returns></returns>
|
555
|
[Tested]
|
556
|
public bool Cut(IComparable<T> c, out T low, out bool lowIsValid, out T high, out bool highIsValid)
|
557
|
{
|
558
|
int lbest = -1, rbest = size;
|
559
|
|
560
|
low = default(T);
|
561
|
lowIsValid = false;
|
562
|
high = default(T);
|
563
|
highIsValid = false;
|
564
|
|
565
|
int bot = 0, top = size, mid, comp = -1, sol;
|
566
|
|
567
|
mid = top / 2;
|
568
|
while (top > bot)
|
569
|
{
|
570
|
if ((comp = c.CompareTo(array[mid])) == 0)
|
571
|
break;
|
572
|
|
573
|
if (comp < 0)
|
574
|
{ rbest = top = mid; }
|
575
|
else
|
576
|
{ lbest = mid; bot = mid + 1; }
|
577
|
|
578
|
mid = (bot + top) / 2;
|
579
|
}
|
580
|
|
581
|
if (comp != 0)
|
582
|
{
|
583
|
if (lbest >= 0) { lowIsValid = true; low = array[lbest]; }
|
584
|
|
585
|
if (rbest < size) { highIsValid = true; high = array[rbest]; }
|
586
|
|
587
|
return false;
|
588
|
}
|
589
|
|
590
|
sol = mid;
|
591
|
bot = sol - 1;
|
592
|
|
593
|
//Invariant: c.Compare(array[x]) < 0 when rbest <= x < size
|
594
|
// c.Compare(array[x]) >= 0 when x < bot)
|
595
|
//(Assuming c.Compare monotonic)
|
596
|
while (rbest > bot)
|
597
|
{
|
598
|
mid = (bot + rbest) / 2;
|
599
|
if (c.CompareTo(array[mid]) < 0)
|
600
|
{ rbest = mid; }
|
601
|
else
|
602
|
{ bot = mid + 1; }
|
603
|
}
|
604
|
|
605
|
if (rbest < size) { highIsValid = true; high = array[rbest]; }
|
606
|
|
607
|
top = sol + 1;
|
608
|
|
609
|
//Invariant: c.Compare(array[x]) > 0 when 0 <= x <= lbest
|
610
|
// c.Compare(array[x]) <= 0 when x>top)
|
611
|
//(Assuming c.Compare monotonic)
|
612
|
while (top > lbest)
|
613
|
{
|
614
|
mid = (lbest + top + 1) / 2;
|
615
|
if (c.CompareTo(array[mid]) > 0)
|
616
|
{ lbest = mid; }
|
617
|
else
|
618
|
{ top = mid - 1; }
|
619
|
}
|
620
|
|
621
|
if (lbest >= 0) { lowIsValid = true; low = array[lbest]; }
|
622
|
|
623
|
return true;
|
624
|
}
|
625
|
|
626
|
|
627
|
IDirectedEnumerable<T> ISorted<T>.RangeFrom(T bot)
|
628
|
{ return RangeFrom(bot); }
|
629
|
|
630
|
|
631
|
IDirectedEnumerable<T> ISorted<T>.RangeFromTo(T bot, T top)
|
632
|
{ return RangeFromTo(bot, top); }
|
633
|
|
634
|
|
635
|
IDirectedEnumerable<T> ISorted<T>.RangeTo(T top)
|
636
|
{ return RangeTo(top); }
|
637
|
|
638
|
|
639
|
/// <summary>
|
640
|
/// Create a directed collection with the same items as this collection.
|
641
|
/// </summary>
|
642
|
/// <returns>The result directed collection.</returns>
|
643
|
[Tested]
|
644
|
public IDirectedCollectionValue<T> RangeAll()
|
645
|
{ return new Range(this, 0, size, true); }
|
646
|
|
647
|
|
648
|
/// <summary>
|
649
|
/// Add all the items from another collection with an enumeration order that
|
650
|
/// is increasing in the items.
|
651
|
/// <exception cref="ArgumentException"/> if the enumerated items turns out
|
652
|
/// not to be in increasing order.
|
653
|
/// </summary>
|
654
|
/// <param name="items">The collection to add.</param>
|
655
|
/// <typeparam name="U"></typeparam>
|
656
|
[Tested]
|
657
|
public void AddSorted<U>(SCG.IEnumerable<U> items) where U : T
|
658
|
{
|
659
|
//Unless items have <=1 elements we would expect it to be
|
660
|
//too expensive to do repeated inserts, thus:
|
661
|
updatecheck();
|
662
|
|
663
|
int j = 0, i = 0, c = -1, itemcount = EnumerableBase<U>.countItems(items), numAdded = 0;
|
664
|
SortedArray<T> res = new SortedArray<T>(size + itemcount, comparer);
|
665
|
T lastitem = default(T);
|
666
|
T[] addedItems = new T[itemcount];
|
667
|
|
668
|
foreach (T item in items)
|
669
|
{
|
670
|
while (i < size && (c = comparer.Compare(array[i], item)) <= 0)
|
671
|
{
|
672
|
lastitem = res.array[j++] = array[i++];
|
673
|
if (c == 0)
|
674
|
goto next;
|
675
|
}
|
676
|
|
677
|
if (j > 0 && comparer.Compare(lastitem, item) >= 0)
|
678
|
throw new ArgumentException("Argument not sorted");
|
679
|
|
680
|
addedItems[numAdded++] = lastitem = res.array[j++] = item;
|
681
|
next:
|
682
|
c = -1;
|
683
|
}
|
684
|
|
685
|
while (i < size) res.array[j++] = array[i++];
|
686
|
|
687
|
size = j;
|
688
|
array = res.array;
|
689
|
raiseForAddAll(addedItems, numAdded);
|
690
|
}
|
691
|
|
692
|
|
693
|
/// <summary>
|
694
|
/// Remove all items of this collection above or at a supplied threshold.
|
695
|
/// </summary>
|
696
|
/// <param name="low">The lower threshold (inclusive).</param>
|
697
|
[Tested]
|
698
|
public void RemoveRangeFrom(T low)
|
699
|
{
|
700
|
int lowind;
|
701
|
|
702
|
binarySearch(low, out lowind);
|
703
|
if (lowind == size)
|
704
|
return;
|
705
|
|
706
|
T[] removed = new T[size - lowind];
|
707
|
Array.Copy(array, lowind, removed, 0, removed.Length);
|
708
|
Array.Reverse(removed);
|
709
|
|
710
|
Array.Clear(array, lowind, size - lowind);
|
711
|
size = lowind;
|
712
|
|
713
|
raiseForRemoveRange(removed);
|
714
|
}
|
715
|
|
716
|
|
717
|
/// <summary>
|
718
|
/// Remove all items of this collection between two supplied thresholds.
|
719
|
/// </summary>
|
720
|
/// <param name="low">The lower threshold (inclusive).</param>
|
721
|
/// <param name="hi">The upper threshold (exclusive).</param>
|
722
|
[Tested]
|
723
|
public void RemoveRangeFromTo(T low, T hi)
|
724
|
{
|
725
|
int lowind, highind;
|
726
|
|
727
|
binarySearch(low, out lowind);
|
728
|
binarySearch(hi, out highind);
|
729
|
if (highind <= lowind)
|
730
|
return;
|
731
|
|
732
|
T[] removed = new T[highind - lowind];
|
733
|
Array.Copy(array, lowind, removed, 0, removed.Length);
|
734
|
Array.Reverse(removed);
|
735
|
|
736
|
Array.Copy(array, highind, array, lowind, size - highind);
|
737
|
Array.Clear(array, size - highind + lowind, highind - lowind);
|
738
|
size -= highind - lowind;
|
739
|
|
740
|
raiseForRemoveRange(removed);
|
741
|
}
|
742
|
|
743
|
|
744
|
/// <summary>
|
745
|
/// Remove all items of this collection below a supplied threshold.
|
746
|
/// </summary>
|
747
|
/// <param name="hi">The upper threshold (exclusive).</param>
|
748
|
[Tested]
|
749
|
public void RemoveRangeTo(T hi)
|
750
|
{
|
751
|
int highind;
|
752
|
|
753
|
binarySearch(hi, out highind);
|
754
|
if (highind == 0)
|
755
|
return;
|
756
|
|
757
|
T[] removed = new T[highind];
|
758
|
Array.Copy(array, 0, removed, 0, removed.Length);
|
759
|
|
760
|
Array.Copy(array, highind, array, 0, size - highind);
|
761
|
Array.Clear(array, size - highind, highind);
|
762
|
size = size - highind;
|
763
|
|
764
|
raiseForRemoveRange(removed);
|
765
|
}
|
766
|
|
767
|
private void raiseForRemoveRange(T[] removed)
|
768
|
{
|
769
|
foreach(T item in removed)
|
770
|
raiseItemsRemoved(item, 1);
|
771
|
|
772
|
if(removed.Length > 0)
|
773
|
raiseCollectionChanged();
|
774
|
}
|
775
|
|
776
|
#endregion
|
777
|
|
778
|
#region ICollection<T> Members
|
779
|
/// <summary>
|
780
|
/// The value is symbolic indicating the type of asymptotic complexity
|
781
|
/// in terms of the size of this collection (worst-case).
|
782
|
/// </summary>
|
783
|
/// <value>Speed.Log</value>
|
784
|
[Tested]
|
785
|
public Speed ContainsSpeed { [Tested]get { return Speed.Log; } }
|
786
|
|
787
|
/// <summary>
|
788
|
/// Remove all items from this collection, resetting internal array size.
|
789
|
/// </summary>
|
790
|
[Tested]
|
791
|
override public void Clear()
|
792
|
{
|
793
|
int oldCount = size;
|
794
|
base.Clear();
|
795
|
if(oldCount > 0)
|
796
|
{
|
797
|
raiseCollectionCleared(true, oldCount);
|
798
|
raiseCollectionChanged();
|
799
|
}
|
800
|
}
|
801
|
|
802
|
/// <summary>
|
803
|
/// Check if this collection contains (an item equivalent according to the
|
804
|
/// itemequalityComparer) to a particular value.
|
805
|
/// </summary>
|
806
|
/// <param name="item">The value to check for.</param>
|
807
|
/// <returns>True if the items is in this collection.</returns>
|
808
|
[Tested]
|
809
|
public bool Contains(T item)
|
810
|
{
|
811
|
int ind;
|
812
|
|
813
|
return binarySearch(item, out ind);
|
814
|
}
|
815
|
|
816
|
|
817
|
/// <summary>
|
818
|
/// Check if this collection contains an item equivalent according to the
|
819
|
/// itemequalityComparer to a particular value. If so, return in the ref argument (a
|
820
|
/// binary copy of) the actual value found.
|
821
|
/// </summary>
|
822
|
/// <param name="item">The value to look for.</param>
|
823
|
/// <returns>True if the items is in this collection.</returns>
|
824
|
[Tested]
|
825
|
public bool Find(ref T item)
|
826
|
{
|
827
|
int ind;
|
828
|
|
829
|
if (binarySearch(item, out ind))
|
830
|
{
|
831
|
item = array[ind];
|
832
|
return true;
|
833
|
}
|
834
|
|
835
|
return false;
|
836
|
}
|
837
|
|
838
|
|
839
|
//This should probably just be bool Add(ref T item); !!!
|
840
|
/// <summary>
|
841
|
/// Check if this collection contains an item equivalent according to the
|
842
|
/// itemequalityComparer to a particular value. If so, return in the ref argument (a
|
843
|
/// binary copy of) the actual value found. Else, add the item to the collection.
|
844
|
/// </summary>
|
845
|
/// <param name="item">The value to look for.</param>
|
846
|
/// <returns>True if the item was added (hence not found).</returns>
|
847
|
[Tested]
|
848
|
public bool FindOrAdd(ref T item)
|
849
|
{
|
850
|
updatecheck();
|
851
|
|
852
|
int ind;
|
853
|
|
854
|
if (binarySearch(item, out ind))
|
855
|
{
|
856
|
item = array[ind];
|
857
|
return true;
|
858
|
}
|
859
|
|
860
|
if (size == array.Length) expand();
|
861
|
|
862
|
Array.Copy(array, ind, array, ind + 1, size - ind);
|
863
|
array[ind] = item;
|
864
|
size++;
|
865
|
raiseForAdd(item);
|
866
|
return false;
|
867
|
}
|
868
|
|
869
|
|
870
|
/// <summary>
|
871
|
/// Check if this collection contains an item equivalent according to the
|
872
|
/// itemequalityComparer to a particular value. If so, update the item in the collection
|
873
|
/// to with a binary copy of the supplied value. If the collection has bag semantics,
|
874
|
/// it is implementation dependent if this updates all equivalent copies in
|
875
|
/// the collection or just one.
|
876
|
/// </summary>
|
877
|
/// <param name="item">Value to update.</param>
|
878
|
/// <returns>True if the item was found and hence updated.</returns>
|
879
|
[Tested]
|
880
|
public bool Update(T item)
|
881
|
{ T olditem; return Update(item, out olditem); }
|
882
|
|
883
|
/// <summary>
|
884
|
///
|
885
|
/// </summary>
|
886
|
/// <param name="item"></param>
|
887
|
/// <param name="olditem"></param>
|
888
|
/// <returns></returns>
|
889
|
public bool Update(T item, out T olditem)
|
890
|
{
|
891
|
updatecheck();
|
892
|
|
893
|
int ind;
|
894
|
|
895
|
if (binarySearch(item, out ind))
|
896
|
{
|
897
|
olditem = array[ind];
|
898
|
array[ind] = item;
|
899
|
raiseForUpdate(item, olditem);
|
900
|
return true;
|
901
|
}
|
902
|
|
903
|
olditem = default(T);
|
904
|
return false;
|
905
|
}
|
906
|
|
907
|
|
908
|
/// <summary>
|
909
|
/// Check if this collection contains an item equivalent according to the
|
910
|
/// itemequalityComparer to a particular value. If so, update the item in the collection
|
911
|
/// to with a binary copy of the supplied value; else add the value to the collection.
|
912
|
/// </summary>
|
913
|
/// <param name="item">Value to add or update.</param>
|
914
|
/// <returns>True if the item was found and updated (hence not added).</returns>
|
915
|
[Tested]
|
916
|
public bool UpdateOrAdd(T item)
|
917
|
{ T olditem; return UpdateOrAdd(item, out olditem); }
|
918
|
|
919
|
/// <summary>
|
920
|
///
|
921
|
/// </summary>
|
922
|
/// <param name="item"></param>
|
923
|
/// <param name="olditem"></param>
|
924
|
/// <returns></returns>
|
925
|
public bool UpdateOrAdd(T item, out T olditem)
|
926
|
{
|
927
|
updatecheck();
|
928
|
|
929
|
int ind;
|
930
|
|
931
|
if (binarySearch(item, out ind))
|
932
|
{
|
933
|
olditem = array[ind];
|
934
|
array[ind] = item;
|
935
|
raiseForUpdate(item, olditem);
|
936
|
return true;
|
937
|
}
|
938
|
|
939
|
if (size == array.Length) expand();
|
940
|
|
941
|
Array.Copy(array, ind, array, ind + 1, size - ind);
|
942
|
array[ind] = item;
|
943
|
size++;
|
944
|
olditem = default(T);
|
945
|
raiseForAdd(item);
|
946
|
return false;
|
947
|
}
|
948
|
|
949
|
|
950
|
/// <summary>
|
951
|
/// Remove a particular item from this collection. If the collection has bag
|
952
|
/// semantics only one copy equivalent to the supplied item is removed.
|
953
|
/// </summary>
|
954
|
/// <param name="item">The value to remove.</param>
|
955
|
/// <returns>True if the item was found (and removed).</returns>
|
956
|
[Tested]
|
957
|
public bool Remove(T item)
|
958
|
{
|
959
|
int ind;
|
960
|
|
961
|
updatecheck();
|
962
|
if (binarySearch(item, out ind))
|
963
|
{
|
964
|
T removeditem = array[ind];
|
965
|
Array.Copy(array, ind + 1, array, ind, size - ind - 1);
|
966
|
array[--size] = default(T);
|
967
|
raiseForRemove(removeditem);
|
968
|
return true;
|
969
|
}
|
970
|
|
971
|
return false;
|
972
|
}
|
973
|
|
974
|
|
975
|
/// <summary>
|
976
|
/// Remove a particular item from this collection if found. If the collection
|
977
|
/// has bag semantics only one copy equivalent to the supplied item is removed,
|
978
|
/// which one is implementation dependent.
|
979
|
/// If an item was removed, report a binary copy of the actual item removed in
|
980
|
/// the argument.
|
981
|
/// </summary>
|
982
|
/// <param name="item">The value to remove.</param>
|
983
|
/// <param name="removeditem">The removed value.</param>
|
984
|
/// <returns>True if the item was found (and removed).</returns>
|
985
|
[Tested]
|
986
|
public bool Remove(T item, out T removeditem)
|
987
|
{
|
988
|
int ind;
|
989
|
|
990
|
updatecheck();
|
991
|
if (binarySearch(item, out ind))
|
992
|
{
|
993
|
removeditem = array[ind];
|
994
|
Array.Copy(array, ind + 1, array, ind, size - ind - 1);
|
995
|
array[--size] = default(T);
|
996
|
raiseForRemove(removeditem);
|
997
|
return true;
|
998
|
}
|
999
|
|
1000
|
removeditem = default(T);
|
1001
|
return false;
|
1002
|
}
|
1003
|
|
1004
|
|
1005
|
/// <summary>
|
1006
|
/// Remove all items in another collection from this one.
|
1007
|
/// </summary>
|
1008
|
/// <typeparam name="U"></typeparam>
|
1009
|
/// <param name="items">The items to remove.</param>
|
1010
|
[Tested]
|
1011
|
public void RemoveAll<U>(SCG.IEnumerable<U> items) where U : T
|
1012
|
{
|
1013
|
//This is O(m*logn) with n bits extra storage
|
1014
|
//(Not better to collect the m items and sort them)
|
1015
|
updatecheck();
|
1016
|
|
1017
|
RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(this);
|
1018
|
bool mustFire = raiseHandler.MustFire;
|
1019
|
|
1020
|
int[] toremove = new int[(size >> 5) + 1];
|
1021
|
int ind, j = 0;
|
1022
|
|
1023
|
foreach (T item in items)
|
1024
|
if (binarySearch(item, out ind))
|
1025
|
toremove[ind >> 5] |= 1 << (ind & 31);
|
1026
|
|
1027
|
for (int i = 0; i < size; i++)
|
1028
|
if ((toremove[i >> 5] & (1 << (i & 31))) == 0)
|
1029
|
array[j++] = array[i];
|
1030
|
else if (mustFire)
|
1031
|
raiseHandler.Remove(array[i]);
|
1032
|
|
1033
|
Array.Clear(array, j, size - j);
|
1034
|
size = j;
|
1035
|
if (mustFire)
|
1036
|
raiseHandler.Raise();
|
1037
|
}
|
1038
|
|
1039
|
/// <summary>
|
1040
|
/// Remove all items not in some other collection from this one.
|
1041
|
/// </summary>
|
1042
|
/// <typeparam name="U"></typeparam>
|
1043
|
/// <param name="items">The items to retain.</param>
|
1044
|
[Tested]
|
1045
|
public void RetainAll<U>(SCG.IEnumerable<U> items) where U : T
|
1046
|
{
|
1047
|
//This is O(m*logn) with n bits extra storage
|
1048
|
//(Not better to collect the m items and sort them)
|
1049
|
updatecheck();
|
1050
|
|
1051
|
RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(this);
|
1052
|
bool mustFire = raiseHandler.MustFire;
|
1053
|
|
1054
|
int[] toretain = new int[(size >> 5) + 1];
|
1055
|
int ind, j = 0;
|
1056
|
|
1057
|
foreach (T item in items)
|
1058
|
if (binarySearch(item, out ind))
|
1059
|
toretain[ind >> 5] |= 1 << (ind & 31);
|
1060
|
|
1061
|
for (int i = 0; i < size; i++)
|
1062
|
if ((toretain[i >> 5] & (1 << (i & 31))) != 0)
|
1063
|
array[j++] = array[i];
|
1064
|
else if (mustFire)
|
1065
|
raiseHandler.Remove(array[i]);
|
1066
|
|
1067
|
Array.Clear(array, j, size - j);
|
1068
|
size = j;
|
1069
|
if (mustFire)
|
1070
|
raiseHandler.Raise();
|
1071
|
}
|
1072
|
|
1073
|
/// <summary>
|
1074
|
/// Check if this collection contains all the values in another collection.
|
1075
|
/// Multiplicities are not taken into account.
|
1076
|
/// </summary>
|
1077
|
/// <param name="items">The </param>
|
1078
|
/// <typeparam name="U"></typeparam>
|
1079
|
/// <returns>True if all values in <code>items</code>is in this collection.</returns>
|
1080
|
[Tested]
|
1081
|
public bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T
|
1082
|
{
|
1083
|
int tmp;
|
1084
|
|
1085
|
foreach (T item in items)
|
1086
|
if (!binarySearch(item, out tmp))
|
1087
|
return false;
|
1088
|
|
1089
|
return true;
|
1090
|
}
|
1091
|
|
1092
|
|
1093
|
/// <summary>
|
1094
|
/// Count the number of items of the collection equal to a particular value.
|
1095
|
/// Returns 0 if and only if the value is not in the collection.
|
1096
|
/// </summary>
|
1097
|
/// <param name="item">The value to count.</param>
|
1098
|
/// <returns>The number of copies found (0 or 1).</returns>
|
1099
|
[Tested]
|
1100
|
public int ContainsCount(T item)
|
1101
|
{
|
1102
|
int tmp;
|
1103
|
|
1104
|
return binarySearch(item, out tmp) ? 1 : 0;
|
1105
|
}
|
1106
|
|
1107
|
/// <summary>
|
1108
|
///
|
1109
|
/// </summary>
|
1110
|
/// <returns></returns>
|
1111
|
public virtual ICollectionValue<T> UniqueItems() { return this; }
|
1112
|
|
1113
|
/// <summary>
|
1114
|
///
|
1115
|
/// </summary>
|
1116
|
/// <returns></returns>
|
1117
|
public virtual ICollectionValue<KeyValuePair<T, int>> ItemMultiplicities()
|
1118
|
{
|
1119
|
return new MultiplicityOne<T>(this);
|
1120
|
}
|
1121
|
|
1122
|
/// <summary>
|
1123
|
/// Remove all (0 or 1) items equivalent to a given value.
|
1124
|
/// </summary>
|
1125
|
/// <param name="item">The value to remove.</param>
|
1126
|
[Tested]
|
1127
|
public void RemoveAllCopies(T item) { Remove(item); }
|
1128
|
|
1129
|
|
1130
|
/// <summary>
|
1131
|
/// Check the integrity of the internal data structures of this collection.
|
1132
|
/// Only avaliable in DEBUG builds???
|
1133
|
/// </summary>
|
1134
|
/// <returns>True if check does not fail.</returns>
|
1135
|
[Tested]
|
1136
|
public override bool Check()
|
1137
|
{
|
1138
|
bool retval = true;
|
1139
|
|
1140
|
if (size > array.Length)
|
1141
|
{
|
1142
|
Console.WriteLine("Bad size ({0}) > array.Length ({1})", size, array.Length);
|
1143
|
return false;
|
1144
|
}
|
1145
|
|
1146
|
for (int i = 0; i < size; i++)
|
1147
|
{
|
1148
|
if ((object)(array[i]) == null)
|
1149
|
{
|
1150
|
Console.WriteLine("Bad element: null at index {0}", i);
|
1151
|
return false;
|
1152
|
}
|
1153
|
|
1154
|
if (i > 0 && comparer.Compare(array[i], array[i - 1]) <= 0)
|
1155
|
{
|
1156
|
Console.WriteLine("Inversion at index {0}", i);
|
1157
|
retval = false;
|
1158
|
}
|
1159
|
}
|
1160
|
|
1161
|
return retval;
|
1162
|
}
|
1163
|
|
1164
|
#endregion
|
1165
|
|
1166
|
#region IExtensible<T> Members
|
1167
|
|
1168
|
/// <summary>
|
1169
|
///
|
1170
|
/// </summary>
|
1171
|
/// <value>False since this collection has set semantics</value>
|
1172
|
[Tested]
|
1173
|
public bool AllowsDuplicates { [Tested]get { return false; } }
|
1174
|
|
1175
|
/// <summary>
|
1176
|
/// By convention this is true for any collection with set semantics.
|
1177
|
/// </summary>
|
1178
|
/// <value>True if only one representative of a group of equal items
|
1179
|
/// is kept in the collection together with the total count.</value>
|
1180
|
public virtual bool DuplicatesByCounting { get { return true; } }
|
1181
|
|
1182
|
/// <summary>
|
1183
|
/// Add an item to this collection if possible. If this collection has set
|
1184
|
/// semantics, the item will be added if not already in the collection. If
|
1185
|
/// bag semantics, the item will always be added.
|
1186
|
/// </summary>
|
1187
|
/// <param name="item">The item to add.</param>
|
1188
|
/// <returns>True if item was added.</returns>
|
1189
|
[Tested]
|
1190
|
public bool Add(T item)
|
1191
|
{
|
1192
|
updatecheck();
|
1193
|
|
1194
|
int ind;
|
1195
|
|
1196
|
if (binarySearch(item, out ind)) return false;
|
1197
|
|
1198
|
insert(ind, item);
|
1199
|
raiseForAdd(item);
|
1200
|
return true;
|
1201
|
}
|
1202
|
|
1203
|
/// <summary>
|
1204
|
/// Add an item to this collection if possible.
|
1205
|
/// </summary>
|
1206
|
/// <param name="item">The item to add.</param>
|
1207
|
[Tested]
|
1208
|
void SCG.ICollection<T>.Add(T item)
|
1209
|
{
|
1210
|
Add(item);
|
1211
|
}
|
1212
|
|
1213
|
|
1214
|
/// <summary>
|
1215
|
/// Add the elements from another collection with a more specialized item type
|
1216
|
/// to this collection. Since this
|
1217
|
/// collection has set semantics, only items not already in the collection
|
1218
|
/// will be added.
|
1219
|
/// </summary>
|
1220
|
/// <typeparam name="U">The type of items to add</typeparam>
|
1221
|
/// <param name="items">The items to add</param>
|
1222
|
[Tested]
|
1223
|
public void AddAll<U>(SCG.IEnumerable<U> items) where U : T
|
1224
|
{
|
1225
|
int toadd = EnumerableBase<U>.countItems(items), newsize = array.Length;
|
1226
|
|
1227
|
while (newsize < size + toadd) { newsize *= 2; }
|
1228
|
|
1229
|
T[] newarr = new T[newsize];
|
1230
|
|
1231
|
toadd = 0;
|
1232
|
foreach (T item in items) newarr[size + toadd++] = item;
|
1233
|
|
1234
|
Sorting.IntroSort<T>(newarr, size, toadd, comparer);
|
1235
|
|
1236
|
int j = 0, i = 0, numAdded = 0;
|
1237
|
T lastitem = default(T);
|
1238
|
T[] addedItems = new T[toadd];
|
1239
|
|
1240
|
//The following eliminates duplicates (including duplicates in input)
|
1241
|
//while merging the old and new collection
|
1242
|
for (int k = size, klimit = size + toadd; k < klimit; k++)
|
1243
|
{
|
1244
|
while (i < size && comparer.Compare(array[i], newarr[k]) <= 0)
|
1245
|
lastitem = newarr[j++] = array[i++];
|
1246
|
|
1247
|
if (j == 0 || comparer.Compare(lastitem, newarr[k]) < 0)
|
1248
|
addedItems[numAdded++] = lastitem = newarr[j++] = newarr[k];
|
1249
|
}
|
1250
|
|
1251
|
while (i < size) newarr[j++] = array[i++];
|
1252
|
|
1253
|
Array.Clear(newarr, j, size + toadd - j);
|
1254
|
size = j;
|
1255
|
array = newarr;
|
1256
|
|
1257
|
raiseForAddAll(addedItems, numAdded);
|
1258
|
}
|
1259
|
|
1260
|
private void raiseForAddAll(T[] addedItems, int numAdded)
|
1261
|
{
|
1262
|
if ((ActiveEvents & EventTypeEnum.Added) != 0)
|
1263
|
for(int i = 0 ;i < numAdded; i += 1)
|
1264
|
raiseItemsAdded(addedItems[i], 1);
|
1265
|
if (numAdded > 0)
|
1266
|
raiseCollectionChanged();
|
1267
|
}
|
1268
|
|
1269
|
#endregion
|
1270
|
|
1271
|
#region IPriorityQueue<T> Members
|
1272
|
|
1273
|
/// <summary>
|
1274
|
/// Find the current least item of this priority queue.
|
1275
|
/// </summary>
|
1276
|
/// <returns>The least item.</returns>
|
1277
|
[Tested]
|
1278
|
public T FindMin()
|
1279
|
{
|
1280
|
if (size == 0)
|
1281
|
throw new NoSuchItemException();
|
1282
|
|
1283
|
return array[0];
|
1284
|
}
|
1285
|
|
1286
|
/// <summary>
|
1287
|
/// Remove the least item from this priority queue.
|
1288
|
/// </summary>
|
1289
|
/// <returns>The removed item.</returns>
|
1290
|
[Tested]
|
1291
|
public T DeleteMin()
|
1292
|
{
|
1293
|
updatecheck();
|
1294
|
if (size == 0)
|
1295
|
throw new NoSuchItemException();
|
1296
|
|
1297
|
T retval = array[0];
|
1298
|
|
1299
|
size--;
|
1300
|
Array.Copy(array, 1, array, 0, size);
|
1301
|
array[size] = default(T);
|
1302
|
raiseForRemove(retval);
|
1303
|
return retval;
|
1304
|
}
|
1305
|
|
1306
|
|
1307
|
/// <summary>
|
1308
|
/// Find the current largest item of this priority queue.
|
1309
|
/// </summary>
|
1310
|
/// <returns>The largest item.</returns>
|
1311
|
[Tested]
|
1312
|
public T FindMax()
|
1313
|
{
|
1314
|
if (size == 0)
|
1315
|
throw new NoSuchItemException();
|
1316
|
|
1317
|
return array[size - 1];
|
1318
|
}
|
1319
|
|
1320
|
|
1321
|
/// <summary>
|
1322
|
/// Remove the largest item from this priority queue.
|
1323
|
/// </summary>
|
1324
|
/// <returns>The removed item.</returns>
|
1325
|
[Tested]
|
1326
|
public T DeleteMax()
|
1327
|
{
|
1328
|
updatecheck();
|
1329
|
if (size == 0)
|
1330
|
throw new NoSuchItemException();
|
1331
|
|
1332
|
T retval = array[size - 1];
|
1333
|
|
1334
|
size--;
|
1335
|
array[size] = default(T);
|
1336
|
raiseForRemove(retval);
|
1337
|
return retval;
|
1338
|
}
|
1339
|
|
1340
|
/// <summary>
|
1341
|
/// The comparer object supplied at creation time for this collection
|
1342
|
/// </summary>
|
1343
|
/// <value>The comparer</value>
|
1344
|
public SCG.IComparer<T> Comparer { get { return comparer; } }
|
1345
|
|
1346
|
#endregion
|
1347
|
|
1348
|
#region IIndexed<T> Members
|
1349
|
|
1350
|
/// <summary>
|
1351
|
/// <exception cref="IndexOutOfRangeException"/> if i is negative or
|
1352
|
/// >= the size of the collection.
|
1353
|
/// </summary>
|
1354
|
/// <value>The i'th item of this list.</value>
|
1355
|
/// <param name="i">the index to lookup</param>
|
1356
|
[Tested]
|
1357
|
public T this[int i]
|
1358
|
{
|
1359
|
[Tested]
|
1360
|
get
|
1361
|
{
|
1362
|
if (i < 0 || i >= size)
|
1363
|
throw new IndexOutOfRangeException();
|
1364
|
|
1365
|
return array[i];
|
1366
|
}
|
1367
|
}
|
1368
|
|
1369
|
/// <summary>
|
1370
|
///
|
1371
|
/// </summary>
|
1372
|
/// <value></value>
|
1373
|
public virtual Speed IndexingSpeed { get { return Speed.Constant; } }
|
1374
|
|
1375
|
/// <summary>
|
1376
|
/// Searches for an item in the list going forwrds from the start.
|
1377
|
/// </summary>
|
1378
|
/// <param name="item">Item to search for.</param>
|
1379
|
/// <returns>Index of item from start.</returns>
|
1380
|
[Tested]
|
1381
|
public int IndexOf(T item) { return indexOf(item); }
|
1382
|
|
1383
|
|
1384
|
/// <summary>
|
1385
|
/// Searches for an item in the list going backwords from the end.
|
1386
|
/// </summary>
|
1387
|
/// <param name="item">Item to search for.</param>
|
1388
|
/// <returns>Index of of item from the end.</returns>
|
1389
|
[Tested]
|
1390
|
public int LastIndexOf(T item) { return indexOf(item); }
|
1391
|
|
1392
|
|
1393
|
/// <summary>
|
1394
|
/// Remove the item at a specific position of the list.
|
1395
|
/// <exception cref="IndexOutOfRangeException"/> if i is negative or
|
1396
|
/// >= the size of the collection.
|
1397
|
/// </summary>
|
1398
|
/// <param name="i">The index of the item to remove.</param>
|
1399
|
/// <returns>The removed item.</returns>
|
1400
|
[Tested]
|
1401
|
public T RemoveAt(int i)
|
1402
|
{
|
1403
|
if (i < 0 || i >= size)
|
1404
|
throw new IndexOutOfRangeException("Index out of range for sequenced collectionvalue");
|
1405
|
|
1406
|
updatecheck();
|
1407
|
|
1408
|
T retval = array[i];
|
1409
|
|
1410
|
size--;
|
1411
|
Array.Copy(array, i + 1, array, i, size - i);
|
1412
|
array[size] = default(T);
|
1413
|
raiseForRemoveAt(i, retval);
|
1414
|
return retval;
|
1415
|
}
|
1416
|
|
1417
|
/// <summary>
|
1418
|
/// Remove all items in an index interval.
|
1419
|
/// <exception cref="IndexOutOfRangeException"/>???.
|
1420
|
/// </summary>
|
1421
|
/// <param name="start">The index of the first item to remove.</param>
|
1422
|
/// <param name="count">The number of items to remove.</param>
|
1423
|
[Tested]
|
1424
|
public void RemoveInterval(int start, int count)
|
1425
|
{
|
1426
|
updatecheck();
|
1427
|
checkRange(start, count);
|
1428
|
Array.Copy(array, start + count, array, start, size - start - count);
|
1429
|
size -= count;
|
1430
|
Array.Clear(array, size, count);
|
1431
|
raiseForRemoveInterval(start, count);
|
1432
|
}
|
1433
|
|
1434
|
private void raiseForRemoveInterval(int start, int count)
|
1435
|
{
|
1436
|
if (ActiveEvents != 0 && count > 0)
|
1437
|
{
|
1438
|
raiseCollectionCleared(size == 0, count);
|
1439
|
raiseCollectionChanged();
|
1440
|
}
|
1441
|
}
|
1442
|
|
1443
|
#endregion
|
1444
|
|
1445
|
#region IDirectedEnumerable<T> Members
|
1446
|
|
1447
|
/// <summary>
|
1448
|
/// Create a collection containing the same items as this collection, but
|
1449
|
/// whose enumerator will enumerate the items backwards. The new collection
|
1450
|
/// will become invalid if the original is modified. Method typicaly used as in
|
1451
|
/// <code>foreach (T x in coll.Backwards()) {...}</code>
|
1452
|
/// </summary>
|
1453
|
/// <returns>The backwards collection.</returns>
|
1454
|
[Tested]
|
1455
|
IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards()
|
1456
|
{ return Backwards(); }
|
1457
|
|
1458
|
#endregion
|
1459
|
|
1460
|
#region ICloneable Members
|
1461
|
|
1462
|
/// <summary>
|
1463
|
/// Make a shallow copy of this SortedArray.
|
1464
|
/// </summary>
|
1465
|
/// <returns></returns>
|
1466
|
public virtual object Clone()
|
1467
|
{
|
1468
|
SortedArray<T> clone = new SortedArray<T>(size, comparer, itemequalityComparer);
|
1469
|
clone.AddSorted(this);
|
1470
|
return clone;
|
1471
|
}
|
1472
|
|
1473
|
#endregion
|
1474
|
|
1475
|
}
|
1476
|
}
|