/****************************************************************************** Singly 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 a dummy header node to eliminate the special case of the // first element not having a predecessor. Last must point to a node or else // adding at the end of the list becomes expensive. /** Implementation of a sequence of objects as a singly linked list. @author Gunnar Gotshalks @version 1.0 1999 Jan 16 @see Sequence */ public class SLList 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 the dummy headerNode. First always points to the headerNode. 

  length = 0 <=> header = last = current
  length ~= 0 => current ~= header
  sequence[-1] = header
*/ public SLList() { // Variables set in declaration statements. } //***************************************************************************** /****************************************************************************** Defining the component objects *******************************************************************************/ /** Define a Node as an inner class. Users of singly 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 a null next field. */ public Node(final Object obj) { this(obj, null); } /** Create a node with a specified next field. */ public Node(final Object obj, final Node next) { datum = obj; this.next = next; } /** Stores the object */ protected Object datum; /** Points to the next node in a list. */ protected Node next; /** Provide a shallow clone operation. */ public Object clone() { try { return super.clone(); } catch (CloneNotSupportedException e) { System.err.println("Cannot clone" + e); return null;} } } //********************************* /** Points to the dummy header for the list. The datum is null. */ protected Node header = new Node(null); /** Points to the last element in the list. */ protected Node last = header; /** Number of elements in the list. */ protected int length = 0; /** Points to the last referenced element. */ protected Node current = header; /******************************************************************************* 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; while (current.next != null) { current = current.next; if (current.datum.equals(obj)) return true; } 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 != null); 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 != null; } /** Returns the next object in the list.

Requires: hasMoreElements()
Ensures: Returns next element in the enumeration. */ public Object nextElement() { if (current == null) return null; //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). 

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 != null) { 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 != null) { 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 = last; 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) { Node newNode = new Node(obj); last = current = last.next = newNode; 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. Node previous = goToPrevious(index); previous.next = current = new Node(obj, previous.next); if (previous == last) last = current; } /** Empty the container. 

Requires: True
Ensures: sequence = null // the empty sequence.
*/ synchronized public void removeAll() { last = current = header; length = 0; } /** Remove and return the first element in the sequence. If the sequence is empty, return null. Should not store null in the list but can disambiguate with a check on not empty before the remove. 

Requires: isEmpty = true or false
Ensures: old sequence = obj ^ sequence
*/ synchronized public Object remove() { if (length > 0) { Object result = header.next.datum; removeAt(0); return result; } else { return null;} } /** 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) { Node previous = header; current = header.next; while (current != null) { if (current.datum.equals(obj)) { length--; current = previous.next = current.next; if (current == null) { current = last = previous; } return true; } previous = current; current = current.next; } current = last; 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) { Node previous = goToPrevious(index); if (previous.next == last) { current = last = previous; previous.next = null; } else { previous.next = current = previous.next.next; } length--; } /** 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) { if (index == length) { last.datum = obj; } else { 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 list
*/ synchronized public Object clone() { SLList result = new SLList(); Node current = header.next; while (current != null) { 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("[ "); Enumeration e = elements(); result.append(e.nextElement().toString()); while (e.hasMoreElements()) { result.append(" " + e.nextElement().toString()); } result.append(" ]"); return result.toString(); } /** Check for equality of contents of two lists. By equality we mean an 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 SLList) { SLList otherList = (SLList) 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 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); } /** Returns a pointer to the predecessor of the element at the specified index. For valid indices a predecessor always exists due to the dummy header element. 

Requires: True
Ensures: 0 <= index < size or throws exception
@return ^sequence[index-1] @exception SequenceIndexException when index is out of bounds. */ private Node goToPrevious(final int index) { verifyIndex(index); Node previous = header; int currentIndex = 0; while (currentIndex < index) { currentIndex++; previous = previous.next; } return previous; } /** Insert the argument list 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]
               ^ clone(newSequence[first..last])
               ^ old sequence[index..last]
@exception SequenceIndexException when index is out of bounds. */ synchronized public void insertAt(final SLList list, final int index) { if (!list.isEmpty()) { length += 1; // Add to length to make the new index valid. Node previous = goToPrevious(index); list.last.next = previous.next; previous.next = list.header.next; if (previous == last) last = list.last; length += list.length - 1; // increase length. already added 1 earlier. current = previous; } } } // End of class