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 C5;
|
24
|
using NUnit.Framework;
|
25
|
using SCG=System.Collections.Generic;
|
26
|
|
27
|
|
28
|
namespace C5UnitTests.trees.RBDictionary
|
29
|
{
|
30
|
using DictionaryIntToInt = TreeDictionary<int, int>;
|
31
|
|
32
|
static class Factory
|
33
|
{
|
34
|
public static IDictionary<K,V> New<K,V>() { return new TreeDictionary<K,V>(); }
|
35
|
}
|
36
|
|
37
|
[TestFixture]
|
38
|
public class GenericTesters
|
39
|
{
|
40
|
[Test]
|
41
|
public void TestSerialize()
|
42
|
{
|
43
|
C5UnitTests.Templates.Extensible.Serialization.DTester<DictionaryIntToInt>();
|
44
|
}
|
45
|
}
|
46
|
|
47
|
|
48
|
[TestFixture]
|
49
|
public class Formatting
|
50
|
{
|
51
|
IDictionary<int,int> coll;
|
52
|
IFormatProvider rad16;
|
53
|
[SetUp]
|
54
|
public void Init() { coll = Factory.New<int,int>(); rad16 = new RadixFormatProvider(16); }
|
55
|
[TearDown]
|
56
|
public void Dispose() { coll = null; rad16 = null; }
|
57
|
[Test]
|
58
|
public void Format()
|
59
|
{
|
60
|
Assert.AreEqual("[ ]", coll.ToString());
|
61
|
coll.Add(23, 67); coll.Add(45, 89);
|
62
|
Assert.AreEqual("[ 23 => 67, 45 => 89 ]", coll.ToString());
|
63
|
Assert.AreEqual("[ 17 => 43, 2D => 59 ]", coll.ToString(null, rad16));
|
64
|
Assert.AreEqual("[ 23 => 67, ... ]", coll.ToString("L14", null));
|
65
|
Assert.AreEqual("[ 17 => 43, ... ]", coll.ToString("L14", rad16));
|
66
|
}
|
67
|
}
|
68
|
|
69
|
[TestFixture]
|
70
|
public class RBDict
|
71
|
{
|
72
|
private TreeDictionary<string,string> dict;
|
73
|
|
74
|
|
75
|
[SetUp]
|
76
|
public void Init() { dict = new TreeDictionary<string,string>(new SC()); }
|
77
|
|
78
|
|
79
|
[TearDown]
|
80
|
public void Dispose() { dict = null; }
|
81
|
|
82
|
[Test]
|
83
|
[ExpectedException(typeof(NullReferenceException))]
|
84
|
public void NullEqualityComparerinConstructor1()
|
85
|
{
|
86
|
new TreeDictionary<int,int>(null);
|
87
|
}
|
88
|
|
89
|
[Test]
|
90
|
public void Choose()
|
91
|
{
|
92
|
dict.Add("YES","NO");
|
93
|
Assert.AreEqual(new KeyValuePair<string,string>("YES","NO"), dict.Choose());
|
94
|
}
|
95
|
|
96
|
[Test]
|
97
|
[ExpectedException(typeof(NoSuchItemException))]
|
98
|
public void BadChoose()
|
99
|
{
|
100
|
dict.Choose();
|
101
|
}
|
102
|
|
103
|
[Test]
|
104
|
public void Pred1()
|
105
|
{
|
106
|
dict.Add("A", "1");
|
107
|
dict.Add("C", "2");
|
108
|
dict.Add("E", "3");
|
109
|
Assert.AreEqual("1", dict.Predecessor("B").Value);
|
110
|
Assert.AreEqual("1", dict.Predecessor("C").Value);
|
111
|
Assert.AreEqual("1", dict.WeakPredecessor("B").Value);
|
112
|
Assert.AreEqual("2", dict.WeakPredecessor("C").Value);
|
113
|
Assert.AreEqual("2", dict.Successor("B").Value);
|
114
|
Assert.AreEqual("3", dict.Successor("C").Value);
|
115
|
Assert.AreEqual("2", dict.WeakSuccessor("B").Value);
|
116
|
Assert.AreEqual("2", dict.WeakSuccessor("C").Value);
|
117
|
}
|
118
|
|
119
|
[Test]
|
120
|
public void Pred2()
|
121
|
{
|
122
|
dict.Add("A", "1");
|
123
|
dict.Add("C", "2");
|
124
|
dict.Add("E", "3");
|
125
|
KeyValuePair<String, String> res;
|
126
|
Assert.IsTrue(dict.TryPredecessor("B", out res));
|
127
|
Assert.AreEqual("1", res.Value);
|
128
|
Assert.IsTrue(dict.TryPredecessor("C", out res));
|
129
|
Assert.AreEqual("1", res.Value);
|
130
|
Assert.IsTrue(dict.TryWeakPredecessor("B", out res));
|
131
|
Assert.AreEqual("1", res.Value);
|
132
|
Assert.IsTrue(dict.TryWeakPredecessor("C", out res));
|
133
|
Assert.AreEqual("2", res.Value);
|
134
|
Assert.IsTrue(dict.TrySuccessor("B", out res));
|
135
|
Assert.AreEqual("2", res.Value);
|
136
|
Assert.IsTrue(dict.TrySuccessor("C", out res));
|
137
|
Assert.AreEqual("3", res.Value);
|
138
|
Assert.IsTrue(dict.TryWeakSuccessor("B", out res));
|
139
|
Assert.AreEqual("2", res.Value);
|
140
|
Assert.IsTrue(dict.TryWeakSuccessor("C", out res));
|
141
|
Assert.AreEqual("2", res.Value);
|
142
|
|
143
|
Assert.IsFalse(dict.TryPredecessor("A", out res));
|
144
|
Assert.AreEqual(null, res.Key);
|
145
|
Assert.AreEqual(null, res.Value);
|
146
|
|
147
|
Assert.IsFalse(dict.TryWeakPredecessor("@", out res));
|
148
|
Assert.AreEqual(null, res.Key);
|
149
|
Assert.AreEqual(null, res.Value);
|
150
|
|
151
|
Assert.IsFalse(dict.TrySuccessor("E", out res));
|
152
|
Assert.AreEqual(null, res.Key);
|
153
|
Assert.AreEqual(null, res.Value);
|
154
|
|
155
|
Assert.IsFalse(dict.TryWeakSuccessor("F", out res));
|
156
|
Assert.AreEqual(null, res.Key);
|
157
|
Assert.AreEqual(null, res.Value);
|
158
|
}
|
159
|
|
160
|
[Test]
|
161
|
public void Initial()
|
162
|
{
|
163
|
bool res;
|
164
|
Assert.IsFalse(dict.IsReadOnly);
|
165
|
|
166
|
Assert.AreEqual(dict.Count, 0, "new dict should be empty");
|
167
|
dict.Add("A", "B");
|
168
|
Assert.AreEqual(dict.Count, 1, "bad count");
|
169
|
Assert.AreEqual(dict["A"], "B", "Wrong value for dict[A]");
|
170
|
dict.Add("C", "D");
|
171
|
Assert.AreEqual(dict.Count, 2, "bad count");
|
172
|
Assert.AreEqual(dict["A"], "B", "Wrong value");
|
173
|
Assert.AreEqual(dict["C"], "D", "Wrong value");
|
174
|
res = dict.Remove("A");
|
175
|
Assert.IsTrue(res, "bad return value from Remove(A)");
|
176
|
Assert.IsTrue(dict.Check());
|
177
|
Assert.AreEqual(dict.Count, 1, "bad count");
|
178
|
Assert.AreEqual(dict["C"], "D", "Wrong value of dict[C]");
|
179
|
res = dict.Remove("Z");
|
180
|
Assert.IsFalse(res, "bad return value from Remove(Z)");
|
181
|
Assert.AreEqual(dict.Count, 1, "bad count");
|
182
|
Assert.AreEqual(dict["C"], "D", "Wrong value of dict[C] (2)");
|
183
|
dict.Clear();
|
184
|
Assert.AreEqual(dict.Count, 0, "dict should be empty");
|
185
|
}
|
186
|
[Test]
|
187
|
public void Contains()
|
188
|
{
|
189
|
dict.Add("C", "D");
|
190
|
Assert.IsTrue(dict.Contains("C"));
|
191
|
Assert.IsFalse(dict.Contains("D"));
|
192
|
}
|
193
|
|
194
|
|
195
|
[Test]
|
196
|
[ExpectedException(typeof(DuplicateNotAllowedException), "Key being added: 'A'")]
|
197
|
public void IllegalAdd()
|
198
|
{
|
199
|
dict.Add("A", "B");
|
200
|
dict.Add("A", "B");
|
201
|
}
|
202
|
|
203
|
|
204
|
[Test]
|
205
|
[ExpectedException(typeof(NoSuchItemException))]
|
206
|
public void GettingNonExisting()
|
207
|
{
|
208
|
Console.WriteLine(dict["R"]);
|
209
|
}
|
210
|
|
211
|
|
212
|
[Test]
|
213
|
public void Setter()
|
214
|
{
|
215
|
dict["R"] = "UYGUY";
|
216
|
Assert.AreEqual(dict["R"], "UYGUY");
|
217
|
dict["R"] = "UIII";
|
218
|
Assert.AreEqual(dict["R"], "UIII");
|
219
|
dict["S"] = "VVV";
|
220
|
Assert.AreEqual(dict["R"], "UIII");
|
221
|
Assert.AreEqual(dict["S"], "VVV");
|
222
|
//dict.dump();
|
223
|
}
|
224
|
}
|
225
|
|
226
|
[TestFixture]
|
227
|
public class GuardedSortedDictionaryTest
|
228
|
{
|
229
|
private GuardedSortedDictionary<string, string> dict;
|
230
|
|
231
|
[SetUp]
|
232
|
public void Init() {
|
233
|
ISortedDictionary<string,string> dict = new TreeDictionary<string, string>(new SC());
|
234
|
dict.Add("A", "1");
|
235
|
dict.Add("C", "2");
|
236
|
dict.Add("E", "3");
|
237
|
this.dict = new GuardedSortedDictionary<string, string>(dict);
|
238
|
}
|
239
|
|
240
|
[TearDown]
|
241
|
public void Dispose() { dict = null; }
|
242
|
|
243
|
[Test]
|
244
|
public void Pred1()
|
245
|
{
|
246
|
Assert.AreEqual("1", dict.Predecessor("B").Value);
|
247
|
Assert.AreEqual("1", dict.Predecessor("C").Value);
|
248
|
Assert.AreEqual("1", dict.WeakPredecessor("B").Value);
|
249
|
Assert.AreEqual("2", dict.WeakPredecessor("C").Value);
|
250
|
Assert.AreEqual("2", dict.Successor("B").Value);
|
251
|
Assert.AreEqual("3", dict.Successor("C").Value);
|
252
|
Assert.AreEqual("2", dict.WeakSuccessor("B").Value);
|
253
|
Assert.AreEqual("2", dict.WeakSuccessor("C").Value);
|
254
|
}
|
255
|
|
256
|
[Test]
|
257
|
public void Pred2()
|
258
|
{
|
259
|
KeyValuePair<String, String> res;
|
260
|
Assert.IsTrue(dict.TryPredecessor("B", out res));
|
261
|
Assert.AreEqual("1", res.Value);
|
262
|
Assert.IsTrue(dict.TryPredecessor("C", out res));
|
263
|
Assert.AreEqual("1", res.Value);
|
264
|
Assert.IsTrue(dict.TryWeakPredecessor("B", out res));
|
265
|
Assert.AreEqual("1", res.Value);
|
266
|
Assert.IsTrue(dict.TryWeakPredecessor("C", out res));
|
267
|
Assert.AreEqual("2", res.Value);
|
268
|
Assert.IsTrue(dict.TrySuccessor("B", out res));
|
269
|
Assert.AreEqual("2", res.Value);
|
270
|
Assert.IsTrue(dict.TrySuccessor("C", out res));
|
271
|
Assert.AreEqual("3", res.Value);
|
272
|
Assert.IsTrue(dict.TryWeakSuccessor("B", out res));
|
273
|
Assert.AreEqual("2", res.Value);
|
274
|
Assert.IsTrue(dict.TryWeakSuccessor("C", out res));
|
275
|
Assert.AreEqual("2", res.Value);
|
276
|
|
277
|
Assert.IsFalse(dict.TryPredecessor("A", out res));
|
278
|
Assert.AreEqual(null, res.Key);
|
279
|
Assert.AreEqual(null, res.Value);
|
280
|
|
281
|
Assert.IsFalse(dict.TryWeakPredecessor("@", out res));
|
282
|
Assert.AreEqual(null, res.Key);
|
283
|
Assert.AreEqual(null, res.Value);
|
284
|
|
285
|
Assert.IsFalse(dict.TrySuccessor("E", out res));
|
286
|
Assert.AreEqual(null, res.Key);
|
287
|
Assert.AreEqual(null, res.Value);
|
288
|
|
289
|
Assert.IsFalse(dict.TryWeakSuccessor("F", out res));
|
290
|
Assert.AreEqual(null, res.Key);
|
291
|
Assert.AreEqual(null, res.Value);
|
292
|
}
|
293
|
|
294
|
[Test]
|
295
|
public void Initial()
|
296
|
{
|
297
|
Assert.IsTrue(dict.IsReadOnly);
|
298
|
|
299
|
Assert.AreEqual(3, dict.Count);
|
300
|
Assert.AreEqual("1", dict["A"]);
|
301
|
}
|
302
|
|
303
|
[Test]
|
304
|
public void Contains()
|
305
|
{
|
306
|
Assert.IsTrue(dict.Contains("A"));
|
307
|
Assert.IsFalse(dict.Contains("1"));
|
308
|
}
|
309
|
|
310
|
[Test]
|
311
|
[ExpectedException(typeof(ReadOnlyCollectionException))]
|
312
|
public void IllegalAdd()
|
313
|
{
|
314
|
dict.Add("Q", "7");
|
315
|
}
|
316
|
|
317
|
[Test]
|
318
|
[ExpectedException(typeof(ReadOnlyCollectionException))]
|
319
|
public void IllegalClear()
|
320
|
{
|
321
|
dict.Clear();
|
322
|
}
|
323
|
[Test]
|
324
|
|
325
|
[ExpectedException(typeof(ReadOnlyCollectionException))]
|
326
|
public void IllegalSet()
|
327
|
{
|
328
|
dict["A"] = "8";
|
329
|
}
|
330
|
|
331
|
[ExpectedException(typeof(ReadOnlyCollectionException))]
|
332
|
public void IllegalRemove()
|
333
|
{
|
334
|
dict.Remove("A");
|
335
|
}
|
336
|
|
337
|
[Test]
|
338
|
[ExpectedException(typeof(NoSuchItemException))]
|
339
|
public void GettingNonExisting()
|
340
|
{
|
341
|
Console.WriteLine(dict["R"]);
|
342
|
}
|
343
|
}
|
344
|
|
345
|
[TestFixture]
|
346
|
public class Enumerators
|
347
|
{
|
348
|
private TreeDictionary<string,string> dict;
|
349
|
|
350
|
private SCG.IEnumerator<KeyValuePair<string,string>> dictenum;
|
351
|
|
352
|
|
353
|
[SetUp]
|
354
|
public void Init()
|
355
|
{
|
356
|
dict = new TreeDictionary<string,string>(new SC());
|
357
|
dict["S"] = "A";
|
358
|
dict["T"] = "B";
|
359
|
dict["R"] = "C";
|
360
|
dictenum = dict.GetEnumerator();
|
361
|
}
|
362
|
|
363
|
|
364
|
[TearDown]
|
365
|
public void Dispose()
|
366
|
{
|
367
|
dictenum = null;
|
368
|
dict = null;
|
369
|
}
|
370
|
|
371
|
[Test]
|
372
|
public void KeysEnumerator()
|
373
|
{
|
374
|
SCG.IEnumerator<string> keys = dict.Keys.GetEnumerator();
|
375
|
Assert.AreEqual(3, dict.Keys.Count);
|
376
|
Assert.IsTrue(keys.MoveNext());
|
377
|
Assert.AreEqual("R",keys.Current);
|
378
|
Assert.IsTrue(keys.MoveNext());
|
379
|
Assert.AreEqual("S",keys.Current);
|
380
|
Assert.IsTrue(keys.MoveNext());
|
381
|
Assert.AreEqual("T",keys.Current);
|
382
|
Assert.IsFalse(keys.MoveNext());
|
383
|
}
|
384
|
|
385
|
[Test]
|
386
|
public void KeysISorted()
|
387
|
{
|
388
|
ISorted<string> keys = dict.Keys;
|
389
|
Assert.IsTrue(keys.IsReadOnly);
|
390
|
Assert.AreEqual("R", keys.FindMin());
|
391
|
Assert.AreEqual("T", keys.FindMax());
|
392
|
Assert.IsTrue(keys.Contains("S"));
|
393
|
Assert.AreEqual(3, keys.Count);
|
394
|
// This doesn't hold, maybe because the dict uses a special key comparer?
|
395
|
// Assert.IsTrue(keys.SequencedEquals(new WrappedArray<string>(new string[] { "R", "S", "T" })));
|
396
|
Assert.IsTrue(keys.UniqueItems().All(delegate(String s) { return s == "R" || s == "S" || s == "T"; }));
|
397
|
Assert.IsTrue(keys.All(delegate(String s) { return s == "R" || s == "S" || s == "T"; }));
|
398
|
Assert.IsFalse(keys.Exists(delegate(String s) { return s != "R" && s != "S" && s != "T"; }));
|
399
|
String res;
|
400
|
Assert.IsTrue(keys.Find(delegate(String s) { return s == "R"; }, out res));
|
401
|
Assert.AreEqual("R", res);
|
402
|
Assert.IsFalse(keys.Find(delegate(String s) { return s == "Q"; }, out res));
|
403
|
Assert.AreEqual(null, res);
|
404
|
}
|
405
|
|
406
|
[Test]
|
407
|
public void KeysISortedPred()
|
408
|
{
|
409
|
ISorted<string> keys = dict.Keys;
|
410
|
String res;
|
411
|
Assert.IsTrue(keys.TryPredecessor("S", out res));
|
412
|
Assert.AreEqual("R", res);
|
413
|
Assert.IsTrue(keys.TryWeakPredecessor("R", out res));
|
414
|
Assert.AreEqual("R", res);
|
415
|
Assert.IsTrue(keys.TrySuccessor("S", out res));
|
416
|
Assert.AreEqual("T", res);
|
417
|
Assert.IsTrue(keys.TryWeakSuccessor("T", out res));
|
418
|
Assert.AreEqual("T", res);
|
419
|
Assert.IsFalse(keys.TryPredecessor("R", out res));
|
420
|
Assert.AreEqual(null, res);
|
421
|
Assert.IsFalse(keys.TryWeakPredecessor("P", out res));
|
422
|
Assert.AreEqual(null, res);
|
423
|
Assert.IsFalse(keys.TrySuccessor("T", out res));
|
424
|
Assert.AreEqual(null, res);
|
425
|
Assert.IsFalse(keys.TryWeakSuccessor("U", out res));
|
426
|
Assert.AreEqual(null, res);
|
427
|
|
428
|
Assert.AreEqual("R", keys.Predecessor("S"));
|
429
|
Assert.AreEqual("R", keys.WeakPredecessor("R"));
|
430
|
Assert.AreEqual("T", keys.Successor("S"));
|
431
|
Assert.AreEqual("T", keys.WeakSuccessor("T"));
|
432
|
}
|
433
|
|
434
|
[Test]
|
435
|
public void ValuesEnumerator()
|
436
|
{
|
437
|
SCG.IEnumerator<string> values = dict.Values.GetEnumerator();
|
438
|
Assert.AreEqual(3, dict.Values.Count);
|
439
|
Assert.IsTrue(values.MoveNext());
|
440
|
Assert.AreEqual("C",values.Current);
|
441
|
Assert.IsTrue(values.MoveNext());
|
442
|
Assert.AreEqual("A",values.Current);
|
443
|
Assert.IsTrue(values.MoveNext());
|
444
|
Assert.AreEqual("B",values.Current);
|
445
|
Assert.IsFalse(values.MoveNext());
|
446
|
}
|
447
|
|
448
|
[Test]
|
449
|
public void Fun()
|
450
|
{
|
451
|
Assert.AreEqual("B", dict.Fun("T"));
|
452
|
}
|
453
|
|
454
|
|
455
|
[Test]
|
456
|
public void NormalUse()
|
457
|
{
|
458
|
Assert.IsTrue(dictenum.MoveNext());
|
459
|
Assert.AreEqual(dictenum.Current, new KeyValuePair<string,string>("R", "C"));
|
460
|
Assert.IsTrue(dictenum.MoveNext());
|
461
|
Assert.AreEqual(dictenum.Current, new KeyValuePair<string,string>("S", "A"));
|
462
|
Assert.IsTrue(dictenum.MoveNext());
|
463
|
Assert.AreEqual(dictenum.Current, new KeyValuePair<string,string>("T", "B"));
|
464
|
Assert.IsFalse(dictenum.MoveNext());
|
465
|
}
|
466
|
}
|
467
|
|
468
|
|
469
|
namespace PathCopyPersistence
|
470
|
{
|
471
|
[TestFixture]
|
472
|
public class Simple
|
473
|
{
|
474
|
private TreeDictionary<string,string> dict;
|
475
|
|
476
|
private TreeDictionary<string,string> snap;
|
477
|
|
478
|
|
479
|
[SetUp]
|
480
|
public void Init()
|
481
|
{
|
482
|
dict = new TreeDictionary<string,string>(new SC());
|
483
|
dict["S"] = "A";
|
484
|
dict["T"] = "B";
|
485
|
dict["R"] = "C";
|
486
|
dict["V"] = "G";
|
487
|
snap = (TreeDictionary<string,string>)dict.Snapshot();
|
488
|
}
|
489
|
|
490
|
|
491
|
[Test]
|
492
|
public void Test()
|
493
|
{
|
494
|
dict["SS"] = "D";
|
495
|
Assert.AreEqual(5, dict.Count);
|
496
|
Assert.AreEqual(4, snap.Count);
|
497
|
dict["T"] = "bb";
|
498
|
Assert.AreEqual(5, dict.Count);
|
499
|
Assert.AreEqual(4, snap.Count);
|
500
|
Assert.AreEqual("B", snap["T"]);
|
501
|
Assert.AreEqual("bb", dict["T"]);
|
502
|
Assert.IsFalse(dict.IsReadOnly);
|
503
|
Assert.IsTrue(snap.IsReadOnly);
|
504
|
//Finally, update of root node:
|
505
|
TreeDictionary<string,string> snap2 = (TreeDictionary<string,string>)dict.Snapshot();
|
506
|
dict["S"] = "abe";
|
507
|
Assert.AreEqual("abe", dict["S"]);
|
508
|
}
|
509
|
|
510
|
|
511
|
[Test]
|
512
|
[ExpectedException(typeof(ReadOnlyCollectionException))]
|
513
|
public void UpdateSnap()
|
514
|
{
|
515
|
snap["Y"] = "J";
|
516
|
}
|
517
|
|
518
|
|
519
|
[TearDown]
|
520
|
public void Dispose()
|
521
|
{
|
522
|
dict = null;
|
523
|
snap = null;
|
524
|
}
|
525
|
}
|
526
|
}
|
527
|
}
|