2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Back to the Main Page
|
||
|
Select a Chapter:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Back to the Main Page
|
||
| Chapter Seventeen listings: 8 classes | ||
SUMMARY SHEET FOR CHAPTER SEVENTEEN
public class Genealogy
{ private TreeNode itsRoot; // the root node of the tree
Genealogy (String lilith)
public void addChild (String parent)
public void listChildren (String parent)
public void listEverybody()
}
public class TreeNode
{ public static final TreeNode ET = new TreeNode (null);
private Object itsData; // the data value stored in this tree
private TreeNode itsLeft = ET; // left subtree of this tree
private TreeNode itsRight = ET; // right subtree of this tree
public TreeNode (Object given)
public boolean isEmpty()
public Object getData()
public TreeNode getLeft()
public TreeNode getRight()
public int size()
public TreeNode firstNode()
public void deleteLastNode()
public void listAll (String indent)
public void printInOrder() // in the TreeNode class
public TreeNode search (Object given)
public String toString() // in the TreeNode class
public void pushLeft (Object newInfo)
public String leftListToString()
public TreeNode lookUp (Comparable id)
private static int compare (Comparable id, Object data)
public Object putRecursive (Comparable id, Object val)
private Object putInLeftSubtree (Comparable id, Object val)
private Object putInRightSubtree (Comparable id, Object val)
public void removeData()
public static TreeNode make (Object[] item, int lo, int hi) // in TreeNode
public TreeNode nextIn (TreeNode ancestor)
public void inorderTraverseLR (QueueADT queue)
public static TreeNode balanced (int numNodes, java.util.Iterator it)
public Object removeFirst (TreeNode[] root)
public void add (Object ob, java.util.Comparator test)
}
public class BintMap implements Mapping
{ private TreeNode itsRoot;
public BintMap()
public boolean containsKey (Object id)
public Object get (Object id)
public boolean isEmpty()
public int size()
public Object put (Object id, Object value)
public Object remove (Object id)
public java.util.Iterator iterator()
public class MapIt implements java.util.Iterator
{ private TreeNode itsPos;
private TreeNode itsRoot;
public MapIt (TreeNode given)
public boolean hasNext()
public Object next()
public void remove()
}
public BintMap (Mapping par)
}
class GenealogyApp
{
/** Read in names of members of a family with their
* parent-child relationships. Then answer questions about
* what people are the children of what other people. */
public static void main (String[] args)
{ String s = IO.askLine ("Enter the ancestor of everyone:");
Genealogy family = new Genealogy (s);
IO.say ("Your choices: L = list everyone\n"
+ "\t A = add a child of a person\n"
+ "\t S = search for children of 1 person\n"
+ "\t E = exit the program ");
String choice = IO.askLine ("Choose L, A, S, or E ");
while ( ! choice.equals ("E"))
{ if (choice.equals ("A"))
family.addChild (IO.askLine
("parent of the person to be added? "));
else if (choice.equals ("S"))
family.listChildren (IO.askLine
("parent of children to be listed? "));
else // it must be "L"
family.listEverybody();
choice = IO.askLine ("Choose L, A, S, or E ");
}
System.exit (0);
} //========================
}
public class Genealogy
{
private TreeNode itsRoot; // the root node of the tree
/** Create a dataset of parent-child relations with lilith as
* the root data value and no other values in the dataset. */
Genealogy (String lilith)
{ itsRoot = new TreeNode (lilith);
} //========================
/** If the given parent is in the dataset, ask for a child of
* that parent and then add that child to the dataset. */
public void addChild (String parent)
{ TreeNode node = itsRoot.search (parent);
if (node == TreeNode.ET)
IO.say ("I'm sorry, that person is not in the family");
else
node.pushLeft (IO.askLine ("What's the child's name?"));
} //========================
/** List all children of the parent. */
public void listChildren (String parent)
{ TreeNode node = itsRoot.search (parent);
if (node == TreeNode.ET)
IO.say ("I'm sorry, that person is not in the family");
else if (node.getLeft() == TreeNode.ET)
IO.say ("None are in the dataset");
else
{ TreeNode kid = node.getLeft();
String s = kid.getData().toString();
for (kid = kid.getRight(); kid != TreeNode.ET;
kid = kid.getRight())
s += ", " + kid.getData().toString();
IO.say (s);
}
} //========================
/** List all values in the dataset, one per output line,
* with all children of any data value X listed before X
* and in the order they were entered (right-to-left
* postorder), and each indented 3 spaces further than X. */
public void listEverybody()
{ itsRoot.listAll (""); // left as a recursive exercise
} //========================
}
public class TreeNode
{
public static final TreeNode ET = new TreeNode (null);
private Object itsData; // the data value stored in this tree
private TreeNode itsLeft = ET; // left subtree of this tree
private TreeNode itsRight = ET; // right subtree of this tree
public TreeNode (Object given)
{ itsData = given;
} //========================
/** Return whether this is an empty tree. */
public boolean isEmpty()
{ return this.itsData == null; // generally, only ET
} //========================
/** Return the data value stored at the root of this tree. */
public Object getData()
{ return itsData;
} //========================
/** Return the node at the root of the left subtree. */
public TreeNode getLeft()
{ return itsLeft;
} //========================
/** Return the node at the root of the right subtree. */
public TreeNode getRight()
{ return itsRight;
} //========================
/** Return the number of data values in the tree. */
public int size()
{ return this.isEmpty() ? 0
: 1 + this.itsLeft.size() + this.itsRight.size();
} //========================
/** Return the leftmost node in the tree rooted at this.
Throw an Exception if this is an empty tree. */
public TreeNode firstNode()
{ return itsLeft.isEmpty() ? this : itsLeft.firstNode();
} //========================
/** Precondition: this is a non-empty node with a non-empty
node to its right. Postcondition: the rightmost node of
the subtree rooted at this is removed. */
public void deleteLastNode()
{ if (itsRight.itsRight.isEmpty())
itsRight = itsRight.itsLeft;
else
itsRight.deleteLastNode();
} //========================
public void listAll (String indent)
{ // just so Genealogy compiles
} //========================
// 1 method from the text of Section 17.2
/** Print all the data values in order left to right. */
public void printInOrder() // in the TreeNode class
{ if ( ! this.isEmpty())
{ itsLeft.printInOrder();
System.out.println (itsData.toString());
itsRight.printInOrder();
}
} //========================
// 1 method from Listing 17.3
/** The search process implemented with a queue.
* Precondition: The executor is not empty. */
public TreeNode search (Object given)
{ QueueADT people = new NodeQueue();
people.enqueue (this);
do
{ TreeNode node = (TreeNode) people.dequeue();
if (node.itsData.equals (given))
return node;
if ( ! node.itsRight.isEmpty())
people.enqueue (node.itsRight);
if ( ! node.itsLeft.isEmpty())
people.enqueue (node.itsLeft);
}while ( ! people.isEmpty())
return ET;
} //========================
// 1 method from the text of Section 17.3
public String toString() // in the TreeNode class
{ if (this.isEmpty())
return "";
else
return " (" + itsRight.toString() + itsData.toString()
+ itsLeft.toString() + ") ";
} //========================
// 2 methods from Listing 17.4
public void pushLeft (Object newInfo)
{ TreeNode newNode = new TreeNode (newInfo);
newNode.itsRight = this.itsLeft;
this.itsLeft = newNode;
} //========================
public String leftListToString()
{ if (itsLeft == TreeNode.ET)
return "None are in the dataset";
String s = itsLeft.itsData.toString();
for (TreeNode p = itsLeft.itsRight; p !=ET; p = p.itsRight)
s += ", " + p.itsData.toString();
return s;
} //========================
// 2 methods from Listing 17.5
/** Return null if id is nowhere in the subtree rooted at
* this node. Otherwise return the MapEntry containing id.
* Precondition: id is not null, nor is this.itsData; also,
* this tree is a binary search tree. */
public TreeNode lookUp (Comparable id)
{ if (compare (id, itsData) < 0)
return itsLeft.isEmpty() ? null : itsLeft.lookUp (id);
if (compare (id, itsData) > 0)
return itsRight.isEmpty() ? null : itsRight.lookUp (id);
return this; // this is the node with the id
} //======================
private static int compare (Comparable id, Object data)
{ return id.compareTo (((MapEntry) data).getKey());
} //======================
// 3 methods from Listing 17.6
/** Add the id/value pair to the non-empty binary search tree.
* Return the value the id previously had (null if none). */
public Object putRecursive (Comparable id, Object val)
{ if (compare (id, itsData) < 0) // go left //8
return putInLeftSubtree (id, val); //9
if (compare (id, itsData) > 0) // go right //10
return putInRightSubtree (id, val); //11
Object valueToReturn = ((MapEntry) itsData).getValue();//12
itsData = new MapEntry (id, val); //13
return valueToReturn; //14
} //======================
private Object putInLeftSubtree (Comparable id, Object val)
{ if (itsLeft.isEmpty()) //15
{ itsLeft = new TreeNode (new MapEntry (id, val)); //16
return null; //17
} //18
else //19
return itsLeft.putRecursive (id, val); //20
} //======================
private Object putInRightSubtree (Comparable id, Object val)
{ if (itsRight.isEmpty()) //21
{ itsRight = new TreeNode (new MapEntry (id, val)); //22
return null; //23
} //24
else //25
return itsRight.putRecursive (id, val); //26
} //======================
// 1 method from Listing 17.7
/** Precondition: The executor is a non-empty binary search
* tree. Postcondition: The data in the executor node is
* removed, leaving a binary search tree 1 node smaller. */
public void removeData()
{ if (itsRight.isEmpty()) //9
{ itsData = itsLeft.itsData; //10
itsRight = itsLeft.itsRight; //11
itsLeft = itsLeft.itsLeft; //12
} //13
else if (itsRight.itsLeft.isEmpty()) //14
{ itsData = itsRight.itsData; //15
itsRight = itsRight.itsRight; //16
} //17
else //18
{ TreeNode p = this.itsRight; //19
while ( ! p.itsLeft.itsLeft.isEmpty()) //20
p = p.itsLeft; //21
this.itsData = p.itsLeft.itsData; //22
p.itsLeft = p.itsLeft.itsRight; //23
} //24
} //======================
// 1 method from the text of Section 17.4
/** Create a well-balanced binary tree with the data in item[lo]...
* item[hi]. Precondition: Those components contain MapEntries. */
public static TreeNode make (Object[] item, int lo, int hi) // in TreeNode
{ int middle = (lo + hi + 1) / 2; // halfway from lo to hi
TreeNode root = new TreeNode (item[middle]);
if (lo < middle)
root.itsLeft = make (item, lo, middle - 1);
if (middle < hi)
root.itsRight = make (item, middle + 1, hi);
return root;
} //========================
// 1 method from Listing 17.8
/** Return the next TreeNode that appears in left-right
* inorder traversal; return null if there is none.
* Precondition: The executor is not empty. */
public TreeNode nextIn (TreeNode ancestor)
{ if ( ! this.itsRight.isEmpty())
return this.itsRight.firstNode();
Comparable id = (Comparable) ((MapEntry) itsData).getKey();
TreeNode lastLeftTurn = null;
while (ancestor != this)
{ if (compare (id, ancestor.itsData) > 0)
ancestor = ancestor.itsRight;
else
{ lastLeftTurn = ancestor;
ancestor = ancestor.itsLeft;
}
}
return lastLeftTurn;
} //======================
// 1 method from Listing 17.9
/** Add to the given queue all data values in the standard
* left-to-right inorder traversal. */
public void inorderTraverseLR (QueueADT queue)
{ if (isEmpty())
return;
itsLeft.inorderTraverseLR (queue);
queue.enqueue (itsData);
itsRight.inorderTraverseLR (queue);
} //========================
// 1 method from Listing 17.11
/** Return a near-full binary tree with the same ordering.
* Precondition: it has at least numNodes >= 1 values. */
public static TreeNode balanced (int numNodes, java.util.Iterator it)
{ if (numNodes == 1)
return new TreeNode (it.next());
TreeNode leftSide = balanced (numNodes / 2, it);
TreeNode root = new TreeNode (it.next());
root.itsLeft = leftSide;
int n = numNodes - 1 - numNodes / 2;
root.itsRight = (n == 0) ? ET : balanced (n, it);
return root;
} //======================
// 2 methods from Listing 18.9
/** Delete and return the first data value in a non-empty
* tree. If that data value is in the executor, assign
* to root the TreeNode to its right. */
public Object removeFirst (TreeNode[] root)
{ if (itsLeft == ET) //1
{ root[0] = this.itsRight; //2
return this.itsData; //3
} //4
TreeNode p = this; //5
while (p.itsLeft.itsLeft != ET) //6
p = p.itsLeft; // p becomes parent of leftmost node //7
Object valueToReturn = p.itsLeft.itsData; //8
p.itsLeft = p.itsLeft.itsRight; // it may be ET //9
return valueToReturn; //10
} //=======================
/** Add ob to the tree, keeping the binary search property.
* Precondition: this is not an empty tree. */
public void add (Object ob, java.util.Comparator test)
{ if (test. compare (ob, itsData) < 0) //11
{ if (itsLeft == ET) //12
itsLeft = new TreeNode (ob); //13
else //14
itsLeft.add (ob, test); //15
} //16
else //17
{ if (itsRight == ET) //18
itsRight = new TreeNode (ob); //19
else //20
itsRight.add (ob, test); //21
} //22
} //=======================
}
//Methods throw a RuntimeException for non-Comparable ids.
public class BintMap implements Mapping
{
private TreeNode itsRoot;
public BintMap()
{ itsRoot = TreeNode.ET;
} //======================
public boolean containsKey (Object id)
{ return id != null && ! this.isEmpty()
&& itsRoot.lookUp ((Comparable) id) != null;
} //======================
public Object get (Object id)
{ if (id == null || this.isEmpty())
return null;
TreeNode loc = itsRoot.lookUp ((Comparable) id);
return (loc == null) ? null
: ((MapEntry) loc.getData()).getValue();
} //======================
public boolean isEmpty()
{ return itsRoot.isEmpty();
} //======================
public int size()
{ return itsRoot.size();
} //======================
public Object put (Object id, Object value)
{ if (id == null) //1
return null; //2
if (this.isEmpty()) //3
{ itsRoot = new TreeNode (new MapEntry (id, value));//4
return null; //5
} //6
return itsRoot.putRecursive ((Comparable) id, value); //7
} //======================
public Object remove (Object id)
{ if (id == null || this.isEmpty()) //1
return null; //2
TreeNode loc = itsRoot.lookUp ((Comparable) id); //3
if (loc == null) //4
return null; //5
MapEntry data = (MapEntry) loc.getData(); //6
loc.removeData(); //7
return data.getValue(); //8
} //======================
public java.util.Iterator iterator()
{ return new MapIt (this.itsRoot);
} //======================
private static class MapIt implements java.util.Iterator
{
private TreeNode itsPos;
private TreeNode itsRoot;
public MapIt (TreeNode given)
{ itsRoot = given;
itsPos = given.isEmpty() ? null : given.firstNode();
} //======================
public boolean hasNext()
{ return itsPos != null;
} //======================
public Object next()
{ if ( ! hasNext())
throw new java.util.NoSuchElementException
("iterator has no next element!");
Object valueToReturn = itsPos.getData();
itsPos = itsPos.nextIn (itsRoot);
return valueToReturn;
} //======================
public void remove()
{ throw new UnsupportedOperationException ("no remove!");
} //======================
}
/** Precondition: par has MapEntries in ascending order. */
public BintMap (Mapping par)
{ itsRoot = (par == null || par.isEmpty())
? TreeNode.ET
: TreeNode.balanced (par.size(), par.iterator());
} //======================
}
public class QueueMapIt implements java.util.Iterator
{
private QueueADT itsQueue = new NodeQueue();
public QueueMapIt (TreeNode given)
{ given.inorderTraverseLR (itsQueue);
} //======================
public boolean hasNext()
{ return ! itsQueue.isEmpty();
} //======================
public Object next()
{ return itsQueue.dequeue();
} //======================
public void remove()
{ throw new UnsupportedOperationException ("no remove!");
} //======================
}
public class StackMapIt implements java.util.Iterator
{
private StackADT itsStack = new NodeStack();
public StackMapIt (TreeNode given)
{ pushAllLefties (given, itsStack);
} //======================
public boolean hasNext()
{ return ! itsStack.isEmpty();
} //======================
public Object next()
{ TreeNode pos = (TreeNode) itsStack.pop();
pushAllLefties (pos.getRight(), itsStack);
return pos.getData();
} //======================
public void remove()
{ throw new UnsupportedOperationException ("no remove!");
} //======================
private void pushAllLefties (TreeNode node, StackADT stack)
{ while ( ! node.isEmpty())
{ stack.push (node);
node = node.getLeft();
}
} //======================
}
// Red-black alternative TreeNode coding from Listing 17.10
/*
private boolean isRed = true;
private Object putInLeftSubtree (Comparable id, Object val)
{ if (itsLeft.isEmpty()) //15
{ itsLeft = new TreeNode (new MapEntry (id, val)); //16
return this.isRed ? ET : null; //17'
} //18
else //19
{ Object e = itsLeft.putRecursive (id, val); //20'
if ( ! this.isRed && e == ET) //20a
{ fixLeftRedRed(); //20b
return null; //20c
} //20d
else //20e
return this.isRed && itsLeft.isRed ? ET : e; //20f
} //20g
} //======================
private Object putInRightSubtree (Comparable id, Object val)
{ if (itsRight.isEmpty()) //21
{ itsRight = new TreeNode (new MapEntry (id, val)); //22
return this.isRed ? ET : null; //23'
} //24
else //25
{ Object e = itsRight.putRecursive (id, val); //26'
if ( ! this.isRed && e == ET) //26a
{ fixRightRedRed(); //26b
return null; //26c
} //26d
else //26e
return this.isRed && itsRight.isRed ? ET : e; //26f
} //26g
} //======================
*/
public class BigCircle implements Mapping
{
private final int MAX = 4; // maximum number of subtrees
private MapEntry[] itsData = new MapEntry[MAX - 1];
private BigCircle[] itsSubtree = new BigCircle[MAX];
/** Return the value for this id, or null if not there.
* Throw a RuntimeException if id is not Comparable. */
public Object get (Object id)
{ int k = 0;
for ( ; k < MAX - 1 && itsData[k] != null; k++)
{ int comp = ((Comparable) id).compareTo
(itsData[k].getKey());
if (comp <= 0)
return (comp == 0) ? itsData[k].getValue()
: (itsSubtree[k] == null) ? null // a leaf
: itsSubtree[k].get (id);
}
return (itsSubtree[k] == null) ? null // a leaf
: itsSubtree[k].get (id);
} //======================
}
public class CustomerManager // stubbed
{
/** Verify that the customer's description is on file.
* If not, obtain and file it. Then file the order. */
public void storeOrder (CustomerOrder order) { }
/** Find all orders that are currently unfilled.
* Fill any such order for which all product is available. */
public void fillAllPossibleOrders() { }
/** Return a description of all orders from this customer
* that are currently unfilled. */
public String getStatus (String customerID) { return null; }
/** Return a description of all orders currently unfilled,
* in order of customer ID. */
public String getOrdersByID() { return null; }
/** Return a description of all orders currently unfilled,
* in order of dates entered. */
public String getOrdersByDate() { return null; }
// many other report functions would go here
}
|
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved. |