/******************************************************************************* @file DLlist.d Copyright (c) 2005 Clay Smith This software is provided 'as-is', without any express or implied warranty. In no event will the authors be held liable for damages arising from the use of this software. Permission is granted to anyone to use this software for any purpose, including commercial applications, and to alter it and redistribute it freely, subject to the following restrictions: 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. 3. This notice may not be removed or altered from any source distribution. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @version (2005): initial version @author Clay Smith @description A templated doubly linked list class *******************************************************************************/ module list; import std.stdio; //module core.container.DLlist; /******************************************************************************* Templated doubly-linked list class *******************************************************************************/ class DLlist (T) { public: /******************************************************************************* Constructor and destructor here, right now they do nothing *******************************************************************************/ this() {} ~this() {} /******************************************************************************* Add an item 'T' to the list a) create new node on da heap and implant our data inside it b) if this is the first thing to go into the list, add straight in b1) only thing in list, so its prev and next must be null b2) only thing in list, so head and tail must point to it c) if there is already stuff in the list, add it on the end c1) make the last item point to this new item, instead of 'null' c2) make this new item's previous point to the last item c3) make this new items 'next' be null, since it is added on the end c4) reset the tail pointer to point to our new last item d) increment the size of our list *******************************************************************************/ void add(T newData) { // a Node *item = new Node; item.data = newData; // b if (head is null) // first item in list { // b1 item.next = null; item.prev = null; // b2 head = item; tail = item; // update tail } // c else // add on to the end { // c1 tail.next = item; // c2 item.prev = tail; // c3 item.next = null; // c4 tail = item; } // d ++listSize; } /******************************************************************************* Remove this node 'item' from the list Also, there are 4 cases that need to be handled seperately for a remove, ... 1) item is the middle (most likely case) 2) item is the last item 3) item is the first item (with stuff after it) 4) item is the only item a) if we are dealing with a middle remove a1) switcheroo the pointers, so that 'item' is not in the list b) if we are dealing with an end remove b1) have tail point to the previous item b2) set the previous's item next to null c) if we are dealing with a beginning remove c1) set head to the next pointer in list c2) set the next pointers prev to null d) if we are dealing with removing the last item in the list d1) just set head and tail to null e) crash horribly if none of these scenarios were executed f) remove item from existance and decrement size *******************************************************************************/ void remove() { if (curr is null) return; // a if (curr.prev !== null && curr.next !== null) { // a1 curr.next.prev = curr.prev; curr.prev.next = curr.next; } // b else if (curr.prev !== null && curr.next is null) { // b1 tail = curr.prev; // b2 curr.prev.next = null; } // c else if (curr.prev is null && curr.next !== null) { // c1 head = curr.next; // c2 curr.next.prev = null; } // d else if (curr.prev is null && curr.next is null) { // d1 head = null; tail = null; } // e else assert(false); // f delete curr; curr = null; --listSize; } /******************************************************************************* Returns the length of the list *******************************************************************************/ int length() { return listSize; } int size() { return listSize; } /******************************************************************************* Simple function to tell if list is empty or not *******************************************************************************/ bit empty() { if (listSize == 0) return true; else return false; } /******************************************************************************* Just make curr null again *******************************************************************************/ void reset() { curr = null; } /******************************************************************************* Clear all data from the list a) reset as a precaution, so we don't accidentily just remove half the list b) remove everything *******************************************************************************/ void clear() { // a reset(); // b while (!last) remove(); } /******************************************************************************* Returns the current data from the list *******************************************************************************/ T data() { assert(curr !== null); return curr.data; } /******************************************************************************* Used for traversing from the beginning to the end of the list Returns false when still traversing and true when reached the end of the list a) if there is nothing in the list, we are done with it b) if curr isn't pointing to anything, make it point to head c) otherwise... c1) go to the next item c2) if we have reached the end, then signal to stop *******************************************************************************/ bit last() { // a if (empty()) return true; // b if (curr is null) curr = head; // c else { // c1 curr = curr.next; // c2 if (curr is null) return true; } return false; } /******************************************************************************* Used for traversing from the end to the beginning of the list Returns false when still traversing and true when reached the end of the list a) if list is empty, we are done with it a) if curr isn't pointing to anything, make it point to tail b) otherwise... b1) go to the prev item b2) if we have reached the end, then signal to stop *******************************************************************************/ bit first() { // a if (empty()) return true; // b if (curr is null) curr = tail; // c else { // c1 curr = curr.prev; // c2 if (curr is null) return true; } return false; } private: /******************************************************************************* Simple vars to keep track of our heaping list *******************************************************************************/ int listSize = 0; Node *head = null; Node *tail = null; Node *curr = null; /******************************************************************************* Templated Node structure, holds pointers to previous and next items in the list *******************************************************************************/ struct Node { Node *prev; T data; Node *next; } }