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
|
/// An entry in a dictionary from K to V.
|
29
|
/// </summary>
|
30
|
[Serializable]
|
31
|
public struct KeyValuePair<K, V> : IEquatable<KeyValuePair<K, V>>, IShowable
|
32
|
{
|
33
|
/// <summary>
|
34
|
/// The key field of the entry
|
35
|
/// </summary>
|
36
|
public K Key;
|
37
|
|
38
|
/// <summary>
|
39
|
/// The value field of the entry
|
40
|
/// </summary>
|
41
|
public V Value;
|
42
|
|
43
|
/// <summary>
|
44
|
/// Create an entry with specified key and value
|
45
|
/// </summary>
|
46
|
/// <param name="key">The key</param>
|
47
|
/// <param name="value">The value</param>
|
48
|
public KeyValuePair(K key, V value) { Key = key; Value = value; }
|
49
|
|
50
|
|
51
|
/// <summary>
|
52
|
/// Create an entry with a specified key. The value will be the default value of type <code>V</code>.
|
53
|
/// </summary>
|
54
|
/// <param name="key">The key</param>
|
55
|
public KeyValuePair(K key) { Key = key; Value = default(V); }
|
56
|
|
57
|
|
58
|
/// <summary>
|
59
|
/// Pretty print an entry
|
60
|
/// </summary>
|
61
|
/// <returns>(key, value)</returns>
|
62
|
[Tested]
|
63
|
public override string ToString() { return "(" + Key + ", " + Value + ")"; }
|
64
|
|
65
|
|
66
|
/// <summary>
|
67
|
/// Check equality of entries.
|
68
|
/// </summary>
|
69
|
/// <param name="obj">The other object</param>
|
70
|
/// <returns>True if obj is an entry of the same type and has the same key and value</returns>
|
71
|
[Tested]
|
72
|
public override bool Equals(object obj)
|
73
|
{
|
74
|
if (!(obj is KeyValuePair<K, V>))
|
75
|
return false;
|
76
|
KeyValuePair<K, V> other = (KeyValuePair<K, V>)obj;
|
77
|
return Equals(other);
|
78
|
}
|
79
|
|
80
|
|
81
|
/// <summary>
|
82
|
/// Get the hash code of the pair.
|
83
|
/// </summary>
|
84
|
/// <returns>The hash code</returns>
|
85
|
[Tested]
|
86
|
public override int GetHashCode() { return EqualityComparer<K>.Default.GetHashCode(Key) + 13984681 * EqualityComparer<V>.Default.GetHashCode(Value); }
|
87
|
|
88
|
/// <summary>
|
89
|
///
|
90
|
/// </summary>
|
91
|
/// <param name="other"></param>
|
92
|
/// <returns></returns>
|
93
|
public bool Equals(KeyValuePair<K, V> other)
|
94
|
{
|
95
|
return EqualityComparer<K>.Default.Equals(Key, other.Key) && EqualityComparer<V>.Default.Equals(Value, other.Value);
|
96
|
}
|
97
|
|
98
|
/// <summary>
|
99
|
///
|
100
|
/// </summary>
|
101
|
/// <param name="pair1"></param>
|
102
|
/// <param name="pair2"></param>
|
103
|
/// <returns></returns>
|
104
|
public static bool operator ==(KeyValuePair<K, V> pair1, KeyValuePair<K, V> pair2) { return pair1.Equals(pair2); }
|
105
|
|
106
|
/// <summary>
|
107
|
///
|
108
|
/// </summary>
|
109
|
/// <param name="pair1"></param>
|
110
|
/// <param name="pair2"></param>
|
111
|
/// <returns></returns>
|
112
|
public static bool operator !=(KeyValuePair<K, V> pair1, KeyValuePair<K, V> pair2) { return !pair1.Equals(pair2); }
|
113
|
|
114
|
#region IShowable Members
|
115
|
|
116
|
/// <summary>
|
117
|
///
|
118
|
/// </summary>
|
119
|
/// <param name="stringbuilder"></param>
|
120
|
/// <param name="formatProvider"></param>
|
121
|
/// <param name="rest"></param>
|
122
|
/// <returns></returns>
|
123
|
public bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
|
124
|
{
|
125
|
if (rest < 0)
|
126
|
return false;
|
127
|
if (!Showing.Show(Key, stringbuilder, ref rest, formatProvider))
|
128
|
return false;
|
129
|
stringbuilder.Append(" => ");
|
130
|
rest -= 4;
|
131
|
if (!Showing.Show(Value, stringbuilder, ref rest, formatProvider))
|
132
|
return false;
|
133
|
return rest >= 0;
|
134
|
}
|
135
|
#endregion
|
136
|
|
137
|
#region IFormattable Members
|
138
|
|
139
|
/// <summary>
|
140
|
///
|
141
|
/// </summary>
|
142
|
/// <param name="format"></param>
|
143
|
/// <param name="formatProvider"></param>
|
144
|
/// <returns></returns>
|
145
|
public string ToString(string format, IFormatProvider formatProvider)
|
146
|
{
|
147
|
return Showing.ShowString(this, format, formatProvider);
|
148
|
}
|
149
|
|
150
|
#endregion
|
151
|
}
|
152
|
|
153
|
|
154
|
|
155
|
/// <summary>
|
156
|
/// Default comparer for dictionary entries in a sorted dictionary.
|
157
|
/// Entry comparisons only look at keys and uses an externally defined comparer for that.
|
158
|
/// </summary>
|
159
|
[Serializable]
|
160
|
public class KeyValuePairComparer<K, V> : SCG.IComparer<KeyValuePair<K, V>>
|
161
|
{
|
162
|
SCG.IComparer<K> comparer;
|
163
|
|
164
|
|
165
|
/// <summary>
|
166
|
/// Create an entry comparer for a item comparer of the keys
|
167
|
/// </summary>
|
168
|
/// <param name="comparer">Comparer of keys</param>
|
169
|
public KeyValuePairComparer(SCG.IComparer<K> comparer)
|
170
|
{
|
171
|
if (comparer == null)
|
172
|
throw new NullReferenceException();
|
173
|
this.comparer = comparer;
|
174
|
}
|
175
|
|
176
|
|
177
|
/// <summary>
|
178
|
/// Compare two entries
|
179
|
/// </summary>
|
180
|
/// <param name="entry1">First entry</param>
|
181
|
/// <param name="entry2">Second entry</param>
|
182
|
/// <returns>The result of comparing the keys</returns>
|
183
|
[Tested]
|
184
|
public int Compare(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)
|
185
|
{ return comparer.Compare(entry1.Key, entry2.Key); }
|
186
|
}
|
187
|
|
188
|
|
189
|
|
190
|
/// <summary>
|
191
|
/// Default equalityComparer for dictionary entries.
|
192
|
/// Operations only look at keys and uses an externaly defined equalityComparer for that.
|
193
|
/// </summary>
|
194
|
[Serializable]
|
195
|
public sealed class KeyValuePairEqualityComparer<K, V> : SCG.IEqualityComparer<KeyValuePair<K, V>>
|
196
|
{
|
197
|
SCG.IEqualityComparer<K> keyequalityComparer;
|
198
|
|
199
|
|
200
|
/// <summary>
|
201
|
/// Create an entry equalityComparer using the default equalityComparer for keys
|
202
|
/// </summary>
|
203
|
public KeyValuePairEqualityComparer() { keyequalityComparer = EqualityComparer<K>.Default; }
|
204
|
|
205
|
|
206
|
/// <summary>
|
207
|
/// Create an entry equalityComparer from a specified item equalityComparer for the keys
|
208
|
/// </summary>
|
209
|
/// <param name="keyequalityComparer">The key equalityComparer</param>
|
210
|
public KeyValuePairEqualityComparer(SCG.IEqualityComparer<K> keyequalityComparer)
|
211
|
{
|
212
|
if (keyequalityComparer == null)
|
213
|
throw new NullReferenceException("Key equality comparer cannot be null");
|
214
|
this.keyequalityComparer = keyequalityComparer;
|
215
|
}
|
216
|
|
217
|
|
218
|
/// <summary>
|
219
|
/// Get the hash code of the entry
|
220
|
/// </summary>
|
221
|
/// <param name="entry">The entry</param>
|
222
|
/// <returns>The hash code of the key</returns>
|
223
|
[Tested]
|
224
|
public int GetHashCode(KeyValuePair<K, V> entry) { return keyequalityComparer.GetHashCode(entry.Key); }
|
225
|
|
226
|
|
227
|
/// <summary>
|
228
|
/// Test two entries for equality
|
229
|
/// </summary>
|
230
|
/// <param name="entry1">First entry</param>
|
231
|
/// <param name="entry2">Second entry</param>
|
232
|
/// <returns>True if keys are equal</returns>
|
233
|
[Tested]
|
234
|
public bool Equals(KeyValuePair<K, V> entry1, KeyValuePair<K, V> entry2)
|
235
|
{ return keyequalityComparer.Equals(entry1.Key, entry2.Key); }
|
236
|
}
|
237
|
|
238
|
|
239
|
|
240
|
/// <summary>
|
241
|
/// A base class for implementing a dictionary based on a set collection implementation.
|
242
|
/// <i>See the source code for <see cref="T:C5.HashDictionary`2"/> for an example</i>
|
243
|
///
|
244
|
/// </summary>
|
245
|
[Serializable]
|
246
|
public abstract class DictionaryBase<K, V> : CollectionValueBase<KeyValuePair<K, V>>, IDictionary<K, V>
|
247
|
{
|
248
|
/// <summary>
|
249
|
/// The set collection of entries underlying this dictionary implementation
|
250
|
/// </summary>
|
251
|
protected ICollection<KeyValuePair<K, V>> pairs;
|
252
|
|
253
|
SCG.IEqualityComparer<K> keyequalityComparer;
|
254
|
|
255
|
#region Events
|
256
|
ProxyEventBlock<KeyValuePair<K, V>> eventBlock;
|
257
|
|
258
|
/// <summary>
|
259
|
/// The change event. Will be raised for every change operation on the collection.
|
260
|
/// </summary>
|
261
|
public override event CollectionChangedHandler<KeyValuePair<K, V>> CollectionChanged
|
262
|
{
|
263
|
add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionChanged += value; }
|
264
|
remove { if (eventBlock != null) eventBlock.CollectionChanged -= value; }
|
265
|
}
|
266
|
|
267
|
/// <summary>
|
268
|
/// The change event. Will be raised for every change operation on the collection.
|
269
|
/// </summary>
|
270
|
public override event CollectionClearedHandler<KeyValuePair<K, V>> CollectionCleared
|
271
|
{
|
272
|
add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).CollectionCleared += value; }
|
273
|
remove { if (eventBlock != null) eventBlock.CollectionCleared -= value; }
|
274
|
}
|
275
|
|
276
|
/// <summary>
|
277
|
/// The item added event. Will be raised for every individual addition to the collection.
|
278
|
/// </summary>
|
279
|
public override event ItemsAddedHandler<KeyValuePair<K, V>> ItemsAdded
|
280
|
{
|
281
|
add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsAdded += value; }
|
282
|
remove { if (eventBlock != null) eventBlock.ItemsAdded -= value; }
|
283
|
}
|
284
|
|
285
|
/// <summary>
|
286
|
/// The item added event. Will be raised for every individual removal from the collection.
|
287
|
/// </summary>
|
288
|
public override event ItemsRemovedHandler<KeyValuePair<K, V>> ItemsRemoved
|
289
|
{
|
290
|
add { (eventBlock ?? (eventBlock = new ProxyEventBlock<KeyValuePair<K, V>>(this, pairs))).ItemsRemoved += value; }
|
291
|
remove { if (eventBlock != null) eventBlock.ItemsRemoved -= value; }
|
292
|
}
|
293
|
|
294
|
/// <summary>
|
295
|
///
|
296
|
/// </summary>
|
297
|
public override EventTypeEnum ListenableEvents
|
298
|
{
|
299
|
get
|
300
|
{
|
301
|
return EventTypeEnum.Basic;
|
302
|
}
|
303
|
}
|
304
|
|
305
|
/// <summary>
|
306
|
///
|
307
|
/// </summary>
|
308
|
public override EventTypeEnum ActiveEvents
|
309
|
{
|
310
|
get
|
311
|
{
|
312
|
return pairs.ActiveEvents;
|
313
|
}
|
314
|
}
|
315
|
|
316
|
#endregion
|
317
|
|
318
|
/// <summary>
|
319
|
///
|
320
|
/// </summary>
|
321
|
/// <param name="keyequalityComparer"></param>
|
322
|
protected DictionaryBase(SCG.IEqualityComparer<K> keyequalityComparer)
|
323
|
{
|
324
|
if (keyequalityComparer == null)
|
325
|
throw new NullReferenceException("Key equality comparer cannot be null");
|
326
|
this.keyequalityComparer = keyequalityComparer;
|
327
|
}
|
328
|
|
329
|
#region IDictionary<K,V> Members
|
330
|
|
331
|
/// <summary>
|
332
|
///
|
333
|
/// </summary>
|
334
|
/// <value></value>
|
335
|
public virtual SCG.IEqualityComparer<K> EqualityComparer { get { return keyequalityComparer; } }
|
336
|
|
337
|
|
338
|
/// <summary>
|
339
|
/// Add a new (key, value) pair (a mapping) to the dictionary.
|
340
|
/// </summary>
|
341
|
/// <exception cref="DuplicateNotAllowedException"> if there already is an entry with the same key. </exception>
|
342
|
/// <param name="key">Key to add</param>
|
343
|
/// <param name="value">Value to add</param>
|
344
|
[Tested]
|
345
|
public virtual void Add(K key, V value)
|
346
|
{
|
347
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
|
348
|
|
349
|
if (!pairs.Add(p))
|
350
|
throw new DuplicateNotAllowedException("Key being added: '" + key + "'");
|
351
|
}
|
352
|
|
353
|
/// <summary>
|
354
|
/// Add the entries from a collection of <see cref="T:C5.KeyValuePair`2"/> pairs to this dictionary.
|
355
|
/// <para><b>TODO: add restrictions L:K and W:V when the .Net SDK allows it </b></para>
|
356
|
/// </summary>
|
357
|
/// <exception cref="DuplicateNotAllowedException">
|
358
|
/// If the input contains duplicate keys or a key already present in this dictionary.</exception>
|
359
|
/// <param name="entries"></param>
|
360
|
public virtual void AddAll<L, W>(SCG.IEnumerable<KeyValuePair<L, W>> entries)
|
361
|
where L : K
|
362
|
where W : V
|
363
|
{
|
364
|
foreach (KeyValuePair<L, W> pair in entries)
|
365
|
{
|
366
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(pair.Key, pair.Value);
|
367
|
if (!pairs.Add(p))
|
368
|
throw new DuplicateNotAllowedException("Key being added: '" + pair.Key + "'");
|
369
|
}
|
370
|
}
|
371
|
|
372
|
/// <summary>
|
373
|
/// Remove an entry with a given key from the dictionary
|
374
|
/// </summary>
|
375
|
/// <param name="key">The key of the entry to remove</param>
|
376
|
/// <returns>True if an entry was found (and removed)</returns>
|
377
|
[Tested]
|
378
|
public virtual bool Remove(K key)
|
379
|
{
|
380
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
|
381
|
|
382
|
return pairs.Remove(p);
|
383
|
}
|
384
|
|
385
|
|
386
|
/// <summary>
|
387
|
/// Remove an entry with a given key from the dictionary and report its value.
|
388
|
/// </summary>
|
389
|
/// <param name="key">The key of the entry to remove</param>
|
390
|
/// <param name="value">On exit, the value of the removed entry</param>
|
391
|
/// <returns>True if an entry was found (and removed)</returns>
|
392
|
[Tested]
|
393
|
public virtual bool Remove(K key, out V value)
|
394
|
{
|
395
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
|
396
|
|
397
|
if (pairs.Remove(p, out p))
|
398
|
{
|
399
|
value = p.Value;
|
400
|
return true;
|
401
|
}
|
402
|
else
|
403
|
{
|
404
|
value = default(V);
|
405
|
return false;
|
406
|
}
|
407
|
}
|
408
|
|
409
|
|
410
|
/// <summary>
|
411
|
/// Remove all entries from the dictionary
|
412
|
/// </summary>
|
413
|
[Tested]
|
414
|
public virtual void Clear() { pairs.Clear(); }
|
415
|
|
416
|
/// <summary>
|
417
|
///
|
418
|
/// </summary>
|
419
|
/// <value></value>
|
420
|
public virtual Speed ContainsSpeed { get { return pairs.ContainsSpeed; } }
|
421
|
|
422
|
/// <summary>
|
423
|
/// Check if there is an entry with a specified key
|
424
|
/// </summary>
|
425
|
/// <param name="key">The key to look for</param>
|
426
|
/// <returns>True if key was found</returns>
|
427
|
[Tested]
|
428
|
public virtual bool Contains(K key)
|
429
|
{
|
430
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
|
431
|
|
432
|
return pairs.Contains(p);
|
433
|
}
|
434
|
|
435
|
[Serializable]
|
436
|
class LiftedEnumerable<H> : SCG.IEnumerable<KeyValuePair<K, V>> where H : K
|
437
|
{
|
438
|
SCG.IEnumerable<H> keys;
|
439
|
public LiftedEnumerable(SCG.IEnumerable<H> keys) { this.keys = keys; }
|
440
|
public SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator() { foreach (H key in keys) yield return new KeyValuePair<K, V>(key); }
|
441
|
|
442
|
#region IEnumerable Members
|
443
|
|
444
|
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
|
445
|
{
|
446
|
throw new Exception("The method or operation is not implemented.");
|
447
|
}
|
448
|
|
449
|
#endregion
|
450
|
}
|
451
|
|
452
|
/// <summary>
|
453
|
///
|
454
|
/// </summary>
|
455
|
/// <param name="keys"></param>
|
456
|
/// <returns></returns>
|
457
|
public virtual bool ContainsAll<H>(SCG.IEnumerable<H> keys) where H : K
|
458
|
{
|
459
|
return pairs.ContainsAll(new LiftedEnumerable<H>(keys));
|
460
|
}
|
461
|
|
462
|
/// <summary>
|
463
|
/// Check if there is an entry with a specified key and report the corresponding
|
464
|
/// value if found. This can be seen as a safe form of "val = this[key]".
|
465
|
/// </summary>
|
466
|
/// <param name="key">The key to look for</param>
|
467
|
/// <param name="value">On exit, the value of the entry</param>
|
468
|
/// <returns>True if key was found</returns>
|
469
|
[Tested]
|
470
|
public virtual bool Find(K key, out V value)
|
471
|
{
|
472
|
return Find(ref key, out value);
|
473
|
}
|
474
|
/// <summary>
|
475
|
/// Check if there is an entry with a specified key and report the corresponding
|
476
|
/// value if found. This can be seen as a safe form of "val = this[key]".
|
477
|
/// </summary>
|
478
|
/// <param name="key">The key to look for</param>
|
479
|
/// <param name="value">On exit, the value of the entry</param>
|
480
|
/// <returns>True if key was found</returns>
|
481
|
public virtual bool Find(ref K key, out V value)
|
482
|
{
|
483
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
|
484
|
|
485
|
if (pairs.Find(ref p))
|
486
|
{
|
487
|
key = p.Key;
|
488
|
value = p.Value;
|
489
|
return true;
|
490
|
}
|
491
|
else
|
492
|
{
|
493
|
value = default(V);
|
494
|
return false;
|
495
|
}
|
496
|
}
|
497
|
|
498
|
|
499
|
/// <summary>
|
500
|
/// Look for a specific key in the dictionary and if found replace the value with a new one.
|
501
|
/// This can be seen as a non-adding version of "this[key] = val".
|
502
|
/// </summary>
|
503
|
/// <param name="key">The key to look for</param>
|
504
|
/// <param name="value">The new value</param>
|
505
|
/// <returns>True if key was found</returns>
|
506
|
[Tested]
|
507
|
public virtual bool Update(K key, V value)
|
508
|
{
|
509
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
|
510
|
|
511
|
return pairs.Update(p);
|
512
|
}
|
513
|
|
514
|
|
515
|
/// <summary>
|
516
|
///
|
517
|
/// </summary>
|
518
|
/// <param name="key"></param>
|
519
|
/// <param name="value"></param>
|
520
|
/// <param name="oldvalue"></param>
|
521
|
/// <returns></returns>
|
522
|
public virtual bool Update(K key, V value, out V oldvalue)
|
523
|
{
|
524
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
|
525
|
|
526
|
bool retval = pairs.Update(p, out p);
|
527
|
oldvalue = p.Value;
|
528
|
return retval;
|
529
|
}
|
530
|
|
531
|
|
532
|
/// <summary>
|
533
|
/// Look for a specific key in the dictionary. If found, report the corresponding value,
|
534
|
/// else add an entry with the key and the supplied value.
|
535
|
/// </summary>
|
536
|
/// <param name="key">On entry the key to look for</param>
|
537
|
/// <param name="value">On entry the value to add if the key is not found.
|
538
|
/// On exit the value found if any.</param>
|
539
|
/// <returns>True if key was found</returns>
|
540
|
[Tested]
|
541
|
public virtual bool FindOrAdd(K key, ref V value)
|
542
|
{
|
543
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
|
544
|
|
545
|
if (!pairs.FindOrAdd(ref p))
|
546
|
return false;
|
547
|
else
|
548
|
{
|
549
|
value = p.Value;
|
550
|
//key = p.key;
|
551
|
return true;
|
552
|
}
|
553
|
}
|
554
|
|
555
|
|
556
|
/// <summary>
|
557
|
/// Update value in dictionary corresponding to key if found, else add new entry.
|
558
|
/// More general than "this[key] = val;" by reporting if key was found.
|
559
|
/// </summary>
|
560
|
/// <param name="key">The key to look for</param>
|
561
|
/// <param name="value">The value to add or replace with.</param>
|
562
|
/// <returns>True if entry was updated.</returns>
|
563
|
[Tested]
|
564
|
public virtual bool UpdateOrAdd(K key, V value)
|
565
|
{
|
566
|
return pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value));
|
567
|
}
|
568
|
|
569
|
|
570
|
/// <summary>
|
571
|
/// Update value in dictionary corresponding to key if found, else add new entry.
|
572
|
/// More general than "this[key] = val;" by reporting if key was found and the old value if any.
|
573
|
/// </summary>
|
574
|
/// <param name="key"></param>
|
575
|
/// <param name="value"></param>
|
576
|
/// <param name="oldvalue"></param>
|
577
|
/// <returns></returns>
|
578
|
public virtual bool UpdateOrAdd(K key, V value, out V oldvalue)
|
579
|
{
|
580
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(key, value);
|
581
|
bool retval = pairs.UpdateOrAdd(p, out p);
|
582
|
oldvalue = p.Value;
|
583
|
return retval;
|
584
|
}
|
585
|
|
586
|
|
587
|
|
588
|
#region Keys,Values support classes
|
589
|
[Serializable]
|
590
|
internal class ValuesCollection : CollectionValueBase<V>, ICollectionValue<V>
|
591
|
{
|
592
|
ICollection<KeyValuePair<K, V>> pairs;
|
593
|
|
594
|
|
595
|
internal ValuesCollection(ICollection<KeyValuePair<K, V>> pairs)
|
596
|
{ this.pairs = pairs; }
|
597
|
|
598
|
|
599
|
public override V Choose() { return pairs.Choose().Value; }
|
600
|
|
601
|
[Tested]
|
602
|
public override SCG.IEnumerator<V> GetEnumerator()
|
603
|
{
|
604
|
//Updatecheck is performed by the pairs enumerator
|
605
|
foreach (KeyValuePair<K, V> p in pairs)
|
606
|
yield return p.Value;
|
607
|
}
|
608
|
|
609
|
public override bool IsEmpty { get { return pairs.IsEmpty; } }
|
610
|
|
611
|
[Tested]
|
612
|
public override int Count { [Tested]get { return pairs.Count; } }
|
613
|
|
614
|
public override Speed CountSpeed { get { return Speed.Constant; } }
|
615
|
}
|
616
|
|
617
|
|
618
|
|
619
|
[Serializable]
|
620
|
internal class KeysCollection : CollectionValueBase<K>, ICollectionValue<K>
|
621
|
{
|
622
|
ICollection<KeyValuePair<K, V>> pairs;
|
623
|
|
624
|
|
625
|
internal KeysCollection(ICollection<KeyValuePair<K, V>> pairs)
|
626
|
{ this.pairs = pairs; }
|
627
|
|
628
|
public override K Choose() { return pairs.Choose().Key; }
|
629
|
|
630
|
[Tested]
|
631
|
public override SCG.IEnumerator<K> GetEnumerator()
|
632
|
{
|
633
|
foreach (KeyValuePair<K, V> p in pairs)
|
634
|
yield return p.Key;
|
635
|
}
|
636
|
|
637
|
public override bool IsEmpty { get { return pairs.IsEmpty; } }
|
638
|
|
639
|
[Tested]
|
640
|
public override int Count { [Tested]get { return pairs.Count; } }
|
641
|
|
642
|
public override Speed CountSpeed { get { return pairs.CountSpeed; } }
|
643
|
}
|
644
|
#endregion
|
645
|
|
646
|
/// <summary>
|
647
|
///
|
648
|
/// </summary>
|
649
|
/// <value>A collection containg the all the keys of the dictionary</value>
|
650
|
[Tested]
|
651
|
public virtual ICollectionValue<K> Keys { [Tested]get { return new KeysCollection(pairs); } }
|
652
|
|
653
|
|
654
|
/// <summary>
|
655
|
///
|
656
|
/// </summary>
|
657
|
/// <value>A collection containing all the values of the dictionary</value>
|
658
|
[Tested]
|
659
|
public virtual ICollectionValue<V> Values { [Tested]get { return new ValuesCollection(pairs); } }
|
660
|
|
661
|
/// <summary>
|
662
|
///
|
663
|
/// </summary>
|
664
|
public virtual Fun<K, V> Fun { get { return delegate(K k) { return this[k]; }; } }
|
665
|
|
666
|
/// <summary>
|
667
|
/// Indexer by key for dictionary.
|
668
|
/// <para>The get method will throw an exception if no entry is found. </para>
|
669
|
/// <para>The set method behaves like <see cref="M:C5.DictionaryBase`2.UpdateOrAdd(`0,`1)"/>.</para>
|
670
|
/// </summary>
|
671
|
/// <exception cref="NoSuchItemException"> On get if no entry is found. </exception>
|
672
|
/// <value>The value corresponding to the key</value>
|
673
|
[Tested]
|
674
|
public virtual V this[K key]
|
675
|
{
|
676
|
[Tested]
|
677
|
get
|
678
|
{
|
679
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(key);
|
680
|
|
681
|
if (pairs.Find(ref p))
|
682
|
return p.Value;
|
683
|
else
|
684
|
throw new NoSuchItemException("Key '" + key.ToString() + "' not present in Dictionary");
|
685
|
}
|
686
|
[Tested]
|
687
|
set
|
688
|
{ pairs.UpdateOrAdd(new KeyValuePair<K, V>(key, value)); }
|
689
|
}
|
690
|
|
691
|
|
692
|
/// <summary>
|
693
|
///
|
694
|
/// </summary>
|
695
|
/// <value>True if dictionary is read only</value>
|
696
|
[Tested]
|
697
|
public virtual bool IsReadOnly { [Tested]get { return pairs.IsReadOnly; } }
|
698
|
|
699
|
|
700
|
/// <summary>
|
701
|
/// Check the integrity of the internal data structures of this dictionary.
|
702
|
/// </summary>
|
703
|
/// <returns>True if check does not fail.</returns>
|
704
|
[Tested]
|
705
|
public virtual bool Check() { return pairs.Check(); }
|
706
|
|
707
|
#endregion
|
708
|
|
709
|
#region ICollectionValue<KeyValuePair<K,V>> Members
|
710
|
|
711
|
/// <summary>
|
712
|
///
|
713
|
/// </summary>
|
714
|
/// <value>True if this collection is empty.</value>
|
715
|
public override bool IsEmpty { get { return pairs.IsEmpty; } }
|
716
|
|
717
|
|
718
|
/// <summary>
|
719
|
///
|
720
|
/// </summary>
|
721
|
/// <value>The number of entrues in the dictionary</value>
|
722
|
[Tested]
|
723
|
public override int Count { [Tested]get { return pairs.Count; } }
|
724
|
|
725
|
/// <summary>
|
726
|
///
|
727
|
/// </summary>
|
728
|
/// <value>The number of entrues in the dictionary</value>
|
729
|
[Tested]
|
730
|
public override Speed CountSpeed { [Tested]get { return pairs.CountSpeed; } }
|
731
|
|
732
|
/// <summary>
|
733
|
/// Choose some entry in this Dictionary.
|
734
|
/// </summary>
|
735
|
/// <exception cref="NoSuchItemException">if collection is empty.</exception>
|
736
|
/// <returns></returns>
|
737
|
public override KeyValuePair<K, V> Choose() { return pairs.Choose(); }
|
738
|
|
739
|
/// <summary>
|
740
|
/// Create an enumerator for the collection of entries of the dictionary
|
741
|
/// </summary>
|
742
|
/// <returns>The enumerator</returns>
|
743
|
[Tested]
|
744
|
public override SCG.IEnumerator<KeyValuePair<K, V>> GetEnumerator()
|
745
|
{
|
746
|
return pairs.GetEnumerator(); ;
|
747
|
}
|
748
|
|
749
|
#endregion
|
750
|
|
751
|
/// <summary>
|
752
|
///
|
753
|
/// </summary>
|
754
|
/// <param name="stringbuilder"></param>
|
755
|
/// <param name="rest"></param>
|
756
|
/// <param name="formatProvider"></param>
|
757
|
/// <returns></returns>
|
758
|
public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
|
759
|
{
|
760
|
return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);
|
761
|
}
|
762
|
|
763
|
/// <summary>
|
764
|
///
|
765
|
/// </summary>
|
766
|
/// <returns></returns>
|
767
|
public abstract object Clone();
|
768
|
|
769
|
}
|
770
|
|
771
|
/// <summary>
|
772
|
/// A base class for implementing a sorted dictionary based on a sorted set collection implementation.
|
773
|
/// <i>See the source code for <see cref="T:C5.TreeDictionary`2"/> for an example</i>
|
774
|
///
|
775
|
/// </summary>
|
776
|
[Serializable]
|
777
|
public abstract class SortedDictionaryBase<K, V> : DictionaryBase<K, V>, ISortedDictionary<K, V>
|
778
|
{
|
779
|
#region Fields
|
780
|
|
781
|
/// <summary>
|
782
|
///
|
783
|
/// </summary>
|
784
|
protected ISorted<KeyValuePair<K, V>> sortedpairs;
|
785
|
SCG.IComparer<K> keycomparer;
|
786
|
|
787
|
/// <summary>
|
788
|
///
|
789
|
/// </summary>
|
790
|
/// <param name="keycomparer"></param>
|
791
|
/// <param name="keyequalityComparer"></param>
|
792
|
protected SortedDictionaryBase(SCG.IComparer<K> keycomparer, SCG.IEqualityComparer<K> keyequalityComparer) : base(keyequalityComparer) { this.keycomparer = keycomparer; }
|
793
|
|
794
|
#endregion
|
795
|
|
796
|
#region ISortedDictionary<K,V> Members
|
797
|
|
798
|
/// <summary>
|
799
|
/// The key comparer used by this dictionary.
|
800
|
/// </summary>
|
801
|
/// <value></value>
|
802
|
public SCG.IComparer<K> Comparer { get { return keycomparer; } }
|
803
|
|
804
|
/// <summary>
|
805
|
///
|
806
|
/// </summary>
|
807
|
/// <value></value>
|
808
|
public new ISorted<K> Keys { get { return new SortedKeysCollection(this, sortedpairs, keycomparer, EqualityComparer); } }
|
809
|
|
810
|
/// <summary>
|
811
|
/// Find the entry in the dictionary whose key is the
|
812
|
/// predecessor of the specified key.
|
813
|
/// </summary>
|
814
|
/// <param name="key">The key</param>
|
815
|
/// <param name="res">The predecessor, if any</param>
|
816
|
/// <returns>True if key has a predecessor</returns>
|
817
|
[Tested]
|
818
|
public bool TryPredecessor(K key, out KeyValuePair<K, V> res)
|
819
|
{
|
820
|
return sortedpairs.TryPredecessor(new KeyValuePair<K, V>(key), out res);
|
821
|
}
|
822
|
|
823
|
/// <summary>
|
824
|
/// Find the entry in the dictionary whose key is the
|
825
|
/// successor of the specified key.
|
826
|
/// </summary>
|
827
|
/// <param name="key">The key</param>
|
828
|
/// <param name="res">The successor, if any</param>
|
829
|
/// <returns>True if the key has a successor</returns>
|
830
|
[Tested]
|
831
|
public bool TrySuccessor(K key, out KeyValuePair<K, V> res)
|
832
|
{
|
833
|
return sortedpairs.TrySuccessor(new KeyValuePair<K, V>(key), out res);
|
834
|
}
|
835
|
|
836
|
/// <summary>
|
837
|
/// Find the entry in the dictionary whose key is the
|
838
|
/// weak predecessor of the specified key.
|
839
|
/// </summary>
|
840
|
/// <param name="key">The key</param>
|
841
|
/// <param name="res">The predecessor, if any</param>
|
842
|
/// <returns>True if key has a weak predecessor</returns>
|
843
|
[Tested]
|
844
|
public bool TryWeakPredecessor(K key, out KeyValuePair<K, V> res)
|
845
|
{
|
846
|
return sortedpairs.TryWeakPredecessor(new KeyValuePair<K, V>(key), out res);
|
847
|
}
|
848
|
|
849
|
/// <summary>
|
850
|
/// Find the entry in the dictionary whose key is the
|
851
|
/// weak successor of the specified key.
|
852
|
/// </summary>
|
853
|
/// <param name="key">The key</param>
|
854
|
/// <param name="res">The weak successor, if any</param>
|
855
|
/// <returns>True if the key has a weak successor</returns>
|
856
|
[Tested]
|
857
|
public bool TryWeakSuccessor(K key, out KeyValuePair<K, V> res)
|
858
|
{
|
859
|
return sortedpairs.TryWeakSuccessor(new KeyValuePair<K, V>(key), out res);
|
860
|
}
|
861
|
|
862
|
/// <summary>
|
863
|
/// Get the entry in the dictionary whose key is the
|
864
|
/// predecessor of the specified key.
|
865
|
/// </summary>
|
866
|
/// <exception cref="NoSuchItemException"></exception>
|
867
|
/// <param name="key">The key</param>
|
868
|
/// <returns>The entry</returns>
|
869
|
[Tested]
|
870
|
public KeyValuePair<K, V> Predecessor(K key)
|
871
|
{
|
872
|
return sortedpairs.Predecessor(new KeyValuePair<K, V>(key));
|
873
|
}
|
874
|
|
875
|
/// <summary>
|
876
|
/// Get the entry in the dictionary whose key is the
|
877
|
/// successor of the specified key.
|
878
|
/// </summary>
|
879
|
/// <exception cref="NoSuchItemException"></exception>
|
880
|
/// <param name="key">The key</param>
|
881
|
/// <returns>The entry</returns>
|
882
|
[Tested]
|
883
|
public KeyValuePair<K, V> Successor(K key)
|
884
|
{
|
885
|
return sortedpairs.Successor(new KeyValuePair<K, V>(key));
|
886
|
}
|
887
|
|
888
|
/// <summary>
|
889
|
/// Get the entry in the dictionary whose key is the
|
890
|
/// weak predecessor of the specified key.
|
891
|
/// </summary>
|
892
|
/// <exception cref="NoSuchItemException"></exception>
|
893
|
/// <param name="key">The key</param>
|
894
|
/// <returns>The entry</returns>
|
895
|
[Tested]
|
896
|
public KeyValuePair<K, V> WeakPredecessor(K key)
|
897
|
{
|
898
|
return sortedpairs.WeakPredecessor(new KeyValuePair<K, V>(key));
|
899
|
}
|
900
|
|
901
|
/// <summary>
|
902
|
/// Get the entry in the dictionary whose key is the
|
903
|
/// weak successor of the specified key.
|
904
|
/// </summary>
|
905
|
/// <exception cref="NoSuchItemException"></exception>
|
906
|
/// <param name="key">The key</param>
|
907
|
/// <returns>The entry</returns>
|
908
|
[Tested]
|
909
|
public KeyValuePair<K, V> WeakSuccessor(K key)
|
910
|
{
|
911
|
return sortedpairs.WeakSuccessor(new KeyValuePair<K, V>(key));
|
912
|
}
|
913
|
|
914
|
#endregion
|
915
|
|
916
|
#region ISortedDictionary<K,V> Members
|
917
|
|
918
|
/// <summary>
|
919
|
///
|
920
|
/// </summary>
|
921
|
/// <returns></returns>
|
922
|
public KeyValuePair<K, V> FindMin()
|
923
|
{
|
924
|
return sortedpairs.FindMin();
|
925
|
}
|
926
|
|
927
|
/// <summary>
|
928
|
///
|
929
|
/// </summary>
|
930
|
/// <returns></returns>
|
931
|
public KeyValuePair<K, V> DeleteMin()
|
932
|
{
|
933
|
return sortedpairs.DeleteMin();
|
934
|
}
|
935
|
|
936
|
/// <summary>
|
937
|
///
|
938
|
/// </summary>
|
939
|
/// <returns></returns>
|
940
|
public KeyValuePair<K, V> FindMax()
|
941
|
{
|
942
|
return sortedpairs.FindMax();
|
943
|
}
|
944
|
|
945
|
/// <summary>
|
946
|
///
|
947
|
/// </summary>
|
948
|
/// <returns></returns>
|
949
|
public KeyValuePair<K, V> DeleteMax()
|
950
|
{
|
951
|
return sortedpairs.DeleteMax();
|
952
|
}
|
953
|
|
954
|
/// <summary>
|
955
|
///
|
956
|
/// </summary>
|
957
|
/// <param name="cutter"></param>
|
958
|
/// <param name="lowEntry"></param>
|
959
|
/// <param name="lowIsValid"></param>
|
960
|
/// <param name="highEntry"></param>
|
961
|
/// <param name="highIsValid"></param>
|
962
|
/// <returns></returns>
|
963
|
public bool Cut(IComparable<K> cutter, out KeyValuePair<K, V> lowEntry, out bool lowIsValid, out KeyValuePair<K, V> highEntry, out bool highIsValid)
|
964
|
{
|
965
|
return sortedpairs.Cut(new KeyValuePairComparable(cutter), out lowEntry, out lowIsValid, out highEntry, out highIsValid);
|
966
|
}
|
967
|
|
968
|
/// <summary>
|
969
|
///
|
970
|
/// </summary>
|
971
|
/// <param name="bot"></param>
|
972
|
/// <returns></returns>
|
973
|
public IDirectedEnumerable<KeyValuePair<K, V>> RangeFrom(K bot)
|
974
|
{
|
975
|
return sortedpairs.RangeFrom(new KeyValuePair<K, V>(bot));
|
976
|
}
|
977
|
|
978
|
/// <summary>
|
979
|
///
|
980
|
/// </summary>
|
981
|
/// <param name="bot"></param>
|
982
|
/// <param name="top"></param>
|
983
|
/// <returns></returns>
|
984
|
public IDirectedEnumerable<KeyValuePair<K, V>> RangeFromTo(K bot, K top)
|
985
|
{
|
986
|
return sortedpairs.RangeFromTo(new KeyValuePair<K, V>(bot), new KeyValuePair<K, V>(top));
|
987
|
}
|
988
|
|
989
|
/// <summary>
|
990
|
///
|
991
|
/// </summary>
|
992
|
/// <param name="top"></param>
|
993
|
/// <returns></returns>
|
994
|
public IDirectedEnumerable<KeyValuePair<K, V>> RangeTo(K top)
|
995
|
{
|
996
|
return sortedpairs.RangeTo(new KeyValuePair<K, V>(top));
|
997
|
}
|
998
|
|
999
|
/// <summary>
|
1000
|
///
|
1001
|
/// </summary>
|
1002
|
/// <returns></returns>
|
1003
|
public IDirectedCollectionValue<KeyValuePair<K, V>> RangeAll()
|
1004
|
{
|
1005
|
return sortedpairs.RangeAll();
|
1006
|
}
|
1007
|
|
1008
|
/// <summary>
|
1009
|
///
|
1010
|
/// </summary>
|
1011
|
/// <param name="items"></param>
|
1012
|
public void AddSorted(SCG.IEnumerable<KeyValuePair<K, V>> items)
|
1013
|
{
|
1014
|
sortedpairs.AddSorted(items);
|
1015
|
}
|
1016
|
|
1017
|
/// <summary>
|
1018
|
///
|
1019
|
/// </summary>
|
1020
|
/// <param name="lowKey"></param>
|
1021
|
public void RemoveRangeFrom(K lowKey)
|
1022
|
{
|
1023
|
sortedpairs.RemoveRangeFrom(new KeyValuePair<K, V>(lowKey));
|
1024
|
}
|
1025
|
|
1026
|
/// <summary>
|
1027
|
///
|
1028
|
/// </summary>
|
1029
|
/// <param name="lowKey"></param>
|
1030
|
/// <param name="highKey"></param>
|
1031
|
public void RemoveRangeFromTo(K lowKey, K highKey)
|
1032
|
{
|
1033
|
sortedpairs.RemoveRangeFromTo(new KeyValuePair<K, V>(lowKey), new KeyValuePair<K, V>(highKey));
|
1034
|
}
|
1035
|
|
1036
|
/// <summary>
|
1037
|
///
|
1038
|
/// </summary>
|
1039
|
/// <param name="highKey"></param>
|
1040
|
public void RemoveRangeTo(K highKey)
|
1041
|
{
|
1042
|
sortedpairs.RemoveRangeTo(new KeyValuePair<K, V>(highKey));
|
1043
|
}
|
1044
|
|
1045
|
#endregion
|
1046
|
[Serializable]
|
1047
|
class KeyValuePairComparable : IComparable<KeyValuePair<K, V>>
|
1048
|
{
|
1049
|
IComparable<K> cutter;
|
1050
|
|
1051
|
internal KeyValuePairComparable(IComparable<K> cutter) { this.cutter = cutter; }
|
1052
|
|
1053
|
public int CompareTo(KeyValuePair<K, V> other) { return cutter.CompareTo(other.Key); }
|
1054
|
|
1055
|
public bool Equals(KeyValuePair<K, V> other) { return cutter.Equals(other.Key); }
|
1056
|
}
|
1057
|
|
1058
|
[Serializable]
|
1059
|
class ProjectedDirectedEnumerable : MappedDirectedEnumerable<KeyValuePair<K, V>, K>
|
1060
|
{
|
1061
|
public ProjectedDirectedEnumerable(IDirectedEnumerable<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }
|
1062
|
|
1063
|
public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }
|
1064
|
|
1065
|
}
|
1066
|
|
1067
|
[Serializable]
|
1068
|
class ProjectedDirectedCollectionValue : MappedDirectedCollectionValue<KeyValuePair<K, V>, K>
|
1069
|
{
|
1070
|
public ProjectedDirectedCollectionValue(IDirectedCollectionValue<KeyValuePair<K, V>> directedpairs) : base(directedpairs) { }
|
1071
|
|
1072
|
public override K Map(KeyValuePair<K, V> pair) { return pair.Key; }
|
1073
|
|
1074
|
}
|
1075
|
|
1076
|
[Serializable]
|
1077
|
class SortedKeysCollection : SequencedBase<K>, ISorted<K>
|
1078
|
{
|
1079
|
ISortedDictionary<K, V> sorteddict;
|
1080
|
//TODO: eliminate this. Only problem is the Find method because we lack method on dictionary that also
|
1081
|
// returns the actual key.
|
1082
|
ISorted<KeyValuePair<K, V>> sortedpairs;
|
1083
|
SCG.IComparer<K> comparer;
|
1084
|
|
1085
|
internal SortedKeysCollection(ISortedDictionary<K, V> sorteddict, ISorted<KeyValuePair<K, V>> sortedpairs, SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> itemequalityComparer)
|
1086
|
: base(itemequalityComparer)
|
1087
|
{
|
1088
|
this.sorteddict = sorteddict;
|
1089
|
this.sortedpairs = sortedpairs;
|
1090
|
this.comparer = comparer;
|
1091
|
}
|
1092
|
|
1093
|
public override K Choose() { return sorteddict.Choose().Key; }
|
1094
|
|
1095
|
public override SCG.IEnumerator<K> GetEnumerator()
|
1096
|
{
|
1097
|
foreach (KeyValuePair<K, V> p in sorteddict)
|
1098
|
yield return p.Key;
|
1099
|
}
|
1100
|
|
1101
|
public override bool IsEmpty { get { return sorteddict.IsEmpty; } }
|
1102
|
|
1103
|
public override int Count { [Tested]get { return sorteddict.Count; } }
|
1104
|
|
1105
|
public override Speed CountSpeed { get { return sorteddict.CountSpeed; } }
|
1106
|
|
1107
|
#region ISorted<K> Members
|
1108
|
|
1109
|
public K FindMin() { return sorteddict.FindMin().Key; }
|
1110
|
|
1111
|
public K DeleteMin() { throw new ReadOnlyCollectionException(); }
|
1112
|
|
1113
|
public K FindMax() { return sorteddict.FindMax().Key; }
|
1114
|
|
1115
|
public K DeleteMax() { throw new ReadOnlyCollectionException(); }
|
1116
|
|
1117
|
public SCG.IComparer<K> Comparer { get { return comparer; } }
|
1118
|
|
1119
|
public bool TryPredecessor(K item, out K res)
|
1120
|
{
|
1121
|
KeyValuePair<K, V> pRes;
|
1122
|
bool success = sorteddict.TryPredecessor(item, out pRes);
|
1123
|
res = pRes.Key;
|
1124
|
return success;
|
1125
|
}
|
1126
|
|
1127
|
public bool TrySuccessor(K item, out K res)
|
1128
|
{
|
1129
|
KeyValuePair<K, V> pRes;
|
1130
|
bool success = sorteddict.TrySuccessor(item, out pRes);
|
1131
|
res = pRes.Key;
|
1132
|
return success;
|
1133
|
}
|
1134
|
|
1135
|
public bool TryWeakPredecessor(K item, out K res)
|
1136
|
{
|
1137
|
KeyValuePair<K, V> pRes;
|
1138
|
bool success = sorteddict.TryWeakPredecessor(item, out pRes);
|
1139
|
res = pRes.Key;
|
1140
|
return success;
|
1141
|
}
|
1142
|
|
1143
|
public bool TryWeakSuccessor(K item, out K res)
|
1144
|
{
|
1145
|
KeyValuePair<K, V> pRes;
|
1146
|
bool success = sorteddict.TryWeakSuccessor(item, out pRes);
|
1147
|
res = pRes.Key;
|
1148
|
return success;
|
1149
|
}
|
1150
|
|
1151
|
public K Predecessor(K item) { return sorteddict.Predecessor(item).Key; }
|
1152
|
|
1153
|
public K Successor(K item) { return sorteddict.Successor(item).Key; }
|
1154
|
|
1155
|
public K WeakPredecessor(K item) { return sorteddict.WeakPredecessor(item).Key; }
|
1156
|
|
1157
|
public K WeakSuccessor(K item) { return sorteddict.WeakSuccessor(item).Key; }
|
1158
|
|
1159
|
public bool Cut(IComparable<K> c, out K low, out bool lowIsValid, out K high, out bool highIsValid)
|
1160
|
{
|
1161
|
KeyValuePair<K, V> lowpair, highpair;
|
1162
|
bool retval = sorteddict.Cut(c, out lowpair, out lowIsValid, out highpair, out highIsValid);
|
1163
|
low = lowpair.Key;
|
1164
|
high = highpair.Key;
|
1165
|
return retval;
|
1166
|
}
|
1167
|
|
1168
|
public IDirectedEnumerable<K> RangeFrom(K bot)
|
1169
|
{
|
1170
|
return new ProjectedDirectedEnumerable(sorteddict.RangeFrom(bot));
|
1171
|
}
|
1172
|
|
1173
|
public IDirectedEnumerable<K> RangeFromTo(K bot, K top)
|
1174
|
{
|
1175
|
return new ProjectedDirectedEnumerable(sorteddict.RangeFromTo(bot, top));
|
1176
|
}
|
1177
|
|
1178
|
public IDirectedEnumerable<K> RangeTo(K top)
|
1179
|
{
|
1180
|
return new ProjectedDirectedEnumerable(sorteddict.RangeTo(top));
|
1181
|
}
|
1182
|
|
1183
|
public IDirectedCollectionValue<K> RangeAll()
|
1184
|
{
|
1185
|
return new ProjectedDirectedCollectionValue(sorteddict.RangeAll());
|
1186
|
}
|
1187
|
|
1188
|
public void AddSorted<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
|
1189
|
|
1190
|
public void RemoveRangeFrom(K low) { throw new ReadOnlyCollectionException(); }
|
1191
|
|
1192
|
public void RemoveRangeFromTo(K low, K hi) { throw new ReadOnlyCollectionException(); }
|
1193
|
|
1194
|
public void RemoveRangeTo(K hi) { throw new ReadOnlyCollectionException(); }
|
1195
|
#endregion
|
1196
|
|
1197
|
#region ICollection<K> Members
|
1198
|
public Speed ContainsSpeed { get { return sorteddict.ContainsSpeed; } }
|
1199
|
|
1200
|
public bool Contains(K key) { return sorteddict.Contains(key); ; }
|
1201
|
|
1202
|
public int ContainsCount(K item) { return sorteddict.Contains(item) ? 1 : 0; }
|
1203
|
|
1204
|
/// <summary>
|
1205
|
///
|
1206
|
/// </summary>
|
1207
|
/// <returns></returns>
|
1208
|
public virtual ICollectionValue<K> UniqueItems()
|
1209
|
{
|
1210
|
return this;
|
1211
|
}
|
1212
|
|
1213
|
/// <summary>
|
1214
|
///
|
1215
|
/// </summary>
|
1216
|
/// <returns></returns>
|
1217
|
public virtual ICollectionValue<KeyValuePair<K, int>> ItemMultiplicities()
|
1218
|
{
|
1219
|
return new MultiplicityOne<K>(this);
|
1220
|
}
|
1221
|
|
1222
|
|
1223
|
public bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : K
|
1224
|
{
|
1225
|
//TODO: optimize?
|
1226
|
foreach (K item in items)
|
1227
|
if (!sorteddict.Contains(item))
|
1228
|
return false;
|
1229
|
return true;
|
1230
|
}
|
1231
|
|
1232
|
public bool Find(ref K item)
|
1233
|
{
|
1234
|
KeyValuePair<K, V> p = new KeyValuePair<K, V>(item);
|
1235
|
bool retval = sortedpairs.Find(ref p);
|
1236
|
item = p.Key;
|
1237
|
return retval;
|
1238
|
}
|
1239
|
|
1240
|
public bool FindOrAdd(ref K item) { throw new ReadOnlyCollectionException(); }
|
1241
|
|
1242
|
public bool Update(K item) { throw new ReadOnlyCollectionException(); }
|
1243
|
|
1244
|
public bool Update(K item, out K olditem) { throw new ReadOnlyCollectionException(); }
|
1245
|
|
1246
|
public bool UpdateOrAdd(K item) { throw new ReadOnlyCollectionException(); }
|
1247
|
|
1248
|
public bool UpdateOrAdd(K item, out K olditem) { throw new ReadOnlyCollectionException(); }
|
1249
|
|
1250
|
public bool Remove(K item) { throw new ReadOnlyCollectionException(); }
|
1251
|
|
1252
|
public bool Remove(K item, out K removeditem) { throw new ReadOnlyCollectionException(); }
|
1253
|
|
1254
|
public void RemoveAllCopies(K item) { throw new ReadOnlyCollectionException(); }
|
1255
|
|
1256
|
public void RemoveAll<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
|
1257
|
|
1258
|
public void Clear() { throw new ReadOnlyCollectionException(); }
|
1259
|
|
1260
|
public void RetainAll<U>(SCG.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
|
1261
|
|
1262
|
#endregion
|
1263
|
|
1264
|
#region IExtensible<K> Members
|
1265
|
public override bool IsReadOnly { get { return true; } }
|
1266
|
|
1267
|
public bool AllowsDuplicates { get { return false; } }
|
1268
|
|
1269
|
public bool DuplicatesByCounting { get { return true; } }
|
1270
|
|
1271
|
public bool Add(K item) { throw new ReadOnlyCollectionException(); }
|
1272
|
|
1273
|
void SCG.ICollection<K>.Add(K item) { throw new ReadOnlyCollectionException(); }
|
1274
|
|
1275
|
public void AddAll(System.Collections.Generic.IEnumerable<K> items) { throw new ReadOnlyCollectionException(); }
|
1276
|
|
1277
|
public void AddAll<U>(System.Collections.Generic.IEnumerable<U> items) where U : K { throw new ReadOnlyCollectionException(); }
|
1278
|
|
1279
|
public bool Check() { return sorteddict.Check(); }
|
1280
|
|
1281
|
#endregion
|
1282
|
|
1283
|
#region IDirectedCollectionValue<K> Members
|
1284
|
|
1285
|
public override IDirectedCollectionValue<K> Backwards()
|
1286
|
{
|
1287
|
return RangeAll().Backwards();
|
1288
|
}
|
1289
|
|
1290
|
#endregion
|
1291
|
|
1292
|
#region IDirectedEnumerable<K> Members
|
1293
|
|
1294
|
IDirectedEnumerable<K> IDirectedEnumerable<K>.Backwards() { return Backwards(); }
|
1295
|
#endregion
|
1296
|
|
1297
|
#region ICloneable Members
|
1298
|
|
1299
|
//TODO: test
|
1300
|
/// <summary>
|
1301
|
/// Make a shallow copy of this SortedKeysCollection.
|
1302
|
/// </summary>
|
1303
|
/// <returns></returns>
|
1304
|
public virtual object Clone()
|
1305
|
{
|
1306
|
//
|
1307
|
SortedArrayDictionary<K, V> dictclone = new SortedArrayDictionary<K, V>(sortedpairs.Count, comparer, EqualityComparer);
|
1308
|
SortedArray<KeyValuePair<K, V>> sortedpairsclone = (SortedArray<KeyValuePair<K, V>>)(dictclone.sortedpairs);
|
1309
|
foreach (K key in sorteddict.Keys)
|
1310
|
{
|
1311
|
sortedpairsclone.Add(new KeyValuePair<K, V>(key, default(V)));
|
1312
|
}
|
1313
|
return new SortedKeysCollection(dictclone, sortedpairsclone, comparer, EqualityComparer);
|
1314
|
}
|
1315
|
|
1316
|
#endregion
|
1317
|
|
1318
|
}
|
1319
|
|
1320
|
/// <summary>
|
1321
|
///
|
1322
|
/// </summary>
|
1323
|
/// <param name="stringbuilder"></param>
|
1324
|
/// <param name="rest"></param>
|
1325
|
/// <param name="formatProvider"></param>
|
1326
|
/// <returns></returns>
|
1327
|
public override bool Show(System.Text.StringBuilder stringbuilder, ref int rest, IFormatProvider formatProvider)
|
1328
|
{
|
1329
|
return Showing.ShowDictionary<K, V>(this, stringbuilder, ref rest, formatProvider);
|
1330
|
}
|
1331
|
|
1332
|
}
|
1333
|
|
1334
|
[Serializable]
|
1335
|
class SortedArrayDictionary<K, V> : SortedDictionaryBase<K, V>, IDictionary<K, V>, ISortedDictionary<K, V>
|
1336
|
{
|
1337
|
#region Constructors
|
1338
|
|
1339
|
public SortedArrayDictionary() : this(Comparer<K>.Default, EqualityComparer<K>.Default) { }
|
1340
|
|
1341
|
/// <summary>
|
1342
|
/// Create a red-black tree dictionary using an external comparer for keys.
|
1343
|
/// </summary>
|
1344
|
/// <param name="comparer">The external comparer</param>
|
1345
|
public SortedArrayDictionary(SCG.IComparer<K> comparer) : this(comparer, new ComparerZeroHashCodeEqualityComparer<K>(comparer)) { }
|
1346
|
|
1347
|
/// <summary>
|
1348
|
///
|
1349
|
/// </summary>
|
1350
|
/// <param name="comparer"></param>
|
1351
|
/// <param name="equalityComparer"></param>
|
1352
|
public SortedArrayDictionary(SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> equalityComparer)
|
1353
|
: base(comparer, equalityComparer)
|
1354
|
{
|
1355
|
pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(new KeyValuePairComparer<K, V>(comparer));
|
1356
|
}
|
1357
|
|
1358
|
/// <summary>
|
1359
|
///
|
1360
|
/// </summary>
|
1361
|
/// <param name="comparer"></param>
|
1362
|
/// <param name="equalityComparer"></param>
|
1363
|
/// <param name="capacity"></param>
|
1364
|
public SortedArrayDictionary(int capacity, SCG.IComparer<K> comparer, SCG.IEqualityComparer<K> equalityComparer)
|
1365
|
: base(comparer, equalityComparer)
|
1366
|
{
|
1367
|
pairs = sortedpairs = new SortedArray<KeyValuePair<K, V>>(capacity, new KeyValuePairComparer<K, V>(comparer));
|
1368
|
}
|
1369
|
#endregion
|
1370
|
|
1371
|
/// <summary>
|
1372
|
///
|
1373
|
/// </summary>
|
1374
|
/// <returns></returns>
|
1375
|
public override object Clone()
|
1376
|
{
|
1377
|
SortedArrayDictionary<K, V> clone = new SortedArrayDictionary<K, V>(Comparer, EqualityComparer);
|
1378
|
clone.sortedpairs.AddSorted(sortedpairs);
|
1379
|
return clone;
|
1380
|
}
|
1381
|
|
1382
|
}
|
1383
|
}
|