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

        Based upon Doug Lea's Java collection package

        Copyright:
            Copyright (c) 2008 Kris Bell.
            Some parts copyright (c) 2009-2016 dunnhumby Germany GmbH.
            All rights reserved.

        License:
            Tango Dual License: 3-Clause BSD License / Academic Free License v3.0.
            See LICENSE_TANGO.txt for details.

        Version: Apr 2008: Initial release

        Authors: Kris

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

module ocean.util.container.Slink;

import ocean.core.Enforce;

import ocean.meta.types.Qualifiers;
import ocean.meta.types.Typedef;

import ocean.util.container.model.IContainer;

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

        Slink instances provide standard linked list next-fields, and
        support standard operations upon them. Slink structures are pure
        implementation tools, and perform no argument checking, no result
        screening, and no synchronization. They rely on user-level classes
        (see HashSet, for example) to do such things.

        Still, Slink is made `public' so that you can use it to build other
        kinds of containers

        Note that when K is specified, support for keys are enabled. When
        Identity is stipulated as 'true', those keys are compared using an
        identity-comparison instead of equality (using 'is'). Similarly, if
        HashCache is set true, an additional attribute is create in order to
        retain the hash of K

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

private
{
    mixin(Typedef!(int, "KeyDummy"));
}

struct Slink (V, K=KeyDummy, bool Identity = false, bool HashCache = false)
{
        alias Slink!(V, K, Identity, HashCache) Type;
        alias Type                              *Ref;
        alias Compare!(V)                       Comparator;

        Ref             next;           // pointer to next
        V               value;          // element value

        static if (HashCache == true)
        {
        hash_t       cache;             // retain hash value?
        }

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

                add support for keys also?

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

        static if (!is(typeof(K) == KeyDummy))
        {
                K key;

                final Ref set (K k, V v, Ref n)
                {
                        key = k;
                        return set (v, n);
                }

                final hash_t hash()
                {
                        return typeid(K).getHash(&key);
                }

                final Ref findKey (K key)
                {
                        static if (Identity == true)
                        {
                           for (auto p= &this; p; p = p.next)
                                if (key is p.key)
                                    return p;
                        }
                        else
                        {
                           for (auto p= &this; p; p = p.next)
                                if (key == p.key)
                                    return p;
                        }
                        return null;
                }

                final Ref findPair (K key, V value)
                {
                        static if (Identity == true)
                        {
                           for (auto p= &this; p; p = p.next)
                                if (key is p.key && value == p.value)
                                    return p;
                        }
                        else
                        {
                           for (auto p= &this; p; p = p.next)
                                if (key == p.key && value == p.value)
                                    return p;
                        }
                        return null;
                }

                final int indexKey (K key)
                {
                        int i = 0;
                        static if (Identity == true)
                        {
                           for (auto p= &this; p; p = p.next, ++i)
                                if (key is p.key)
                                    return i;
                        }
                        else
                        {
                           for (auto p= &this; p; p = p.next, ++i)
                                if (key == p.key)
                                    return i;
                        }
                        return -1;
                }

                final int indexPair (K key, V value)
                {
                        int i = 0;
                        static if (Identity == true)
                        {
                           for (auto p= &this; p; p = p.next, ++i)
                                if (key is p.key && value == p.value)
                                    return i;
                        }
                        else
                        {
                           for (auto p= &this; p; p = p.next, ++i)
                                if (key == p.key && value == p.value)
                                    return i;
                        }
                        return -1;
                }

                final int countKey (K key)
                {
                        int c = 0;
                        static if (Identity == true)
                        {
                           for (auto p= &this; p; p = p.next)
                                if (key is p.key)
                                    ++c;
                        }
                        else
                        {
                           for (auto p= &this; p; p = p.next)
                                if (key == p.key)
                                    ++c;
                        }
                        return c;
                }

                final int countPair (K key, V value)
                {
                        int c = 0;
                        static if (Identity == true)
                        {
                           for (auto p= &this; p; p = p.next)
                                if (key is p.key && value == p.value)
                                    ++c;
                        }
                        else
                        {
                           for (auto p= &this; p; p = p.next)
                                if (key == p.key && value == p.value)
                                    ++c;
                        }
                        return c;
                }
        }

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

                 Set to point to n as next cell

                 param: n, the new next cell

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

        final Ref set (V v, Ref n)
        {
                next = n;
                value = v;
                return &this;
        }

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

                 Splice in p between current cell and whatever it was
                 previously pointing to

                 param: p, the cell to splice

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

        final void attach (Ref p)
        {
                if (p)
                    p.next = next;
                next = p;
        }

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

                Cause current cell to skip over the current next() one,
                effectively removing the next element from the list

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

        final void detachNext()
        {
                if (next)
                    next = next.next;
        }

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

                 Linear search down the list looking for element

                 param: element to look for
                 Returns: the cell containing element, or null if no such

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

        final Ref find (V element)
        {
                for (auto p = &this; p; p = p.next)
                     if (element == p.value)
                         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

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

        final int index (V element)
        {
                int i;
                for (auto p = &this; p; p = p.next, ++i)
                     if (element == p.value)
                         return i;

                return -1;
        }

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

                Count the number of occurrences of element in list

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

        final int count (V element)
        {
                int c;
                for (auto p = &this; p; p = p.next)
                     if (element == p.value)
                         ++c;
                return c;
        }

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

                 Return the number of cells in the list

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

        final int count ()
        {
                int c;
                for (auto p = &this; p; p = p.next)
                     ++c;
                return c;
        }

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

                Return the cell representing the last element of the list
                (i.e., the one whose next() is null

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

        final Ref tail ()
        {
                auto p = &this;
                while (p.next)
                       p = p.next;
                return p;
        }

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

                Return the nth cell of the list, or null if no such

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

        final Ref nth (long n)
        {
                enforce(n >= 0);

                auto p = &this;
                for (long i; i < n && p; ++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

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

        final Ref copy (scope Ref delegate() alloc)
        {
                auto newlist = dup (alloc);
                auto current = newlist;

                for (auto p = next; p; p = p.next)
                    {
                    current.next = p.dup (alloc);
                    current = current.next;
                    }
                current.next = null;
                return newlist;
        }

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

                dup is shallow; i.e., just makes a copy of the current cell

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

        private Ref dup (scope Ref delegate() alloc)
        {
                auto ret = alloc();
                static if (is(typeof(K) == KeyDummy))
                           ret.set (value, next);
                       else
                          ret.set (key, value, next);
                return ret;
        }

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

                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

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

        static Ref merge (Ref fst, Ref snd, Comparator cmp)
        {
                auto a = fst;
                auto b = snd;
                Ref hd = null;
                Ref 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 (a.value, b.value);
                    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;
                       }
                    }
        }

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

                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

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

        static Ref split (Ref s)
        {
                auto fast = s;
                auto slow = s;

                if (fast is null || fast.next is null)
                    return null;

                while (fast)
                      {
                      fast = fast.next;
                      if (fast && fast.next)
                         {
                         fast = fast.next;
                         slow = slow.next;
                         }
                      }

                auto 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

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

        static Ref sort (Ref s, Comparator cmp)
        {
                if (s is null || s.next is null)
                    return s;
                else
                   {
                   auto right = split (s);
                   auto left = s;
                   left = sort (left, cmp);
                   right = sort (right, cmp);
                   return merge (left, right, cmp);
                   }
        }

}

version (unittest)
{
    import ocean.core.Test : NamedTest;
}

unittest
{
    auto t = new NamedTest("Test nth() with an index out of bounds");

    static immutable total_items = 11;
    static immutable index_out_of_bounds = total_items * 2;

    auto slink = new Slink!(int);
    t.test!("==")(slink.nth(0).value, 0);
    t.test!("==")(slink.count(), 1);

    auto tail = slink;
    for (int i = 1; i < total_items; ++i)
    {
        auto item = new Slink!(int);
        item.value = tail.value + 1;
        tail.set(tail.value, item);
        tail = item;
    }

    // Self-verification
    t.test!("==")(slink.count(), total_items);
    for (int i = 0; i < total_items; ++i)
    {
        t.test!("==")(slink.nth(i).value, i);
    }

    t.test!("==")(slink.nth(total_items), null);
    t.test!("==")(slink.nth(index_out_of_bounds), null);
}