OoasTools

/*

 Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft

 Permission is hereby granted, free of charge, to any person obtaining a copy

 of this software and associated documentation files (the "Software"), to deal

 in the Software without restriction, including without limitation the rights

 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

 copies of the Software, and to permit persons to whom the Software is

 furnished to do so, subject to the following conditions:

 The above copyright notice and this permission notice shall be included in

 all copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

 SOFTWARE.

*/

#define HASHINDEXnot

using System;

using System.Diagnostics;

using SCG = System.Collections.Generic;

namespace C5

{

  /// <summary>

  /// A list collection class based on a doubly linked list data structure.

  /// </summary>

  [Serializable]

  public class LinkedList<T> : SequencedBase<T>, IList<T>, SCG.IList<T>

#if HASHINDEX

#else

, IStack<T>, IQueue<T>

#endif

  {

    #region Fields

    /// <summary>

    /// IExtensible.Add(T) always does AddLast(T), fIFO determines 

    /// if T Remove() does RemoveFirst() or RemoveLast()

    /// </summary>

    bool fIFO = true;

    #region Events

    /// <summary>

    /// 

    /// </summary>

    /// <value></value>

    public override EventTypeEnum ListenableEvents { get { return underlying == null ? EventTypeEnum.All : EventTypeEnum.None; } }

    #endregion

    //Invariant:  startsentinel != null && endsentinel != null

    //If size==0: startsentinel.next == endsentinel && endsentinel.prev == startsentinel

    //Else:      startsentinel.next == First && endsentinel.prev == Last)

    /// <summary>

    /// Node to the left of first node 

    /// </summary>

    Node startsentinel;

    /// <summary>

    /// Node to the right of last node

    /// </summary>

    Node endsentinel;

    /// <summary>

    /// Offset of this view in underlying list

    /// </summary>

#if HASHINDEX

    int? offset;

#else

    int offset;

#endif

    /// <summary>

    /// underlying list of this view (or null for the underlying list)

    /// </summary>

    LinkedList<T> underlying;

    //Note: all views will have the same views list since all view objects are created by MemberwiseClone()

    WeakViewList<LinkedList<T>> views;

    WeakViewList<LinkedList<T>>.Node myWeakReference;

    /// <summary>

    /// Has this list or view not been invalidated by some operation (by someone calling Dispose())

    /// </summary>

    bool isValid = true;

#if HASHINDEX

    HashDictionary<T, Node> dict;

    /// <summary>

    /// Number of taggroups

    /// </summary>

    int taggroups;

    /// <summary>

    /// 

    /// </summary>

    /// <value></value>

    int Taggroups

    {

      get { return underlying == null ? taggroups : underlying.taggroups; }

      set { if (underlying == null) taggroups = value; else underlying.taggroups = value; }

    }

#endif

    #endregion

    #region Util

    bool equals(T i1, T i2) { return itemequalityComparer.Equals(i1, i2); }

    #region Check utilities

    /// <summary>

    /// Check if it is valid to perform updates and increment stamp of 

    /// underlying if this is a view.

    /// <para>This method should be called in every public modifying 

    /// methods before any modifications are performed.

    /// </para>

    /// </summary>

    /// <exception cref="InvalidOperationException"> if check fails.</exception>

    protected override void updatecheck()

    {

      validitycheck();

      base.updatecheck();

      if (underlying != null)

        underlying.stamp++;

    }

    /// <summary>

    /// Check if we are a view that the underlyinglist has only been updated through us.

    /// <br/>

    /// This method should be called from enumerators etc to guard against 

    /// modification of the base collection.

    /// </summary>

    /// <exception cref="InvalidOperationException"> if check fails.</exception>

    void validitycheck()

    {

      if (!isValid)

        throw new ViewDisposedException();

    }

    /// <summary>

    /// Check that the list has not been updated since a particular time.

    /// </summary>

    /// <param name="stamp">The stamp indicating the time.</param>

    /// <exception cref="CollectionModifiedException"> if check fails.</exception>

    protected override void modifycheck(int stamp)

    {

      validitycheck();

      if ((underlying != null ? underlying.stamp : this.stamp) != stamp)

        throw new CollectionModifiedException();

    }

    #endregion

    #region Searching

    bool contains(T item, out Node node)

    {

#if HASHINDEX

      if (dict.Find(item, out node))

        return insideview(node);

#else

      //TODO: search from both ends? Or search from the end selected by FIFO?

      node = startsentinel.next;

      while (node != endsentinel)

      {

        if (equals(item, node.item))

          return true;

        node = node.next;

      }

#endif

      return false;

    }

    /// <summary>

    /// Search forwards from a node for a node with a particular item.

    /// </summary>

    /// <param name="item">The item to look for</param>

    /// <param name="node">On input, the node to start at. If item was found, the node found on output.</param>

    /// <param name="index">If node was found, the value will be the number of links followed higher than 

    /// the value on input. If item was not found, the value on output is undefined.</param>

    /// <returns>True if node was found.</returns>

    bool find(T item, ref Node node, ref int index)

    {

      while (node != endsentinel)

      {

        //if (item.Equals(node.item))

        if (itemequalityComparer.Equals(item, node.item))

          return true;

        index++;

        node = node.next;

      }

      return false;

    }

    bool dnif(T item, ref Node node, ref int index)

    {

      while (node != startsentinel)

      {

        //if (item.Equals(node.item))

        if (itemequalityComparer.Equals(item, node.item))

          return true;

        index--;

        node = node.prev;

      }

      return false;

    }

#if HASHINDEX

    bool insideview(Node node)

    {

      if (underlying == null)

        return true;

      return (startsentinel.precedes(node) && node.precedes(endsentinel));

    }

#endif

    #endregion

    #region Indexing

    /// <summary>

    /// Return the node at position pos

    /// </summary>

    /// <param name="pos"></param>

    /// <returns></returns>

    Node get(int pos)

    {

      if (pos < 0 || pos >= size)

        throw new IndexOutOfRangeException();

      else if (pos < size / 2)

      {              // Closer to front

        Node node = startsentinel;

        for (int i = 0; i <= pos; i++)

          node = node.next;

        return node;

      }

      else

      {                            // Closer to end

        Node node = endsentinel;

        for (int i = size; i > pos; i--)

          node = node.prev;

        return node;

      }

    }

    /// <summary>

    /// Find the distance from pos to the set given by positions. Return the

    /// signed distance as return value and as an out parameter, the

    /// array index of the nearest position. This is used for up to length 5 of

    /// positions, and we do not assume it is sorted. 

    /// </summary>

    /// <param name="pos"></param>

    /// <param name="positions"></param>

    /// <param name="nearest"></param>

    /// <returns></returns>

    int dist(int pos, out int nearest, int[] positions)

    {

      nearest = -1;

      int bestdist = int.MaxValue;

      int signeddist = bestdist;

      for (int i = 0; i < positions.Length; i++)

      {

        int thisdist = positions[i] - pos;

        if (thisdist >= 0 && thisdist < bestdist) { nearest = i; bestdist = thisdist; signeddist = thisdist; }

        if (thisdist < 0 && -thisdist < bestdist) { nearest = i; bestdist = -thisdist; signeddist = thisdist; }

      }

      return signeddist;

    }

    /// <summary>

    /// Find the node at position pos, given known positions of several nodes.

    /// </summary>

    /// <param name="pos"></param>

    /// <param name="positions"></param>

    /// <param name="nodes"></param>

    /// <returns></returns>

    Node get(int pos, int[] positions, Node[] nodes)

    {

      int nearest;

      int delta = dist(pos, out nearest, positions);

      Node node = nodes[nearest];

      if (delta > 0)

        for (int i = 0; i < delta; i++)

          node = node.prev;

      else

        for (int i = 0; i > delta; i--)

          node = node.next;

      return node;

    }

    /// <summary>

    /// Get nodes at positions p1 and p2, given nodes at several positions.

    /// </summary>

    /// <param name="p1"></param>

    /// <param name="p2"></param>

    /// <param name="n1"></param>

    /// <param name="n2"></param>

    /// <param name="positions"></param>

    /// <param name="nodes"></param>

    void getPair(int p1, int p2, out Node n1, out Node n2, int[] positions, Node[] nodes)

    {

      int nearest1, nearest2;

      int delta1 = dist(p1, out nearest1, positions), d1 = delta1 < 0 ? -delta1 : delta1;

      int delta2 = dist(p2, out nearest2, positions), d2 = delta2 < 0 ? -delta2 : delta2;

      if (d1 < d2)

      {

        n1 = get(p1, positions, nodes);

        n2 = get(p2, new int[] { positions[nearest2], p1 }, new Node[] { nodes[nearest2], n1 });

      }

      else

      {

        n2 = get(p2, positions, nodes);

        n1 = get(p1, new int[] { positions[nearest1], p2 }, new Node[] { nodes[nearest1], n2 });

      }

    }

    #endregion

    #region Insertion

#if HASHINDEX

    void insert(int index, Node succ, T item)

    {

      Node newnode = new Node(item);

      if (dict.FindOrAdd(item, ref newnode))

        throw new DuplicateNotAllowedException("Item already in indexed list");

      insertNode(true, succ, newnode);

    }

    /// <summary>

    /// Insert a Node before another one. Unchecked version. 

    /// </summary>

    /// <param name="succ">The successor to be</param>

    /// <param name="newnode">Node to insert</param>

    /// <param name="updateViews">update overlapping view in this call</param>

    void insertNode(bool updateViews, Node succ, Node newnode)

    {

      newnode.next = succ;

      Node pred = newnode.prev = succ.prev;

      succ.prev.next = newnode;

      succ.prev = newnode;

      size++;

      if (underlying != null)

        underlying.size++;

      settag(newnode);

      if (updateViews)

        fixViewsAfterInsert(succ, pred, 1, 0);

    }

#else

    /// <summary>

    /// 

    /// </summary>

    /// <param name="index">The index in this view</param>

    /// <param name="succ"></param>

    /// <param name="item"></param>

    /// <returns></returns>

    Node insert(int index, Node succ, T item)

    {

      Node newnode = new Node(item, succ.prev, succ);

      succ.prev.next = newnode;

      succ.prev = newnode;

      size++;

      if (underlying != null)

        underlying.size++;

      fixViewsAfterInsert(succ, newnode.prev, 1, Offset + index);

      return newnode;

    }

#endif

    #endregion

    #region Removal

    T remove(Node node, int index)

    {

      fixViewsBeforeSingleRemove(node, Offset + index);

      node.prev.next = node.next;

      node.next.prev = node.prev;

      size--;

      if (underlying != null)

        underlying.size--;

#if HASHINDEX

      removefromtaggroup(node);

#endif

      return node.item;

    }

#if HASHINDEX

    private bool dictremove(T item, out Node node)

    {

      if (underlying == null)

      {

        if (!dict.Remove(item, out node))

          return false;

      }

      else

      {

        //We cannot avoid calling dict twice - have to intersperse the listorder test!

        if (!contains(item, out node))

          return false;

        dict.Remove(item);

      }

      return true;

    }

#endif

    #endregion

    #region fixView utilities

    /// <summary>

    /// 

    /// </summary>

    /// <param name="added">The actual number of inserted nodes</param>

    /// <param name="pred">The predecessor of the inserted nodes</param>

    /// <param name="succ">The successor of the added nodes</param>

    /// <param name="realInsertionIndex"></param>

    void fixViewsAfterInsert(Node succ, Node pred, int added, int realInsertionIndex)

    {

      if (views != null)

        foreach (LinkedList<T> view in views)

        {

          if (view != this)

          {

#if HASHINDEX

            if (pred.precedes(view.startsentinel) || (view.startsentinel == pred && view.size > 0))

              view.offset += added;

            if (view.startsentinel.precedes(pred) && succ.precedes(view.endsentinel))

              view.size += added;

            if (view.startsentinel == pred && view.size > 0)

              view.startsentinel = succ.prev;

            if (view.endsentinel == succ)

              view.endsentinel = pred.next;

#else

            if (view.Offset == realInsertionIndex && view.size > 0)

              view.startsentinel = succ.prev;

            if (view.Offset + view.size == realInsertionIndex)

              view.endsentinel = pred.next;

            if (view.Offset < realInsertionIndex && view.Offset + view.size > realInsertionIndex)

              view.size += added;

            if (view.Offset > realInsertionIndex || (view.Offset == realInsertionIndex && view.size > 0))

              view.offset += added;

#endif

          }

        }

    }

    void fixViewsBeforeSingleRemove(Node node, int realRemovalIndex)

    {

      if (views != null)

        foreach (LinkedList<T> view in views)

        {

          if (view != this)

          {

#if HASHINDEX

            if (view.startsentinel.precedes(node) && node.precedes(view.endsentinel))

              view.size--;

            if (!view.startsentinel.precedes(node))

              view.offset--;

            if (view.startsentinel == node)

              view.startsentinel = node.prev;

            if (view.endsentinel == node)

              view.endsentinel = node.next;

#else

            if (view.offset - 1 == realRemovalIndex)

              view.startsentinel = node.prev;

            if (view.offset + view.size == realRemovalIndex)

              view.endsentinel = node.next;

            if (view.offset <= realRemovalIndex && view.offset + view.size > realRemovalIndex)

              view.size--;

            if (view.offset > realRemovalIndex)

              view.offset--;

#endif

          }

        }

    }

#if HASHINDEX

#else

    void fixViewsBeforeRemove(int start, int count, Node first, Node last)

    {

      int clearend = start + count - 1;

      if (views != null)

        foreach (LinkedList<T> view in views)

        {

          if (view == this)

            continue;

          int viewoffset = view.Offset, viewend = viewoffset + view.size - 1;

          //sentinels

          if (start < viewoffset && viewoffset - 1 <= clearend)

            view.startsentinel = first.prev;

          if (start <= viewend + 1 && viewend < clearend)

            view.endsentinel = last.next;

          //offsets and sizes

          if (start < viewoffset)

          {

            if (clearend < viewoffset)

              view.offset = viewoffset - count;

            else

            {

              view.offset = start;

              view.size = clearend < viewend ? viewend - clearend : 0;

            }

          }

          else if (start <= viewend)

            view.size = clearend <= viewend ? view.size - count : start - viewoffset;

        }

    }

#endif

    /// <summary>

    /// 

    /// </summary>

    /// <param name="otherView"></param>

    /// <returns>The position of View(otherOffset, otherSize) wrt. this view</returns>

    MutualViewPosition viewPosition(LinkedList<T> otherView)

    {

#if HASHINDEX

      Node otherstartsentinel = otherView.startsentinel, otherendsentinel = otherView.endsentinel,

        first = startsentinel.next, last = endsentinel.prev,

        otherfirst = otherstartsentinel.next, otherlast = otherendsentinel.prev;

      if (last.precedes(otherfirst) || otherlast.precedes(first))

        return MutualViewPosition.NonOverlapping;

      if (size == 0 || (otherstartsentinel.precedes(first) && last.precedes(otherendsentinel)))

        return MutualViewPosition.Contains;

      if (otherView.size == 0 || (startsentinel.precedes(otherfirst) && otherlast.precedes(endsentinel)))

        return MutualViewPosition.ContainedIn;

      return MutualViewPosition.Overlapping;

#else

      int end = offset + size, otherOffset = otherView.offset, otherSize = otherView.size, otherEnd = otherOffset + otherSize;

      if (otherOffset >= end || otherEnd <= offset)

        return MutualViewPosition.NonOverlapping;

      if (size == 0 || (otherOffset <= offset && end <= otherEnd))

        return MutualViewPosition.Contains;

      if (otherSize == 0 || (offset <= otherOffset && otherEnd <= end))

        return MutualViewPosition.ContainedIn;

      return MutualViewPosition.Overlapping;

#endif

    }

    void disposeOverlappingViews(bool reverse)

    {

      if (views != null)

      {

        foreach (LinkedList<T> view in views)

        {

          if (view != this)

          {

            switch (viewPosition(view))

            {

              case MutualViewPosition.ContainedIn:

                if (reverse)

                { }

                else

                  view.Dispose();

                break;

              case MutualViewPosition.Overlapping:

                view.Dispose();

                break;

              case MutualViewPosition.Contains:

              case MutualViewPosition.NonOverlapping:

                break;

            }

          }

        }

      }

    }

    #endregion

    #endregion

    #region Constructors

    /// <summary>

    /// Create a linked list with en external item equalityComparer

    /// </summary>

    /// <param name="itemequalityComparer">The external equalityComparer</param>

    public LinkedList(SCG.IEqualityComparer<T> itemequalityComparer)

      : base(itemequalityComparer)

    {

      offset = 0;

      size = stamp = 0;

      startsentinel = new Node(default(T));

      endsentinel = new Node(default(T));

      startsentinel.next = endsentinel;

      endsentinel.prev = startsentinel;

#if HASHINDEX

      //It is important that the sentinels are different:

      startsentinel.taggroup = new TagGroup();

      startsentinel.taggroup.tag = int.MinValue;

      startsentinel.taggroup.count = 0;

      endsentinel.taggroup = new TagGroup();

      endsentinel.taggroup.tag = int.MaxValue;

      endsentinel.taggroup.count = 0;

      dict = new HashDictionary<T, Node>(itemequalityComparer);

#endif

    }

    /// <summary>

    /// Create a linked list with the natural item equalityComparer

    /// </summary>

    public LinkedList() : this(EqualityComparer<T>.Default) { }

    #endregion

    #region Node nested class

    /// <summary>

    /// An individual cell in the linked list

    /// </summary>

    [Serializable]

    class Node

    {

      public Node prev;

      public Node next;

      public T item;

      #region Tag support

#if HASHINDEX

      internal int tag;

      internal TagGroup taggroup;

      internal bool precedes(Node that)

      {

        //Debug.Assert(taggroup != null, "taggroup field null");

        //Debug.Assert(that.taggroup != null, "that.taggroup field null");

        int t1 = taggroup.tag;

        int t2 = that.taggroup.tag;

        return t1 < t2 ? true : t1 > t2 ? false : tag < that.tag;

      }

#endif

      #endregion

      [Tested]

      internal Node(T item) { this.item = item; }

      [Tested]

      internal Node(T item, Node prev, Node next)

      {

        this.item = item; this.prev = prev; this.next = next;

      }

      public override string ToString()

      {

#if HASHINDEX

        return String.Format("Node: (item={0}, tag={1})", item, tag);

#else

        return String.Format("Node(item={0})", item);

#endif

      }

    }

    #endregion

    #region Taggroup nested class and tag maintenance utilities

#if HASHINDEX

    /// <summary>

    /// A group of nodes with the same high tag. Purpose is to be

    /// able to tell the sequence order of two nodes without having to scan through

    /// the list.

    /// </summary>

    [Serializable]

    class TagGroup

    {

      internal int tag, count;

      internal Node first, last;

      /// <summary>

      /// Pretty print a tag group

      /// </summary>

      /// <returns>Formatted tag group</returns>

      public override string ToString()

      { return String.Format("TagGroup(tag={0}, cnt={1}, fst={2}, lst={3})", tag, count, first, last); }

    }

    //Constants for tag maintenance

    const int wordsize = 32;

    const int lobits = 3;

    const int hibits = lobits + 1;

    const int losize = 1 << lobits;

    const int hisize = 1 << hibits;

    const int logwordsize = 5;

    TagGroup gettaggroup(Node pred, Node succ, out int lowbound, out int highbound)

    {

      TagGroup predgroup = pred.taggroup, succgroup = succ.taggroup;

      if (predgroup == succgroup)

      {

        lowbound = pred.tag + 1;

        highbound = succ.tag - 1;

        return predgroup;

      }

      else if (predgroup.first != null)

      {

        lowbound = pred.tag + 1;

        highbound = int.MaxValue;

        return predgroup;

      }

      else if (succgroup.first != null)

      {

        lowbound = int.MinValue;

        highbound = succ.tag - 1;

        return succgroup;

      }

      else

      {

        lowbound = int.MinValue;

        highbound = int.MaxValue;

        return new TagGroup();

      }

    }

    /// <summary>

    /// Put a tag on a node (already inserted in the list). Split taggroups and renumber as 

    /// necessary.

    /// </summary>

    /// <param name="node">The node to tag</param>

    void settag(Node node)

    {

      Node pred = node.prev, succ = node.next;

      TagGroup predgroup = pred.taggroup, succgroup = succ.taggroup;

      if (predgroup == succgroup)

      {

        node.taggroup = predgroup;

        predgroup.count++;

        if (pred.tag + 1 == succ.tag)

          splittaggroup(predgroup);

        else

          node.tag = (pred.tag + 1) / 2 + (succ.tag - 1) / 2;

      }

      else if (predgroup.first != null)

      {

        node.taggroup = predgroup;

        predgroup.last = node;

        predgroup.count++;

        if (pred.tag == int.MaxValue)

          splittaggroup(predgroup);

        else

          node.tag = pred.tag / 2 + int.MaxValue / 2 + 1;

      }

      else if (succgroup.first != null)

      {

        node.taggroup = succgroup;

        succgroup.first = node;

        succgroup.count++;

        if (succ.tag == int.MinValue)

          splittaggroup(node.taggroup);

        else

          node.tag = int.MinValue / 2 + (succ.tag - 1) / 2;

      }

      else

      {

        Debug.Assert(Taggroups == 0);

        TagGroup newgroup = new TagGroup();

        Taggroups = 1;

        node.taggroup = newgroup;

        newgroup.first = newgroup.last = node;

        newgroup.count = 1;

        return;

      }

    }

    /// <summary>

    /// Remove a node from its taggroup.

    /// <br/> When this is called, node must already have been removed from the underlying list

    /// </summary>

    /// <param name="node">The node to remove</param>

    void removefromtaggroup(Node node)

    {

      TagGroup taggroup = node.taggroup;

      if (--taggroup.count == 0)

      {

        Taggroups--;

        return;

      }

      if (node == taggroup.first)

        taggroup.first = node.next;

      if (node == taggroup.last)

        taggroup.last = node.prev;

      //node.taggroup = null;

      if (taggroup.count != losize || Taggroups == 1)

        return;

      TagGroup otg;

      // bug20070911:

      Node neighbor;

      if ((neighbor = taggroup.first.prev) != startsentinel

          && (otg = neighbor.taggroup).count <= losize)

        taggroup.first = otg.first;

      else if ((neighbor = taggroup.last.next) != endsentinel 

               && (otg = neighbor.taggroup).count <= losize)

        taggroup.last = otg.last;

      else

        return;

      Node n = otg.first;

      for (int i = 0, length = otg.count; i < length; i++)

      {

        n.taggroup = taggroup;

        n = n.next;

      }

      taggroup.count += otg.count;

      Taggroups--;

      n = taggroup.first;

      const int ofs = wordsize - hibits;

      for (int i = 0, count = taggroup.count; i < count; i++)

      {

        n.tag = (i - losize) << ofs; //(i-8)<<28 

        n = n.next;

      }

    }

    /// <summary>

    /// Split a tag group to make rom for more tags.

    /// </summary>

    /// <param name="taggroup">The tag group</param>

    void splittaggroup(TagGroup taggroup)

    {

      Node n = taggroup.first;

      int ptgt = taggroup.first.prev.taggroup.tag;

      int ntgt = taggroup.last.next.taggroup.tag;

      Debug.Assert(ptgt + 1 <= ntgt - 1);

      int ofs = wordsize - hibits;

      int newtgs = (taggroup.count - 1) / hisize;

      int tgtdelta = (int)((ntgt + 0.0 - ptgt) / (newtgs + 2)), tgtag = ptgt;

      tgtdelta = tgtdelta == 0 ? 1 : tgtdelta;

      for (int j = 0; j < newtgs; j++)

      {

        TagGroup newtaggroup = new TagGroup();

        newtaggroup.tag = (tgtag = tgtag >= ntgt - tgtdelta ? ntgt : tgtag + tgtdelta);

        newtaggroup.first = n;

        newtaggroup.count = hisize;

        for (int i = 0; i < hisize; i++)

        {

          n.taggroup = newtaggroup;

          n.tag = (i - losize) << ofs; //(i-8)<<28 

          n = n.next;

        }

        newtaggroup.last = n.prev;

      }

      int rest = taggroup.count - hisize * newtgs;

      taggroup.first = n;

      taggroup.count = rest;

      taggroup.tag = (tgtag = tgtag >= ntgt - tgtdelta ? ntgt : tgtag + tgtdelta); ofs--;

      for (int i = 0; i < rest; i++)

      {

        n.tag = (i - hisize) << ofs; //(i-16)<<27 

        n = n.next;

      }

      taggroup.last = n.prev;

      Taggroups += newtgs;

      if (tgtag == ntgt)

        redistributetaggroups(taggroup);

    }

    private void redistributetaggroups(TagGroup taggroup)

    {

      TagGroup pred = taggroup, succ = taggroup, tmp;

      double limit = 1, bigt = Math.Pow(Taggroups, 1.0 / 30);//?????

      int bits = 1, count = 1, lowmask = 0, himask = 0, target = 0;

      do

      {

        bits++;

        lowmask = (1 << bits) - 1;

        himask = ~lowmask;

        target = taggroup.tag & himask;

        while ((tmp = pred.first.prev.taggroup).first != null && (tmp.tag & himask) == target)

        { count++; pred = tmp; }

        while ((tmp = succ.last.next.taggroup).last != null && (tmp.tag & himask) == target)

        { count++; succ = tmp; }

        limit *= bigt;

      } while (count > limit);

      //redistibute tags

      int lob = pred.first.prev.taggroup.tag, upb = succ.last.next.taggroup.tag;

      int delta = upb / (count + 1) - lob / (count + 1);

      Debug.Assert(delta > 0);

      for (int i = 0; i < count; i++)

      {

        pred.tag = lob + (i + 1) * delta;

        pred = pred.last.next.taggroup;

      }

    }

#endif

    #endregion

    #region Position, PositionComparer and ViewHandler nested types

    class PositionComparer : SCG.IComparer<Position>

    {

      static PositionComparer _default;

      PositionComparer() { }

      public static PositionComparer Default { get { return _default ?? (_default = new PositionComparer()); } }

      public int Compare(Position a, Position b)

      {

#if HASHINDEX

        return a.Endpoint == b.Endpoint ? 0 : a.Endpoint.precedes(b.Endpoint) ? -1 : 1;

#else

        return a.Index.CompareTo(b.Index);

#endif

      }

    }

    /// <summary>

    /// During RemoveAll, we need to cache the original endpoint indices of views

    /// </summary>

    struct Position

    {

      public readonly LinkedList<T> View;

      public bool Left;

#if HASHINDEX

      public readonly Node Endpoint;

#else

      public readonly int Index;

#endif

      public Position(LinkedList<T> view, bool left)

      {

        View = view;

        Left = left;

#if HASHINDEX

        Endpoint = left ? view.startsentinel.next : view.endsentinel.prev;

#else

        Index = left ? view.Offset : view.Offset + view.size - 1;

#endif

      }

#if HASHINDEX

      public Position(Node node, int foo) { this.Endpoint = node; View = null; Left = false; }

#else

      public Position(int index) { this.Index = index; View = null; Left = false; }

#endif

    }

    //TODO: merge the two implementations using Position values as arguments

    /// <summary>

    /// Handle the update of (other) views during a multi-remove operation.

    /// </summary>

    struct ViewHandler

    {

      ArrayList<Position> leftEnds;

      ArrayList<Position> rightEnds;

      int leftEndIndex, rightEndIndex, leftEndIndex2, rightEndIndex2;

      internal readonly int viewCount;

      internal ViewHandler(LinkedList<T> list)

      {

        leftEndIndex = rightEndIndex = leftEndIndex2 = rightEndIndex2 = viewCount = 0;

        leftEnds = rightEnds = null;

        if (list.views != null)

          foreach (LinkedList<T> v in list.views)

            if (v != list)

            {

              if (leftEnds == null)

              {

                leftEnds = new ArrayList<Position>();

                rightEnds = new ArrayList<Position>();

              }

              leftEnds.Add(new Position(v, true));

              rightEnds.Add(new Position(v, false));

            }

        if (leftEnds == null)

          return;

        viewCount = leftEnds.Count;

        leftEnds.Sort(PositionComparer.Default);

        rightEnds.Sort(PositionComparer.Default);

      }

#if HASHINDEX

      internal void skipEndpoints(int removed, Node n)

      {

        if (viewCount > 0)

        {

          Position endpoint;

          while (leftEndIndex < viewCount && ((endpoint = leftEnds[leftEndIndex]).Endpoint.prev.precedes(n)))

          {

            LinkedList<T> view = endpoint.View;

            view.offset = view.offset - removed;//TODO: extract offset.Value?

            view.size += removed;

            leftEndIndex++;

          }

          while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Endpoint.precedes(n))

          {

            LinkedList<T> view = endpoint.View;

            view.size -= removed;

            rightEndIndex++;

          }

        }

        if (viewCount > 0)

        {

          Position endpoint;

          while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Endpoint.prev.precedes(n))

            leftEndIndex2++;

          while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Endpoint.next.precedes(n))

            rightEndIndex2++;

        }

      }

      /// <summary>

      /// To be called with n pointing to the right of each node to be removed in a stretch. 

      /// And at the endsentinel. 

      /// 

      /// Update offset of a view whose left endpoint (has not already been handled and) is n or precedes n.

      /// I.e. startsentinel precedes n.

      /// Also update the size as a prelude to handling the right endpoint.

      /// 

      /// Update size of a view not already handled and whose right endpoint precedes n.

      /// </summary>

      /// <param name="removed">The number of nodes left of n to be removed</param>

      /// <param name="n"></param>

      internal void updateViewSizesAndCounts(int removed, Node n)

      {

        if (viewCount > 0)

        {

          Position endpoint;

          while (leftEndIndex < viewCount && ((endpoint = leftEnds[leftEndIndex]).Endpoint.prev.precedes(n)))

          {

            LinkedList<T> view = endpoint.View;

            view.offset = view.offset - removed; //TODO: fix use of offset

            view.size += removed;

            leftEndIndex++;

          }

          while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Endpoint.precedes(n))

          {

            LinkedList<T> view = endpoint.View;

            view.size -= removed;

            rightEndIndex++;

          }

        }

      }

      /// <summary>

      /// To be called with n being the first not-to-be-removed node after a (stretch of) node(s) to be removed.

      /// 

      /// It will update the startsentinel of views (that have not been handled before and) 

      /// whose startsentinel precedes n, i.e. is to be deleted.

      /// 

      /// It will update the endsentinel of views (...) whose endsentinel precedes n, i.e. is to be deleted.

      /// 

      /// PROBLEM: DOESNT WORK AS ORIGINALLY ADVERTISED. WE MUST DO THIS BEFORE WE ACTUALLY REMOVE THE NODES. WHEN THE 

      /// NODES HAVE BEEN REMOVED, THE precedes METHOD WILL NOT WORK!

      /// </summary>

      /// <param name="n"></param>

      /// <param name="newstart"></param>

      /// <param name="newend"></param>

      internal void updateSentinels(Node n, Node newstart, Node newend)

      {

        if (viewCount > 0)

        {

          Position endpoint;

          while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Endpoint.prev.precedes(n))

          {

            LinkedList<T> view = endpoint.View;

            view.startsentinel = newstart;

            leftEndIndex2++;

          }

          while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Endpoint.next.precedes(n))

          {

            LinkedList<T> view = endpoint.View;

            view.endsentinel = newend;

            rightEndIndex2++;

          }

        }

      }

#else

      /// <summary>

      /// This is to be called with realindex pointing to the first node to be removed after a (stretch of) node that was not removed

      /// </summary>

      /// <param name="removed"></param>

      /// <param name="realindex"></param>

      internal void skipEndpoints(int removed, int realindex)

      {

        if (viewCount > 0)

        {

          Position endpoint;

          while (leftEndIndex < viewCount && (endpoint = leftEnds[leftEndIndex]).Index <= realindex)

          {

            LinkedList<T> view = endpoint.View;

            view.offset = view.offset - removed;

            view.size += removed;

            leftEndIndex++;

          }

          while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Index < realindex)

          {

            LinkedList<T> view = endpoint.View;

            view.size -= removed;

            rightEndIndex++;

          }

        }

        if (viewCount > 0)

        {

          Position endpoint;

          while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Index <= realindex)

            leftEndIndex2++;

          while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Index < realindex - 1)

            rightEndIndex2++;

        }

      }

      internal void updateViewSizesAndCounts(int removed, int realindex)

      {

        if (viewCount > 0)

        {

          Position endpoint;

          while (leftEndIndex < viewCount && (endpoint = leftEnds[leftEndIndex]).Index <= realindex)

          {

            LinkedList<T> view = endpoint.View;

            view.offset = view.Offset - removed;

            view.size += removed;

            leftEndIndex++;

          }

          while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Index < realindex)

          {

            LinkedList<T> view = endpoint.View;

            view.size -= removed;

            rightEndIndex++;

          }

        }

      }

      internal void updateSentinels(int realindex, Node newstart, Node newend)

      {

        if (viewCount > 0)

        {

          Position endpoint;

          while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Index <= realindex)

          {

            LinkedList<T> view = endpoint.View;

            view.startsentinel = newstart;

            leftEndIndex2++;

          }

          while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Index < realindex - 1)

          {

            LinkedList<T> view = endpoint.View;

            view.endsentinel = newend;

            rightEndIndex2++;

          }

        }

      }

#endif

    }

    #endregion

    #region Range nested class

    class Range : DirectedCollectionValueBase<T>, IDirectedCollectionValue<T>

    {

      int start, count, rangestamp;

      Node startnode, endnode;

      LinkedList<T> list;

      bool forwards;

      internal Range(LinkedList<T> list, int start, int count, bool forwards)

      {

        this.list = list; this.rangestamp = list.underlying != null ? list.underlying.stamp : list.stamp;

        this.start = start; this.count = count; this.forwards = forwards;

        if (count > 0)

        {

          startnode = list.get(start);

          endnode = list.get(start + count - 1);

        }

      }

      public override bool IsEmpty { get { list.modifycheck(rangestamp); return count == 0; } }

      [Tested]

      public override int Count { [Tested]get { list.modifycheck(rangestamp); return count; } }

      public override Speed CountSpeed { get { list.modifycheck(rangestamp); return Speed.Constant; } }

      public override T Choose()

      {

        list.modifycheck(rangestamp);

        if (count > 0) return startnode.item;

        throw new NoSuchItemException();

      }

      [Tested]

      public override SCG.IEnumerator<T> GetEnumerator()

      {

        int togo = count;

        list.modifycheck(rangestamp);

        if (togo == 0)

          yield break;

        Node cursor = forwards ? startnode : endnode;

        yield return cursor.item;

        while (--togo > 0)

        {

          cursor = forwards ? cursor.next : cursor.prev;

          list.modifycheck(rangestamp);

          yield return cursor.item;

        }

      }

      [Tested]

      public override IDirectedCollectionValue<T> Backwards()

      {

        list.modifycheck(rangestamp);

        Range b = (Range)MemberwiseClone();

        b.forwards = !forwards;

        return b;

      }

      [Tested]

      IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); }

      [Tested]

      public override EnumerationDirection Direction

      {

        [Tested]

        get

        { return forwards ? EnumerationDirection.Forwards : EnumerationDirection.Backwards; }

      }

    }

    #endregion

    #region IDisposable Members

    /// <summary>

    /// Invalidate this list. If a view, just invalidate the view. 

    /// If not a view, invalidate the list and all views on it.

    /// </summary>

    public virtual void Dispose()

    {

      Dispose(false);

    }

    void Dispose(bool disposingUnderlying)

    {

      if (isValid)

      {

        if (underlying != null)

        {

          isValid = false;

          if (!disposingUnderlying && views != null)

            views.Remove(myWeakReference);

          endsentinel = null;

          startsentinel = null;

          underlying = null;

          views = null;

          myWeakReference = null;

        }

        else

        {

          //isValid = false;

          //endsentinel = null;

          //startsentinel = null;

          if (views != null)

            foreach (LinkedList<T> view in views)

              view.Dispose(true);

          //views = null;

          Clear();

        }

      }

    }

    #endregion IDisposable stuff

    #region IList<T> Members

    /// <summary>

    /// </summary>

    /// <exception cref="NoSuchItemException"> if this list is empty.</exception>

    /// <value>The first item in this list.</value>

    [Tested]

    public virtual T First

    {

      [Tested]

      get

      {

        validitycheck();

        if (size == 0)

          throw new NoSuchItemException();

        return startsentinel.next.item;

      }

    }

    /// <summary>

    /// </summary>

    /// <exception cref="NoSuchItemException"> if this list is empty.</exception>

    /// <value>The last item in this list.</value>

    [Tested]

    public virtual T Last

    {

      [Tested]

      get

      {

        validitycheck();

        if (size == 0)

          throw new NoSuchItemException();

        return endsentinel.prev.item;

      }

    }

    /// <summary>

    /// Since <code>Add(T item)</code> always add at the end of the list,

    /// this describes if list has FIFO or LIFO semantics.

    /// </summary>

    /// <value>True if the <code>Remove()</code> operation removes from the

    /// start of the list, false if it removes from the end. THe default for a new linked list is true.</value>

    [Tested]

    public virtual bool FIFO

    {

      [Tested]

      get { validitycheck(); return fIFO; }

      [Tested]

      set { updatecheck(); fIFO = value; }

    }

    /// <summary>

    /// 

    /// </summary>

    public virtual bool IsFixedSize

    {

      get { validitycheck(); return false; }

    }

    /// <summary>

    /// On this list, this indexer is read/write.

    /// <exception cref="IndexOutOfRangeException"/> if i is negative or

    /// >= the size of the collection.

    /// </summary>

    /// <value>The i'th item of this list.</value>

    /// <param name="index">The index of the item to fetch or store.</param>

    [Tested]

    public virtual T this[int index]

    {

      [Tested]

      get { validitycheck(); return get(index).item; }

      [Tested]

      set

      {

        updatecheck();

        Node n = get(index);

        //

        T item = n.item;

#if HASHINDEX

        if (itemequalityComparer.Equals(value, item))

        {

          n.item = value;

          dict.Update(value, n);

        }

        else if (!dict.FindOrAdd(value, ref n))

        {

          dict.Remove(item);

          n.item = value;

        }

        else

          throw new ArgumentException("Item already in indexed list");

#else

        n.item = value;

#endif

        (underlying ?? this).raiseForSetThis(index, value, item);

      }

    }

    /// <summary>

    /// 

    /// </summary>

    /// <value></value>

    public virtual Speed IndexingSpeed { get { return Speed.Linear; } }

    /// <summary>

    /// Insert an item at a specific index location in this list. 

    /// <exception cref="IndexOutOfRangeException"/> if i is negative or

    /// &gt; the size of the collection.</summary>

    /// <param name="i">The index at which to insert.</param>

    /// <param name="item">The item to insert.</param>

    [Tested]

    public virtual void Insert(int i, T item)

    {

      updatecheck();

      insert(i, i == size ? endsentinel : get(i), item);

      if (ActiveEvents != EventTypeEnum.None)

        (underlying ?? this).raiseForInsert(i + Offset, item);

    }

    /// <summary>

    /// Insert an item at the end of a compatible view, used as a pointer.

    /// <para>The <code>pointer</code> must be a view on the same list as

    /// <code>this</code> and the endpoitn of <code>pointer</code> must be

    /// a valid insertion point of <code>this</code></para>

    /// </summary>

    /// <exception cref="IncompatibleViewException">If <code>pointer</code> 

    /// is not a view on the same list as <code>this</code></exception>

    /// <exception cref="IndexOutOfRangeException"><b>??????</b> if the endpoint of 

    ///  <code>pointer</code> is not inside <code>this</code></exception>

    /// <exception cref="DuplicateNotAllowedException"> if the list has

    /// <code>AllowsDuplicates==false</code> and the item is 

    /// already in the list.</exception>

    /// <param name="pointer"></param>

    /// <param name="item"></param>

    public void Insert(IList<T> pointer, T item)

    {

      updatecheck();

      if ((pointer == null) || ((pointer.Underlying ?? pointer) != (underlying ?? this)))

        throw new IncompatibleViewException();

#warning INEFFICIENT

      //TODO: make this efficient (the whole point of the method:

      //Do NOT use Insert, but insert the node at pointer.endsentinel, checking

      //via the ordering that this is a valid insertion point

      Insert(pointer.Offset + pointer.Count - Offset, item);

    }

    /// <summary>

    /// Insert into this list all items from an enumerable collection starting 

    /// at a particular index.

    /// <exception cref="IndexOutOfRangeException"/> if i is negative or

    /// > the size of the collection.

    /// </summary>

    /// <param name="i">Index to start inserting at</param>

    /// <param name="items">Items to insert</param>

    /// <typeparam name="U"></typeparam>

    [Tested]

    public virtual void InsertAll<U>(int i, SCG.IEnumerable<U> items) where U : T

    {

      insertAll(i, items, true);

    }

    void insertAll<U>(int i, SCG.IEnumerable<U> items, bool insertion) where U : T

    {

      updatecheck();

      Node succ, node, pred;

      int count = 0;

      succ = i == size ? endsentinel : get(i);

      pred = node = succ.prev;

#if HASHINDEX

      TagGroup taggroup = null;

      int taglimit = 0, thetag = 0;

      taggroup = gettaggroup(node, succ, out thetag, out taglimit);

      try

      {

        foreach (T item in items)

        {

          Node tmp = new Node(item, node, null);

          if (!dict.FindOrAdd(item, ref tmp))

          {

            tmp.tag = thetag < taglimit ? ++thetag : thetag;

            tmp.taggroup = taggroup;

            node.next = tmp;

            count++;

            node = tmp;

          }

          else

            throw new DuplicateNotAllowedException("Item already in indexed list");

        }

      }

      finally

      {

        if (count != 0)

        { 

          taggroup.count += count;

          if (taggroup != pred.taggroup)

            taggroup.first = pred.next;

          if (taggroup != succ.taggroup)

            taggroup.last = node;

          succ.prev = node;

          node.next = succ;

          if (node.tag == node.prev.tag)

            splittaggroup(taggroup);

          size += count;

          if (underlying != null)

            underlying.size += count;

          fixViewsAfterInsert(succ, pred, count, 0);

          raiseForInsertAll(pred, i, count, insertion);

        }

      }

#else

      foreach (T item in items)

      {

        Node tmp = new Node(item, node, null);

        node.next = tmp;

        count++;

        node = tmp;

      }

      if (count == 0)

        return;

      succ.prev = node;

      node.next = succ;

      size += count;

      if (underlying != null)

        underlying.size += count;

      if (count > 0)

      {

        fixViewsAfterInsert(succ, pred, count, offset + i);

        raiseForInsertAll(pred, i, count, insertion);

      }

#endif

    }

    private void raiseForInsertAll(Node node, int i, int added, bool insertion)

    {

      if (ActiveEvents != 0)

      {

        int index = Offset + i;

        if ((ActiveEvents & (EventTypeEnum.Added | EventTypeEnum.Inserted)) != 0)

          for (int j = index; j < index + added; j++)

          {

#warning must we check stamps here?

            node = node.next;

            T item = node.item;

            if (insertion) raiseItemInserted(item, j);

            raiseItemsAdded(item, 1);

          }

        raiseCollectionChanged();

      }

    }

    /// <summary>

    /// Insert an item at the front of this list.

    /// </summary>

    /// <param name="item">The item to insert.</param>

    [Tested]

    public virtual void InsertFirst(T item)

    {

      updatecheck();

      insert(0, startsentinel.next, item);

      if (ActiveEvents != EventTypeEnum.None)

        (underlying ?? this).raiseForInsert(0 + Offset, item);

    }

    /// <summary>

    /// Insert an item at the back of this list.

    /// </summary>

    /// <param name="item">The item to insert.</param>