DSInterfaces.java

Basic Description

This file contains the list of interfaces that should be fulfilled. They define the basic functionality of the data structures that you should be working on building.

The interfaces

The interfaces revolve around different types of data structures. The methods they call for define what the basic behavior of a data structure of that datatype.

The interfaces are named starting with the capital letter I, for Interface. This is borrowed from COM, and XPCOM in particular. They also all use type T for the type of data they are holding, which comes from the Java 1.5 collections library.

IDS

This is the basic data structure interface. It defines the behavior of ALL data structures.

Methods:

void add(T)

This adds a T to the data structure. A data structure that can’t have Ts added to it wouldn’t be very useful, now, would it?

boolean contains(T)

This tests whether a T is in the data structure or not. What good is putting something in there if you can’t even tell that you did it afterwords

List<T> asList()

This gets the elements of the data structure as a java.util.List<T>. This is mostly used for testing purposes (see DSTest.java).

String toString()

Describes how this data structure should be displayed to users. Also used in testing.

int size()

Returns how many items are contained in this data structure. An empty data structure should have size 0.

void empty()

Empties the data structure of all data stored inside. size() should now return 0.

ILinkedList

This describes linked lists. Right now, doubly and singly linked lists are requested.

The Methods

void sort()

Sorts the elements within the list. Now, iterating over the list should return the elements in sorted order.

T getFirst()

Returns the first element in the list. After being sorted, this should return the least element in the list.

T getLast()

Returns the last element in the list. After being sorted, this should return the greatest element in the list.

T get(int i)

Returns the ith element of the list, starting from 0. So, get(0) = = getFirst(), and get(size() - 1) = = getLast() should be satisfied for every list.

IQueue

This describes queues. Both a queue and a priority queue should be given.

The Methods

void enqueue(T)

This should be the same as add().

T dequeue()

This should return the next item, removing it from the queue.

IStack

This describes stacks.

The Methods

void push()

This should be the same as add().

T pop()

This should return the next item, removing it from the stack.

IBTree

This describes binary trees. In particular, this describes binary search trees.

The Methods

Iterator<T> inOrder()

This defines in-order traversal of the tree. When this iterator is used, the elements of the tree should be iterated such that lesser elements are seen before greater elements.

Iterator<T> postOrder()

This defines post-order traversal of the tree.

Iterator<T> preOrder()

This defines pre-order traversal of the tree.

IMap

This defines a mapping between two data types, K and V. Note that these are used rather than the T used in the previous interfaces.

The Methods

void set(K key, V value)

Associates key with value.

V get(K key)

Returns the value associated with key, if there is one. Otherwise, this should return null.