org.ceryle.util
Class StackSet

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<E>
          java.util.Vector<E>
              java.util.Stack
                  org.ceryle.util.StackSet

All Implemented Interfaces:

Serializable, Cloneable, Iterable, Collection, List, RandomAccess, Set

public class StackSet
extends Stack
implements List, Set

StackSet extends java.util.Stack (a class that represents a last-in-first-out (LIFO) stack of objects, but in this case also includes methods making it addressable at any level) to implement the java.util.Set interface, guaranteeing that all elements in the Stack are unique. Because it is ultimately backed by a Vector, iterator order follows the element order. This provides the missing cross between the List and Set interfaces.

Additionally, this class has a number of important features:

• is able to sort its contents according to the natural ordering of its elements. In this case, all elements in the StackSet must implement the Comparable interface. Furthermore, all elements in the StackSet must be mutually comparable (that is, e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the StackSet.
• it has the ability to rotate its contents forward (top-to-bottom or backward (bottom-to-top), using the rotateUp() and rotateDown() methods.
• there's a rotateToTop() method to rotate a specific object to the top of the stack.

This class had evolved to a point where its proper name would have been AddressableSortedQueueStackSet, but this was such a mouthful that the name was in the end just shortened to StackSet.

Since:

JDK1.2

Version:

$Id: StackSet.java,v 3.5 2007-06-15 12:09:57 altheim Exp $

Author:

Murray Altheim

See Also:

AddressableStack, Stack, Serialized Form

Field Summary

static int

BOTTOM An indicator of the maximum depth or bottom of the stack.

Fields inherited from class java.util.Vector

capacityIncrement, elementCount, elementData

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

StackSet()
Creates an empty StackSet.

StackSet(Collection c)
Creates an StackSet containing the unique members of the Collection c, in the reverse of the order that the Collection's iterator provides them since they're being pushed onto a stack).

Method Summary

void	add(int index, Object element) If the specified object does not already exist in the stack, inserts the specified element at the specified position in this stack.
boolean	add(Object o) If the specified object does not already exist in the stack, appends the specified element to the end of this Vector.
boolean	addAll(Collection c) Appends all of the elements in the specified Collection that are not already part of this StackSet to the end of the stack, in the order that they are returned by the specified Collection's Iterator.
boolean	addAll(int index, Collection c) This method would have inserted all of the elements in the specified Collection not already in this stack into this StackSet at the specified position.
void	addElement(Object obj) If the specified object does not already exist in the stack, adds the specified component to the end of this stack, increasing its size by one.
void	insertElementAt(Object obj, int index) If the specified object does not already exist in the stack, inserts it as a component in this stack at the specified index.
boolean	moveToBeginning(Object o) Moves the Object o to the first element position in the model.
Object	peek(int depth) Looks at the object at the specific depth in this stack without removing it from the stack.
Object	pop(int depth) Pops the object at the specific depth from the stack.
Object	push(Object item) If the specified item does not already exist in the stack, pushes the item onto the top of this stack.
void	removeBottom() Removes the first element of this StackSet.
void	rotateDown() Rotates the stack by removing the first (ie., bottom) element and pushing it onto the end (ie., top) of the stack.
void	rotateDown(int count) Rotates the stack count times by repeatedly removing the first (ie., bottom) element and pushing it onto the end (ie., top) of the stack.
void	rotateToTop(Object o) Rotates the stack as necessary to move the Object o to the top of the stack.
void	rotateUp() Rotates the stack by popping the last (ie., top) element and inserting it at the beginning (ie., bottom) of the stack.
void	rotateUp(int count) Rotates the stack count times by repeatedly popping the last (ie., top) element and inserting it at the beginning (ie., bottom) of the stack.
Object	set(int index, Object element) If the specified object does not already exist in the stack, replaces the element at the specified position in this StackSet with the specified element.
void	setElementAt(Object obj, int index) If the specified object does not yet exist in the Set, sets the component at the specified index of this stack to be the specified object.
void	sort() Sorts the stack's objects into ascending order, according to the natural ordering of its elements.

Methods inherited from class java.util.Stack

empty, peek, pop, search

Methods inherited from class java.util.Vector

capacity, clear, clone, contains, containsAll, copyInto, elementAt, elements, ensureCapacity, equals, firstElement, get, hashCode, indexOf, indexOf, isEmpty, lastElement, lastIndexOf, lastIndexOf, remove, remove, removeAll, removeAllElements, removeElement, removeElementAt, removeRange, retainAll, setSize, size, subList, toArray, toArray, toString, trimToSize

Methods inherited from class java.util.AbstractList

iterator, listIterator, listIterator

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.List

clear, contains, containsAll, equals, get, hashCode, indexOf, isEmpty, iterator, lastIndexOf, listIterator, listIterator, remove, remove, removeAll, retainAll, size, subList, toArray, toArray

Methods inherited from interface java.util.Set

clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray

Field Detail

BOTTOM

public static final int BOTTOM

An indicator of the maximum depth or bottom of the stack.

See Also:

Constant Field Values

Constructor Detail

StackSet

public StackSet()

Creates an empty StackSet.

StackSet

public StackSet(Collection c)

Creates an StackSet containing the unique members of the Collection c, in the reverse of the order that the Collection's iterator provides them since they're being pushed onto a stack).

Method Detail

peek

public Object peek(int depth)

Looks at the object at the specific depth in this stack without removing it from the stack.

Parameters:

depth - an int indicating the peeking depth (zero indicates the top, BOTTOM the bottom)

Returns:

the object at the location depth from the top of this stack

Throws:

EmptyStackException - if this stack is empty

pop

public Object pop(int depth)

Pops the object at the specific depth from the stack.

Parameters:

depth - an int indicating the peeking depth (zero indicates the top, BOTTOM the bottom)

Returns:

the object at the location depth from the top of this stack

Throws:

EmptyStackException - if this stack is empty

setElementAt

public void setElementAt(Object obj,
                         int index)

If the specified object does not yet exist in the Set, sets the component at the specified index of this stack to be the specified object. The previous component at that position is discarded.

The index must be a value greater than or equal to 0 and less than the current size of the stack.

Overrides:

setElementAt in class Vector

Parameters:

obj - what the component is to be set to.

index - the specified index.

Throws:

ArrayIndexOutOfBoundsException - if the index was invalid.

insertElementAt

public void insertElementAt(Object obj,
                            int index)

If the specified object does not already exist in the stack, inserts it as a component in this stack at the specified index. Each component in this stack with an index greater or equal to the specified index is shifted upward to have an index one greater than the value it had previously (this method is really with regard to the stack's underlying Vector).

The index must be a value greater than or equal to 0 and less than or equal to the current size of the stack. (If the index is equal to the current size of the stack, the new element is pushed onto the stack.)

Overrides:

insertElementAt in class Vector

Parameters:

obj - the component to insert.

index - where to insert the new component.

Throws:

ArrayIndexOutOfBoundsException - if the index was invalid.

addElement

public void addElement(Object obj)

If the specified object does not already exist in the stack, adds the specified component to the end of this stack, increasing its size by one. The capacity of this stack is increased if its size becomes greater than its capacity.

Note: null parameters are ignored.

Overrides:

addElement in class Vector

Parameters:

obj - the component to be added.

set

public Object set(int index,
                  Object element)

If the specified object does not already exist in the stack, replaces the element at the specified position in this StackSet with the specified element.

Specified by:

set in interface List

Overrides:

set in class Vector

Parameters:

index - index of element to replace.

element - element to be stored at the specified position.

Returns:

the element previously at the specified position, or if the element already existed in , returns the provided one

Throws:

ArrayIndexOutOfBoundsException - index out of range (index < 0 || index >= size()).

IllegalArgumentException - fromIndex > toIndex.

Since:

1.2

add

public boolean add(Object o)

If the specified object does not already exist in the stack, appends the specified element to the end of this Vector.

Note: null parameters are ignored.

Specified by:

add in interface Collection

Specified by:

add in interface List

Specified by:

add in interface Set

Overrides:

add in class Vector

Parameters:

o - element to be appended to this Vector.

Returns:

true if the object was added

Since:

1.2

add

public void add(int index,
                Object element)

If the specified object does not already exist in the stack, inserts the specified element at the specified position in this stack. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Note: null parameters are ignored.

Specified by:

add in interface List

Overrides:

add in class Vector

Parameters:

index - index at which the specified element is to be inserted.

element - element to be inserted.

Throws:

ArrayIndexOutOfBoundsException - index is out of range (index < 0 || index > size()).

Since:

1.2

addAll

public boolean addAll(Collection c)

Appends all of the elements in the specified Collection that are not already part of this StackSet to the end of the stack, in the order that they are returned by the specified Collection's Iterator. The behavior of this operation is undefined if the specified Collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified Collection is this stack, and the stack is nonempty.)

Specified by:

addAll in interface Collection

Specified by:

addAll in interface List

Specified by:

addAll in interface Set

Overrides:

addAll in class Vector

Parameters:

c - elements to be inserted into this StackSet.

Throws:

ArrayIndexOutOfBoundsException - index out of range (index < 0 || index > size()).

Since:

1.2

addAll

public boolean addAll(int index,
                      Collection c)

This method would have inserted all of the elements in the specified Collection not already in this stack into this StackSet at the specified position. This is included here for compliance with the Set interface, but because there is no guarantee that all elements will be added, and that order may not be preserved as a result, using this method would likely be more confusing than is worth the trouble. Also, this method is not really appropriate to stacks anyway.

Specified by:

addAll in interface List

Overrides:

addAll in class Vector

Throws:

ArrayIndexOutOfBoundsException - index out of range (index

push

public Object push(Object item)

If the specified item does not already exist in the stack, pushes the item onto the top of this stack. This has exactly the same effect as:

 addElement(item)

Overrides:

push in class Stack

Parameters:

item - the item to be pushed onto this stack.

Returns:

the item argument.

See Also:

Vector.addElement(Object)

sort

public void sort()

Sorts the stack's objects into ascending order, according to the natural ordering of its elements. All elements in the stack must implement the Comparable interface. Furthermore, all elements in the array must be mutually comparable (that is, e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the stack).

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

For very large sets this may not be the most efficient way to perform a sort, as this method offloads its contents into an array, sorts, then reloads from the array. But given that sorting in a Collection would likely be slow and that array processing in Java is very fast, it's not likely there's a much better way.

PLEASE NOTE: As of 2005-01-04 it is noted that the sorting facility for StackSet seems to not work under all circumstances. The bug is noted.

See Also:

Arrays.sort(Object[])

moveToBeginning

public boolean moveToBeginning(Object o)

Moves the Object o to the first element position in the model. If the stack doesn't already contain the Object, it is added. Returns true if the object was new to the list.

rotateToTop

public void rotateToTop(Object o)
                 throws NoSuchElementException

Rotates the stack as necessary to move the Object o to the top of the stack. If the object is not a member of the stack, nothing occurs.

Throws:

NoSuchElementException

rotateUp

public void rotateUp(int count)

Rotates the stack count times by repeatedly popping the last (ie., top) element and inserting it at the beginning (ie., bottom) of the stack.

rotateUp

public void rotateUp()

Rotates the stack by popping the last (ie., top) element and inserting it at the beginning (ie., bottom) of the stack.

rotateDown

public void rotateDown(int count)

Rotates the stack count times by repeatedly removing the first (ie., bottom) element and pushing it onto the end (ie., top) of the stack.

rotateDown

public void rotateDown()

Rotates the stack by removing the first (ie., bottom) element and pushing it onto the end (ie., top) of the stack.

removeBottom

public void removeBottom()
                  throws EmptyStackException

Removes the first element of this StackSet.

Throws:

EmptyStackException