A set of unchanging (static) data structures, which return clones every time they are modified, and their equivalent dynamic counterparts.

Static vs. Dynamic

Traditional Java data structures, such as {@link java.util.LinkedList} and {@link java.util.HashMap}, are "dynamic," meaning that their internal state is changed every time a modifying method such as add() or remove() is called.

A "static" data structure remains unchanged when modifying methods are called. Instead of changing the state of the object, these methods return a new instance of that class which realizes the change.

For example, calling {@link sdds.SList#add} on {@link sdds.SList} does not add an element to the list. It returns a new SList which does contain the added element. The original object is unchanged.

Static data structures are useful when every stage of a changing data structure needs to be preserved. Using static data structures is more space and time efficient than constantly cloning a dynamic data structure. For instance, adding an element to an {@link sdds.SList} takes O(1) time, as opposed to cloning a {@link java.util.LinkedList} and adding an element to it, which takes O(n) time for a list of size n.

For convenience, dynamic versions of every static data structure are also provided so that, if you choose, all your data structures can obey the same interface. The performance of the dynamic data structures is roughly equivalent to the java.util structures that they mimic.

Currently, the following data structures have been implemented:

Thread Safety

Static data structures are thread safe because their internal state never changes. Their dynamic equivalents have been synchronized to make them thread safe as well.

Equals vs ==

By default, data structures test equality using == because it is faster. If you wish to use {@link java.lang.Object#equals}, equivalent methods are provided. For example, {@link sdds.SList} provides both {@link sdds.SList#contains} and {@link sdds.SList#containsEquals}.

Subclassing a Static Data Structure

Each static data structure defines a protected method called makeName, where Name is the name of the data structure. The method takes the same argument as the class's main constructor. All modifying methods, such as add() and remove() use this method when creating new instances of the class.

The purpose of these make methods is to allow easy subclassing of static structures.

For example, say we wanted to define a subclass of {@link sdds.SList}, called SQueue, that has a getFirst() method. Every modifying method of SList would need to be rewritten in SQueue so that it would return an instance of SQueue rather than SList. However, because all modifying methods in SList use makeList(int, Node) to create their clones, we can simply override makeList, like so:

public class SQueue<O> extends SList<O> {

	// SQueue keeps track of its first node.
	protected final Node<O> first;

	// This is the main constructor for SQueue.
	protected SQueue(int size, Node<O> last, Node<O> first){
		super(size, last);
		this.first = first;
	}

	// Overrides SList#makeList.
	protected SQueue<O> makeList(int size, Node<O> last){
		return new SQueue<O>(size, last, first);
	}

	// Empty constructor.
	public SQueue(){
		super();
		first = null;
	}

	// Get the first element of the SQueue.
	public O getFirst(){
		if(length == 0) return null;
		else return first.content;
	}

	// Overrides SList#add, but can still use super.add thanks to makeList!
	public SQueue<O> add(O element){
		if(length == 0){
			Node<O> first = new Node<O>(element, null);
			return new SQueue<O>(1, first, first);
		}
		else return (SQueue<O>) super.add(element);
	}

	/* ... other modifying methods here ... */
}