// FILE. . . . . /home/hak/hlt/src/hlt/osfv2/util/DoublyLinkedList.java
// EDIT BY . . . Hassan Ait-Kaci
// ON MACHINE. . Hak-Laptop
// STARTED ON. . Mon Sep 02 15:38:18 2013

/**
 * This class implements a class for doubly linked lists of <tt>Object</tt>s.
 *
 * @version	Last modified on Tue Jan 21 08:08:32 2014 by hak
 * @author      <a href="mailto:hak@acm.org">Hassan A&iuml;t-Kaci</a>
 * @copyright	&copy; <a href="http://www.hassan-ait-kaci.net/">Hassan A&iuml;t-Kaci</a>
 */

package hlt.osf.util;

import java.util.Iterator;
// import java.util.LinkedList;

public class DoublyLinkedList
{
  // Constructors:

  /**
   * Creates a new empty doubly linked list.
   */
  public DoublyLinkedList ()
  {   
  }

  // /**
  //  * Creates a new doubly linked list containing the objects of the
  //  * specified linked list in the same order.
  //  */
  // public DoublyLinkedList (LinkedList list)
  // {
  //   for (Iterator list.iterator(); it.hasNext();)
  //     append(it.next());
  // }

  // /**
  //  * Creates a new doubly linked list containing the objects of the
  //  * specified array in the same order.
  //  */
  // public DoublyLinkedList (Array array)
  // {
  //   for (int i=array.size(); i-->0;)     
  //     prepend(array[i]);
  // }

// Fields:

  /**
   * Contains the first cell element of this list, or null if it is empty.
   */
  private Cell _first = null;

  /**
   * Contains the last cell element of this list, or null if it is empty.
   */
  private Cell _last = null;

  /**
   * Contains the length of this list.
   */
  private int _length = 0;
    
// Methods:

  /**
   * Returns the first cell element of this list, or null if it is empty.
   */
  Cell first ()
  {
    return _first;
  }

  /**
   * Returns the first element of this list, or null if it is empty.
   */
  public Object firstElt ()
  {
    return _first.elt();
  }

  /**
   * Returns the last cell element of this list, or null if it is empty.
   */
  Cell last ()
  {
    return _last;
  }

  /**
   * Returns the last element of this list, or null if it is empty.
   */
  public Object lastElt ()
  {
    return _last.elt();
  }

  /**
   * Contains the length of this list (i.e., the number of elements in it).
   */
  public int length ()
  {
    return _length;
  }

  /**
   * Returns true if this list is empty.
   */
  public boolean isEmpty ()
  {
    return _length == 0;
  }

  /**
   * Modifies this list by adding the specified object at the front of
   * the list, and returns this modified list.
   */
  public DoublyLinkedList prepend (Object obj)
  {
    Cell cell = new Cell(obj);

    if (isEmpty())
      {
	_first = cell;
	_last = cell;
	_length = 1;
      }
    else
      {
	cell.setNext(_first);
	_first.setPrev(cell);
	_first = cell;
	_length++;
      }

    return this;	
  }

  /**
   * Modifies this list by adding the specified object at the back of
   * the list, and returns this modified list.
   */
  public DoublyLinkedList append (Object obj)
  {
    Cell cell = new Cell(obj);

    if (isEmpty())
      {
	_first = cell;
	_last = cell;
	_length = 1;
      }
    else
      {
	cell.setPrev(_last);
	_last.setNext(cell);
	_last = cell;
	_length++;
      }
    
    return this;	
  }

  /**
   * Modifies this list by adding the specified doubly-linked list at
   * the back of it, and returns this modified list.
   */
  public DoublyLinkedList concatenate (DoublyLinkedList list)
  {
    if (isEmpty())
      {
	_first = list.first();
	_last = list.last();
	_length = list.length();
      }
    else
      {
	list.first().setPrev(_last);
	_last.setNext(list.first());
	_last = list.last();
	_length += list.length();
      }
    
    return this;	
  }

  /**
   * Makes this list empty.
   */
  public void clear ()
  {
    _first = null;
    _last = null;
    _length = 0;    
  }

  /**
   * Cloning this list produces a new doubly linked list that is equal to it.
   */
  public Object clone ()
  {
    return copy();
  }

  /**
   * Returns a doubly-linked list that is a shallow copy of this list.
   */
  public DoublyLinkedList copy ()
  {
    DoublyLinkedList copy = new DoublyLinkedList();

    if (!isEmpty())
      for (Iterator it=iterator(); it.hasNext();)
	copy.append(it.next());

    return copy;
  }

  /**
   * Compares this list against the specified object.
   */
  public boolean equals (Object obj)
  {
    if (!(obj instanceof DoublyLinkedList))
      return false;

    DoublyLinkedList list = (DoublyLinkedList)obj;

    if (_length != list.length())
      return false;

    if (!isEmpty())
      {
	Cell cell = _first;
	Cell other = list.first();
	while (cell != _last)
	  if (cell.elt().equals(other.elt()))
	    {
	      cell = cell.next();
	      other = other.next();
	    }
	  else
	    return (cell.elt().equals(other.elt()));
      }

    return true;	
  }

  // /**
  //  * Returns a hash code value for this list.
  //  */
  // public int hashCode ()
  // {
  // }

  /**
   * Returns a string representation of this doubly linked list.
   */
  public String toString ()
  {
    if (isEmpty())
      return "[]";
    
    StringBuffer buf = new StringBuffer("[");
    Cell cell = _first;
    while (cell != _last)
      {
	buf.append(cell.elt()+",");
	cell = cell.next();
      }
    buf.append(_last.elt()+"]");

    return buf.toString();
  }

  // ancillary classes:

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

  public Iterator iterator ()
    {
      return new DoublyLinkedListIterator(this);
    }

  private class DoublyLinkedListIterator implements Iterator
    {
      private Cell _current;

      DoublyLinkedListIterator (DoublyLinkedList list)
        {
          _current = list.first();
        }

      public final boolean hasNext ()
        {
	  return (_current != null);
	}

      public final Object next ()
        {
	  Object elt = _current.elt();
	  _current = _current.next();

          return elt;
        }
      
      public final void remove () throws UnsupportedOperationException
        {
	  throw new UnsupportedOperationException();
        }
      
    }

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

  class Cell
  {
    private Object _elt = null;
    private Cell _next = null;
    private Cell _prev = null;
    
    Cell (Object elt)
      {
	_elt = elt;
      }

    Object elt ()
      {
	return _elt;
      }

    Cell next ()
      {
	return _next;
      }

    Cell prev ()
      {
	return _prev;
      }

    void setNext (Cell cell)
      {
	_next = cell;
      }

    void setPrev (Cell cell)
      {
	_prev = cell;
      }

    public String toString ()
      {
	return _elt.toString();
      }      

  }
}