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

        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.Clink;

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

    Clinks are links that are always arranged in circular lists.

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

struct Clink (V)
{
    alias Clink!(V)    Type;
    alias Type         *Ref;

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

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

        Set to point to ourselves

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

    Ref set (V v)
    {
            return set (v, &this, &this);
    }

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

        Set to point to n as next cell and p as the prior cell

        param: n, the new next cell
        param: p, the new prior cell

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

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

    /**
     * Return true if current cell is the only one on the list
    **/

    bool singleton()
    {
            return next is &this;
    }

    void linkNext (Ref p)
    {
            if (p)
               {
               next.prev = p;
               p.next = next;
               p.prev = &this;
               next = p;
               }
    }

    /**
     * Make a cell holding v and link it immediately after current cell
    **/

    void addNext (V v, scope Ref delegate() alloc)
    {
            auto p = alloc().set (v, &this, next);
            next.prev = p;
            next = p;
    }

    /**
     * make a node holding v, link it before the current cell, and return it
    **/

    Ref addPrev (V v, scope Ref delegate() alloc)
    {
            auto p = prev;
            auto c = alloc().set (v, p, &this);
            p.next = c;
            prev = c;
            return c;
    }

    /**
     * link p before current cell
    **/

    void linkPrev (Ref p)
    {
            if (p)
               {
               prev.next = p;
               p.prev = prev;
               p.next = &this;
               prev = p;
               }
    }

    /**
     * return the number of cells in the list
    **/

    int size()
    {
            int c = 0;
            auto p = &this;
            do {
               ++c;
               p = p.next;
               } while (p !is &this);
            return c;
    }

    /**
     * return the first cell holding element found in a circular traversal starting
     * at current cell, or null if no such
    **/

    Ref find (V element)
    {
            auto p = &this;
            do {
               if (element == p.value)
                   return p;
               p = p.next;
               } while (p !is &this);
            return null;
    }

    /**
     * return the number of cells holding element found in a circular
     * traversal
    **/

    int count (V element)
    {
            int c = 0;
            auto p = &this;
            do {
               if (element == p.value)
                   ++c;
               p = p.next;
               } while (p !is &this);
            return c;
    }

    /**
     * return the nth cell traversed from here. It may wrap around.
    **/

    Ref nth (size_t n)
    {
            auto p = &this;
            for (ptrdiff_t i = 0; i < n; ++i)
                 p = p.next;
            return p;
    }


    /**
     * Unlink the next cell.
     * This has no effect on the list if isSingleton()
    **/

    void unlinkNext ()
    {
            auto nn = next.next;
            nn.prev = &this;
            next = nn;
    }

    /**
     * Unlink the previous cell.
     * This has no effect on the list if isSingleton()
    **/

    void unlinkPrev ()
    {
            auto pp = prev.prev;
            pp.next = &this;
            prev = pp;
    }


    /**
     * Unlink self from list it is in.
     * Causes it to be a singleton
    **/

    void unlink ()
    {
            auto p = prev;
            auto n = next;
            p.next = n;
            n.prev = p;
            prev = &this;
            next = &this;
    }

    /**
     * Make a copy of the list and return new head.
    **/

    Ref copyList (scope Ref delegate() alloc)
    {
            auto hd = &this;

            auto newlist = alloc().set (hd.value, null, null);
            auto current = newlist;

            for (auto p = next; p !is hd; p = p.next)
                 {
                 current.next = alloc().set (p.value, current, null);
                 current = current.next;
                 }
            newlist.prev = current;
            current.next = newlist;
            return newlist;
    }
}