/****************************************************************************** CircularArray ---------------------------------------------------- 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 of a sequence of objects as a circular array. @author Gunnar Gotshalks @version 1.0 1999 Jan 16 @see Sequence */ public class CircularArray implements Sequence{ /******************************************************************************* Constructor Methods *******************************************************************************/ /** Establish the class invariant on an empty sequence.

Class invariant 

  isEmpty => length = 0 && (last-1) mod Capacity = first
  not isFull => length = (Capacity + head - last + 1) mod Capacity
@param capacity Create a CircularArray of the specified capacity. @throws TooSmallException if caller requests a capacity < 2 */ public CircularArray(int capacity) { if (capacity < 2) { throw new TooSmallException("Circular Array should have capacity >= 2"); } Capacity = capacity; sequence = new Object[Capacity]; } //***************************************************************************** /****************************************************************************** Defining the component objects *******************************************************************************/ /** Circular array storage area. */ protected Object[] sequence; /** Points to first item in the sequence. */ protected int first = 1; /** Points to the last item in the sequence. */ protected int last = 0; /** Number of elements in the sequence. */ protected int length = 0; /** Maximum number of elements that can be stored in the sequence. */ final int Capacity; /******************************************************************************* Access Methods *******************************************************************************/ /** Determines whether an element is in the sequence[first..last]. It is O(length) as the sequence must be searched sequentially. 

Requires: True
Ensures: contains(obj) => result = true
            not contains(obj) => result = false
*/ synchronized public boolean contains(Object obj) { int current = first; int workingLength = length; while (workingLength > 0) { if (sequence[current].equals(obj)) return true; current = (current+1) % Capacity; workingLength--; } return false; } /** Determines whether an element is in sequence[startIndex..last]. It is O(length) as potentially the entire sequence 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) { verifyIndex(startIndex); int current = (first + startIndex) % Capacity; int workingLength = length - startIndex; while (workingLength > 0) { if (sequence[current].equals(obj)) return true; current = (current+1) % Capacity; workingLength--; } 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 are more elements 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 workingLength > 0; } /** Returns the next object in the list.

Requires: hasMoreElements()
Ensures: Returns next element in the enumeration. */ public Object nextElement() { if (workingLength <= 0) throw new NoSuchElementException(); Object result = sequence[current]; current = (current+1) % Capacity; workingLength--; return result; } /** Keeps track of how more elements still to process. */ protected int workingLength = length; /* Points to the array element containing the next datum to return. */ protected int current = first; }; // End implementation of Enumeration } // End elements ////////////////////////////// /** Return the element at the specified index. 

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

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

Requires: True
Ensures: contains(obj) => sequence[result] = obj
            not contains(obj) => result = -1
*/ synchronized public int indexOf(final Object obj) { int current = first; int workingLength = length; while (workingLength > 0) { if (sequence[current].equals(obj)) { return ((current+Capacity) - first) % Capacity; } current = (current+1) % Capacity; workingLength--; } return -1; } /** Return the index of the specified element between the start index and the end of the sequence. 

Requires: True
Ensures: 
       sequence[startIndex..length-1].contains(obj) => sequence[result] = obj
   not sequence[startIndex..length-1].contains(obj) => result = -1
*/ synchronized public int indexOf(final Object obj, final int startIndex) { verifyIndex(startIndex); int current = (first + startIndex) % Capacity; int workingLength = length - startIndex; while (workingLength > 0) { if (sequence[current].equals(obj)) { return ((current+Capacity) - first) % Capacity; } current = (current+1) % Capacity; workingLength--; } return -1; } /** Returns true if the sequence is empty. 

Requires: True
Ensures: isEmpty = (length = 0)
*/ synchronized public boolean isEmpty() { return length == 0; } /** Returns true if the sequence is full. 

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

Requires: True
Ensures: isEmpty => result = null
        not isEmpty => result = sequence[last]
*/ synchronized public Object lastElement() { if (length > 0) { return sequence[last]; } else { return null; } } /** Return the number of elements in the sequence. 

Requires: True
Ensures: result = length
*/ synchronized public int size() { return length; } /** Returns the maximum number of elements that can be stored. */ synchronized public int capacity() { return Capacity; } /******************************************************************************* Update Methods *******************************************************************************/ /** Adds obj after the last element of the sequence. 

Requires: True
Ensures: sequence = old sequence ^ obj
@exception ContainerFullException when container already holds Capacity elements. */ synchronized public void add(final Object obj) { if (length < Capacity) { last = (last + 1) % Capacity; sequence[last] = obj; length++; } else { throw new ContainerFullException(); } } /** Adds obj after the last element of the sequence; if full, the thread waits until space is available. 

Requires: True
Ensures: sequence = old sequence ^ obj
*/ synchronized public void addWait(final Object obj) { while (length <= 0) { try { wait(); } catch (InterruptedException e) { /* Nothing to do */ } } last = (last + 1) % Capacity; sequence[last] = obj; length++; notify(); } /** 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. @exception ContainerFullException when container already contains Capacity elements. */ synchronized public void insertAt(final Object obj, final int index) { if (length < Capacity) { length++; verifyIndex(index); int finalIndex = (first + index) % Capacity; int current = first; first = (first + Capacity - 1) % Capacity; int prevIndex = first; while (current != finalIndex) { sequence[prevIndex] = sequence[current]; prevIndex = current; current = (current + 1) % Capacity; } sequence[prevIndex] = obj; } else { throw new ContainerFullException(); } } /** Empty the sequence. 

Requires: True
Ensures: sequence = null // the empty sequence.
*/ synchronized public void removeAll() { first = 1; last = 0; length = 0; } /** Remove the first element in the sequence. 

Requires: isEmpty = false
Ensures: old sequence = obj ^ sequence
@exception ContainerEmptyException when removing from an empty sequence. */ synchronized public Object remove() { if (length > 0) { Object result = sequence[first]; first = (first + 1) % Capacity; length--; return result; } else { throw new ContainerEmptyException(); } } /** Remove the first element in the sequence; if the queue is empty, the thread waits for a notify. 

Requires: isEmpty = false
Ensures: old sequence = obj ^ sequence
*/ synchronized public Object removeWait() { while (length <= 0) { try { wait(); } catch (InterruptedException e) { /* Nothing to do */ } } Object result = sequence[first]; first = (first + 1) % Capacity; length--; notify(); return result; } /** 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) { int index = indexOf(obj); if (index > -1) { length--; int workingIndex = (first + index) % Capacity; int finalIndex = last; int nextIndex = (workingIndex + 1) % Capacity; while (workingIndex != finalIndex) { sequence[workingIndex] = sequence[nextIndex]; workingIndex = nextIndex; nextIndex = (nextIndex+1) % Capacity; } last = (last + Capacity -1) % Capacity; return true; } else { 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) { verifyIndex(index); if (index == 0) { first = (first + 1) % Capacity; } else if (index == length - 1) { last = (last + Capacity - 1) % Capacity; } else { int workingIndex = (first + index) % Capacity; int finalIndex = last; int nextIndex = (workingIndex + 1) % Capacity; while (workingIndex != finalIndex) { sequence[workingIndex] = sequence[nextIndex]; workingIndex = nextIndex; nextIndex = (nextIndex+1) % Capacity; } last = (last + Capacity - 1) % Capacity; } length --; } /** Replace the object at the specified index. 
Requires: 0 <= index < size
Ensures: sequence[index] = obj
@exception SequenceIndexException when index is out of bounds. */ synchronized public void setAt(final Object obj, final int index) { verifyIndex(index); sequence[(first + index) % Capacity] = obj; } /** Return a copy of the sequence that points to the same objects as in the original sequence. 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() { CircularArray result = new CircularArray(Capacity); int current = first; int workingLength = length; while ( workingLength > 0 ) { result.add(sequence[current]); workingLength--; current = (current + 1) % Capacity; } return result; } /** Return a string representation of the contents of the sequence. 

Requires: True
Ensures: result = string representation of contents
*/ 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 sequences. By equality we mean an equal sequence of elements as returned by the Enumerator for each sequence. 

Requires: True
Ensures: result = true => sequences are equal
                result = false => sequences are not equal
*/ synchronized public boolean equals (final Object seq) { if (seq == null) return false; if (seq instanceof CircularArray) { CircularArray otherSeq = (CircularArray) seq; if (length != otherSeq.length) return false; Enumeration e1 = elements(); Enumeration e2 = otherSeq.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 sequence. 

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); } } // End of class