context: 
  /*
   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.
  */
  
  using System;
  using SCG = System.Collections.Generic;
  namespace C5
  {
      /// <summary>
      /// A list collection based on a plain dynamic array data structure.
      /// Expansion of the internal array is performed by doubling on demand. 
      /// The internal array is only shrinked by the Clear method. 
      ///
      /// <i>When the FIFO property is set to false this class works fine as a stack of T.
      /// When the FIFO property is set to true the class will function as a (FIFO) queue
      /// but very inefficiently, use a LinkedList (<see cref="T:C5.LinkedList`1"/>) instead.</i>
      /// </summary>
      public class ArrayList<T> : ArrayBase<T>, IList<T>, IStack<T>, IQueue<T>
      {
          #region Fields
  
          /// <summary>
          /// Has this list or view not been invalidated by some operation (by someone calling Dispose())
          /// </summary>
          bool isValid = true;
  
          //TODO: wonder if we should save some memory on none-view situations by 
          //      putting these three fields into a single ref field?
          /// <summary>
          /// The underlying list if we are a view, null else.
          /// </summary>
          ArrayList<T> underlying;
          WeakViewList<ArrayList<T>> views;
          WeakViewList<ArrayList<T>>.Node myWeakReference;
  
          /// <summary>
          /// The size of the underlying list.
          /// </summary>
          int underlyingsize { get { return (underlying ?? this).size; } }
  
          /// <summary>
          /// The underlying field of the FIFO property
          /// </summary>
          bool fIFO = false;
  
          #endregion
          #region Events
  
          /// <summary>
          /// 
          /// </summary>
          /// <value></value>
          public override EventTypeEnum ListenableEvents { get { return underlying == null ? EventTypeEnum.All : EventTypeEnum.None; } }
  
          /*
              /// <summary>
              /// 
              /// </summary>
              /// <value></value>
              public override event CollectionChangedHandler<T> CollectionChanged
              {
                add
                {
                  if (underlying == null)
                    base.CollectionChanged += value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
                remove
                {
                  if (underlying == null)
                    base.CollectionChanged -= value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
              }
  
              /// <summary>
              /// 
              /// </summary>
              /// <value></value>
              public override event CollectionClearedHandler<T> CollectionCleared
              {
                add
                {
                  if (underlying == null)
                    base.CollectionCleared += value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
                remove
                {
                  if (underlying == null)
                    base.CollectionCleared -= value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
              }
  
              /// <summary>
              /// 
              /// </summary>
              /// <value></value>
              public override event ItemsAddedHandler<T> ItemsAdded
              {
                add
                {
                  if (underlying == null)
                    base.ItemsAdded += value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
                remove
                {
                  if (underlying == null)
                    base.ItemsAdded -= value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
              }
  
              /// <summary>
              /// 
              /// </summary>
              /// <value></value>
              public override event ItemInsertedHandler<T> ItemInserted
              {
                add
                {
                  if (underlying == null)
                    base.ItemInserted += value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
                remove
                {
                  if (underlying == null)
                    base.ItemInserted -= value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
              }
  
              /// <summary>
              /// 
              /// </summary>
              /// <value></value>
              public override event ItemsRemovedHandler<T> ItemsRemoved
              {
                add
                {
                  if (underlying == null)
                    base.ItemsRemoved += value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
                remove
                {
                  if (underlying == null)
                    base.ItemsRemoved -= value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
              }
  
              /// <summary>
              /// 
              /// </summary>
              /// <value></value>
              public override event ItemRemovedAtHandler<T> ItemRemovedAt
              {
                add
                {
                  if (underlying == null)
                    base.ItemRemovedAt += value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
                remove
                {
                  if (underlying == null)
                    base.ItemRemovedAt -= value;
                  else
                    throw new UnlistenableEventException("Can't listen to a view");
                }
              }
  
                */
  
          #endregion
          #region Util
  
          bool equals(T i1, T i2) { return itemequalityComparer.Equals(i1, i2); }
  
          /// <summary>
          /// Increment or decrement the private size fields
          /// </summary>
          /// <param name="delta">Increment (with sign)</param>
          void addtosize(int delta)
          {
              size += delta;
              if (underlying != null)
                  underlying.size += delta;
          }
  
          #region Array handling
          /// <summary>
          /// Double the size of the internal array.
          /// </summary>
          protected override void expand()
          { expand(2 * array.Length, underlyingsize); }
  
  
          /// <summary>
          /// Expand the internal array, resetting the index of the first unused element.
          /// </summary>
          /// <param name="newcapacity">The new capacity (will be rouded upwards to a power of 2).</param>
          /// <param name="newsize">The new count of </param>
          protected override void expand(int newcapacity, int newsize)
          {
              if (underlying != null)
                  underlying.expand(newcapacity, newsize);
              else
              {
                  base.expand(newcapacity, newsize);
                  if (views != null)
                      foreach (ArrayList<T> v in views)
                          v.array = array;
              }
          }
  
          #endregion
  
          #region Checks
          /// <summary>
          /// Check if it is valid to perform updates and increment stamp if so.
          /// </summary>
          /// <exception cref="ViewDisposedException"> If check fails by this list being a disposed view.</exception>
          /// <exception cref="ReadOnlyCollectionException"> If check fails by this being a read only list.</exception>
          protected override void updatecheck()
          {
              validitycheck();
              base.updatecheck();
              if (underlying != null)
                  underlying.stamp++;
          }
  
  
          /// <summary>
          /// Check if we are a view that the underlying list has only been updated through us.
          /// <para>This method should be called from enumerators etc to guard against 
          /// modification of the base collection.</para>
          /// </summary>
          /// <exception cref="ViewDisposedException"> if check fails.</exception>
          void validitycheck()
          {
              if (!isValid)
                  throw new ViewDisposedException();
          }
  
  
          /// <summary>
          /// Check that the list has not been updated since a particular time.
          /// <para>To be used by enumerators and range </para>
          /// </summary>
          /// <exception cref="ViewDisposedException"> If check fails by this list being a disposed view.</exception>
          /// <exception cref="CollectionModifiedException">If the list *has* beeen updated since that  time..</exception>
          /// <param name="stamp">The stamp indicating the time.</param>
          protected override void modifycheck(int stamp)
          {
              validitycheck();
              if (this.stamp != stamp)
                  throw new CollectionModifiedException();
          }
  
          #endregion
  
          #region Searching
  
          /// <summary>
          /// Internal version of IndexOf without modification checks.
          /// </summary>
          /// <param name="item">Item to look for</param>
          /// <returns>The index of first occurrence</returns>
          int indexOf(T item)
          {
              for (int i = 0; i < size; i++)
                  if (equals(item, array[offset + i]))
                      return i;
              return ~size;
          }
  
          /// <summary>
          /// Internal version of LastIndexOf without modification checks.
          /// </summary>
          /// <param name="item">Item to look for</param>
          /// <returns>The index of last occurrence</returns>
          int lastIndexOf(T item)
          {
              for (int i = size - 1; i >= 0; i--)
                  if (equals(item, array[offset + i]))
                      return i;
              return ~size;
          }
          #endregion
  
          #region Inserting
  
          /// <summary>
          /// Internal version of Insert with no modification checks.
          /// </summary>
          /// <param name="i">Index to insert at</param>
          /// <param name="item">Item to insert</param>
          protected override void insert(int i, T item)
          {
              baseinsert(i, item);
          }
  
          private void baseinsert(int i, T item)
          {
              if (underlyingsize == array.Length)
                  expand();
              i += offset;
              if (i < underlyingsize)
                  Array.Copy(array, i, array, i + 1, underlyingsize - i);
              array[i] = item;
              addtosize(1);
              fixViewsAfterInsert(1, i);
          }
          #endregion
  
          #region Removing
  
          /// <summary>
          /// Internal version of RemoveAt with no modification checks.
          /// </summary>
          /// <param name="i">Index to remove at</param>
          /// <returns>The removed item</returns>
          T removeAt(int i)
          {
              i += offset;
              fixViewsBeforeSingleRemove(i);
              T retval = array[i];
              addtosize(-1);
              if (underlyingsize > i)
                  Array.Copy(array, i + 1, array, i, underlyingsize - i);
              array[underlyingsize] = default(T);
  
              return retval;
          }
          #endregion
  
          #region Indexing
  
          #endregion
  
          #region fixView utilities
  
          /// <summary>
          /// 
          /// </summary>
          /// <param name="added">The actual number of inserted nodes</param>
          /// <param name="realInsertionIndex"></param>
          void fixViewsAfterInsert(int added, int realInsertionIndex)
          {
              if (views != null)
                  foreach (ArrayList<T> view in views)
                  {
                      if (view != this)
                      {
                          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;
                      }
                  }
          }
  
          void fixViewsBeforeSingleRemove(int realRemovalIndex)
          {
              if (views != null)
                  foreach (ArrayList<T> view in views)
                  {
                      if (view != this)
                      {
                          if (view.offset <= realRemovalIndex && view.offset + view.size > realRemovalIndex)
                              view.size--;
                          if (view.offset > realRemovalIndex)
                              view.offset--;
                      }
                  }
          }
  
          /// <summary>
          /// Fix offsets and sizes of other views before removing an interval from this 
          /// </summary>
          /// <param name="start">the start of the interval relative to the array/underlying</param>
          /// <param name="count"></param>
          void fixViewsBeforeRemove(int start, int count)
          {
              int clearend = start + count - 1;
              if (views != null)
                  foreach (ArrayList<T> view in views)
                  {
                      if (view == this)
                          continue;
                      int viewoffset = view.offset, viewend = viewoffset + view.size - 1;
                      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;
                  }
          }
  
          /// <summary>
          /// 
          /// </summary>
          /// <param name="otherOffset"></param>
          /// <param name="otherSize"></param>
          /// <returns>The position of View(otherOffset, otherSize) wrt. this view</returns>
          MutualViewPosition viewPosition(int otherOffset, int otherSize)
          {
              int end = offset + 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;
          }
  
          //TODO: make version that fits the new, more forgiving rules for disposing
          void disposeOverlappingViews(bool reverse)
          {
              if (views != null)
                  foreach (ArrayList<T> view in views)
                  {
                      if (view != this)
                      {
                          switch (viewPosition(view.offset, view.size))
                          {
                              case MutualViewPosition.ContainedIn:
                                  if (reverse)
                                      view.offset = 2 * offset + size - view.size - view.offset;
                                  else
                                      view.Dispose();
                                  break;
                              case MutualViewPosition.Overlapping:
                                  view.Dispose();
                                  break;
                              case MutualViewPosition.Contains:
                              case MutualViewPosition.NonOverlapping:
                                  break;
                          }
                      }
                  }
          }
          #endregion
  
          #endregion
  
          #region Position, PositionComparer and ViewHandler nested types
          class PositionComparer : SCG.IComparer<Position>
          {
              public int Compare(Position a, Position b)
              {
                  return a.index.CompareTo(b.index);
              }
          }
          /// <summary>
          /// During RemoveAll, we need to cache the original endpoint indices of views (??? also for ArrayList?)
          /// </summary>
          struct Position
          {
              public readonly ArrayList<T> view;
              public readonly int index;
              public Position(ArrayList<T> view, bool left)
              {
                  this.view = view;
                  index = left ? view.offset : view.offset + view.size - 1;
              }
              public Position(int index) { this.index = index; view = null; }
          }
  
          /// <summary>
          /// Handle the update of (other) views during a multi-remove operation.
          /// </summary>
          struct ViewHandler
          {
              ArrayList<Position> leftEnds;
              ArrayList<Position> rightEnds;
              int leftEndIndex, rightEndIndex;
              internal readonly int viewCount;
              internal ViewHandler(ArrayList<T> list)
              {
                  leftEndIndex = rightEndIndex = viewCount = 0;
                  leftEnds = rightEnds = null;
                  if (list.views != null)
                      foreach (ArrayList<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(new PositionComparer());
                  rightEnds.Sort(new PositionComparer());
              }
              /// <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)
                      {
                          ArrayList<T> view = endpoint.view;
                          view.offset = view.offset - removed;
                          view.size += removed;
                          leftEndIndex++;
                      }
                      while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).index < realindex)
                      {
                          endpoint.view.size -= removed;
                          rightEndIndex++;
                      }
                  }
              }
              internal void updateViewSizesAndCounts(int removed, int realindex)
              {
                  if (viewCount > 0)
                  {
                      Position endpoint;
                      while (leftEndIndex < viewCount && (endpoint = leftEnds[leftEndIndex]).index <= realindex)
                      {
                          ArrayList<T> view = endpoint.view;
                          view.offset = view.Offset - removed;
  
gt:                         view.size += removed;