Mercurial > projects > aid
view trunk/mintl/multiaa.d @ 1:5dd9f598bcd8
Update
author | revcompgeek |
---|---|
date | Sat, 29 Mar 2008 12:30:20 -0600 |
parents | |
children |
line wrap: on
line source
/** \file multiaa.d * \brief An associative array that allows multiple values per key. * * Written by Ben Hinkle and released to the public domain, as * explained at http://creativecommons.org/licenses/publicdomain * The red-black tree code is by Thomas Niemann. * Email comments and bug reports to ben.hinkle@gmail.com * * revision 1.2 */ module mintl.multiaa; private import mintl.share; private import mintl.adapter; private import mintl.sortedaa; private import mintl.hashaa; private import std.stdarg; private import std.boxer; //version = WithBox; /** An associative array of items with duplicate keys. * By default the backing container is a builtin associative array. */ struct MultiAA(Key, Value, ImplType = HashAA!(Key,Value[])) { alias MultiAA ContainerType; alias Value ValueType; alias Key IndexType; alias ImplType AdaptType; const bit isReadOnly = ImplType.isReadOnly; ImplType impl; size_t length() { size_t total = 0; foreach(Value[] val; impl) { total += val.length; } return total; } int opEquals(MultiAA c) { return impl == c.impl; } static if (!ImplType.isReadOnly) { void remove(Key key) { impl.remove(key); } void remove(Key key, Value val) { Value[]* vals = impl.get(key); if (vals) { size_t k; Value[] x = *vals; for(k = 0; k<x.length;k++) { if (x[k] == val) break; } for(; k < x.length-1; k++) { x[k] = x[k+1]; } *vals = x[0 .. k]; } } void addItem(Key key, Value item) { Value[]* vals = impl.put(key); (*vals) ~= item; } void clear(){ impl.clear(); } } // !isReadOnly Value[] opIndex(Key key) {return impl[key];} MultiAA dup() { MultiAA res; res.impl = impl.dup; return res; } bool isEmpty() { return impl.isEmpty(); } // mixin MMAASpecial!(impl,MultiAA,Key,Value,ImplType) mAA; static if (!ImplType.isReadOnly) { /** Inserts the specified items into the target AA by calling * x[key]=value repeatedly. */ void add(...) { vadd(_arguments,_argptr); } void vadd(TypeInfo[] arguments, void* argptr) { for (int k=0;k<arguments.length;k++) { TypeInfo tik = typeid(Key); if (arguments[k] == tik) { Key key = va_arg!(Key)(argptr); k++; addItem(key,va_arg!(Value)(argptr)); } else { version(WithBox) { Box b = box(tik,argptr); Key key = unbox!(Key)(b); k++; TypeInfo tiv = arguments[k]; b = box(tiv,argptr); addItem(key,unbox!(Value)(b)); argptr += va_argumentLength(tiv.tsize()); } } } } /** Construct a container with specified contents */ static MultiAA make(...) { MultiAA res; res.vadd(_arguments,_argptr); return res; } } Key[] keys() { return impl.keys; } Value[][] values() { return impl.values; } int opApply(int delegate(inout Value x) dg){ int res; L0: foreach(inout Value[] item; impl) { foreach(inout Value val; item) { res = dg(val); if (res) break L0; } } return res; } int opApply(int delegate(inout Key key, inout Value x) dg){ int res; L1: foreach(Key key, inout Value[] item; impl) { foreach(inout Value val; item) { res = dg(key,val); if (res) break L1; } } return res; } } // Adapter for a sorted MultiAA template SortedMultiAA(Key,Value) { alias MultiAA!(Key,Value,SortedAA!(Key,Value[])) SortedMultiAA; } //version = MinTLVerboseUnittest; //version = MinTLUnittest; version (MinTLUnittest) { unittest { version (MinTLVerboseUnittest) printf("starting mintl.multiaa unittest\n"); // test MultiSet MultiAA!(int,char[]) ma2; ma2.add(22,"hello",-100,"there",22,"world"); static char[][2] res = ["hello","world"]; static char[][1] res2 = ["there"]; char[][] vv = ma2[22]; assert( ma2[22].length == 2); assert( ma2[22] == res); assert( ma2[-100] == res2); int count22; int count; foreach( int key, char[] item; ma2 ) { if (key == 22) { count22++; } else { count++; } } assert( count22 == 2 ); assert( count == 1 ); ma2.remove(-100); assert( ma2.length == 2 ); ma2.remove(22,"hello"); static char[][1] res3 = ["world"]; assert( ma2[22] == res3); assert( ma2.length == 1 ); ma2.remove(22); assert( ma2.length == 0 ); assert( ma2.isEmpty ); // test SortedMultiSet SortedMultiAA!(char[],int) s3; s3.add("hello",10,"world",20); s3.addItem("hello",40); int[] vals = s3["hello"]; assert( s3["hello"].length == 2); assert( vals[0] == 10 && vals[1] == 40 ); vals = s3["world"]; assert( vals.length == 1 && vals[0] == 20 ); version (MinTLVerboseUnittest) printf("finished mintl.multiaa unittest\n"); } }