/****************************************************************************** Doubly linked list. ---------------------------------------------------- Copyright (c) Gunnar Gotshalks. All Rights Reserved. Permission to use, copy, modify, and distribute this software and its documentation for NON-COMMERCIAL purposes and without fee is hereby granted. *******************************************************************************/ package FlexOr.container; import java.util.*; // Implementation has dummy header and trailer nodes to eliminate the special // cases of adding and removing the ends of the list. /** Implementation of a sequence of objects as a doubly linked list. @author Gunnar Gotshalks @version 1.0 1999 Jan 16 @see Sequence */ public class DLList implements Sequence{ /******************************************************************************* Constructor Methods *******************************************************************************/ /** Establish the class invariant on an empty list.

Class invariant
To simplify assertions we assume sequence[-1] exists for all sequences. It is implemented by a dummy header node. Also we assume sequence[size] exists for all sequences. It is implemented by a dummy trailer node. 

  header.previous = trailer.next = null
  length = 0 <=>  current = header.next = trailer && trailer.previous = header
  sequence[-1] = header
  sequence[size] = trailer
*/ public DLList() { // Variables set in declaration statements. But we need to link the dummy // header and trailer nodes to each other. header.next = trailer; trailer.next = header.previous = null; trailer.previous = header; } /****************************************************************************** Defining the component objects *******************************************************************************/ /** Points to the dummy header for the list. The datum is null. */ protected Node header = new Node(null); /** Points to the dummy trailer for the list. The datum is null. */ protected Node trailer = new Node(null); /** Number of elements in the list. */ protected int length = 0; /** Pointer to the last referenced element. */ protected Node current = trailer; /******************************************************************************* Access Methods *******************************************************************************/ /** Determines whether an element is in the sequence[first..last]. It is O(length) as the list must be searched sequentially. 

Requires: True
Ensures: contains(obj) => result = true
            not contains(obj) => result = false
*/ synchronized public boolean contains(Object obj) { current = header.next; while (current != trailer) { if (current.datum.equals(obj)) return true; current = current.next; } return false; } /** Determines whether an element is in sequence[startIndex..last]. It is O(length) as the list must be searched. 

Requires: True
Ensures:
       sequence[startIndex..length-1].contains(obj) => result = true
   not sequence[startIndex..length-1].contains(obj) => result = false
*/ synchronized public boolean contains(Object obj, int startIndex) { goToIndex(startIndex); do { if (current.datum.equals(obj)) return true; current = current.next; } while (current != trailer); return false; } /******************************************************************************/ /** Returns an enumerator from the current position. The enumeration class is anonymous as we only need a single instance. 

Requires: True
Ensures: enumeration over the elements first to last.
@exception NoSuchElementException when nextElement is called with an empty enumeration sequence. */ synchronized public Enumeration elements() { return new Enumeration() { /** Ask if there is more list to process from this enumeration.

Requires: True
Ensures: Returns TRUE if the next call to nextElement would return a datum, otherwise returns FALSE. */ public boolean hasMoreElements() { return current != trailer; } /** Returns the next object in the list.

Requires: hasMoreElements()
Ensures: Returns next element in the enumeration. */ public Object nextElement() { if (current == trailer) throw new NoSuchElementException(); Object result = current.datum; current = current.next; return result; } /* Points to the node to return the next datum. */ protected Node current = header.next; }; // End implementation of Enumeration } // End elements ////////////////////////////// /** Return the element at the specified index. It is O(length) due to the neead to sequentially scan the list. 

Requires: 0 <= index < size
Ensures: result = sequence[index]
@exception SequenceIndexException when index is out of bounds. */ synchronized public Object elementAt(final int index) { goToIndex(index); return current.datum; } /** Return the first element in the list. 

Requires: True
Ensures: length > 0 => result = sequence[first]
                length = 0 => result = null
*/ synchronized public Object firstElement() { if (length <= 0) { return null; } current = header.next; return current.datum; } /** Return the index of the specified element. The operation is O(length). the last. 

Requires: True
Ensures: contains(obj) => obj = sequence[result]
            not contains(obj) => result = -1
*/ synchronized public int indexOf(final Object obj) { int currentIndex = -1; current = header; while (current.next != trailer) { current = current.next; currentIndex++; if (current.datum.equals(obj)) return currentIndex; } return -1; } /** Return the index of the specified element between the start index and the end of the sequence. 

Requires: True
Ensures: 
       sequence[startIndex..size-1].contains(obj) => obj = sequence[result]
   not sequence[startIndex..size-1].contains(obj) => result = -1
*/ synchronized public int indexOf(final Object obj, final int startIndex) { goToIndex(startIndex); int currentIndex = startIndex; while (current.next != trailer) { current = current.next; currentIndex++; if (current.datum.equals(obj)) return currentIndex; } return -1; } /** Returns true if the list is empty. 

Requires: True
Ensures: isEmpty = (length = 0)
*/ synchronized public boolean isEmpty() { return length == 0; } /** Returns false as a list can never become full. 

Requires: True
Ensures: isFull = false
*/ synchronized public boolean isFull() { return false; } /** Return the last element in the list. 

Requires: True
Ensures: isEmpty => result = null
            ~isEmpty => result = sequence[last]
*/ synchronized public Object lastElement() { if (length <= 0) { return null; } current = trailer.previous; return current.datum; } /** Return the number of elements in the list. 

Requires: True
Ensures: result = length
*/ synchronized public int size() { return length; } /******************************************************************************* Update Methods *******************************************************************************/ /** Adds obj after the last element of the list. 

Requires: True
Ensures: sequence = old sequence ^ obj
*/ synchronized public void add(final Object obj) { current = new Node(obj, trailer, trailer.previous); trailer.previous = trailer.previous.next = current; length++; } /** Insert the element at the specified index. We permit index to be size -- instead of size - 1 -- to specify adding at the end of the list. 

Requires: 0 <= index < old size + 1
Ensures:
    sequence = old sequence[first..index-1] ^ obj ^ old sequence[index..last]
@exception SequenceIndexException when index is out of bounds. */ synchronized public void insertAt(final Object obj, final int index) { length++; // Add to length to make the new index valid. goToIndex(index); Node after = current; current = new Node(obj, after, after.previous); after.previous = after.previous.next = current; } /** Empty the container. 

Requires: True
Ensures: sequence = null // the empty sequence.
*/ synchronized public void removeAll() { header.next = trailer; trailer.previous = header; current = trailer; length = 0; } /** Remove the first element in the sequence. 

Requires: isEmpty = false
Ensures: old sequence = obj ^ sequence
*/ synchronized public Object remove() { if (length > 0) { Object result = header.next.datum; header.next = header.next.next; header.next.previous = header; length--; current = header.next; return result; } else { throw new ContainerEmptyException(); } } /** If obj is found remove it from the container. 

Requires: True
Ensures:
    old sequence.contains(obj) => sequence = old sequence / obj and result = true 
not old sequence.contains(obj) => sequence = old sequence and result = false
*/ synchronized public boolean remove(final Object obj) { current = header.next; while (current != trailer) { if (current.datum.equals(obj)) { length--; current.previous.next = current.next; current.next.previous = current.previous; current = current.next; return true; } current = current.next; } return false; } /** Remove the element at the specified index. 

Requires: 0 <= index < size
Ensures:
    sequence = old sequence[first..index-1] ^ old sequence[index+1..last]
@exception SequenceIndexException when index is out of bounds. */ synchronized public void removeAt(final int index) { goToIndex(index); length--; current.previous.next = current.next; current.next.previous = current.previous; current = current.next; } /** Replace the object at the specified index. 
Requires: 0 <= index < size
Ensures: sequence[index].datum = obj
@exception SequenceIndexException when index is out of bounds. */ synchronized public void setAt(final Object obj, final int index) { goToIndex(index); current.datum = obj; } /** Return a copy of the list with new nodes that point to the same objects as in the original list. Part way between a shallow and deep copy. This is equivalent to how a Vector is cloned. 

Requires: True
Ensures: result = copy of sequence
*/ synchronized public Object clone() { DLList result = new DLList(); Node current = header.next; while (current != trailer) { result.add(((Node) current.clone()).datum); current = current.next; } return result; } /** Return a string representation of the contents of the list. 

Requires: True
Ensures: result = string representation of list
*/ synchronized public String toString() { if (isEmpty()) return "[]"; StringBuffer result = new StringBuffer(); result.append("[ "); Node current = header.next; result.append(current.datum.toString()); current = current.next; while (current != trailer) { result.append(" " + current.datum.toString()); current = current.next; } result.append(" ]"); return result.toString(); } /** Check for equality of contents of two lists. By equality we mean and equal sequence of elements as returned by the Enumerator for each list. 

Requires: True
Ensures: result = true => sequences are equal
                result = false => sequences are not equal
*/ synchronized public boolean equals (final Object list) { if (list == null) return false; if (list instanceof DLList) { DLList otherList = (DLList) list; if (length != otherList.length) return false; Enumeration e1 = elements(); Enumeration e2 = otherList.elements(); while (e1.hasMoreElements()) { if ( ! e1.nextElement().equals(e2.nextElement())) return false; } return true; } else { return false; } } /********************************************************************************* Support classes and methods *********************************************************************************/ /** Checks if the index is within the bounds of the list. 

Requires: True
Ensures: 0 <= index < size or throws exception
@exception SequenceIndexException when index is out of bounds. */ private void verifyIndex(final int index) { if (index < 0 ) throw new SequenceIndexException( "SingleLInkList " + index + " < 0"); if (index >= length) throw new SequenceIndexException( "SingleLInkList " + index + " >= " + length); } /** Move to the element at the specified index. 

Requires: True
Ensures: 0 <= index < size or throws exception
                current = sequence[index]
@exception SequenceIndexException when index is out of bounds. */ private void goToIndex(final int index) { verifyIndex(index); int currentIndex = 0; current = header.next; for( ; currentIndex < index ; currentIndex++ , current = current.next); } //******************************************************************************** /** Define a Node as an inner class. Users of linked lists should not have to know the structure of a node, they are only interested in the objects stored in the list. */ protected class Node implements Cloneable { /** Create a node with null next and previous fields. */ public Node(final Object obj) { this(obj, null, null); } /** Create a node with specified next and previous fields. */ public Node(final Object obj, final Node next, final Node previous) { datum = obj; this.next = next; this.previous = previous; } /** Stores the object */ protected Object datum; /** Points to the next node in a list. */ protected Node next; /** Points to the previous node in a list. */ protected Node previous; /** Provide a shallow clone operation. */ public Object clone() { try { return super.clone(); } catch (CloneNotSupportedException e) { System.err.println("Cannot clone" + e); return null;} } } } // End of class