projects/doodle: doodle/containers/list.d comparison

comparison doodle/containers/list.d @ 40:1f97022e5c6d

Checkpoint. Development continues...

author	daveb
date	Mon, 12 Apr 2010 14:01:54 +0930
parents
children

comparison

equal deleted inserted replaced

-:b6c34f1fc7f3
+:1f97022e5c6d
+module doodle.containers.list;
+///
+/// Doubly-linked list.
+/// Consists of a sequence of cells with references to the previous and next member.
+/// List keeps track of its length.
+///
+/// The list has two ends:
+///     "head" and "tail".
+/// There are two directions:
+///     "forwards" -> towards the "head" and
+///     "backwards" -> towards the "tail"
+/// opApply works from the head to the tail.
+/// opApplyReverse works from the tail to the head.
+///
+/// When used as a queue, typically use addTail and removeHead.
+///
+/// Design goals of list is to be completely symmetric and clear in its
+/// forwards and backwards operations, and to be able to contain immutable types.
+///
+class List(T) {
+//
+// Standard operations:
+//
+/// Construct an empty list
+this() { }
+/// Return a copy of the list
+List!(T) dup() const {
+auto l = new List!(T);
+for (auto c = &mHead; c; c = &c.mBackward) {
+l.addTail(c.mElement);
+}
+return l;
+}
+/// Return true if the list is empty
+bool isEmpty() const {
+return mLength == 0;
+}
+/// Return the length of the list
+uint length() const {
+return mLength;
+}
+/// Return the head of the list, asserting if the list is empty
+T head() {
+assert(!isEmpty());
+return mHead.mElement;
+}
+/// Return the tail of the list, asserting if the list is empty
+T tail() {
+assert(!isEmpty());
+return mTail.mElement;
+}
+/// Add to the head of the list
+void addHead(T t) {
+add(mHead, null, t);
+}
+/// Add to the tail of the list
+void addTail(T t) {
+add(null, mTail, t);
+}
+/// Remove the head of the list, asserting if the list is empty
+T removeHead() {
+return remove(mHead).mElement;
+}
+/// Remove the tail of the list, asserting of the list is empty
+T removeTail() {
+return remove(mTail).mElement;
+}
+// Clear the list (garbage collector does the rest)
+void clear() {
+mHead = mTail = null;
+mLength = 0;
+}
+/// Iterate over the list from head to tail - used by foreach
+int opApply(int delegate(ref T) dg) {
+int result;
+auto c = mHead;
+while (c !is null) {
+auto t = c.mElement;
+result = dg(t);
+if (result != 0) {
+break;
+}
+c = c.mBackward;
+}
+return result;
+}
+/// Iterate over the list from tail to head - used by foreach_reverse
+int opApplyReverse(int delegate(ref T) dg) {
+int result;
+auto c = mTail;
+while (c !is null) {
+auto t = c.mElement;
+result = dg(t);
+if (result != 0) {
+break;
+}
+c = c.mForward;
+}
+return result;
+}
+//
+// Iterator operations:
+//
+/// Return the first matching element going backward from head, or null
+Iterator findHead(T t) {
+for (auto c = mHead; c !is null; c = c.mBackward) {
+if (c.mElement == t) {
+return new Iterator(c);
+}
+}
+return null;
+}
+/// Return the first matching element going forward from tail, or null
+Iterator findTail(T t) {
+for (auto c = mTail; c !is null; c = c.mForward) {
+if (c.mElement == t) {
+return new Iterator(c);
+}
+}
+return null;
+}
+/// insert a new entry into list, forward of entry specified by iterator
+void insertForward(Iterator i, T t) {
+assert(i !is null);
+add(i.mCell, i.mCell.mForward, t);
+}
+/// insert a new entry into list, backward of entry specified by iterator
+void insertBackward(Iterator i, T t) {
+assert(i !is null);
+add(i.mCell.mBackward, i.mCell, t);
+}
+/// Remove specified entry from list, returning iterator to entry forward of removed one
+Iterator eraseForward(Iterator i) {
+assert(i !is null);
+Cell cell = remove(i.mCell);
+return cell.mForward ? new Iterator(cell.mForward) : null;
+}
+/// Remove specified entry from list, returning iterator to entry backward of removed one
+Iterator eraseBackward(Iterator i) {
+assert(i !is null);
+Cell cell = remove(i.mCell);
+return cell.mBackward ? new Iterator(cell.mBackward) : null;
+}
+///
+/// Iterator for a List
+///
+class Iterator {
+private Cell mCell;
+private this(Cell cell) {
+assert(cell !is null);
+mCell = cell;
+}
+T element() {
+return mCell.mElement;
+}
+void goForward() {
+assert(mCell.mForward !is null);
+mCell = mCell.mForward;
+}
+void goBackward() {
+assert(mCell.mBackward !is null);
+mCell = mCell.mBackward;
+}
+bool forwardValid() const {
+return mCell.mForward !is null;
+}
+bool backwardValid() const {
+return mCell.mBackward !is null;
+}
+override bool opEquals(Object other) const {
+Iterator o = cast(Iterator) other;
+if (!o) return 0;
+return mCell is o.mCell;
+}
+}
+//
+// Implementation:
+//
+private {
+Cell mHead;
+Cell mTail;
+uint mLength;
+/// An entry in the list
+class Cell {
+Cell mForward, mBackward;
+T mElement;
+this(T element, Cell backward, Cell forward) {
+mElement = element;
+mBackward = backward;
+mForward = forward;
+}
+}
+/// Add new cell between backward and forward
+void add(Cell backward, Cell forward, T t) {
+Cell cell = new Cell(t, backward, forward);
+if (backward) {
+backward.mForward = cell;
+}
+else {
+mTail = cell;
+}
+if (forward) {
+forward.mBackward = cell;
+}
+else {
+mHead = cell;
+}
+++mLength;
+}
+/// Remove a cell from the list, returning the removed cell
+Cell remove(Cell cell) {
+if (cell.mBackward) {
+cell.mBackward.mForward = cell.mForward;
+}
+else {
+mTail = cell.mForward;
+}
+if (cell.mForward) {
+cell.mForward.mBackward = cell.mBackward;
+}
+else {
+mHead = cell.mBackward;
+}
+--mLength;
+return cell;
+}
+}
+}

Mercurial > projects > doodle

comparison doodle/containers/list.d @ 40:1f97022e5c6d