Package sdds

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

See:
          Description

Class Summary
DHashTable<K,V> A simple dynamic HashTable.
DList<O> A dynamic singly-linked List.
HashTable<K,V> A simple hash-table (the abstract superclass of DHashTable and SHashTable).
List<O> A singly-linked list (the abstract superclass of DList and SList).
SHashTable<K,V> A simple static HashTable.
SList<O> A static singly-linked List.
 

Package sdds Description

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 LinkedList and 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 add(O) on 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 SList takes O(1) time, as opposed to cloning a 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 Object.equals(java.lang.Object), equivalent methods are provided. For example, SList provides both List.contains(O) and List.containsEquals(O).

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 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 ... */
}