root/trunk/tango/util/container/LinkedList.d

/*******************************************************************************

        copyright:      Copyright (c) 2008 Kris Bell. All rights reserved

        license:        BSD style: $(LICENSE)

        version:        Apr 2008: Initial release

        authors:        Kris

        Since:          0.99.7

        Based upon Doug Lea's Java collection package

*******************************************************************************/

module tango.util.container.LinkedList;

private import  tango.util.container.Slink;

public  import  tango.util.container.Container;

private import tango.util.container.model.IContainer;

/*******************************************************************************

        List of singly-linked values

        ---
    Iterator iterator ()
        int opApply (int delegate(ref V value) dg)

        V head ()
        V tail ()
        V head (V value)
        V tail (V value)
        V removeHead ()
        V removeTail ()

        bool contains (V value)
        uint first (V value, uint startingIndex = 0)
        uint last (V value, uint startingIndex = 0)

        LinkedList add (V value)
        LinkedList prepend (V value)
        uint prepend (IContainer!(V) e)
        LinkedList append (V value)
        uint append (IContainer!(V) e)
        LinkedList addAt (uint index, V value)
        uint addAt (uint index, IContainer!(V) e)

        V get (uint index)
        bool take (ref V v)
        uint remove (V value, bool all)
        bool removeAt (uint index)
        uint removeRange (uint fromIndex, uint toIndex)
        uint replace (V oldElement, V newElement, bool all)
        bool replaceAt (uint index, V value)

        LinkedList clear ()
        LinkedList reset ()

        LinkedList subset (uint from, uint length = int.max)
        LinkedList dup ()

        uint size ()
        bool isEmpty ()
        V[] toArray (V[] dst)
        LinkedList sort (Compare!(V) cmp)
        LinkedList check ()
        ---

*******************************************************************************/

class LinkedList (V, alias Reap = Container.reap, 
                     alias Heap = Container.Collect) 
                     : IContainer!(V)
{
        // use this type for Allocator configuration
        private alias Slink!(V) Type;
        
        private alias Type*     Ref;
        private alias V*        VRef;

        private alias Heap!(Type) Alloc;

        // number of elements contained
        private uint            count;

        // configured heap manager
        private Alloc           heap;
        
        // mutation tag updates on each change
        private uint            mutation;

        // head of the list. Null if empty
        private Ref             list;

        /***********************************************************************

                Create a new empty list

        ***********************************************************************/

        this ()
        {
                this (null, 0);
        }

        /***********************************************************************

                Special version of constructor needed by dup

        ***********************************************************************/

        protected this (Ref l, int c)
        {
                list = l;
                count = c;
        }

        /***********************************************************************

                Clean up when deleted

        ***********************************************************************/

        ~this ()
        {
                reset;
        }

        /***********************************************************************

                Return the configured allocator
                
        ***********************************************************************/

        final Alloc allocator ()
        {
                return heap;
        }

        /***********************************************************************

                Return a generic iterator for contained elements
                
        ***********************************************************************/

        final Iterator iterator ()
        {
                Iterator i = void;
                i.mutation = mutation;
                i.node = list ? *(i.hook = &list) : null;
                i.prior = null;
                i.owner = this;
                return i;
        }

        /***********************************************************************


        ***********************************************************************/

        final int opApply (int delegate(ref V value) dg)
        {
                return iterator.opApply (dg);
        }

        /***********************************************************************

                Return the number of elements contained
                
        ***********************************************************************/

        final uint size ()
        {
                return count;
        }

        /***********************************************************************

                Build an independent copy of the list.
                The elements themselves are not cloned

        ***********************************************************************/

        final LinkedList dup ()
        {
                return new LinkedList!(V, Reap, Heap) (list ? list.copy(&heap.allocate) : null, count);
        }

        /***********************************************************************

                Time complexity: O(n)

        ***********************************************************************/

        final bool contains (V value)
        {
                if (count is 0)
                    return false;

                return list.find(value) !is null;
        }

        /***********************************************************************

                 Time complexity: O(1)

        ***********************************************************************/

        final V head ()
        {
                return firstCell.value;
        }

        /***********************************************************************

                 Time complexity: O(n)

        ***********************************************************************/

        final V tail ()
        {
                return lastCell.value;
        }

        /***********************************************************************

                 Time complexity: O(n)

        ***********************************************************************/

        final V get (uint index)
        {
                return cellAt(index).value;
        }

        /***********************************************************************

                 Time complexity: O(n)

        ***********************************************************************/

        final uint first (V value, uint startingIndex = 0)
        {
                if (list is null || startingIndex >= count)
                    return uint.max;

                if (startingIndex < 0)
                    startingIndex = 0;

                auto p = list.nth (startingIndex);
                if (p)
                   {
                   auto i = p.index (value);
                   if (i >= 0)
                       return i + startingIndex;
                   }
                return uint.max;
        }

        /***********************************************************************

                 Time complexity: O(n)

        ***********************************************************************/

        final uint last (V value, uint startingIndex = 0)
        {
                if (list is null)
                    return uint.max;

                auto i = 0;
                if (startingIndex >= count)
                    startingIndex = count - 1;

                auto index = uint.max;
                auto p = list;
                while (i <= startingIndex && p)
                      {
                      if (p.value == value)
                          index = i;
                      ++i;
                      p = p.next;
                      }
                return index;
        }

        /***********************************************************************

                 Time complexity: O(length)

        ***********************************************************************/

        final LinkedList subset (uint from, uint length = int.max)
        {
                Ref newlist = null;

                if (length > 0)
                   {
                   auto p = cellAt (from);
                   auto current = newlist = heap.allocate.set (p.value, null);
         
                   for (auto i = 1; i < length; ++i)
                        if ((p = p.next) is null)
                             length = i;
                        else
                           {
                           current.attach (heap.allocate.set (p.value, null));
                           current = current.next;
                           }
                   }

                return new LinkedList (newlist, length);
        }

        /***********************************************************************

                 Time complexity: O(n)

        ***********************************************************************/

        final LinkedList clear ()
        {
                return clear (false);
        }

        /***********************************************************************

                Reset the HashMap contents and optionally configure a new
                heap manager. We cannot guarantee to clean up reconfigured 
                allocators, so be sure to invoke reset() before discarding
                this class

                Time complexity: O(n)
                
        ***********************************************************************/

        final LinkedList reset ()
        {
                return clear (true);
        }

        /***********************************************************************
        
                Takes the first value on the list

                Time complexity: O(1)

        ***********************************************************************/

        final bool take (ref V v)
        {
                if (count)
                   {
                   v = head;
                   removeHead;
                   return true;
                   }
                return false;
        }

        /***********************************************************************

                Uses a merge-sort-based algorithm.

                Time complexity: O(n log n)

        ***********************************************************************/

        final LinkedList sort (Compare!(V) cmp)
        {
                if (list)
                   {
                   list = Ref.sort (list, cmp);
                   mutate;
                   }
                return this;
        }

        /***********************************************************************

                Time complexity: O(1)

        ***********************************************************************/

        final LinkedList add (V value)
        {
                return prepend (value);
        }

        /***********************************************************************

                Time complexity: O(1)

        ***********************************************************************/

        final LinkedList prepend (V value)
        {
                list = heap.allocate.set (value, list);
                increment;
                return this;
        }

        /***********************************************************************

                Time complexity: O(n)

        ***********************************************************************/

        final uint remove (V value, bool all = false)
        {
                auto c = count;
                if (c)
                   {
                   auto p = list;
                   auto trail = p;

                   while (p)
                         {
                         auto n = p.next;
                         if (p.value == value)
                            {
                            decrement (p);
                            if (p is list)
                               {
                               list = n;
                               trail = n;
                               }
                            else
                               trail.next = n;

                            if (!all || count is 0)
                                 break;
                            else
                               p = n;
                            }
                         else
                            {
                            trail = p;
                            p = n;
                            }
                         }
                   }
                return c - count;
        }

        /***********************************************************************

                Time complexity: O(n)

        ***********************************************************************/

        final uint replace (V oldElement, V newElement, bool all = false)
        {
                uint c;
                if (count && oldElement != newElement)
                   {
                   auto p = list.find (oldElement);
                   while (p)
                         {
                         ++c;
                         mutate;
                         p.value = newElement;
                         if (!all)
                              break;
                         p = p.find (oldElement);
                         }
                   }
                return c;
        }

        /***********************************************************************

                 Time complexity: O(1)

        ***********************************************************************/

        final V head (V value)
        {
                auto cell = firstCell;
                auto v = cell.value;
                cell.value = value;
                mutate;
                return v;
        }

        /***********************************************************************

                 Time complexity: O(1)

        ***********************************************************************/

        final V removeHead ()
        {
                auto p = firstCell;
                auto v = p.value;
                list = p.next;
                decrement (p);
                return v;
        }

        /***********************************************************************

                 Time complexity: O(n)

        ***********************************************************************/

        final LinkedList append (V value)
        {
                if (list is null)
                    prepend (value);
                else
                   {
                   list.tail.next = heap.allocate.set (value, null);
                   increment;
                   }
                return this;
        }

        /***********************************************************************

                 Time complexity: O(n)

        ***********************************************************************/

        final V tail (V value)
        {
                auto p = lastCell;
                auto v = p.value;
                p.value = value;
                mutate;
                return v;
        }

        /***********************************************************************

                 Time complexity: O(n)

        ***********************************************************************/

        final V removeTail ()
        {
                if (firstCell.next is null)
                    return removeHead;

                auto trail = list;
                auto p = trail.next;

                while (p.next)
                      {
                      trail = p;
                      p = p.next;
                      }
                trail.next = null;
                auto v = p.value;
                decrement (p);
                return v;
        }

        /***********************************************************************

                Time complexity: O(n)

        ***********************************************************************/

        final LinkedList addAt (uint index, V value)
        {
                if (index is 0)
                    prepend (value);
                else
                   {
                   cellAt(index - 1).attach (heap.allocate.set(value, null));
                   increment;
                   }
                return this;
        }

        /***********************************************************************

                 Time complexity: O(n)

        ***********************************************************************/

        final LinkedList removeAt (uint index)
        {
                if (index is 0)
                    removeHead;
                else
                   {
                   auto p = cellAt (index - 1);
                   auto t = p.next;
                   p.detachNext;
                   decrement (t);
                   }
                return this;
        }

        /***********************************************************************

                 Time complexity: O(n)

        ***********************************************************************/

        final LinkedList replaceAt (uint index, V value)
        {
                cellAt(index).value = value;
                mutate;
                return this;
        }

        /***********************************************************************

                 Time complexity: O(number of elements in e)

        ***********************************************************************/

        final uint prepend (IContainer!(V) e)
        {
                auto c = count;
                splice_ (e, null, list);
                return count - c;
        }

        /***********************************************************************

                 Time complexity: O(n + number of elements in e)

        ***********************************************************************/

        final uint append (IContainer!(V) e)
        {
                auto c = count;
                if (list is null)
                    splice_ (e, null, null);
                else
                   splice_ (e, list.tail, null);
                return count - c;
        }

        /***********************************************************************

                Time complexity: O(n + number of elements in e)

        ***********************************************************************/

        final uint addAt (uint index, IContainer!(V) e)
        {
                auto c = count;
                if (index is 0)
                    splice_ (e, null, list);
                else
                   {
                   auto p = cellAt (index - 1);
                   splice_ (e, p, p.next);
                   }
                return count - c;
        }

        /***********************************************************************

                Time complexity: O(n)

        ***********************************************************************/

        final uint removeRange (uint fromIndex, uint toIndex)
        {
                auto c = count;
                if (fromIndex <= toIndex)
                   {
                   if (fromIndex is 0)
                      {
                      auto p = firstCell;
                      for (int i = fromIndex; i <= toIndex; ++i)
                           p = p.next;
                      list = p;
                      }
                   else
                      {
                      auto f = cellAt (fromIndex - 1);
                      auto p = f;
                      for (int i = fromIndex; i <= toIndex; ++i)
                           p = p.next;
                      f.next = p.next;
                      }

                  count -= (toIndex - fromIndex + 1);
                  mutate;
                  }
                return c - count;
        }

        /***********************************************************************

                Copy and return the contained set of values in an array, 
                using the optional dst as a recipient (which is resized 
                as necessary).

                Returns a slice of dst representing the container values.
                
                Time complexity: O(n)
                
        ***********************************************************************/

        final V[] toArray (V[] dst = null)
        {
                if (dst.length < count)
                    dst.length = count;

                int i = 0;
&nbs