Stack and Queue

LordSauron Joined: 01/22/08 Posts: 9

Posted: 01/22/08 23:19:41 I know some people were asking for a implementation of Stack and Queue in Tango's collections classes. I got really bored and wrote a bare-bones implementation of both using a circular doubly-linked list. I'm still "moving in" to D, so it's probably not using the best features of D, and I haven't even tested or compiled it yet, but here it goes. And yes, I know it's perfectly useless to have a circular doubly-linked stack. I was writing a queue, then I forgot what I was doing and wrote a stack. I came out of my stupor wondering why I had a circular doubly-linked stack. It was funny. package tango.util.collection.LinkedQueue; // written 20080122110838 PST // by Chris Miller (lord Sauron the Great {at} gmail {dot} com) class LinkedQueue(K) { private struct Node(K) { K data; Node(K) left, right; } // private struct Node(K) private Node(K) head=null; public LinkedQueue(); public void push(K e) { Node(K) d=new Node(); d.data=e; if(!head) { head=d; d.left=d; d.right=d; return; } // if(!head) head.left.right=d; d.left=head.left; head.left=d; d.right=head; } // public void push(K e) public K peek() { if(!head) return null; return head.data; } public K pop() { if(!head) return null; else if(head.left==head && head.right==head) { K temp=head.data; head=null; return temp; } // else if(head.left==head && head.right==head) K temp=head.data; head.left.right=head.right; head.right.left=head.left; head=head.right; return temp; } // public K pop() } // class LinkedQueue(K) package tango.util.collection.LinkedStack; // written 20080122101455 PST // by Chris Miller (lord Sauron the Great {at} gmail {dot} com) class LinkedStack(K) { private struct Node(K) { K data; Node(K) left, right; } // private struct Node(K) private Node(K) head=null; public LinkedStack(); public void push(K e) { Node(K) d=new Node(); d.data=e; d.right=head; d.left=head.left; head.left=d; head.right=d; head=d; } // public void push(K e) public K peek() { if(!head) return null; return head.data; } public K pop() { if(!head) return null; if(head.left==head && head.right==head) { K temp=head.data; head=null; return temp; } // if(head.left==head && head.right==head) head.right.left=head.left; head.left.right=head.right; K temp=head.data; head=head.right; return temp; } // public K pop() } // class LinkedStack(K) I'm not all to familiar with Tango, either, so that probably ignores a lot of Tango conventions for collections, but it's a starting point, no? Registered Linux Addict #431495 http://profile.xfire.com/mrstalinman | John 3:16! http://www.fsdev.net/ | http://www.mindofsauron.blogspot.com/

Author	Message
LordSauron Joined: 01/22/08 Posts: 9	Posted: 01/22/08 23:35:39 And then I became more bored as well: package tango.util.collection.ArrayStack; // written 20080122135351 PST // by Chris Miller (lord Sauron the Great {at} gmail {dot} com) class ArrayStack(K) { uint l_bound=0, r_bound=0; K[] data; public ArrayStack() { this(5); } public ArrayStack(uint size) { assert(size!=0); ensureCapacity(size); } // public ArrayStack(uint size) public void ensureCapacity(uint capacity) { if(data.length>=capacity) { if(data.length-r_bound+(r_bound-l_bound)>=capacity) return; else rebalance(); } // if(data.length>=capacity) K[capacity] new_data; for(uint i=0; i!=r_bound-l_bound; i++) new_data[i]=data[i+l_bound]; data=new_data; l_bound=0; } // public void ensureCapacity(uint capacity) public K pop() { if(r_bound-l_bound==0) // empty stack return null; return data[l_bound++]; } // public K pop() public void rebalance() { if(l_bound==0) return; if(r_bound-l_bound==0) { l_bound=0; r_bound=0; return; } // if (r_bound-l_bound==0) for(uint i=0; i!=r_bound-l_bound; i++) data[i]=data[l_bound+i]; r_bound-=l_bound; l_bound=0; } // public void rebalance() public K peek() { if(r_bound-l_bound!=0) return data[l_bound]; return null; } public void push(K e) { if(data.length-r_bound==0) ensureCapacity(data.length*1.5f); data[r_bound++]=e; } // public void push(K e) } // class ArrayStack(K) You can tell how interesting school is for me. Registered Linux Addict #431495 http://profile.xfire.com/mrstalinman | John 3:16! http://www.fsdev.net/ | http://www.mindofsauron.blogspot.com/
larsivi Joined: 03/27/04 Posts: 614	Posted: 01/22/08 23:38:44 Have you looked at the interfaces in use in the collection package and whether your collections fit / can fit in?
LordSauron Joined: 01/22/08 Posts: 9	Posted: 01/22/08 23:52:03 No, I was in a classroom and warming up the laptop and tapping away with the keyboard is significantly more distracting to other students. I was fine, I already know the material, but I don't want to distract them. Small minds, small pleasures, I try to keep myself off their pleasures list if you know what I mean. I do know there's a significant infrastructure in the tango.util.collection area, though I have yet to memorize it. Those base classes should be able to evolve into something that can dovetail right in with the rest of the data structures, whether by my doing or someone else's I do not know. I'll try, but I can make no guarantees. I'm only a monkey with a Allen-wrench at this point, though I hope to progress to some form of Neanderthal at a later date. Registered Linux Addict #431495 http://profile.xfire.com/mrstalinman | John 3:16! http://www.fsdev.net/ | http://www.mindofsauron.blogspot.com/
larsivi Joined: 03/27/04 Posts: 614	Posted: 01/23/08 00:13:25 We all tend to be somewhat busy, and so wish list items tend to be put on the backburner until someone comes along, whether they are evil overlords or small hobbits. If you are able get these classes into the collection framework, then we certainly will consider them for inclusion. Good luck :)
LordSauron Joined: 01/22/08 Posts: 9	Posted: 01/23/08 02:08:29 Yeah, sure thing. I can't test for Linux, however, since I haven't yet gotten GDC and Tango all nice and happy with each other. I'll beat it until it works on DMD though. Registered Linux Addict #431495 http://profile.xfire.com/mrstalinman | John 3:16! http://www.fsdev.net/ | http://www.mindofsauron.blogspot.com/
LordSauron Joined: 01/22/08 Posts: 9	Posted: 01/23/08 03:46:39 Right now it's throwing me a lovely build error related to my lazy setup of a project based off of the Tango SVN trunk. Everything else compiles as it should, though if that single import error is masking other issues I do not know. I'd like to check in with my progress before continuing. I'd just like to stop any bad behavior on my part now, as opposed to later. So if it's not too much trouble if someone wiser and more experienced than I (read: basically anyone) could glance this over and see if I'm going awry I'd really like that. module tango.util.collection.LinkedQueue; private import tango.util.collection.impl.CLCell; /** * Standard Queue implementation using a Linked List (circular doubly-linked). * * No iterator yet written, until such time please use while(!peek) { ... } * * @author Chris Miller */ public class LinkedQueue(K) { private CLCell!(K) head=null; public LinkedQueue(); public void push(K e) { if(!head) { head=new CLCell(e); return; } // if(!head) head.addPrev(e); } // public void push(K e) public K peek() { if(!head) return null; return head.element(); } public K pop() { if(!head) return null; else if(head.next() is head && head.prev() is head) { K temp=head.element(); head=null; return temp; } // else if(head.left==head && head.right==head) K temp=head.element(); head=head.next(); head.prev().unlink(); return temp; } // public K pop() } // class LinkedQueue(K) Registered Linux Addict #431495 http://profile.xfire.com/mrstalinman | John 3:16! http://www.fsdev.net/ | http://www.mindofsauron.blogspot.com/
LordSauron Joined: 01/22/08 Posts: 9	Posted: 01/24/08 23:58:50 So I was working more, trying to get LinkQueue? up to parity with the rest of the stuff in tango.util.collection. I was working on the Iterators and ran into opApply. It's all very difficult to track down because it is spread over many different interfaces and classes in many different files. Would I be correct in saying that opApply called on the data structure itself will delete all elements which do not satisfy opApply, and in an iterator opApply just skips elements which do not satisfy the predicate? Or am I wrong, and am I not understanding this. I think it might help some if I knew what the "op" part stands for. Registered Linux Addict #431495 http://profile.xfire.com/mrstalinman | John 3:16! http://www.fsdev.net/ | http://www.mindofsauron.blogspot.com/
larsivi Joined: 03/27/04 Posts: 614	Posted: 01/25/08 09:32:16 opApply is a rather badly named operation (opVisit probably would have been better). It is what a class or struct must implement for foreach to work. Queue queue = new Queue!(ElemType); // add some elements; foreach (elem; queue) // where elem automatically will have the type ElemType elem.foo; opApply will definately not delete anything ever. Generally, you cannot modify the collection itself while iterating over it, and especially not when using opApply as the compiler may optimize on the backgrounds that it expects no modification to happen. The predicate version is correctly enough there to filter the elements passed along to the foreach body.
kris Joined: 03/27/04 Posts: 581	Posted: 01/25/08 17:38:20 In the documentation, there are a couple of diagrams showing the relationships and structure of this package. That may be helpful?
larsivi Joined: 03/27/04 Posts: 614	Posted: 01/25/08 17:47:13 The documentation in question is ChapterStorage.
LordSauron Joined: 01/22/08 Posts: 9	Posted: 01/26/08 01:54:56 -- Modified: 01/26/08 05:20:03 by LordSauron larsivi wrote: opApply is a rather badly named operation (opVisit probably would have been better). It is what a class or struct must implement for foreach to work. Queue queue = new Queue!(ElemType); // add some elements; foreach (elem; queue) // where elem automatically will have the type ElemType elem.foo; opApply will definately not delete anything ever. Generally, you cannot modify the collection itself while iterating over it, and especially not when using opApply as the compiler may optimize on the backgrounds that it expects no modification to happen. The predicate version is correctly enough there to filter the elements passed along to the foreach body. So, it's sort of like an Iterator that returns the next element index? Iterators themselves use this to iterate over the collections, yes? Coming from Java, I have to say "dude, that's weird!" I think I can make this work... though I don't particularly agree with the idea of not being able to change the data structure while iterating. I wrote a ton of data structure implementations in AP Computer Science where you could modify the data structure during iteration. I'd think that would be a very important feature indeed! Heck, I may have to write my own alternate implementation modeled more closely to the Java types to make myself happy. It'll be a fun exercise if nothing else. I'll do it right after finishing up these stacks and queues. If I get them to a point of cohesion with the rest of the Tango collection classes, can they be merged into the Tango sources (assuming I test them and find them stable)? I can make a SVN patch file which should make it easier. EDIT 200801252049 PST: On second thought, I really don't think it's appropriate to make stacks and queues iterable. My thinking is that they're special kinds of structures which aren't like lists. They are very specific about the order in which elements are accessed. In both stacks and queues the act of accessing elements changes the contents (something which won't go over well with opApply I think). It just won't do to have a stack or queue that's maskable by Predicates either. I'm not a Tango dev, however. Someone with authority to make final decisions needs to make the final call. I think I could write it either way, however, I'd strongly discourage making it iterable. It'd require iterating over the collection without removing the elements as is supposed to happen in these data structures. Just asking for guidance, this isn't my project, but I want to help. It's already helped me learn more about D, and I'd like to do a few smaller odd-jobs around Tango. It's fun, and it's a library I immediately thought "hey, I could get into this!" I was enthralled with it when I read about Fibers, actually. No guesses what I value in a program. Let me know what you think. My current progress is here: http://files.fsdev.net/#1 Registered Linux Addict #431495 http://profile.xfire.com/mrstalinman | John 3:16! http://www.fsdev.net/ | http://www.mindofsauron.blogspot.com/
larsivi Joined: 03/27/04 Posts: 614	Posted: 01/26/08 08:52:53 The internal implementation of an opApply is a bit of magic, so I recommend reading http://www.digitalmars.com/d/1.0/statement.html#ForeachStatement Generally, in the foreach I showed further up, elem is the element, whereas foreach (i, elem; list) would also give you the index that element has in the list as i. As I'm sure you know, this is exactly how it looks when you iterate over a native array, like Foo[] list; . As for iteration support in Stack and Queue, it does indeed sound somewhat malplaced. And for iterators not being able modify the container; it has been discussed, but due to typical concurrency issues, you would need to synchronize the edit and it would be excessively slow. When you feel you are done, please create a ticket and attach the implementation, and we will consider it for inclusion. Thank you very much for your work so far :)
LordSauron Joined: 01/22/08 Posts: 9	Posted: 01/26/08 19:08:59 Yeah, so I'm gonna leave out the iterators under the thinking that they're really a example of Heisenberg principle. You can't access them without changing them. If someone wants to access them without changing them they can always extend the class and write their own accessors. It wouldn't be that hard. At this point one of my main concerns is applying a hand of healing to my circular doubly-linked stack. How I ever got that far without realizing the data linkage is completely useless I may never know! Registered Linux Addict #431495 http://profile.xfire.com/mrstalinman | John 3:16! http://www.fsdev.net/ | http://www.mindofsauron.blogspot.com/