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

/**
 * @version	Last modified on Mon Sep 09 16:17:44 2019 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;

/**
 * This class implements a doubly linked list of <tt>Object</tt>s, each
 * wrapped as a <tt>Cell</tt> element (defined as a local class below).
 */
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 it=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 (Object[] obs)
  {
    for (int i=obs.length; i-->0;)     
      prepend(obs[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 end 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 end 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
   * (in other words, the lists are not the same objects but their
   * elements are shared).
   */
  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 doubly-linked list.
   */
  public int hashCode ()
  {
    if (_length == 0)
      return 1;

    int code = 0;
    for (Iterator it=iterator(); it.hasNext();)
      code += it.next().hashCode();
    return code/_length;
  }

  /**
   * 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();
        }
      
    }

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

  /**
   * The local class <tt>Cell</tt> represents a
   * <tt>DoublyLinkedList</tt> element as an object wrapper with
   * <tt>prev()</tt> and <tt>next()</tt> neighbor getters, and related
   * <tt>setPrev()</tt> and <tt>setNext()</tt> neighbor setters.
   */
  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();
      }      

  }
}