Mercurial > projects > ldc
diff tango/tango/util/collection/impl/LLCell.d @ 132:1700239cab2e trunk
[svn r136] MAJOR UNSTABLE UPDATE!!!
Initial commit after moving to Tango instead of Phobos.
Lots of bugfixes...
This build is not suitable for most things.
author | lindquist |
---|---|
date | Fri, 11 Jan 2008 17:57:40 +0100 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tango/tango/util/collection/impl/LLCell.d Fri Jan 11 17:57:40 2008 +0100 @@ -0,0 +1,330 @@ +/* + File: LLCell.d + + Originally written by Doug Lea and released into the public domain. + Thanks for the assistance and support of Sun Microsystems Labs, Agorics + Inc, Loral, and everyone contributing, testing, and using this code. + + History: + Date Who What + 24Sep95 dl@cs.oswego.edu Create from tango.util.collection.d working file + +*/ + + +module tango.util.collection.impl.LLCell; + +private import tango.util.collection.impl.Cell; + +private import tango.util.collection.model.Comparator; + +/** + * + * + * LLCells extend Cells with standard linkedlist next-fields, + * and provide a standard operations on them. + * <P> + * LLCells are pure implementation tools. They perform + * no argument checking, no result screening, and no synchronization. + * They rely on user-level classes (see for example LinkedList) to do such things. + * Still, the class is made `public' so that you can use them to + * build other kinds of collections or whatever, not just the ones + * currently supported. + * + author: Doug Lea + * @version 0.93 + * + * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>. +**/ + +public class LLCell(T) : Cell!(T) +{ + alias Comparator!(T) ComparatorT; + + + protected LLCell next_; + + /** + * Return the next cell (or null if none) + **/ + + public LLCell next() + { + return next_; + } + + /** + * set to point to n as next cell + * @param n, the new next cell + **/ + + public void next(LLCell n) + { + next_ = n; + } + + public this (T v, LLCell n) + { + super(v); + next_ = n; + } + + public this (T v) + { + this(v, null); + } + + public this () + { + this(T.init, null); + } + + + /** + * Splice in p between current cell and whatever it was previously + * pointing to + * @param p, the cell to splice + **/ + + public final void linkNext(LLCell p) + { + if (p !is null) + p.next_ = next_; + next_ = p; + } + + /** + * Cause current cell to skip over the current next() one, + * effectively removing the next element from the list + **/ + + public final void unlinkNext() + { + if (next_ !is null) + next_ = next_.next_; + } + + /** + * Linear search down the list looking for element (using T.equals) + * @param element to look for + * Returns: the cell containing element, or null if no such + **/ + + public final LLCell find(T element) + { + for (LLCell p = this; p !is null; p = p.next_) + if (p.element() == element) + return p; + return null; + } + + /** + * return the number of cells traversed to find first occurrence + * of a cell with element() element, or -1 if not present + **/ + + public final int index(T element) + { + int i = 0; + for (LLCell p = this; p !is null; p = p.next_) + { + if (p.element() == element) + return i; + else + ++i; + } + return -1; + } + + /** + * Count the number of occurrences of element in list + **/ + + public final int count(T element) + { + int c = 0; + for (LLCell p = this; p !is null; p = p.next_) + if (p.element() == element) + ++c; + return c; + } + + /** + * return the number of cells in the list + **/ + + public final int _length() + { + int c = 0; + for (LLCell p = this; p !is null; p = p.next_) + ++c; + return c; + } + + /** + * return the cell representing the last element of the list + * (i.e., the one whose next() is null + **/ + + public final LLCell tail() + { + LLCell p = this; + for ( ; p.next_ !is null; p = p.next_) + {} + return p; + } + + /** + * return the nth cell of the list, or null if no such + **/ + + public final LLCell nth(int n) + { + LLCell p = this; + for (int i = 0; i < n; ++i) + p = p.next_; + return p; + } + + + /** + * make a copy of the list; i.e., a new list containing new cells + * but including the same elements in the same order + **/ + + public final LLCell copyList() + { + LLCell newlist = null; + newlist = duplicate(); + LLCell current = newlist; + + for (LLCell p = next_; p !is null; p = p.next_) + { + current.next_ = p.duplicate(); + current = current.next_; + } + current.next_ = null; + return newlist; + } + + /** + * Clone is SHALLOW; i.e., just makes a copy of the current cell + **/ + + private final LLCell duplicate() + { + return new LLCell(element(), next_); + } + + /** + * Basic linkedlist merge algorithm. + * Merges the lists head by fst and snd with respect to cmp + * @param fst head of the first list + * @param snd head of the second list + * @param cmp a Comparator used to compare elements + * Returns: the merged ordered list + **/ + + public final static LLCell merge(LLCell fst, LLCell snd, ComparatorT cmp) + { + LLCell a = fst; + LLCell b = snd; + LLCell hd = null; + LLCell current = null; + for (;;) + { + if (a is null) + { + if (hd is null) + hd = b; + else + current.next(b); + return hd; + } + else + if (b is null) + { + if (hd is null) + hd = a; + else + current.next(a); + return hd; + } + + int diff = cmp.compare(a.element(), b.element()); + if (diff <= 0) + { + if (hd is null) + hd = a; + else + current.next(a); + current = a; + a = a.next(); + } + else + { + if (hd is null) + hd = b; + else + current.next(b); + current = b; + b = b.next(); + } + } + return null; + } + + /** + * Standard list splitter, used by sort. + * Splits the list in half. Returns the head of the second half + * @param s the head of the list + * Returns: the head of the second half + **/ + + public final static LLCell split(LLCell s) + { + LLCell fast = s; + LLCell slow = s; + + if (fast is null || fast.next() is null) + return null; + + while (fast !is null) + { + fast = fast.next(); + if (fast !is null && fast.next() !is null) + { + fast = fast.next(); + slow = slow.next(); + } + } + + LLCell r = slow.next(); + slow.next(null); + return r; + + } + + /** + * Standard merge sort algorithm + * @param s the list to sort + * @param cmp, the comparator to use for ordering + * Returns: the head of the sorted list + **/ + + public final static LLCell mergeSort(LLCell s, ComparatorT cmp) + { + if (s is null || s.next() is null) + return s; + else + { + LLCell right = split(s); + LLCell left = s; + left = mergeSort(left, cmp); + right = mergeSort(right, cmp); + return merge(left, right, cmp); + } + } + +} +