Mercurial > projects > ldc
diff tango/tango/util/collection/LinkMap.d @ 132:1700239cab2e trunk
[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 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tango/tango/util/collection/LinkMap.d Fri Jan 11 17:57:40 2008 +0100 @@ -0,0 +1,583 @@ +/* + File: LinkMap.d + + Originally written by Doug Lea and released into the public domain. + Thanks for the assistance and support of Sun Microsystems Labs, Agorics + Inc, Loral, and everyone contributing, testing, and using this code. + + History: + Date Who What + 24Sep95 dl@cs.oswego.edu Create from tango.util.collection.d working file + 13Oct95 dl Changed protection statuses + 21Oct95 dl Fixed error in remove + +*/ + + +module tango.util.collection.LinkMap; + +private import tango.core.Exception; + +private import tango.io.protocol.model.IReader, + tango.io.protocol.model.IWriter; + +private import tango.util.collection.model.View, + tango.util.collection.model.GuardIterator; + +private import tango.util.collection.impl.LLCell, + tango.util.collection.impl.LLPair, + tango.util.collection.impl.MapCollection, + tango.util.collection.impl.AbstractIterator; + +/** + * Linked lists of (key, element) pairs + * author: Doug Lea +**/ +public class LinkMap(K, T) : MapCollection!(K, T) // , IReadable, IWritable +{ + alias LLCell!(T) LLCellT; + alias LLPair!(K, T) LLPairT; + + alias MapCollection!(K, T).remove remove; + alias MapCollection!(K, T) .removeAll removeAll; + + // instance variables + + /** + * The head of the list. Null if empty + **/ + + package LLPairT list; + + // constructors + + /** + * Make an empty list + **/ + + public this () + { + this(null, null, 0); + } + + /** + * Make an empty list with the supplied element screener + **/ + + public this (Predicate screener) + { + this(screener, null, 0); + } + + /** + * Special version of constructor needed by clone() + **/ + protected this (Predicate s, LLPairT l, int c) + { + super(s); + list = l; + count = c; + } + + /** + * Make an independent copy of the list. Does not clone elements + **/ + + public LinkMap duplicate() + { + if (list is null) + return new LinkMap (screener, null, 0); + else + return new LinkMap (screener, cast(LLPairT)(list.copyList()), count); + } + + + // Collection methods + + /** + * Implements tango.util.collection.impl.Collection.Collection.contains. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.contains + **/ + public final bool contains(T element) + { + if (!isValidArg(element) || list is null) + return false; + + return list.find(element) !is null; + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.instances. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.instances + **/ + public final uint instances(T element) + { + if (!isValidArg(element) || list is null) + return 0; + + return list.count(element); + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.elements. + * Time complexity: O(1). + * See_Also: tango.util.collection.impl.Collection.Collection.elements + **/ + public final GuardIterator!(T) elements() + { + return keys(); + } + + /*********************************************************************** + + Implements tango.util.collection.model.View.View.opApply + Time complexity: O(n) + + See_Also: tango.util.collection.model.View.View.opApply + + ************************************************************************/ + + int opApply (int delegate (inout T value) dg) + { + auto scope iterator = new MapIterator!(K, T)(this); + return iterator.opApply (dg); + } + + + /*********************************************************************** + + Implements tango.util.collection.MapView.opApply + Time complexity: O(n) + + See_Also: tango.util.collection.MapView.opApply + + ************************************************************************/ + + int opApply (int delegate (inout K key, inout T value) dg) + { + auto scope iterator = new MapIterator!(K, T)(this); + return iterator.opApply (dg); + } + + + // Map methods + + + /** + * Implements tango.util.collection.Map.containsKey. + * Time complexity: O(n). + * See_Also: tango.util.collection.Map.containsKey + **/ + public final bool containsKey(K key) + { + if (!isValidKey(key) || list is null) + return false; + + return list.findKey(key) !is null; + } + + /** + * Implements tango.util.collection.Map.containsPair + * Time complexity: O(n). + * See_Also: tango.util.collection.Map.containsPair + **/ + public final bool containsPair(K key, T element) + { + if (!isValidKey(key) || !isValidArg(element) || list is null) + return false; + return list.find(key, element) !is null; + } + + /** + * Implements tango.util.collection.Map.keys. + * Time complexity: O(1). + * See_Also: tango.util.collection.Map.keys + **/ + public final PairIterator!(K, T) keys() + { + return new MapIterator!(K, T)(this); + } + + /** + * Implements tango.util.collection.Map.get. + * Time complexity: O(n). + * See_Also: tango.util.collection.Map.get + **/ + public final T get(K key) + { + checkKey(key); + if (list !is null) + { + auto p = list.findKey(key); + if (p !is null) + return p.element(); + } + throw new NoSuchElementException("no matching Key"); + } + + /** + * Return the element associated with Key key. + * Params: + * key = a key + * Returns: whether the key is contained or not + **/ + + public final bool get(K key, inout T element) + { + checkKey(key); + if (list !is null) + { + auto p = list.findKey(key); + if (p !is null) + { + element = p.element(); + return true; + } + } + return false; + } + + + + /** + * Implements tango.util.collection.Map.keyOf. + * Time complexity: O(n). + * See_Also: tango.util.collection.Map.keyOf + **/ + public final bool keyOf(inout K key, T value) + { + if (!isValidArg(value) || count is 0) + return false; + + auto p = (cast(LLPairT)(list.find(value))); + if (p is null) + return false; + + key = p.key(); + return true; + } + + + // MutableCollection methods + + /** + * Implements tango.util.collection.impl.Collection.Collection.clear. + * Time complexity: O(1). + * See_Also: tango.util.collection.impl.Collection.Collection.clear + **/ + public final void clear() + { + list = null; + setCount(0); + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.replaceOneOf + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.replaceOneOf + **/ + public final void replace (T oldElement, T newElement) + { + replace_(oldElement, newElement, false); + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.replaceAllOf. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.replaceAllOf + **/ + public final void replaceAll(T oldElement, T newElement) + { + replace_(oldElement, newElement, true); + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.removeAll. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.removeAll + **/ + public final void removeAll(T element) + { + remove_(element, true); + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.removeOneOf. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.removeOneOf + **/ + public final void remove(T element) + { + remove_(element, false); + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.take. + * Time complexity: O(1). + * takes the first element on the list + * See_Also: tango.util.collection.impl.Collection.Collection.take + **/ + public final T take() + { + if (list !is null) + { + auto v = list.element(); + list = cast(LLPairT)(list.next()); + decCount(); + return v; + } + checkIndex(0); + return T.init; // not reached + } + + + // MutableMap methods + + /** + * Implements tango.util.collection.impl.MapCollection.MapCollection.add. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.MapCollection.MapCollection.add + **/ + public final void add (K key, T element) + { + checkKey(key); + checkElement(element); + + if (list !is null) + { + auto p = list.findKey(key); + if (p !is null) + { + if (p.element() != (element)) + { + p.element(element); + incVersion(); + } + return ; + } + } + list = new LLPairT(key, element, list); + incCount(); + } + + + /** + * Implements tango.util.collection.impl.MapCollection.MapCollection.remove. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.MapCollection.MapCollection.remove + **/ + public final void removeKey (K key) + { + if (!isValidKey(key) || list is null) + return ; + + auto p = list; + auto trail = p; + + while (p !is null) + { + auto n = cast(LLPairT)(p.next()); + if (p.key() == (key)) + { + decCount(); + if (p is list) + list = n; + else + trail.unlinkNext(); + return ; + } + else + { + trail = p; + p = n; + } + } + } + + /** + * Implements tango.util.collection.impl.MapCollection.MapCollection.replaceElement. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.MapCollection.MapCollection.replaceElement + **/ + public final void replacePair (K key, T oldElement, T newElement) + { + if (!isValidKey(key) || !isValidArg(oldElement) || list is null) + return ; + + auto p = list.find(key, oldElement); + if (p !is null) + { + checkElement(newElement); + p.element(newElement); + incVersion(); + } + } + + private final void remove_(T element, bool allOccurrences) + { + if (!isValidArg(element) || count is 0) + return ; + + auto p = list; + auto trail = p; + + while (p !is null) + { + auto n = cast(LLPairT)(p.next()); + if (p.element() == (element)) + { + decCount(); + if (p is list) + { + list = n; + trail = n; + } + else + trail.next(n); + + if (!allOccurrences || count is 0) + return ; + else + p = n; + } + else + { + trail = p; + p = n; + } + } + } + + /** + * Helper for replace + **/ + + private final void replace_(T oldElement, T newElement, bool allOccurrences) + { + if (list is null || !isValidArg(oldElement) || oldElement == (newElement)) + return ; + + auto p = list.find(oldElement); + while (p !is null) + { + checkElement(newElement); + p.element(newElement); + incVersion(); + if (!allOccurrences) + return ; + p = p.find(oldElement); + } + } + + // ImplementationCheckable methods + + /** + * Implements tango.util.collection.model.View.View.checkImplementation. + * See_Also: tango.util.collection.model.View.View.checkImplementation + **/ + public override void checkImplementation() + { + super.checkImplementation(); + + assert(((count is 0) is (list is null))); + assert((list is null || list._length() is count)); + + for (auto p = list; p !is null; p = cast(LLPairT)(p.next())) + { + assert(allows(p.element())); + assert(allowsKey(p.key())); + assert(containsKey(p.key())); + assert(contains(p.element())); + assert(instances(p.element()) >= 1); + assert(containsPair(p.key(), p.element())); + } + } + + + /*********************************************************************** + + opApply() has migrated here to mitigate the virtual call + on method get() + + ************************************************************************/ + + private static class MapIterator(K, V) : AbstractMapIterator!(K, V) + { + private LLPairT pair; + + public this (LinkMap map) + { + super (map); + pair = map.list; + } + + public final V get(inout K key) + { + if (pair) + key = pair.key; + return get(); + } + + public final V get() + { + decRemaining(); + auto v = pair.element(); + pair = cast(LLPairT) pair.next(); + return v; + } + + int opApply (int delegate (inout V value) dg) + { + int result; + + for (auto i=remaining(); i--;) + { + auto value = get(); + if ((result = dg(value)) != 0) + break; + } + return result; + } + + int opApply (int delegate (inout K key, inout V value) dg) + { + K key; + int result; + + for (auto i=remaining(); i--;) + { + auto value = get(key); + if ((result = dg(key, value)) != 0) + break; + } + return result; + } + } +} + + + +debug(Test) +{ + void main() + { + auto map = new LinkMap!(Object, double); + + foreach (key, value; map.keys) {typeof(key) x; x = key;} + + foreach (value; map.keys) {} + + foreach (value; map.elements) {} + + auto keys = map.keys(); + while (keys.more) + auto v = keys.get(); + + foreach (value; map) {} + foreach (key, value; map) {} + + map.checkImplementation(); + } +}