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 Eighteen listings: 15 classes and 2 interfaces |
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 } //================================================ } |
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved. |