| 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123 | /******************************************************************************* copyright: Copyright (c) 2008 Kris Bell. All rights reserved license: BSD style: $(LICENSE) version: Apr 2008: Initial release authors: Kris Since: 0.99.7 Based upon Doug Lea's Java collection package *******************************************************************************/ module tango.util.container.SortedMap; public import tango.util.container.Container; private import tango.util.container.RedBlack; private import tango.util.container.model.IContainer; private import tango.core.Exception : NoSuchElementException; /******************************************************************************* RedBlack trees of (key, value) pairs --- Iterator iterator (bool forward) Iterator iterator (K key, bool forward) int opApply (scope int delegate (ref V value) dg) int opApply (scope int delegate (ref K key, ref V value) dg) bool contains (V value) bool containsKey (K key) bool containsPair (K key, V value) bool keyOf (V value, ref K key) bool get (K key, ref V value) bool take (ref V v) bool take (K key, ref V v) bool removeKey (K key) size_t remove (V value, bool all) size_t remove (IContainer!(V) e, bool all) bool add (K key, V value) size_t replace (V oldElement, V newElement, bool all) bool replacePair (K key, V oldElement, V newElement) bool opIndexAssign (V element, K key) K nearbyKey (K key, bool greater) V opIndex (K key) V* opIn_r (K key) size_t size () bool isEmpty () V[] toArray (V[] dst) SortedMap dup () SortedMap clear () SortedMap reset () SortedMap comparator (Comparator c) --- *******************************************************************************/ class SortedMap (K, V, alias Reap = Container.reap, alias Heap = Container.DefaultCollect) : IContainer!(V) { // use this type for Allocator configuration public alias RedBlack!(K, V) Type; private alias Type *Ref; private alias Heap!(Type) Alloc; private alias Compare!(K) Comparator; // root of the tree. Null if empty. package Ref tree; // configured heap manager private Alloc heap; // Comparators used for ordering private Comparator cmp; private Compare!(V) cmpElem; private size_t count, mutation; /*********************************************************************** Make an empty tree, using given Comparator for ordering ***********************************************************************/ public this (Comparator c = null) { this (c, 0); } /*********************************************************************** Special version of constructor needed by dup() ***********************************************************************/ private this (Comparator c, size_t n) { count = n; cmpElem = &compareElem; cmp = (c is null) ? &compareKey : c; } /*********************************************************************** Clean up when deleted ***********************************************************************/ ~this () { reset; } /*********************************************************************** Return a generic iterator for contained elements ***********************************************************************/ final Iterator iterator (bool forward = true) { Iterator i = void; i.node = count ? (forward ? tree.leftmost : tree.rightmost) : null; i.bump = forward ? &Iterator.fore : &Iterator.back; i.mutation = mutation; i.owner = this; i.prior = null; return i; } /*********************************************************************** Return an iterator which return all elements matching or greater/lesser than the key in argument. The second argument dictates traversal direction. Return a generic iterator for contained elements ***********************************************************************/ final Iterator iterator (K key, bool forward) { Iterator i = iterator (forward); i.node = count ? tree.findFirst(key, cmp, forward) : null; return i; } /*********************************************************************** Configure the assigned allocator with the size of each allocation block (number of nodes allocated at one time) and the number of nodes to pre-populate the cache with. Time complexity: O(n) ***********************************************************************/ final SortedMap cache (size_t chunk, size_t count=0) { heap.config (chunk, count); return this; } /*********************************************************************** Return the number of elements contained ***********************************************************************/ @property final const size_t size () { return count; } /*********************************************************************** Create an independent copy. Does not clone elements ***********************************************************************/ @property final SortedMap dup () { auto clone = new SortedMap!(K, V, Reap, Heap) (cmp, count); if (count) clone.tree = tree.copyTree (&clone.heap.allocate); return clone; } /*********************************************************************** Time complexity: O(log n) ***********************************************************************/ final bool contains (V value) { if (count is 0) return false; return tree.findAttribute (value, cmpElem) !is null; } /*********************************************************************** ***********************************************************************/ final int opApply (scope int delegate (ref V value) dg) { return iterator.opApply ((ref K k, ref V v) {return dg(v);}); } /*********************************************************************** ***********************************************************************/ final int opApply (scope int delegate (ref K key, ref V value) dg) { return iterator.opApply (dg); } /*********************************************************************** Use a new Comparator. Causes a reorganization ***********************************************************************/ final SortedMap comparator (Comparator c) { if (cmp !is c) { cmp = (c is null) ? &compareKey : c; if (count !is 0) { // must rebuild tree! mutate; auto t = tree.leftmost; tree = null; count = 0; while (t) { add_ (t.value, t.attribute, false); t = t.successor; } } } return this; } /*********************************************************************** Time complexity: O(log n) ***********************************************************************/ final bool containsKey (K key) { if (count is 0) return false; return tree.find (key, cmp) !is null; } /*********************************************************************** Time complexity: O(n) ***********************************************************************/ final bool containsPair (K key, V value) { if (count is 0) return false; return tree.find (key, value, cmp) !is null; } /*********************************************************************** Return the value associated with Key key. param: key a key Returns: whether the key is contained or not ***********************************************************************/ final bool get (K key, ref V value) { if (count) { auto p = tree.find (key, cmp); if (p) { value = p.attribute; return true; } } return false; } /*********************************************************************** Return the value of the key exactly matching the provided key or, if none, the key just after/before it based on the setting of the second argument param: key a key param: after indicates whether to look beyond or before the given key, where there is no exact match throws: NoSuchElementException if none found returns: a pointer to the value, or null if not present ***********************************************************************/ K nearbyKey (K key, bool after) { if (count) { auto p = tree.findFirst (key, cmp, after); if (p) return p.value; } noSuchElement ("no such key"); assert (0); } /*********************************************************************** Return the first key of the map throws: NoSuchElementException where the map is empty ***********************************************************************/ K firstKey () { if (count) return tree.leftmost.value; noSuchElement ("no such key"); assert (0); } /*********************************************************************** Return the last key of the map throws: NoSuchElementException where the map is empty ***********************************************************************/ K lastKey () { if (count) return tree.rightmost.value; noSuchElement ("no such key"); assert (0); } /*********************************************************************** Return the value associated with Key key. param: key a key Returns: a pointer to the value, or null if not present ***********************************************************************/ final V* opIn_r (K key) { if (count) { auto p = tree.find (key, cmp); if (p) return &p.attribute; } return null; } /*********************************************************************** Time complexity: O(n) ***********************************************************************/ final bool keyOf (V value, ref K key) { if (count is 0) return false; auto p = tree.findAttribute (value, cmpElem); if (p is null) return false; key = p.value; return true; } /*********************************************************************** Time complexity: O(n) ***********************************************************************/ final SortedMap clear () { return clear (false); } /*********************************************************************** Reset the SortedMap contents. This releases more memory than clear() does Time complexity: O(n) ***********************************************************************/ final SortedMap reset () { return clear (true); } /*********************************************************************** ************************************************************************/ final size_t remove (IContainer!(V) e, bool all) { auto c = count; foreach (v; e) remove (v, all); return c - count; } /*********************************************************************** Time complexity: O(n ***********************************************************************/ final size_t remove (V value, bool all = false) { size_t i = count; if (count) { auto p = tree.findAttribute (value, cmpElem); while (p) { tree = p.remove (tree); decrement (p); if (!all || count is 0) break; p = tree.findAttribute (value, cmpElem); } } return i - count; } /*********************************************************************** Time complexity: O(n) ***********************************************************************/ final size_t replace (V oldElement, V newElement, bool all = false) { size_t c; if (count) { auto p = tree.findAttribute (oldElement, cmpElem); while (p) { ++c; mutate; p.attribute = newElement; if (!all) break; p = tree.findAttribute (oldElement, cmpElem); } } return c; } /*********************************************************************** Time complexity: O(log n) Takes the value associated with the least key. ***********************************************************************/ final bool take (ref V v) { if (count) { auto p = tree.leftmost; v = p.attribute; tree = p.remove (tree); decrement (p); return true; } return false; } /*********************************************************************** Time complexity: O(log n) ***********************************************************************/ final bool take (K key, ref V value) { if (count) { auto p = tree.find (key, cmp); if (p) { value = p.attribute; tree = p.remove (tree); decrement (p); return true; } } return false; } /*********************************************************************** Time complexity: O(log n) Returns true if inserted, false where an existing key exists and was updated instead ***********************************************************************/ final bool add (K key, V value) { return add_ (key, value, true); } /*********************************************************************** Time complexity: O(log n) Returns true if inserted, false where an existing key exists and was updated instead ***********************************************************************/ final bool opIndexAssign (V element, K key) { return add (key, element); } /*********************************************************************** Operator retreival function Throws NoSuchElementException where key is missing ***********************************************************************/ final V opIndex (K key) { auto p = opIn_r (key); if (p) return *p; noSuchElement ("missing or invalid key"); assert (0); } /*********************************************************************** Time complexity: O(log n) ***********************************************************************/ final bool removeKey (K key) { V value; return take (key, value); } /*********************************************************************** Time complexity: O(log n) ***********************************************************************/ final bool replacePair (K key, V oldElement, V newElement) { if (count) { auto p = tree.find (key, oldElement, cmp); if (p) { p.attribute = newElement; mutate; return true; } } return false; } /*********************************************************************** Copy and return the contained set of values in an array, using the optional dst as a recipient (which is resized as necessary). Returns a slice of dst representing the container values. Time complexity: O(n) ***********************************************************************/ final V[] toArray (V[] dst = null) { if (dst.length < count) dst.length = count; size_t i = 0; foreach (k, v; this) dst[i++] = v; return dst [0 .. count]; } /*********************************************************************** Is this container empty? Time complexity: O(1) ***********************************************************************/ final const bool isEmpty () { return count is 0; } /*********************************************************************** ***********************************************************************/ final SortedMap check () { assert(cmp !is null); assert(((count is 0) is (tree is null))); assert((tree is null || tree.size() is count)); if (tree) { tree.checkImplementation; auto t = tree.leftmost; K last = K.init; while (t) { auto v = t.value; assert((last is K.init || cmp(last, v) <= 0)); last = v; t = t.successor; } } return this; } /*********************************************************************** ***********************************************************************/ private void noSuchElement (immutable(char)[] msg) { throw new NoSuchElementException (msg); } /*********************************************************************** Time complexity: O(log n) ***********************************************************************/ private size_t instances (V value) { if (count is 0) return 0; return tree.countAttribute (value, cmpElem); } /*********************************************************************** Returns true where an element is added, false where an existing key is found ***********************************************************************/ private final bool add_ (K key, V value, bool checkOccurrence) { if (tree is null) { tree = heap.allocate.set (key, value); increment; } else { auto t = tree; for (;;) { int diff = cmp (key, t.value); if (diff is 0 && checkOccurrence) { if (t.attribute != value) { t.attribute = value; mutate; } return false; } else if (diff <= 0) { if (t.left) t = t.left; else { tree = t.insertLeft (heap.allocate.set(key, value), tree); increment; break; } } else { if (t.right) t = t.right; else { tree = t.insertRight (heap.allocate.set(key, value), tree); increment; break; } } } } return true; } /*********************************************************************** Time complexity: O(n) ***********************************************************************/ private SortedMap clear (bool all) { mutate; // collect each node if we can't collect all at once if ((heap.collect(all) is false) & count) { auto node = tree.leftmost; while (node) { auto next = node.successor; decrement (node); node = next; } } count = 0; tree = null; return this; } /*********************************************************************** Time complexity: O(log n) ***********************************************************************/ private void remove (Ref node) { tree = node.remove (tree); decrement (node); } /*********************************************************************** new element was added ***********************************************************************/ private void increment () { ++mutation; ++count; } /*********************************************************************** element was removed ***********************************************************************/ private void decrement (Ref p) { Reap (p.value, p.attribute); heap.collect (p); ++mutation; --count; } /*********************************************************************** set was changed ***********************************************************************/ private void mutate () { ++mutation; } /*********************************************************************** The default key comparator @param fst first argument @param snd second argument Returns: a negative number if fst is less than snd; a positive number if fst is greater than snd; else 0 ***********************************************************************/ private static int compareKey (ref K fst, ref K snd) { if (fst is snd) return 0; return typeid(K).compare (&fst, &snd); } /*********************************************************************** The default value comparator @param fst first argument @param snd second argument Returns: a negative number if fst is less than snd; a positive number if fst is greater than snd; else 0 ***********************************************************************/ private static int compareElem(ref V fst, ref V snd) { if (fst is snd) return 0; return typeid(V).compare (&fst, &snd); } /*********************************************************************** Iterator with no filtering ***********************************************************************/ private struct Iterator { Ref function(Ref) bump; Ref node, prior; SortedMap owner; size_t mutation; /*************************************************************** Did the container change underneath us? ***************************************************************/ bool valid () { return owner.mutation is mutation; } /*************************************************************** Accesses the next value, and returns false when there are no further values to traverse ***************************************************************/ bool next (ref K k, ref V v) { auto n = next (k); return (n) ? v = *n, true : false; } /*************************************************************** Return a pointer to the next value, or null when there are no further values to traverse ***************************************************************/ V* next (ref K k) { V* r; if (node) { prior = node; k = node.value; r = &node.attribute; node = bump (node); } return r; } /*************************************************************** Foreach support ***************************************************************/ int opApply (scope int delegate(ref K key, ref V value) dg) { int result; auto n = node; while (n) { prior = n; auto next = bump (n); if ((result = dg(n.value, n.attribute)) != 0) break; n = next; } node = n; return result; } /*************************************************************** Remove value at the current iterator location ***************************************************************/ bool remove () { if (prior) { owner.remove (prior); // ignore this change ++mutation; return true; } prior = null; return false; } /*************************************************************** ***************************************************************/ Iterator reverse () { if (bump is &fore) bump = &back; else bump = &fore; return this; } /*************************************************************** ***************************************************************/ private static Ref fore (Ref p) { return p.successor; } /*************************************************************** ***************************************************************/ private static Ref back (Ref p) { return p.predecessor; } } } /******************************************************************************* *******************************************************************************/ debug (SortedMap) { import tango.io.Stdout; import tango.core.Thread; import tango.time.StopWatch; import tango.math.random.Kiss; void main() { // usage examples ... auto map = new SortedMap!(char[], int); map.add ("foo", 1); map.add ("bar", 2); map.add ("wumpus", 3); // implicit generic iteration foreach (key, value; map) Stdout.formatln ("{}:{}", key, value); // explicit iteration foreach (key, value; map.iterator("foo", false)) Stdout.formatln ("{}:{}", key, value); // generic iteration with optional remove auto s = map.iterator; foreach (key, value; s) {} // s.remove; // incremental iteration, with optional remove char[] k; int v; auto iterator = map.iterator; while (iterator.next(k, v)) {} //iterator.remove; // incremental iteration, with optional failfast auto it = map.iterator; while (it.valid && it.next(k, v)) {} // remove specific element map.removeKey ("wumpus"); // remove first element ... while (map.take(v)) Stdout.formatln ("taking {}, {} left", v, map.size); // setup for benchmark, with a set of integers. We // use a chunk allocator, and presize the bucket[] auto test = new SortedMap!(int, int, Container.reap, Container.Chunk); test.cache (1000, 500_000); const count = 500_000; StopWatch w; auto keys = new int[count]; foreach (ref vv; keys) vv = Kiss.instance.toInt(int.max); // benchmark adding w.start; for (int i=count; i--;) test.add(keys[i], i); Stdout.formatln ("{} adds: {}/s", test.size, test.size/w.stop); // benchmark reading w.start; for (int i=count; i--;) test.get(keys[i], v); Stdout.formatln ("{} lookups: {}/s", test.size, test.size/w.stop); // benchmark adding without allocation overhead test.clear; w.start; for (int i=count; i--;) test.add(keys[i], i); Stdout.formatln ("{} adds (after clear): {}/s", test.size, test.size/w.stop); // benchmark duplication w.start; auto dup = test.dup; Stdout.formatln ("{} element dup: {}/s", dup.size, dup.size/w.stop); // benchmark iteration w.start; foreach (key, value; test) {} Stdout.formatln ("{} element iteration: {}/s", test.size, test.size/w.stop); test.check; } } |