Mercurial > projects > ldc

comparison tango/tango/util/collection/LinkMap.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
1 /*
2 File: LinkMap.d
3
4 Originally written by Doug Lea and released into the public domain.
5 Thanks for the assistance and support of Sun Microsystems Labs, Agorics
6 Inc, Loral, and everyone contributing, testing, and using this code.
7
8 History:
9 Date Who What
10 24Sep95 dl@cs.oswego.edu Create from tango.util.collection.d working file
11 13Oct95 dl Changed protection statuses
12 21Oct95 dl Fixed error in remove
13
14 */
15
16
17 module tango.util.collection.LinkMap;
18
19 private import tango.core.Exception;
20
21 private import tango.io.protocol.model.IReader,
22 tango.io.protocol.model.IWriter;
23
24 private import tango.util.collection.model.View,
25 tango.util.collection.model.GuardIterator;
26
27 private import tango.util.collection.impl.LLCell,
28 tango.util.collection.impl.LLPair,
29 tango.util.collection.impl.MapCollection,
30 tango.util.collection.impl.AbstractIterator;
31
32 /**
33 * Linked lists of (key, element) pairs
34 * author: Doug Lea
35 **/
36 public class LinkMap(K, T) : MapCollection!(K, T) // , IReadable, IWritable
37 {
38 alias LLCell!(T) LLCellT;
39 alias LLPair!(K, T) LLPairT;
40
41 alias MapCollection!(K, T).remove remove;
42 alias MapCollection!(K, T) .removeAll removeAll;
43
44 // instance variables
45
46 /**
47 * The head of the list. Null if empty
48 **/
49
50 package LLPairT list;
51
52 // constructors
53
54 /**
55 * Make an empty list
56 **/
57
58 public this ()
59 {
60 this(null, null, 0);
61 }
62
63 /**
64 * Make an empty list with the supplied element screener
65 **/
66
67 public this (Predicate screener)
68 {
69 this(screener, null, 0);
70 }
71
72 /**
73 * Special version of constructor needed by clone()
74 **/
75 protected this (Predicate s, LLPairT l, int c)
76 {
77 super(s);
78 list = l;
79 count = c;
80 }
81
82 /**
83 * Make an independent copy of the list. Does not clone elements
84 **/
85
86 public LinkMap duplicate()
87 {
88 if (list is null)
89 return new LinkMap (screener, null, 0);
90 else
91 return new LinkMap (screener, cast(LLPairT)(list.copyList()), count);
92 }
93
94
95 // Collection methods
96
97 /**
98 * Implements tango.util.collection.impl.Collection.Collection.contains.
99 * Time complexity: O(n).
100 * See_Also: tango.util.collection.impl.Collection.Collection.contains
101 **/
102 public final bool contains(T element)
103 {
104 if (!isValidArg(element) || list is null)
105 return false;
106
107 return list.find(element) !is null;
108 }
109
110 /**
111 * Implements tango.util.collection.impl.Collection.Collection.instances.
112 * Time complexity: O(n).
113 * See_Also: tango.util.collection.impl.Collection.Collection.instances
114 **/
115 public final uint instances(T element)
116 {
117 if (!isValidArg(element) || list is null)
118 return 0;
119
120 return list.count(element);
121 }
122
123 /**
124 * Implements tango.util.collection.impl.Collection.Collection.elements.
125 * Time complexity: O(1).
126 * See_Also: tango.util.collection.impl.Collection.Collection.elements
127 **/
128 public final GuardIterator!(T) elements()
129 {
130 return keys();
131 }
132
133 /***********************************************************************
134
135 Implements tango.util.collection.model.View.View.opApply
136 Time complexity: O(n)
137
138 See_Also: tango.util.collection.model.View.View.opApply
139
140 ************************************************************************/
141
142 int opApply (int delegate (inout T value) dg)
143 {
144 auto scope iterator = new MapIterator!(K, T)(this);
145 return iterator.opApply (dg);
146 }
147
148
149 /***********************************************************************
150
151 Implements tango.util.collection.MapView.opApply
152 Time complexity: O(n)
153
154 See_Also: tango.util.collection.MapView.opApply
155
156 ************************************************************************/
157
158 int opApply (int delegate (inout K key, inout T value) dg)
159 {
160 auto scope iterator = new MapIterator!(K, T)(this);
161 return iterator.opApply (dg);
162 }
163
164
165 // Map methods
166
167
168 /**
169 * Implements tango.util.collection.Map.containsKey.
170 * Time complexity: O(n).
171 * See_Also: tango.util.collection.Map.containsKey
172 **/
173 public final bool containsKey(K key)
174 {
175 if (!isValidKey(key) || list is null)
176 return false;
177
178 return list.findKey(key) !is null;
179 }
180
181 /**
182 * Implements tango.util.collection.Map.containsPair
183 * Time complexity: O(n).
184 * See_Also: tango.util.collection.Map.containsPair
185 **/
186 public final bool containsPair(K key, T element)
187 {
188 if (!isValidKey(key) || !isValidArg(element) || list is null)
189 return false;
190 return list.find(key, element) !is null;
191 }
192
193 /**
194 * Implements tango.util.collection.Map.keys.
195 * Time complexity: O(1).
196 * See_Also: tango.util.collection.Map.keys
197 **/
198 public final PairIterator!(K, T) keys()
199 {
200 return new MapIterator!(K, T)(this);
201 }
202
203 /**
204 * Implements tango.util.collection.Map.get.
205 * Time complexity: O(n).
206 * See_Also: tango.util.collection.Map.get
207 **/
208 public final T get(K key)
209 {
210 checkKey(key);
211 if (list !is null)
212 {
213 auto p = list.findKey(key);
214 if (p !is null)
215 return p.element();
216 }
217 throw new NoSuchElementException("no matching Key");
218 }
219
220 /**
221 * Return the element associated with Key key.
222 * Params:
223 * key = a key
224 * Returns: whether the key is contained or not
225 **/
226
227 public final bool get(K key, inout T element)
228 {
229 checkKey(key);
230 if (list !is null)
231 {
232 auto p = list.findKey(key);
233 if (p !is null)
234 {
235 element = p.element();
236 return true;
237 }
238 }
239 return false;
240 }
241
242
243
244 /**
245 * Implements tango.util.collection.Map.keyOf.
246 * Time complexity: O(n).
247 * See_Also: tango.util.collection.Map.keyOf
248 **/
249 public final bool keyOf(inout K key, T value)
250 {
251 if (!isValidArg(value) || count is 0)
252 return false;
253
254 auto p = (cast(LLPairT)(list.find(value)));
255 if (p is null)
256 return false;
257
258 key = p.key();
259 return true;
260 }
261
262
263 // MutableCollection methods
264
265 /**
266 * Implements tango.util.collection.impl.Collection.Collection.clear.
267 * Time complexity: O(1).
268 * See_Also: tango.util.collection.impl.Collection.Collection.clear
269 **/
270 public final void clear()
271 {
272 list = null;
273 setCount(0);
274 }
275
276 /**
277 * Implements tango.util.collection.impl.Collection.Collection.replaceOneOf
278 * Time complexity: O(n).
279 * See_Also: tango.util.collection.impl.Collection.Collection.replaceOneOf
280 **/
281 public final void replace (T oldElement, T newElement)
282 {
283 replace_(oldElement, newElement, false);
284 }
285
286 /**
287 * Implements tango.util.collection.impl.Collection.Collection.replaceAllOf.
288 * Time complexity: O(n).
289 * See_Also: tango.util.collection.impl.Collection.Collection.replaceAllOf
290 **/
291 public final void replaceAll(T oldElement, T newElement)
292 {
293 replace_(oldElement, newElement, true);
294 }
295
296 /**
297 * Implements tango.util.collection.impl.Collection.Collection.removeAll.
298 * Time complexity: O(n).
299 * See_Also: tango.util.collection.impl.Collection.Collection.removeAll
300 **/
301 public final void removeAll(T element)
302 {
303 remove_(element, true);
304 }
305
306 /**
307 * Implements tango.util.collection.impl.Collection.Collection.removeOneOf.
308 * Time complexity: O(n).
309 * See_Also: tango.util.collection.impl.Collection.Collection.removeOneOf
310 **/
311 public final void remove(T element)
312 {
313 remove_(element, false);
314 }
315
316 /**
317 * Implements tango.util.collection.impl.Collection.Collection.take.
318 * Time complexity: O(1).
319 * takes the first element on the list
320 * See_Also: tango.util.collection.impl.Collection.Collection.take
321 **/
322 public final T take()
323 {
324 if (list !is null)
325 {
326 auto v = list.element();
327 list = cast(LLPairT)(list.next());
328 decCount();
329 return v;
330 }
331 checkIndex(0);
332 return T.init; // not reached
333 }
334
335
336 // MutableMap methods
337
338 /**
339 * Implements tango.util.collection.impl.MapCollection.MapCollection.add.
340 * Time complexity: O(n).
341 * See_Also: tango.util.collection.impl.MapCollection.MapCollection.add
342 **/
343 public final void add (K key, T element)
344 {
345 checkKey(key);
346 checkElement(element);
347
348 if (list !is null)
349 {
350 auto p = list.findKey(key);
351 if (p !is null)
352 {
353 if (p.element() != (element))
354 {
355 p.element(element);
356 incVersion();
357 }
358 return ;
359 }
360 }
361 list = new LLPairT(key, element, list);
362 incCount();
363 }
364
365
366 /**
367 * Implements tango.util.collection.impl.MapCollection.MapCollection.remove.
368 * Time complexity: O(n).
369 * See_Also: tango.util.collection.impl.MapCollection.MapCollection.remove
370 **/
371 public final void removeKey (K key)
372 {
373 if (!isValidKey(key) || list is null)
374 return ;
375
376 auto p = list;
377 auto trail = p;
378
379 while (p !is null)
380 {
381 auto n = cast(LLPairT)(p.next());
382 if (p.key() == (key))
383 {
384 decCount();
385 if (p is list)
386 list = n;
387 else
388 trail.unlinkNext();
389 return ;
390 }
391 else
392 {
393 trail = p;
394 p = n;
395 }
396 }
397 }
398
399 /**
400 * Implements tango.util.collection.impl.MapCollection.MapCollection.replaceElement.
401 * Time complexity: O(n).
402 * See_Also: tango.util.collection.impl.MapCollection.MapCollection.replaceElement
403 **/
404 public final void replacePair (K key, T oldElement, T newElement)
405 {
406 if (!isValidKey(key) || !isValidArg(oldElement) || list is null)
407 return ;
408
409 auto p = list.find(key, oldElement);
410 if (p !is null)
411 {
412 checkElement(newElement);
413 p.element(newElement);
414 incVersion();
415 }
416 }
417
418 private final void remove_(T element, bool allOccurrences)
419 {
420 if (!isValidArg(element) || count is 0)
421 return ;
422
423 auto p = list;
424 auto trail = p;
425
426 while (p !is null)
427 {
428 auto n = cast(LLPairT)(p.next());
429 if (p.element() == (element))
430 {
431 decCount();
432 if (p is list)
433 {
434 list = n;
435 trail = n;
436 }
437 else
438 trail.next(n);
439
440 if (!allOccurrences || count is 0)
441 return ;
442 else
443 p = n;
444 }
445 else
446 {
447 trail = p;
448 p = n;
449 }
450 }
451 }
452
453 /**
454 * Helper for replace
455 **/
456
457 private final void replace_(T oldElement, T newElement, bool allOccurrences)
458 {
459 if (list is null || !isValidArg(oldElement) || oldElement == (newElement))
460 return ;
461
462 auto p = list.find(oldElement);
463 while (p !is null)
464 {
465 checkElement(newElement);
466 p.element(newElement);
467 incVersion();
468 if (!allOccurrences)
469 return ;
470 p = p.find(oldElement);
471 }
472 }
473
474 // ImplementationCheckable methods
475
476 /**
477 * Implements tango.util.collection.model.View.View.checkImplementation.
478 * See_Also: tango.util.collection.model.View.View.checkImplementation
479 **/
480 public override void checkImplementation()
481 {
482 super.checkImplementation();
483
484 assert(((count is 0) is (list is null)));
485 assert((list is null || list._length() is count));
486
487 for (auto p = list; p !is null; p = cast(LLPairT)(p.next()))
488 {
489 assert(allows(p.element()));
490 assert(allowsKey(p.key()));
491 assert(containsKey(p.key()));
492 assert(contains(p.element()));
493 assert(instances(p.element()) >= 1);
494 assert(containsPair(p.key(), p.element()));
495 }
496 }
497
498
499 /***********************************************************************
500
501 opApply() has migrated here to mitigate the virtual call
502 on method get()
503
504 ************************************************************************/
505
506 private static class MapIterator(K, V) : AbstractMapIterator!(K, V)
507 {
508 private LLPairT pair;
509
510 public this (LinkMap map)
511 {
512 super (map);
513 pair = map.list;
514 }
515
516 public final V get(inout K key)
517 {
518 if (pair)
519 key = pair.key;
520 return get();
521 }
522
523 public final V get()
524 {
525 decRemaining();
526 auto v = pair.element();
527 pair = cast(LLPairT) pair.next();
528 return v;
529 }
530
531 int opApply (int delegate (inout V value) dg)
532 {
533 int result;
534
535 for (auto i=remaining(); i--;)
536 {
537 auto value = get();
538 if ((result = dg(value)) != 0)
539 break;
540 }
541 return result;
542 }
543
544 int opApply (int delegate (inout K key, inout V value) dg)
545 {
546 K key;
547 int result;
548
549 for (auto i=remaining(); i--;)
550 {
551 auto value = get(key);
552 if ((result = dg(key, value)) != 0)
553 break;
554 }
555 return result;
556 }
557 }
558 }
559
560
561
562 debug(Test)
563 {
564 void main()
565 {
566 auto map = new LinkMap!(Object, double);
567
568 foreach (key, value; map.keys) {typeof(key) x; x = key;}
569
570 foreach (value; map.keys) {}
571
572 foreach (value; map.elements) {}
573
574 auto keys = map.keys();
575 while (keys.more)
576 auto v = keys.get();
577
578 foreach (value; map) {}
579 foreach (key, value; map) {}
580
581 map.checkImplementation();
582 }
583 }