Overview Sequences and sets are two foundational abstract datatypes that appear
ID: 3597578 • Letter: O
Question
Overview
Sequences and sets are two foundational abstract datatypes that appear in diverse forms everywhere in computing. As we have discussed in class, sequences are defined as ordered collections of objects of the same type; while sets are unordered collections of distinct objects of the same type. As part of our in-class discussions we have discussed several different mechanisms for implementing these mathematical types - for sequences we covered array-based, and dynamic link-based representations; and for sets we covered (thus far), the bit-set, binary search tree, and AVL-tree representations.
Sequences
As we have already seen, sequences are an abstract datatype representing the notion of ordered collections of objects of the same type. This tells us what the objects which inhabit this datatype look like, but not the operations that we can reasonably perform on them. To help with this, we can turn to the Sequence<T> interface given below in the Java programming language:
public interface Sequence<T> {
/**
* Adds the specified object to the end of the sequence.
*
* @param obj object to be appended to this sequence
*/
void add(T obj);
/**
* Adds the specified object at the given position in the sequence.
*
* @param idx index at which the specified object is to be inserted
* @param obj object to be appended to this sequence
* @throws IndexOutOfBoundsException if the index is out of range
* (index < 0 || index > size())
*/
void add(int idx, T obj) throws IndexOutOfBoundsException;
/**
* Removes all of the elements from the sequence.
*/
void clear();
/**
* Returns the object at the specified position in the sequence.
*
* @param idx index of the element to return
* @return the object at the specified position in the sequence
* @throws IndexOutOfBoundsException if the index is out of range
* (index < 0 || index > size())
*/
T get(int idx) throws IndexOutOfBoundsException;
/**
* Returns {@code true} if the sequence contains the specified object and
* {@code false} otherwise.
*
* @param obj the object to find in the sequence
* @return {@code true} if the sequence contains the specified object and
* {@code false} otherwise
*/
boolean contains(T obj);
/**
* Returns the index of the first occurrence of the specified object in
* this sequence, or -1 if object is not present.
*
* @param obj the object to find in the sequence
* @return the index of the first occurrence of the specified object in
* this sequence, or -1 if object is not present
*/
int indexOf(T obj);
/**
* Returns {@code true} if the sequence is empty and {@code false}
* otherwise.
*
* @return {@code true} if the sequence is empty and {@code false}
* otherwise
*/
boolean isEmpty();
/**
* Removes the object at the specified position in the sequence.
*
* @param idx index of the element to remove
* @return the object previously at the specified position
* @throws IndexOutOfBoundsException if the index is out of range
* (index < 0 || index > size())
*/
T remove(int idx) throws IndexOutOfBoundsException;
/**
* Remove the first occurrence of the specified object from the sequence,
* if it is present.
*
* @param obj the object to remove
* @return {@code true} if the sequence contained the specified object and
* {@code false} otherwise
*/
boolean remove(T obj);
/**
* Returns the number of elements in the sequence.
*
* @return the number of elements in the sequence
*/
int size();
/**
* Returns an array containing all of the elements in the sequence in the
* proper order (from first to last).
*
* @return an array containing the elements of the sequence
*/
T[] toArray();
}
The first part of your project is to define a LinkedList<T> class which implements this interface. You will notice that there is no requirement to provide a definition for a toString() member function, this is left to your own discretion. In addition, pay attention to the specifications of the individual member functions: some of them may be of use in implementing others. Lastly, the interface only defines the minimal set of functions/methods that your implementation must provide (i.e. the public API through which objects of the LinkedList<T> type may be manipulated). This does not mean that you ought not define additional functions to help in implementing these.
Sets
Sequences are an abstract datatype representing the notion of ordered collections of objects of the same type. As before, this only tells us what the objects which inhabit this datatype look like, but not the operations that we can reasonably perform on them. To help with this, we can turn to the Set<T> interface given below in the Java programming language:
/**
* The {@code Set} interface defines a minimal suite of operations that are to
* be support by the Set abstract data type.
*
* @param <T> the type over which a {@code Set} is defined
* @version 1.0
*/
public interface Set<T> {
/**
* Adds the specified object to the set.
*
* @param obj object to be added to the set
*/
void add(T obj);
/**
* Removes all of the elements from the set.
*/
void clear();
/**
* Returns {@code true} if the set contains the specified object and
* {@code false} otherwise.
*
* @param obj the object to find in the set
* @return {@code true} if the set contains the specified object and
* {@code false} otherwise
*/
boolean contains(T obj);
/**
* Returns {@code true} if the set is empty and {@code false} otherwise.
*
* @return {@code true} if the set is empty and {@code false} otherwise
*/
boolean isEmpty();
/**
* Remove the specified object from the set, if it is present.
*
* @param obj the object to remove
* @return {@code true} if the set contained the specified object and
* {@code false} otherwise
*/
void remove(T obj);
/**
* Returns the number of elements in the set.
*
* @return the number of elements in the set
*/
int size();
/**
* Returns an array containing all of the objects in the set in the proper
* order (from least to greatest).
*
* @return an array containing the objects in the set
*/
T[] toArray();
}
The second part of your project is to define a BinarySearchTree<T> class which implements this interface. As in Part 1, there is no requirement to provide a definition for a toString() member function, this is left to your own discretion. Similarly, when implementing this interface, look for opportunities to generalize and simplify your implementation through the introduction of simplifying functions and procedures. Lastly, recall that the AVL-Tree datatype is an extension of a binary search tree. So when implementing your BinarySearchTree<T> class, be mindful so that you design it to be reused for implementing a subsequent AVLTree<T>.
Finally, keep in mind the invariant properties of a binary search tree, and use them as a guide in your implementation:
Every node has at most two children.
Consider any node X. Every node in the left subtree of X has a value less than X's, while every node in the right subtree of X has a value greater than X's.
Regarding Testing
You will notice that there is no main method or class specified in this assignment. This is on purpose for two reasons:
It is important for you to learn to design and implement your means of testing your implementations. Consequently, this is entirely up to you.
It is as important for you to learn to write programs/definitions which satisfy a specification. Towards that end, you will not know what the main method I will use to test your programs is like, aside from the fact that my program will operate under the assumption that your definitions meet the provided spec.
Explanation / Answer
/**
* Adds the specified object to the end of the sequence.
*
* @param obj object to be appended to this sequence
*/
void add(T obj);
/**
* Adds the specified object at the given position in the sequence.
*
* @param idx index at which the specified object is to be inserted
* @param obj object to be appended to this sequence
* @throws IndexOutOfBoundsException if the index is out of range
* (index < 0 || index > size())
*/
void add(int idx, T obj) throws IndexOutOfBoundsException;
/**
* Removes all of the elements from the sequence.
*/
void clear();
/**
* Returns the object at the specified position in the sequence.
*
* @param idx index of the element to return
* @return the object at the specified position in the sequence
* @throws IndexOutOfBoundsException if the index is out of range
* (index < 0 || index > size())
*/
T get(int idx) throws IndexOutOfBoundsException;
/**
* Returns {@code true} if the sequence contains the specified object and
* {@code false} otherwise.
*
* @param obj the object to find in the sequence
* @return {@code true} if the sequence contains the specified object and
* {@code false} otherwise
*/
boolean contains(T obj);
/**
* Returns the index of the first occurrence of the specified object in
* this sequence, or -1 if object is not present.
*
* @param obj the object to find in the sequence
* @return the index of the first occurrence of the specified object in
* this sequence, or -1 if object is not present
*/
int indexOf(T obj);
/**
* Returns {@code true} if the sequence is empty and {@code false}
* otherwise.
*
* @return {@code true} if the sequence is empty and {@code false}
* otherwise
*/
boolean isEmpty();
/**
* Removes the object at the specified position in the sequence.
*
* @param idx index of the element to remove
* @return the object previously at the specified position
* @throws IndexOutOfBoundsException if the index is out of range
* (index < 0 || index > size())
*/
T remove(int idx) throws IndexOutOfBoundsException;
/**
* Remove the first occurrence of the specified object from the sequence,
* if it is present.
*
* @param obj the object to remove
* @return {@code true} if the sequence contained the specified object and
* {@code false} otherwise
*/
boolean remove(T obj);
/**
* Returns the number of elements in the sequence.
*
* @return the number of elements in the sequence
*/
int size();
/**
* Returns an array containing all of the elements in the sequence in the
* proper order (from first to last).
*
* @return an array containing the elements of the sequence
*/
T[] toArray();
}
The first part of your project is to define a LinkedList<T> class which implements this interface. You will notice that there is no requirement to provide a definition for a toString() member function, this is left to your own discretion. In addition, pay attention to the specifications of the individual member functions: some of them may be of use in implementing others. Lastly, the interface only defines the minimal set of functions/methods that your implementation must provide (i.e. the public API through which objects of the LinkedList<T> type may be manipulated). This does not mean that you ought not define additional functions to help in implementing these.
Sets
Sequences are an abstract datatype representing the notion of ordered collections of objects of the same type. As before, this only tells us what the objects which inhabit this datatype look like, but not the operations that we can reasonably perform on them. To help with this, we can turn to the Set<T> interface given below in the Java programming language:
/**
* The {@code Set} interface defines a minimal suite of operations that are to
* be support by the Set abstract data type.
*
* @param <T> the type over which a {@code Set} is defined
* @version 1.0
*/
public interface Set<T> {
/**
* Adds the specified object to the set.
*
* @param obj object to be added to the set
*/
void add(T obj);
/**
* Removes all of the elements from the set.
*/
void clear();
/**
* Returns {@code true} if the set contains the specified object and
* {@code false} otherwise.
*
* @param obj the object to find in the set
* @return {@code true} if the set contains the specified object and
* {@code false} otherwise
*/
boolean contains(T obj);
/**
* Returns {@code true} if the set is empty and {@code false} otherwise.
*
* @return {@code true} if the set is empty and {@code false} otherwise
*/
boolean isEmpty();
/**
* Remove the specified object from the set, if it is present.
*
* @param obj the object to remove
* @return {@code true} if the set contained the specified object and
* {@code false} otherwise
*/
void remove(T obj);
/**
* Returns the number of elements in the set.
*
* @return the number of elements in the set
*/
int size();
/**
* Returns an array containing all of the objects in the set in the proper
* order (from least to greatest).
*
* @return an array containing the objects in the set
*/
T[] toArray();
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.