Forum Navigation
I want this type of collection
Posted: 07/09/08 15:11:22Hi,
It would be nice to have something like linked list in Tango (I know we already have a lot of these:). I called my list a "round map". Round because items are stored in array and they are reused. So it is circular and circles are round lol. Map because items can be accessed by their index. So I will try to explain. The difference is that all items are stored in a linear array, so they could be accessed very fast by their index. The list maintains the index of the head item and tail item. The tail item is actually the the next free slot. And since the stuff is stored in an array, it needs to grow. For example:
The list is empty. Add several items and the list becomes something like this: 1--2--3--4. Each item knows the index of the next and previous one. And when you call mylist.add(newitem), the add fuction returns the index of the newly added item. Now lets say we delete the second item. The list becomes something like this 1-----3--4--2 and the tail is now the second item so the next call to add will reuse this spot in the array and return the index.
This kind of list is extremely useful when working with C libraries. Take Win32 for example. To associate a HWND with a D class you need associative array. And these are slow. Instead of using AA you use this kind of list. So you add one item and you get its index. Set the user data for the HWND to this integer value and later access the class by index instead of doing AA lookups.
I have a basic implementation of this class, but I am not good at this stuff so it is probably buggy. It would be nice if it is implemented better in Tango consistent style:
import tango.io.Stdout; //todo: won't work if T.init is nan class RoundMap(T) { this(uint step=32,uint initial=0,T bad=T.init) { stack.length=initial; this.bad=bad; this.step=(step==0?1:step); } uint add(T v) { if(size==stack.length) { auto start=stack.length; stack.length=stack.length+step; for(uint c=start;c<stack.length;++c) { auto s=&stack[c]; s.next=c+1; s.prev=c-1; s.value=bad; } if(start+1<stack.length) stack[start+1].prev=tail; stack[tail].next=start+1; } auto i=tail; auto s=&stack[tail]; s.value=v; tail=s.next; ++size; return i; } T del(uint i) { auto s=&stack[i]; auto r=s.value; if(r==bad) return r; s.value=bad; if(s.prev!=uint.max) stack[s.prev].next=s.next; if(s.next!=uint.max) stack[s.next].prev=s.prev; if(i==head) head=s.next; if(tail<stack.length) //insert the free cell after the tail { auto t=&stack[tail]; s.next=t.next; s.prev=tail; if(s.next<stack.length) stack[s.next].prev=i; t.next=i; } else //insert the free cell after the last item and make it tail { Container* t; uint c=tail; if(tail>=stack.length) for(c=head;c!=tail;c=stack[c].next) t=&stack[c]; s.prev=c; s.next=tail; tail=t.next=i; } --size; return r; } uint index(bool delegate(ref T v) cmp) { for(uint c=head;c!=tail;c=stack[c].next) if(cmp(stack[c].value)) return c; return uint.max; } /*void print() { tango.io.Stdout.Stdout("used (",head,tail,"): "); for(uint c=head;c!=tail && c<stack.length;c=stack[c].next) Stdout(c," ");//,stack[c].prev,"<>",stack[c].next,"||| "); tango.io.Stdout.Stdout("\nfree (",tail,size,stack.length,"): "); for(uint c=tail;c!=uint.max && c<stack.length;c=stack[c].next) Stdout(c," ");//,stack[c].prev,"<>",stack[c].next,"||| "); tango.io.Stdout.Stdout("\n").newline.flush; }*/ T get(uint index){return stack[index].value;} T* getRef(uint index){return &stack[index].value;} uint length(){return size;} uint limit(){return stack.length;} T bad; protected: Container[] stack; uint head,tail; uint size,step; struct Container { //static Container* opCall(T v,uint p){auto ret=new Container;ret.value=v;ret.prev=p;return ret;} T value; uint prev=uint.max,next=uint.max; } }
