context: /* --------------------------------------------------------------------------
   * Copyrights
   *
   * Portions created by or assigned to Cursive Systems, Inc. are
   * Copyright (c) 2002-2008 Cursive Systems, Inc.  All Rights Reserved.  Contact
   * information for Cursive Systems, Inc. is available at
   * http://www.cursive.net/.
   *
   * License
   *
   * Jabber-Net is licensed under the LGPL.
   * See LICENSE.txt for details.
   * --------------------------------------------------------------------------*/
  using System;
  
  using System.Collections;
  using bedrock.util;
  namespace bedrock.collections
  {
      /// <summary>
      /// A doubly-linked list implementation, with a sentinal wrap-around
      /// m_header.  Yes, it <b>does</b> seem like this should have been included
      /// in System.Collections.  This may be a nicer implementation of Queue
      /// than the one in System.Collections, which uses an array.  YMMV.
      /// </summary>
      [SVN(@"$Id: LinkedList.cs 724 2008-08-06 18:09:25Z hildjj $")]
      public class LinkedList : IList
      {
          private Node      m_header     = new Node(null, null, null);
          private int       m_size       = 0;
          private int       m_modCount   = 0;
          private IComparer m_comparator = null;
          private bool      m_readOnly   = false;
          private bool      m_synch      = false;
          /// <summary>
          /// Creates an empty list.
          /// </summary>
          public LinkedList()
          {
              m_header.next = m_header.previous = m_header;
          }
          /// <summary>
          /// Create a list with the targets of the given
          /// enumeration copied into it.
          /// </summary>
          /// <param name="e"></param>
          public LinkedList(IEnumerable e) : this()
          {
              foreach (object o in e)
              {
                  Add(o);
              }
          }
          #region IEnumerable
          /// <summary>
          /// Iterate over the list.
          /// </summary>
          /// <returns></returns>
          public IEnumerator GetEnumerator()
          {
              return new ListEnumerator(this);
          }
          #endregion
          #region ICollection
          /// <summary>
          /// How many elements in the list?
          /// </summary>
          public int Count
          {
              get
              {
                  return m_size;
              }
          }
  
          /// <summary>
          /// Determines if the list is read-only (Can the user add or remove an item from this list).
          /// </summary>
          public bool IsReadOnly
          {
              get
              {
                  return m_readOnly;
              }
              set
              {
                  m_readOnly = value;
              }
          }
  
          /// <summary>
          /// Is the list thread-safe?
          /// TODO: implement thread-safe
          /// </summary>
          public bool IsSynchronized
          {
              get
              {
                  return m_synch;
              }
              set
              {
                  m_synch = value;
              }
          }
  
          /// <summary>
          /// The object to synchronize on.
          /// TODO: implement settable SyncRoot
          /// </summary>
          public object SyncRoot
          {
              get
              {
                  return this;
              }
          }
  
          /// <summary>
          /// Copy this list to the given array.
          /// </summary>
          /// <param name="array">Array to copy into</param>
          /// <param name="index">Index to start copying at</param>
          public void CopyTo(Array array, int index)
          {
              int i = index;
              foreach (object o in this)
              {
                  array.SetValue(o, i++);
              }
          }
          #endregion
          #region IList
          /// <summary>
          /// Gets the indexth element by walking the list.
          /// </summary>
          public object this[int index]
          {
              get
              {
                  return GetNode(index).element;
              }
              set
              {
                  GetNode(index).element = value;
              }
          }
  
          /// <summary>
          /// Insert an element at the end of the list
          /// </summary>
          /// <param name="value"></param>
          /// <returns></returns>
          public int Add(object value)
          {
              AddBefore(value, m_header);
              return m_size-1;
          }
  
          /// <summary>
          /// Remove all of the elements.
          /// </summary>
          public void Clear()
          {
              m_modCount++;
              m_header.next = m_header.previous = m_header;
              m_size = 0;
          }
  
          /// <summary>
          /// Is the given object in the list?
          /// </summary>
          /// <param name="value">The object to find</param>
          /// <returns>True if the object is in the list</returns>
          public bool Contains(object value)
          {
              return IndexOf(value) != -1;
          }
  
          /// <summary>
          /// Determines where in the index the specified object exists.
          /// </summary>
          /// <param name="value">The object to find</param>
          /// <returns>The position of the object in the list, or -1 if not found</returns>
          public int IndexOf(object value)
          {
              int index = 0;
              if (value == null)
              {
                  for (Node e = m_header.next; e != m_header; e = e.next)
                  {
                      if (e.element == null)
                          return index;
                      index++;
                  }
              }
              else
              {
                  for (Node e = m_header.next; e != m_header; e = e.next)
                  {
                      if (value.Equals(e.element))
                          return index;
                      index++;
                  }
              }
              return -1;
          }
  
          /// <summary>
          /// Inserts an item into the list at the given index.
          /// </summary>
          /// <param name="index">The position to insert before</param>
          /// <param name="value">The object to insert</param>
          public void Insert(int index, object value)
          {
              if (index >= m_size)
              {
                  AddBefore(value, m_header);
              }
              else
              {
                  Node n = GetNode(index);
                  AddBefore(value, n);
              }
          }
  
          /// <summary>
          /// Always returns "false" for now.
          /// TODO: implement fixed size
          /// </summary>
          public bool IsFixedSize
          {
              get { return false; }
          }
  
          /// <summary>
          /// Finds the first matching object, and removes it from the list.
          /// </summary>
          /// <param name="value">The object to remove</param>
          /// <exception cref="System.ArgumentException">Object not found</exception>
          public void Remove(object value)
          {
              if (value == null)
              {
                  for (Node e = m_header.next; e != m_header; e = e.next)
                  {
                      if (e.element == null)
                      {
                          Remove(e);
                          return;
                      }
                  }
              }
              else
              {
                  for (Node e = m_header.next; e != m_header; e = e.next)
                  {
                      if (value.Equals(e.element))
                      {
                          Remove(e);
                          return;
                      }
                  }
              }
              throw new ArgumentException("Object not found", "value");
          }
  
          /// <summary>
          /// Removes the indexth element from the list.
          /// </summary>
          /// <param name="index">The index of the element to delete</param>
          public void RemoveAt(int index)
          {
              Node e = GetNode(index);
              Remove(e);
          }
          #endregion
  
          #region Queue
          /// <summary>
          /// Inserts an element at the end of the list.
          /// </summary>
          /// <param name="value">Element to insert.</param>
          public void Enqueue(object value)
          {
              AddBefore(value, m_header);
          }
  
          /// <summary>
          /// Remove and return the element at the front of the list
          /// </summary>
          /// <returns>The element at the end of the list</returns>
          public object Dequeue()
          {
              object value = m_header.next.element;
              Remove(m_header.next);
              return value;
          }
  
          /// <summary>
          /// Retrieve the element at the front of the list, without removing it.
          /// </summary>
          /// <returns></returns>
          public object Peek()
          {
              return m_header.next.element;
          }
          #endregion
          #region Stack
          /// <summary>
          /// Add an element to the front of the list.
          /// </summary>
          /// <param name="value"></param>
          public void Push(object value)
          {
              AddBefore(value, m_header.next);
          }
  
          /// <summary>
          /// Retrieve and remove the element at the front of the list.
          /// </summary>
          /// <returns></returns>
          public object Pop()
          {
              return Dequeue();
          }
          #endregion Stack
          #region private
          private Node GetNode(int index)
          {
              if ((index < 0) || (index >= m_size))
              {
                  throw new IndexOutOfRangeException("Must choose index between 0 and " +
                                                     (m_size-1));
              }
  
              Node e = m_header;
              // start from end if closer
              if (index < m_size/2)
              {
                  for (int i = 0; i <= index; i++)
                      e = e.next;
              }
              else
              {
                  for (int i = m_size; i > index; i--)
                      e = e.previous;
              }
              return e;
          }
  
          private Node AddBefore(object value, Node n)
          {
              if (m_readOnly)
              {
                  throw new InvalidOperationException("Cannot add to a read-only list");
              }
  
              if (m_synch)
              {
                  lock (this)
                  {
  
gt:                     return UncheckedAdd(value, n);