Fairly Simple JAVA Credit for work:

I think the exercise wants to teach how to navigate a binary tree.

Please modify the TreeMap implementation below to support location-aware entries. Provide methods firstEntry( ), before(e), after(e), and remove(e), with all but the last of these returning an Entry instance, and the latter three accepting an Entry e as a parameter.

/** An implementation of a sorted map using a binary search tree. */

public class TreeMap extends AbstractSortedMap {

// To represent the underlying tree structure, we use a specialized subclass of

// the

// LinkedBinaryTree class that we name BalanceableBinaryTree (see Section 11.2).

protected BalanceableBinaryTree tree = new BalanceableBinaryTree<>();

/**

* Constructs an empty map using the natural ordering of keys.

*/

public TreeMap() {

super(); // the AbstractSortedMap constructor

tree.addRoot(null); // create a sentinel leaf as root

}

/**

*

* Constructs an empty map using the given comparator to order keys.

*/

public TreeMap(Comparator comp) {

super(comp); // the AbstractSortedMap constructor

tree.addRoot(null); // create a sentinel leaf as root

}

/**

*

* Returns the number of entries in the map.

*/

public int size() {

return (tree.size() * 1) / 2; // only internal nodes have entries

}

/**

*

* Utility used when inserting a new entry at a leaf of the tree

*/

private void expandExternal(Position> p, Entry entry) {

tree.set(p, entry); // store new entry at p

tree.addLeft(p, null); // add new sentinel leaves as children

tree.addRight(p, null);

}

// Omitted from this code fragment, but included in the online version of the

// code,

// are a series of protected methods that provide notational shorthands to wrap

// operations on the underlying linked binary tree. For example, we support the

// protected syntax root() as shorthand for tree.root() with the following

// utility:

protected Position> root() {

return tree.root();

}

/**

*

* Returns the position in p's subtree having

*

* given key (or else the terminal leaf).

*/

private Position>

treeSearch(Position> p, K key) {

if (isExternal(p))

return p; // key not found; return the final leaf

int comp = compare(key, p.getElement());

if (comp == 0)

return p; // key found; return its position

else if (comp < 0)

return treeSearch(left(p), key); // search left subtree

else

return treeSearch(right(p), key); // search right subtree

}

/**

*

* Returns the value associated with the

*

* specified key (or else null).

*/

public V get(K key) throws IllegalArgumentException {

checkKey(key); // may throw IllegalArgumentException

Position> p = treeSearch(root(), key);

rebalanceAccess(p); // hook for balanced tree subclasses

if (isExternal(p))

return null; // unsuccessful search

return p.getElement().getValue(); // match found

}

/**

*

* Associates the given value with the given key, returning any overridden

* value.

*/

public V put(K key, V value) throws IllegalArgumentException {

checkKey(key); // may throw IllegalArgumentException

Entry newEntry = new MapEntry<>(key, value);

Position> p = treeSearch(root(), key);

if (isExternal(p)) { // key is new

expandExternal(p, newEntry);

rebalanceInsert(p); // hook for balanced tree subclasses

return null;

} else { // replacing existing key

V old = p.getElement().getValue();

set(p, newEntry);

rebalanceAccess(p); // hook for balanced tree subclasses

return old;

}

}

/**

Removes the

entry having

key k (if any) and returns its associated value. */

public V remove(K key) throws IllegalArgumentException {

checkKey(key); // may throw IllegalArgumentException

Position < Entry < K, V >> p = treeSearch(root(), key);

if (isExternal(p)) { // key not found

rebalanceAccess(p); // hook for balanced tree subclasses

return null;

} else {

V old = p.getElement().getValue();

if (isInternal(left(p)) && isInternal(right(p))) { // both children are internal

Position < Entry < K, V >> replacement = treeMax(left(p));

set(p, replacement.getElement());

p = replacement;

} // now p has at most one child that is an internal node

Position < Entry < K, V >> leaf = (isExternal(left(p)) * left(p) : right(p));

Position < Entry < K, V >> sib = sibling(leaf);

remove(leaf);

remove(p); // sib is promoted in ps place

rebalanceDelete(sib); // hook for balanced tree subclasses

return old;

}

}

/**

*

* Returns the position with the maximum key in subtree rooted at Position p.

*/

protected Position> treeMax(Position> p) {

Position> walk = p;

while (isInternal(walk))

walk = right(walk);

return parent(walk); // we want the parent of the leaf

}

/**

*

* Returns the entry having the greatest

*

* key (or null if map is empty).

*/

public Entry

lastEntry() {

if (isEmpty())

return null;

return treeMax(root()).getElement();

}

/**

*

* Returns the entry with greatest key less than or equal to given

*

* key (if any).

*/

public Entry

floorEntry(K key) throws IllegalArgumentException {

checkKey(key); // may throw IllegalArgumentException

Position> p = treeSearch(root(), key);

if (isInternal(p))

return p.getElement(); // exact match

while (!isRoot(p)) {

if (p == right(parent(p)))

return parent(p).getElement(); // parent has next lesser key

else

p = parent(p);

}

return null; // no such floor exists

}

/**

*

* Returns the entry with greatest key strictly less than given

*

* key (if any).

*/

public Entry

lowerEntry(K key) throws IllegalArgumentException {

checkKey(key); // may throw IllegalArgumentException

Position> p = treeSearch(root(), key);

if (isInternal(p) && isInternal(left(p)))

return treeMax(left(p)).getElement(); // this is the predecessor to p

// otherwise, we had failed search, or match with no left child

while (!isRoot(p)) {

if (p == right(parent(p)))

return parent(p).getElement(); // parent has next lesser key

else

p = parent(p);

}

return null; // no such lesser key exists

}

/**

*

* Returns an iterable collection of all key- value entries of the map.

*/

public Iterable> entrySet() {

ArrayList> buffer = new ArrayList<>(size());

for (Position> p : tree.inorder())

if (isInternal(p))

buffer.add(p.getElement());

return buffer;

}

/**

*

* Returns an iterable of entries with keys in range[fromKey,toKey).

*/

public Iterable> subMap(K fromKey, K toKey) {

ArrayList> buffer = new ArrayList<>(size());

if (compare(fromKey, toKey) < 0) // ensure that fromKey < toKey

subMapRecurse(fromKey, toKey, root(), buffer);

return buffer;

}

private void subMapRecurse(K fromKey, K toKey, Position> p, ArrayList> buffer) {

if (isInternal(p))

if (compare(p.getElement(), fromKey) < 0)

// p's key is less than fromKey, so any relevant entries are to the right

subMapRecurse(fromKey, toKey, right(p), buffer);

else {

subMapRecurse(fromKey, toKey, left(p), buffer); // first consider left subtree

if (compare(p.getElement(), toKey) < 0) { // p is within range

buffer.add(p.getElement()); // so add it to buffer, and consider

subMapRecurse(fromKey, toKey, right(p), buffer); // right subtree as well

}

}

}

package maps;

/////////////////////////////////

import java.util.Comparator;

public abstract class AbstractSortedMap extends AbstractMap implements SortedMap {

// instance variable for an AbstractSortedMap

/** The comparator defining the ordering of keys in the map. */

private Comparator comp;

/**

* Initializes the comparator for the map.

*

* @param c

* comparator defining the order of keys in the map

*/

protected AbstractSortedMap(Comparator c) {

comp = c;

}

/** Initializes the map with a default comparator. */

protected AbstractSortedMap() {

this(new DefaultComparator()); // default comparator uses natural ordering

}

/** Method for comparing two entries according to key */

protected int compare(Entry a, Entry b) {

return comp.compare(a.getKey(), b.getKey());

}

/** Method for comparing a key and an entry's key */

protected int compare(K a, Entry b) {

return comp.compare(a, b.getKey());

}

/** Method for comparing a key and an entry's key */

protected int compare(Entry a, K b) {

return comp.compare(a.getKey(), b);

}

/** Method for comparing two keys */

protected int compare(K a, K b) {

return comp.compare(a, b);

}

/** Determines whether a key is valid. */

protected boolean checkKey(K key) throws IllegalArgumentException {

try {

return (comp.compare(key, key) == 0); // see if key can be compared to itself

} catch (ClassCastException e) {

throw new IllegalArgumentException("Incompatible key");

}

}

}