SUMMARY SHEET FOR CHAPTER EIGHTEEN
public interface PriQue // not in the Sun library
{ public boolean isEmpty();
public Object peekMin();
public Object removeMin();
public void add (Object ob);
}
public class Ascendor implements java.util.Comparator
{ public int compare (Object one, Object two)
}
public class ArrayOutPriQue implements PriQue
{ private Object[] itsItem = new Object[10];
private int itsSize = 0;
private java.util.Comparator itsTest;
public ArrayOutPriQue (java.util.Comparator givenTest)
public ArrayOutPriQue()
// PLUS ALL FOUR PriQue METHODS
}
public class ArrayInPriQue implements PriQue
{ private Object[] itsItem = new Object[10];
private int itsSize = 0;
private java.util.Comparator itsTest;
public ArrayInPriQue (java.util.Comparator givenTest)
public ArrayInPriQue()
private int searchMin()
// PLUS ALL FOUR PriQue METHODS
}
public class NodeOutPriQue implements PriQue
{ private Node itsFirst = new Node (null, null); // trailer node
private java.util.Comparator itsTest;
public NodeOutPriQue (java.util.Comparator givenTest)
public NodeOutPriQue()
public int size()
public String toString()
private static class Node
{ public Object itsData;
public Node itsNext;
public Node (Object data, Node next)
} //======================
// PLUS ALL FOUR PriQue METHODS
}
public class NodeInPriQue implements PriQue
{ private Node itsFirst = new Node (null, null); // trailer node
private java.util.Comparator itsTest;
public NodeInPriQue (java.util.Comparator givenTest)
public NodeInPriQue()
private Node searchMin()
public int size()
public String toString()
private static class Node
{ public Object itsData;
public Node itsNext;
public Node (Object data, Node next)
} //======================
// PLUS ALL FOUR PriQue METHODS
}
public class NodeGroupPriQue implements PriQue
{ private Node itsFirst = new Node (null, null); // trailer node
private java.util.Comparator itsTest;
public NodeGroupPriQue (java.util.Comparator givenTest)
public NodeGroupPriQue()
private static class Node
{ public QueueADT itsData;
public Node itsNext;
public Node (QueueADT data, Node next)
} //======================
// PLUS ALL FOUR PriQue METHODS
}
public class TreePriQue implements PriQue
{ private TreeNode itsRoot = TreeNode.ET;
private java.util.Comparator itsTest;
public TreePriQue (java.util.Comparator givenTest)
public TreePriQue()
// PLUS ALL FOUR PriQue METHODS
}
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 TreeNode firstNode()
public Object getData()
public Object removeFirst (TreeNode[] root)
public void add (Object ob, java.util.Comparator test)
public void inorderTraverseLR (QueueADT queue)
}
public class HeapPriQue implements PriQue
{ private Object[] itsItem = new Object[10];
private int itsSize = 0;
private java.util.Comparator itsTest;
public HeapPriQue (java.util.Comparator givenTest)
public HeapPriQue()
private void siftDown (Object toInsert)
// PLUS ALL FOUR PriQue METHODS
}
public interface PriQue // not in the Sun library
{
/** Tell whether the priority queue has no more elements. */
public boolean isEmpty();
/** Return the object removeMin would return without modifying
* anything. Throw an Exception if the queue is empty. */
public Object peekMin();
/** Delete the object of highest priority and return it.
* Priority is determined by a Comparator passed to the
* constructor. Throw an Exception if the queue is empty. */
public Object removeMin();
/** Add the given element ob to the priority queue, so the
* priority queue has one more element than it had before.
* Precondition: The Comparator can be applied to ob. */
public void add (Object ob);
}
public class Ascendor implements java.util.Comparator
{
public int compare (Object one, Object two)
{ return ((Comparable) one).compareTo (two);
} //=======================
}
public class HuffmanCompare implements java.util.Comparator
{
public int compare (Object one, Object two)
{ return ((Integer) ((TreeNode) one).getData()).intValue()
- ((Integer) ((TreeNode) two).getData()).intValue();
} //=======================
}
public class ByCost implements java.util.Comparator
{
public int compare (Object one, Object two)
{ return ((Priceable) two).getCost()
- ((Priceable) one).getCost();
} //=======================
}
public interface Priceable
{ public int getCost();
}
public class ArrayOutPriQue implements PriQue
{
private Object[] itsItem = new Object[10];
private int itsSize = 0;
private java.util.Comparator itsTest;
public ArrayOutPriQue (java.util.Comparator givenTest)
{ itsTest = givenTest; //1
} //=======================
public ArrayOutPriQue()
{ itsTest = new Ascendor(); //2
} //=======================
public boolean isEmpty()
{ return itsSize == 0; //3
} //=======================
public Object peekMin()
{ if (isEmpty()) //4
throw new IllegalStateException ("priority Q is empty");
return itsItem[itsSize - 1]; //6
} //=======================
public Object removeMin()
{ if (isEmpty()) //7
throw new IllegalStateException ("priority Q is empty");
itsSize--; //9
return itsItem[itsSize]; //10
} //=======================
public void add (Object ob)
{ if (itsSize == itsItem.length) //11
{ Object[] toDiscard = itsItem;
itsItem = new Object [itsItem.length * 2];
for (int k = 0; k < itsSize; k++)
itsItem[k] = toDiscard[k];
}
int k = itsSize; //13
while (k > 0 && itsTest.compare (ob, itsItem[k - 1]) >= 0)
{ itsItem[k] = itsItem[k - 1]; //15
k--; //16
} //17
itsItem[k] = ob; //18
itsSize++; //19
} //=======================
}
public class ArrayInPriQue implements PriQue
{
private Object[] itsItem = new Object[10];
private int itsSize = 0;
private java.util.Comparator itsTest;
public ArrayInPriQue (java.util.Comparator givenTest)
{ itsTest = givenTest;
} //=======================
public ArrayInPriQue()
{ itsTest = new Ascendor();
} //=======================
public boolean isEmpty()
{ return itsSize == 0;
} //=======================
public Object peekMin()
{ return itsItem[searchMin()]; //1
} //=======================
private int searchMin()
{ if (isEmpty()) //2
throw new IllegalStateException ("priority Q is empty");
int best = 0; //4
for (int k = 1; k < itsSize; k++) //5
{ if (itsTest.compare (itsItem[k], itsItem[best]) < 0)//6
best = k; //7
} //8
return best; //9
} //=======================
public Object removeMin()
{ int best = searchMin(); //10
itsSize--; //11
Object valueToReturn = itsItem[best]; //12
itsItem[best] = itsItem[itsSize]; //13
return valueToReturn; //14
} //=======================
public void add (Object ob)
{ if (itsSize == itsItem.length)
{ Object[] toDiscard = itsItem;
itsItem = new Object [itsItem.length * 2];
for (int k = 0; k < itsSize; k++)
itsItem[k] = toDiscard[k];
}
itsItem[itsSize] = ob;
itsSize++;
} //=======================
}
public class NodeOutPriQue implements PriQue
{
private Node itsFirst = new Node (null, null); // trailer node
private java.util.Comparator itsTest;
public NodeOutPriQue (java.util.Comparator givenTest)
{ itsTest = givenTest;
} //=======================
public NodeOutPriQue()
{ itsTest = new Ascendor();
} //=======================
public boolean isEmpty()
{ return itsFirst.itsNext == null; //1
} //=======================
public Object peekMin()
{ if (isEmpty())
throw new IllegalStateException ("priority Q is empty");
return itsFirst.itsData;
} //=======================
public Object removeMin()
{ if (isEmpty()) //2
throw new IllegalStateException ("priority Q is empty");
Node toDiscard = itsFirst; //4
itsFirst = itsFirst.itsNext; //5
return toDiscard.itsData; //6
} //=======================
public void add (Object ob)
{ Node p = this.itsFirst; //7
while (p.itsNext != null //8
&& itsTest.compare (ob, p.itsData) >= 0) //9
{ p = p.itsNext; //10
} //11
p.itsNext = new Node (p.itsData, p.itsNext); //12
p.itsData = ob; //13
} //=======================
public int size()
{ int count = 0;
for (Node p = itsFirst; p.itsNext != null; p = p.itsNext)
count++;
return count;
} //=======================
public String toString()
{ String valueToReturn = "";
for (Node p = itsFirst; p.itsNext != null; p = p.itsNext)
valueToReturn += '\t' + p.itsData.toString();
return valueToReturn;
} //=======================
public void removeAbove (Object ob) // in NodeOutPriQue
{ while (itsFirst.itsNext != null
&& itsTest.compare (itsFirst.itsData, ob) > 0)
itsFirst = itsFirst.itsNext;
}
private static class Node
{
public Object itsData;
public Node itsNext;
public Node (Object data, Node next)
{ itsData = data; //14
itsNext = next; //15
}
} //======================
}
public class NodeInPriQue implements PriQue
{
private Node itsFirst = new Node (null, null); // trailer node
private java.util.Comparator itsTest;
public NodeInPriQue (java.util.Comparator givenTest)
{ itsTest = givenTest;
} //=======================
public NodeInPriQue()
{ itsTest = new Ascendor();
} //=======================
public boolean isEmpty()
{ return itsFirst.itsNext == null; //1
} //=======================
public Object peekMin()
{ return searchMin().itsData; //2
} //=======================
private Node searchMin()
{ Node best = itsFirst; //3
for (Node p = itsFirst.itsNext; p.itsNext != null; //4
p = p.itsNext) //5
{ if (itsTest.compare (p.itsData, best.itsData) <= 0) //6
best = p; //7
} //8
return best; //9
} //=======================
public Object removeMin()
{ Node best = searchMin(); //10
Object valueToReturn = best.itsData; //11
Node toDiscard = best.itsNext; //12
best.itsData = toDiscard.itsData; //13
best.itsNext = toDiscard.itsNext; //14
return valueToReturn; //15
} //=======================
public void add (Object ob)
{ itsFirst = new Node (ob, itsFirst); //16
} //=======================
public void removeAbove (Object ob) // in NodeInPriQue
{ Node p = itsFirst;
while (p.itsNext.itsNext != null) //so next node has data to compared
{ if (itsTest.compare (p.itsNext.itsData, ob) < 0)
p.itsNext = p.itsNext.itsNext;
else
p = p.itsNext;
}
if ( ! isEmpty() && itsTest.compare (itsFirst.itsData, ob) < 0)
itsFirst = itsFirst.itsNext;
}
private static class Node
{
public Object itsData;
public Node itsNext;
public Node (Object data, Node next)
{ itsData = data; //14
itsNext = next; //15
}
} //======================
}
public class NodeGroupPriQue implements PriQue
{
private Node itsFirst = new Node (null, null); // trailer node
private java.util.Comparator itsTest;
public NodeGroupPriQue (java.util.Comparator givenTest)
{ itsTest = givenTest;
} //=======================
public NodeGroupPriQue()
{ itsTest = new Ascendor();
} //=======================
public boolean isEmpty()
{ return itsFirst.itsNext == null; //1
} //=======================
public Object peekMin()
{ return itsFirst.itsData.peekFront(); //2
} //=======================
public Object removeMin()
{ Object valueToReturn = itsFirst.itsData.dequeue(); //3
if (itsFirst.itsData.isEmpty()) // after the dequeue //4
itsFirst = itsFirst.itsNext; // lose the queue //5
return valueToReturn;
} //=======================
public void add (Object ob)
{ Node p = this.itsFirst; //6
while (p.itsNext != null //7
&& itsTest.compare (ob, p.itsData.peekFront()) > 0)
{ p = p.itsNext; //9
} //10
if (p.itsNext == null //11
|| itsTest.compare (ob, p.itsData.peekFront()) < 0)
{ p.itsNext = new Node (p.itsData, p.itsNext); //13
p.itsData = new NodeQueue(); //14
} //15
p.itsData.enqueue (ob); //16
} //=======================
private static class Node
{
public QueueADT itsData;
public Node itsNext;
public Node (QueueADT data, Node next)
{ itsData = data; //17
itsNext = next; //18
}
} //======================
}
public class CompOp2
{
public static void sort (QueueADT source, PriQue piq)
{ while ( ! source.isEmpty()) // Loop #1
piq.add (source.dequeue());
while ( ! piq.isEmpty()) // Loop #2
source.enqueue (piq.removeMin());
}
public static void sort (Object[] source, PriQue piq)
{ for (int k = source.length - 1; k >= 0; k++) // Loop #1
piq.add (source[k]);
for (int k = 0; k < source.length; k++) // Loop #2
source[k] = piq.removeMin();
}
public static void treeSort (Comparable[] item, int size)
{ if (size <= 1)
return;
java.util.Comparator itsTest = new Ascendor();
TreeNode root = new TreeNode (item[0]);
for (int k = 1; k < size; k++)
root.add (item[k], itsTest); // coded in Listing 18.9
NodeQueue queue = new NodeQueue();
root.inorderTraverseLR (queue); // coded in Listing 17.9
for (int k = 0; k < size; k++)
item[k] = (Comparable) queue.dequeue();
} //=======================
}
public class TreePriQue implements PriQue
{
private TreeNode itsRoot = TreeNode.ET;
private java.util.Comparator itsTest;
public TreePriQue (java.util.Comparator givenTest)
{ itsTest = givenTest;
} //=======================
public TreePriQue()
{ itsTest = new Ascendor();
} //=======================
public boolean isEmpty()
{ return itsRoot.isEmpty();
} //=======================
public Object peekMin()
{ return itsRoot.firstNode().getData();
} //=======================
public void add (Object ob)
{ if (itsRoot == TreeNode.ET)
itsRoot = new TreeNode (ob);
else
itsRoot.add (ob, itsTest);
} //=======================
public Object removeMin()
{ if (isEmpty())
throw new IllegalStateException ("priority Q is empty");
TreeNode[] newRoot = {itsRoot};
Object valueToReturn = itsRoot.removeFirst (newRoot);
itsRoot = newRoot[0];
return valueToReturn;
} //=======================
}
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. */
// AVG EXECUTION TIME is O(1): it executes just 1 statement.
public boolean isEmpty()
{ return this.itsData == null; // generally, only ET
} //========================
/** Precondition: this is an internal node (i.e., not empty).
Return the leftmost node in the tree rooted at this. */
// AVG EXECUTION TIME O(log(N)): navigates only 1 path down the tree.
public TreeNode firstNode()
{ return itsLeft.isEmpty() ? this : itsLeft.firstNode();
} //========================
public Object getData()
{ return itsData;
} //======================
/** 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 the executor's 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; //7
Object valueToReturn = p.itsLeft.itsData; //8
p.itsLeft = p.itsLeft.itsRight; //9
return valueToReturn; //10
} //=======================
/** Add ob to the tree, maintaining 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
} //=======================
/** Add to the given queue all data values in the standard
* left-to-right inorder traversal. */
// AVG EXECUTION TIME is O(N): it goes through every node in the tree.
public void inorderTraverseLR (QueueADT queue)
{ if (isEmpty())
return;
itsLeft.inorderTraverseLR (queue);
queue.enqueue (itsData);
itsRight.inorderTraverseLR (queue);
} //========================
}
public class HeapPriQue implements PriQue
{
private Object[] itsItem = new Object[10];
private int itsSize = 0;
private java.util.Comparator itsTest;
public HeapPriQue (java.util.Comparator givenTest)
{ itsTest = givenTest;
} //=======================
public HeapPriQue()
{ itsTest = new Ascendor();
} //=======================
public boolean isEmpty()
{ return itsSize == 0;
} //=======================
public Object peekMin()
{ if (isEmpty()) //1
throw new IllegalStateException ("priority Q is empty");
return itsItem[0]; //3
} //=======================
public void add (Object ob)
{ if (itsSize == itsItem.length) //4
{ } // left as an exercise in an earlier section //5
int k = itsSize; //6
while (k > 0 && itsTest.compare (ob, //7
itsItem[(k - 1) / 2]) < 0) //8
{ itsItem[k] = itsItem[(k - 1) / 2]; //9
k = (k - 1) / 2; //10
} //11
itsItem[k] = ob; //12
itsSize++; //13
} //=======================
public Object removeMin()
{ if (isEmpty()) //14
throw new IllegalStateException ("priority Q is empty");
Object valueToReturn = itsItem[0]; //16
itsSize--; //17
if (itsSize >= 2) //18
siftDown (itsItem[itsSize]); //19
else if (itsSize == 1) //20
itsItem[0] = itsItem[1]; //21
return valueToReturn; //22
} //=======================
/** Given that itsItem[0]..itsItem[itsSize] is a max-heap,
* in effect replace itsItem[0] by toInsert and then make
* the minimal changes to swap toInsert down so that
* itsItem[0]...itsItem[itsSize-1] is a max-heap again. */
private void siftDown (Object toInsert)
{ int empty = 0; //1
int kid = 1; // empty's child on the left //2
while (kid < itsSize) // there are two children //3
{ if (itsTest.compare (itsItem[kid + 1], //4
itsItem[kid]) < 0) //5
kid++; // use the child on the right //6
if (itsTest.compare (toInsert, itsItem[kid]) < 0) //7
{ itsItem[empty] = toInsert; //8
return; //9
} //10
itsItem[empty] = itsItem[kid]; //11
empty = kid; //12
kid = 2 * empty + 1; // empty's child on the left //13
} //14
itsItem[empty] = toInsert; //15
} //=======================
}
public class Node
{
private Object itsData;
private Node itsNext;
public void sort()
{ itsNext = sorted (itsNext, size()); //1
} //=======================
private Node sorted (Node item, int size)
{ if (size < 2) //2
return item; //3
int halfSize = size / 2; //4
Node end = item; //5
for (int k = 1; k < halfSize; k++) //6
end = end.itsNext; //7
Node secondHalf = end.itsNext; //8
end.itsNext = null; //9
return merged (sorted (item, halfSize), //10
sorted (secondHalf, size - halfSize)); //11
} //=======================
private Node merged (Node one, Node two)
{ Node rear = this; // last node of sorted //12
while (one != null && two != null) //13
{ if (((Comparable) one.itsData) //14
.compareTo (two.itsData) <= 0) //15
{ rear.itsNext = one; //16
one = one.itsNext; //17
} //18
else //19
{ rear.itsNext = two; //20
two = two.itsNext; //21
} //22
rear = rear.itsNext; //23
} //24
rear.itsNext = (one == null) ? two : one; //25
return this.itsNext; //26
} //=======================
public int size()
{ return itsNext == null ? 0 : 1 + itsNext.size();
} //=======================
}
public class ManyFilesMerger
{
private ObjectFile itsInFile; // the original unsorted input
private ObjectFile itsOutFile; // the final sorted output
private HeapPriQue itsData = new HeapPriQue();
public ManyFilesMerger (String inf, String outf)
{ itsInFile = new ObjectFile (inf); // for output //1
itsInFile.openForInput(); // but we need input //2
itsOutFile = new ObjectFile (outf); // for output //3
} //================================================
/** Step 1: Make many files, each sorted. */
public void makeSortedFiles (int maxToSort)
{ ObjectFileSorter sorter = new ObjectFileSorter (maxToSort);
while ( ! itsInFile.isEmpty()) //5
{ ObjectFile tempFile = new ObjectFile (""); //6
sorter.readManyFromFile (itsInFile); //7
sorter.writeManyToFile (tempFile); //8
tempFile.openForInput(); //9
itsData.add (new Pair (tempFile.readObject(),tempFile));
} //11
} //================================================
/** Step 2: Merge the many files into just one sorted file.*/
public void mergeFiles()
{ while ( ! itsData.isEmpty()) //12
{ Pair p = (Pair) itsData.removeMin(); //13
itsOutFile.writeObject (p.itsData); //14
if (! p.itsFile.isEmpty()) //15
{ p.itsData = p.itsFile.readObject(); //16
itsData.add (p); //17
} //18
} //19
} //================================================
private static class Pair implements Comparable
{ public Object itsData;
public final ObjectFile itsFile;
public Pair (Object data, ObjectFile file)
{ itsData = data; //20
itsFile = file; //21
}
public int compareTo (Object ob)
{ return ((Comparable) this.itsData).compareTo //22
(((Pair) ob).itsData); //23
}
} //================================================
}
// 2 stubbed classes
public class ObjectFile // for generic files of objects
{ // Open the file of that name for output; open a
// temporary file if the name is "".
public ObjectFile (String name) { }
// Add ob to the end of the file.
public void writeObject (Object ob) { }
// Change over to providing input, not output.
public void openForInput() { }
// Retrieve the next available object in the file.
public Object readObject() { return null; }
// Switch back to providing output, not input.
public void openForOutput() { }
// Tell whether the input file has no more values.
public boolean isEmpty() { return false; }
}
public class ObjectFileSorter // for sorters of ObjectFiles
{ // Create the object capable of holding max values.
public ObjectFileSorter (int max) { }
// Read max values from the given file, except stop reading
// at the end of the file.
public void readManyFromFile (ObjectFile file) { }
// Write all values you have to the given file in increasing
// order using compareTo.
public void writeManyToFile (ObjectFile file) { }
}
public class FourFilesMerger
{
private ObjectFile itsInFile; // the original unsorted input
private ObjectFile itsOutFile; // the final sorted output
private ObjectFile one, two; // two scratch files
private Object itsSentinel; // sentinel value to mark the end
public FourFilesMerger (String inf, String outf, Object sent)
{ itsInFile = new ObjectFile (inf); // for output //1
itsInFile.openForInput(); // but we need input //2
itsOutFile = new ObjectFile (outf); // for output //3
itsSentinel = sent; //4
} //================================================
public void makeSortedFiles (int maxToSort)
{ ObjectFileSorter sorter = new ObjectFileSorter (maxToSort);
one = new ObjectFile (""); // for output //6
two = new ObjectFile (""); // for output //7
while ( ! itsInFile.isEmpty()) //8
{ sorter.readManyFromFile (itsInFile); //9
sorter.writeManyToFile (one); //10
one.writeObject (itsSentinel); //11
if ( ! itsInFile.isEmpty()) //12
{ sorter.readManyFromFile (itsInFile); //13
sorter.writeManyToFile (two); //14
} //15
two.writeObject (itsSentinel); //16
} //17
} //================================================
public void mergeFiles()
{ if (one != null && ! one.isEmpty()) //18
{ one = mergeToOneFile (one, two, //19
new ObjectFile (""), new ObjectFile ("")); //20
Object data = one.readObject(); //21
while ( ! one.isEmpty()) //22
{ itsOutFile.writeObject (data); //23
data = one.readObject(); //24
} //25
} //26
} //================================================
/** Return a file containing all the values in increasing
* order, plus a sentinel at the end. */
private ObjectFile mergeToOneFile (ObjectFile in1,
ObjectFile in2, ObjectFile out1, ObjectFile out2)
{ return null; // left as an exercise
} //================================================
}
|
2