Question: For this project, you will be creating three custom data structures that need to meet certain runtime performance requirements. Youll create two distinct list structures
For this project, you will be creating three custom data structures that need to meet certain
runtime performance requirements. Youll create two distinct list structures (lists that prohibit
duplicates) - one that provides random access and one that provides sequential access. Youll
also create a red-black tree based map structure that has an insertion-order iterator and
methods that provide sorted-order indexed based key access. Your structures must conform to
the java.util.List and java.util.Map interfaces, respectively.
Runtime Performance Requirements
The methods in your distinct random access list implementation must meet the following runtime
performance requirements.
Method Runtime
add (int, E) linear
get constant
contains constant
indexOf linear
set constant
remove (Object) linear
remove (int) linear
The methods in your distinct sequential access list implementation must meet the following
runtime performance requirements.
Method Runtime
add (int, E) linear
get linear
contains constant
indexOf linear
set linear
remove (Object) linear
remove (int) linear
The methods in your red-black tree implementation must meet the following runtime
performance requirements.
Method Runtime
put logarithmic
get logarithmic
indexOf logarithmic
keyAt logarithmic
containsKey logarithmic
Guidance and Supplemental Requirements
The first thing you should do is create the barebones classes that are sufficient for
executing the provided test harnesses.
Your distinct random-access list must implement java.util.RandomAccess.
a TreeMap class that provides a
basic red-black tree implementation. To create this class, the instructor basically copied
the source code of java.util.TreeMap and then removed all functionality thats not
essential for conforming to the java.util.Map interface. This means that the provide
TreeMap class does not implement java.util.NavigableMap or java.util.SortedMap, and
thats okay for this project.
Copy that provided map class and use that as a starting point for your map class.
Thus, you wont have to implement the red-black mechanics yourself for this
project.
Your map must implement the provided IndexedMap and LinkedMap interfaces.
There are a multitude of ways of approaching solutions. Before you start implementing,
try to slow down and consider various approaches. Try to keep your solutions as simple
as possible and re-use existing classes (especially in java.util) where possible; that will
reduce the amount of coding youll have to do.
***Tree Map Class***
public class TreeMap
extends AbstractMap
/**
* The RED marker.
*/
private static final boolean RED = false;
/**
* The BLACK marker.
*/
private static final boolean BLACK = true;
/**
* Comparators are not used.
*/
private final Comparator
/**
* The tree root.
*/
private Entry
/**
* The set of Entry objects.
*/
private EntrySet entrySet;
/**
* The number of entries in the tree.
*/
private int size = 0;
/**
* The number of structural modifications to the tree.
*/
private int modCount = 0;
/**
* Sole constructor.
*/
public TreeMap() {
super();
}
/* (non-Javadoc)
* @see java.util.AbstractMap#entrySet()
*/
@Override
public Set
if (entrySet == null)
entrySet = new EntrySet();
return entrySet;
}
/* (non-Javadoc)
* @see java.util.AbstractMap#put(java.lang.Object, java.lang.Object)
*/
@Override
public V put(final K key, final V value) {
Entry
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry
if (key == null)
throw new NullPointerException();
Comparable k = (Comparable) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
Entry
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
/* (non-Javadoc)
* @see java.util.AbstractMap#size()
*/
@Override
public int size() {
return size;
}
/**
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
public void clear() {
modCount++;
size = 0;
root = null;
}
/**
* Re-balances the tree after an insertion event.
* Algorithm taken from CLR.
* @param entry Rebalancing beging at this node.
*/
private void fixAfterInsertion(final Entry
Entry
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
/**
* From CLR.
* @param p The root of the subtree being rotated.
*/
private void rotateLeft(final Entry
if (p != null) {
Entry
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
/**
* From CLR.
* @param p The root of the subtree being rotated.
*/
private void rotateRight(final Entry
if (p != null) {
Entry
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
/**
* Delete node d, and then rebalance the tree.
* @param d The node to delete.
*/
private void deleteEntry(final Entry
Entry
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
Entry
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
Entry
if (replacement != null) {
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = null;
p.right = null;
p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
/**
* Re-balances after a deletion event. From CLR.
* @param node The node from which to start re-balancing.
*/
private void fixAfterDeletion(final Entry
Entry
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK
&& colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
Entry
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK
&& colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
/**
* Compares two keys using the correct comparison method for this TreeMap.
* @param k1 first key
* @param k2 second key
* @return {@link Comparable#compareTo(Object)}.
*/
@SuppressWarnings("unchecked")
final int compare(final Object k1, final Object k2) {
return comparator == null ? ((Comparable) k1).compareTo((K) k2)
: comparator.compare((K) k1, (K) k2);
}
/**
* Returns the first Entry in the TreeMap (according to the TreeMap's
* key-sort function). Returns null if the TreeMap is empty.
* @return the first Entry in the TreeMap (according to the TreeMap's
* key-sort function), or null if the TreeMap is empty.
*/
final Entry
Entry
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
/**
* Returns this map's entry for the given key, or {@code null} if the map
* does not contain an entry for the key.
*
* @param key The key of the entry to return.
* @return this map's entry for the given key, or {@code null} if the map
* does not contain an entry for the key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
final Entry
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable k = (Comparable) key;
Entry
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
/**
* Returns the color of p.
* @param p The node whose color gets returned.
* @param
* @param
* @return the color of p
*/
private static
return (p == null ? BLACK : p.color);
}
/**
* Returns the parent of p.
* @param p The node to query.
* @param
* @param
* @return the color of p
*/
private static
return (p == null ? null : p.parent);
}
/**
* Sets the color of p.
* @param p The node to set.
* @param c either {@link TreeMap#RED} or {@link TreeMap#BLACK}.
* @param
* @param
*/
private static
if (p != null)
p.color = c;
}
/**
* Returns the left child of p.
* @param p The node to query.
* @param
* @param
* @return the left child of p.
*/
private static
return (p == null) ? null : p.left;
}
/**
* Returns the right child of p.
* @param p The node to query.
* @param
* @param
* @return the right child of p.
*/
private static
return (p == null) ? null : p.right;
}
/**
* Test two values for equality. Differs from o1.equals(o2) only in
* that it copes with {@code null} o1 properly.
* @param o1 first object
* @param o2 second object
* @return whether o1 and o2 are equal.
*/
static final boolean valEquals(final Object o1, final Object o2) {
return (o1 == null ? o2 == null : o1.equals(o2));
}
/**
* Returns the successor of the specified Entry, or null if no such.
* @param t The node to query.
* @param
* @param
* @return the successor of the specified Entry, or null if no such.
*/
static
if (t == null)
return null;
else if (t.right != null) {
Entry
while (p.left != null)
p = p.left;
return p;
} else {
Entry
Entry
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
/**
* Returns the predecessor of the specified Entry, or null if no such.
* @param t The node to query.
* @param
* @param
* @return the predecessor of the specified Entry, or null if no such.
*/
static
if (t == null)
return null;
else if (t.left != null) {
Entry
while (p.right != null)
p = p.right;
return p;
} else {
Entry
Entry
while (p != null && ch == p.left) {
ch = p;
p = p.parent;
}
return p;
}
}
/**
* Models a red-black tree Entry / Node.
* @author Anwar Reddick copied the Java source.
*
* @param
* @param
*/
static final class Entry
/**
* key.
*/
K key;
/**
* value.
*/
V value;
/**
* left child.
*/
Entry
/**
* right child.
*/
Entry
/**
* parent node.
*/
Entry
/**
* default is black.
*/
boolean color = BLACK;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
* @param key key
* @param value value
* @param parent parent
*/
Entry(final K key, final V value, final Entry
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
*
* @param value the new value.
* @return the value associated with the key before this method was
* called
*/
public V setValue(final V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
/* (non-Javadoc)
* @see java.lang.Object#equals(java.lang.Object)
*/
@Override
public boolean equals(final Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
return valEquals(key, e.getKey()) && valEquals(value, e.getValue());
}
/* (non-Javadoc)
* @see java.lang.Object#hashCode()
*/
@Override
public int hashCode() {
int keyHash = (key == null ? 0 : key.hashCode());
int valueHash = (value == null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return key + "=" + value;
}
}
/**
* A set of {@link Entry} objects from the map.
*
* @author Anwar Reddick
*
*/
class EntrySet extends AbstractSet
/* (non-Javadoc)
* @see java.util.AbstractCollection#iterator()
*/
@Override
public Iterator
return new EntryIterator(getFirstEntry());
}
/* (non-Javadoc)
* @see java.util.AbstractCollection#contains(java.lang.Object)
*/
@Override
public boolean contains(final Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry entry = (Map.Entry) o;
Object value = entry.getValue();
Entry
return p != null && valEquals(p.getValue(), value);
}
/* (non-Javadoc)
* @see java.util.AbstractCollection#remove(java.lang.Object)
*/
@Override
public boolean remove(final Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry entry = (Map.Entry) o;
Object value = entry.getValue();
Entry
if (p != null && valEquals(p.getValue(), value)) {
deleteEntry(p);
return true;
}
return false;
}
/* (non-Javadoc)
* @see java.util.AbstractCollection#size()
*/
@Override
public int size() {
return TreeMap.this.size();
}
/* (non-Javadoc)
* @see java.util.AbstractCollection#clear()
*/
@Override
public void clear() {
TreeMap.this.clear();
}
}
/**
* Base class for TreeMap Iterators.
* @param
*/
abstract class PrivateEntryIterator
/**
* next entry.
*/
Entry
/**
* The entry that was most recently returned by nextEntry or prevEntry.
*/
Entry
/**
* Expected # of modifications to the underlying map caused by calls to
* methods on this class.
*/
int expectedModCount;
/**
* Initializes fields.
* @param first the beginning entry.
*/
PrivateEntryIterator(final Entry
expectedModCount = modCount;
lastReturned = null;
next = first;
}
/* (non-Javadoc)
* @see java.util.Iterator#hasNext()
*/
@Override
public final boolean hasNext() {
return next != null;
}
/**
* Returns the next entry object and moves the cursor forward.
* @return the next entry object.
*/
final Entry
Entry
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e);
lastReturned = e;
return e;
}
/**
* Returns the previous entry object and moves the cursor backward.
* Repeatedly calling this and nextEntry will repeatedly result in the
* same object being returned.
* @return the previous entry object.
*/
final Entry
Entry
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = predecessor(e);
lastReturned = e;
return e;
}
/* (non-Javadoc)
* @see java.util.Iterator#remove()
*/
@Override
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// deleted entries are replaced by their successors
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
deleteEntry(lastReturned);
expectedModCount = modCount;
lastReturned = null;
}
}
/**
* The primary iterator. No other iterators from {@link java.util.TreeMap}
* were copied into this class.
*
* @author Anwar Reddick
*
*/
final class EntryIterator extends PrivateEntryIterator
/**
* Initializes - first will be the first object processed in the first
* call to next.
* @param first the first object to be processed in the first
* call to next.
*/
EntryIterator(final Entry
super(first);
}
/* (non-Javadoc)
* @see java.util.Iterator#next()
*/
@Override
public Map.Entry
return nextEntry();
}
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help