Mercurial > projects > aid
view trunk/mintl/set.d @ 1:5dd9f598bcd8
Update
author | revcompgeek |
---|---|
date | Sat, 29 Mar 2008 12:30:20 -0600 |
parents | |
children |
line wrap: on
line source
/** \file set.d * \brief Set, sorted set and multi-set containers. * * Written by Ben Hinkle and released to the public domain, as * explained at http://creativecommons.org/licenses/publicdomain * Email comments and bug reports to ben.hinkle@gmail.com * * revision 2.7.1 */ module mintl.set; 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; template MAddSet(Container,Value) { /** Inserts the specified items into the set. */ void add(...) { vadd(_arguments,_argptr); } void vadd(TypeInfo[] arguments, void* argptr) { for (int k=0;k<arguments.length;k++) { TypeInfo tik = typeid(Value); if (arguments[k] == tik) { addItem(va_arg!(Value)(argptr)); } else { version(WithBox) { Box b = box(tik,argptr); addItem(unbox!(Value)(b)); argptr += va_argumentLength(tik.tsize()); } } } } /** Construct a container with specified contents */ static Container make(...) { Container res; res.vadd(_arguments,_argptr); return res; } } /** A set of items. By default the backing container is a HashAA * associative array. */ struct Set(Value, ImplType = HashAA!(Value,uint)) { alias Set ContainerType; alias Value ValueType; alias ImplType AdaptType; const bit isReadOnly = ImplType.isReadOnly; ImplType impl; mixin MAdaptBuiltin!(impl,Set); static if (!ImplType.isReadOnly) { void remove(Value item) { impl.remove(item); } } bool opIndex(Value item) {return impl.contains(item); } Set dup() { Set res; res.impl = impl.dup; return res; } void clear(){ impl.clear(); } bool isEmpty() { return impl.isEmpty(); } static if (!ImplType.isReadOnly) { mixin MAddSet!(Set,Value) mAdd; } Value[] values() { return impl.keys; } void addItem(Value item) { impl[item] = 1; } int opApply(int delegate(inout Value x) dg){ int res; foreach(Value item, uint ignore; impl) { res = dg(item); if (res) break; } return res; } } /** Adapter for sorted set of items. */ template SortedSet(Value) { alias Set!(Value,SortedAA!(Value,uint)) SortedSet; } /** A set of items with repeats. By default the backing container is a * HashAA associative array. */ struct MultiSet(Value, ImplType = HashAA!(Value,uint)) { alias Set ContainerType; alias Value ValueType; alias ImplType AdaptType; static if (is(ImplType:uint[Value])) { const bit isReadOnly = false; } else { const bit isReadOnly = ImplType.isReadOnly; } ImplType impl; size_t length() { size_t total = 0; foreach(uint val; impl) { total += val; } return total; } int opEquals(MultiSet c) { return impl == c.impl; } static if (!ImplType.isReadOnly) { void remove(Value item) { uint* val = impl.get(item); if (val && (--(*val) == 0)) impl.remove(item); } void addItem(Value item) { (*impl.put(item))++; } } bool opIndex(Value item) {return impl.get(item) !is null; } MultiSet dup() { MultiSet res; res.impl = impl.dup; return res; } void clear(){ impl.clear(); } bool isEmpty() { return impl.isEmpty(); } static if (!ImplType.isReadOnly) { mixin MAddSet!(MultiSet, Value) mAdd; } Value[] values() { return impl.keys; } int opApply(int delegate(inout Value x) dg){ int res; foreach(Value item, uint val; impl) { while (val--) { res = dg(item); if (res) break; } } return res; } } /** Adapter for sorted multi-set. */ template SortedMultiSet(Value) { alias MultiSet!(Value,SortedAA!(Value,uint)) SortedMultiSet; } //version = MinTLVerboseUnittest; //version = MinTLUnittest; version (MinTLUnittest) { unittest { version (MinTLVerboseUnittest) printf("starting mintl.set unittest\n"); // test Set Set!(char[]) s; s.add("hello","world"); assert( s["world"] ); assert( s["hello"] ); assert( !s["worldfoo"] ); foreach(char[] val ; s) { version (MinTLVerboseUnittest) printf("%.*s\n",val); } // test SortedSet SortedSet!(char[]) s2; s2.add("hello","world"); assert( s2["world"] ); assert( s2["hello"] ); assert( !s2["worldfoo"] ); foreach(char[] val ; s2) { version (MinTLVerboseUnittest) printf("%.*s\n",val); } assert( !s2.isEmpty ); // test MultiSet MultiSet!(int) ma2; ma2.add(22,-100,22); assert( ma2[22] ); assert( ma2[-100] ); int count22; int count; foreach( int item; ma2 ) { if (item == 22) { count22++; } else { count++; } } assert( count22 == 2 ); assert( count == 1 ); ma2.remove(-100); assert( ma2.length == 2 ); ma2.remove(22); assert( ma2[22] ); assert( ma2.length == 1 ); ma2.remove(22); assert( ma2.length == 0 ); assert( ma2.isEmpty ); // test SortedMultiSet SortedMultiSet!(char[]) s3; s3.add("hello","world"); assert( s3["world"] ); assert( s3["hello"] ); assert( !s3["worldfoo"] ); version (MinTLVerboseUnittest) printf("finished mintl.set unittest\n"); } }