From: "Lloyd Noronha" To: Cc: Subject: Proj4 Solution Date: Mon, 2 Aug 1999 04:14:34 -0400 Dr. Schmalz, The solution for Proj4 is enclosed. I picked it up from Ashish Myles. Lloyd. ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="TreeDFS.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="TreeDFS.java" // Ashish Myles // COP3530 // Fri 07/23/99 import Traverser; import Array; import LinkedBinaryTree; import BinaryTreeNode; public class TreeDFS implements Traverser { // Run the DFS traversal and output the result public Array traverse(LinkedBinaryTree btree) { Array traversalOutput = new Array(); DFS(btree.rootNode(), traversalOutput); return traversalOutput; } // Recursive procedure to run the DFS traversal private void DFS(BinaryTreeNode bnode, Array traversalOutput) { if (bnode != null) { traversalOutput.append(bnode.element); DFS(bnode.getLeftChild(), traversalOutput); DFS(bnode.getRightChild(), traversalOutput); } } } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="AVLtree.java" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="AVLtree.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Dr. Sahni's code // AVL tree import java.util.*; public class AVLtree extends BinarySearchTree { // top-level nested class static class AVLElement { // data members Object element; // element in node int bf; // balance factor of node // constructors AVLElement(int theBalanceFactor, Object theElement) { bf =3D theBalanceFactor; element =3D theElement; } AVLElement(Object theElement) {element =3D theElement;} /** @return equivalent string suitable for output */ public String toString() {return element.toString();} } // ascend is inherited from BinarySearchTree /** @return element whose key is theKey * @return null if there is no element with key theKey */ public Object get(Object theKey) { Object theElement =3D super.get(theKey); if (theElement =3D=3D null) // no matching element return null; else return ((AVLElement) theElement).element; } /** set balance factors on path from q to r */ static void fixBF(BinaryTreeNode q, BinaryTreeNode r, Comparable = theKey) {// Balance factors from q to r were originally 0. // They need to be changed to +1 or -1. // Use theKey to find path from q to r. =20 while (q !=3D r) if (theKey.lessThan(((Data) q.element).key)) {// height of left subtree has increased ((AVLElement) ((Data) q.element).element).bf =3D 1; q =3D q.leftChild; } else {// height of right subtree has increased ((AVLElement) ((Data) q.element).element).bf =3D -1; q =3D q.rightChild; } } =20 /** LL rotation around a, pa is parent of a and b is left child of a = */ void llRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b) { // restructure subtree at A a.leftChild =3D b.rightChild; b.rightChild =3D a; if (pa !=3D null) // a is not the root if (a =3D=3D pa.leftChild) pa.leftChild =3D b; else pa.rightChild =3D b; else root =3D b; =20 // set balance factors ((AVLElement) ((Data) a.element).element).bf =3D 0; ((AVLElement) ((Data) b.element).element).bf =3D 0; } =20 /** RR rotation around a, pa is parent of a and b is right child of a = */ void rrRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b) { // restructure subtree at a a.rightChild =3D b.leftChild; b.leftChild =3D a; if (pa !=3D null) // a is not the root if (a =3D=3D pa.leftChild) pa.leftChild =3D b; else pa.rightChild =3D b; else root =3D b; =20 // set balance factors ((AVLElement) ((Data) a.element).element).bf =3D 0; ((AVLElement) ((Data) b.element).element).bf =3D 0; } =20 /** LR rotation around a, pa is parent of a and b is left child of a = */ void lrRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b) { BinaryTreeNode c =3D b.rightChild; =20 // restructure subtree at a a.leftChild =3D c.rightChild; b.rightChild =3D c.leftChild; c.leftChild =3D b; c.rightChild =3D a; if (pa !=3D null) // a is not the root if (a =3D=3D pa.leftChild) pa.leftChild =3D c; else=20 pa.rightChild =3D c; else=20 root =3D c; =20 // set balance factors int bfOfC =3D ((AVLElement) ((Data) c.element).element).bf; if (bfOfC =3D=3D 1) { =20 ((AVLElement) ((Data) a.element).element).bf =3D -1; ((AVLElement) ((Data) b.element).element).bf =3D 0; } else if (bfOfC =3D=3D -1) { ((AVLElement) ((Data) a.element).element).bf =3D 0; ((AVLElement) ((Data) b.element).element).bf =3D 1; } else {// bfOfC =3D 0 ((AVLElement) ((Data) a.element).element).bf =3D 0; ((AVLElement) ((Data) b.element).element).bf =3D 0; } ((AVLElement) ((Data) c.element).element).bf =3D 0; } =20 /** RL rotation around a, pa is parent of a and b is right child of a = */ void rlRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b) { BinaryTreeNode c =3D b.leftChild; =20 // restructure subtree at a a.rightChild =3D c.leftChild; b.leftChild =3D c.rightChild; c.leftChild =3D a; c.rightChild =3D b; if (pa !=3D null) // a is not the root if (a =3D=3D pa.leftChild) pa.leftChild =3D c; else=20 pa.rightChild =3D c; else=20 root =3D c; =20 // set balance factors int bfOfC =3D ((AVLElement) ((Data) c.element).element).bf; if (bfOfC =3D=3D 1) { =20 ((AVLElement) ((Data) a.element).element).bf =3D 0; ((AVLElement) ((Data) b.element).element).bf =3D -1; } else if (bfOfC =3D=3D -1) { ((AVLElement) ((Data) a.element).element).bf =3D 1; ((AVLElement) ((Data) b.element).element).bf =3D 0; } else {// bfOfC =3D 0 ((AVLElement) ((Data) a.element).element).bf =3D 0; ((AVLElement) ((Data) b.element).element).bf =3D 0; } ((AVLElement) ((Data) c.element).element).bf =3D 0; } =20 /** insert an element with the specified key * overwrite old element if there is already an * element with the given key */ public void put(Object theKey, Object theElement) { BinaryTreeNode p =3D root, // search pointer pp =3D null, // parent of p a =3D null, // node with bf !=3D 0 pa =3D null; // parent of a // find place to insert theElement // also record most recent node with bf !=3D 0 // in a and its parent in pa Comparable elementKey =3D (Comparable) theKey; while (p !=3D null) {// examine p.element.key Data pData =3D (Data) p.element; if (((AVLElement) pData.element).bf !=3D 0) {// new candidate for a node a =3D p; pa =3D pp; } pp =3D p; // move p to a child if (elementKey.lessThan(pData.key)) p =3D p.leftChild; else if (elementKey.greaterThan(pData.key)) p =3D p.rightChild; else {// overwrite element with same key ((AVLElement) pData.element).element =3D theElement; return; } } =20 // get a node for theElement and attach to pp AVLElement q =3D new AVLElement(0, theElement); BinaryTreeNode r =3D new BinaryTreeNode (new Data(elementKey, q)); if (root !=3D null) // the tree is not empty if (elementKey.lessThan(((Data) pp.element).key)) pp.leftChild =3D r; else pp.rightChild =3D r; else {// insertion into empty tree root =3D r; return; } =20 // see if we must rebalance or simply change balance factors if (a !=3D null) {// possible rebalancing needed Data aData =3D (Data) a.element; if (((AVLElement) aData.element).bf < 0) // bf =3D -1 before insertion if (elementKey.lessThan(aData.key)) {// insertion in left subtree // height of left subtree has increased by 1 // new bf of a is 0, no rebalancing ((AVLElement) aData.element).bf =3D 0; // fix bf on path from a to r fixBF(a.leftChild, r, elementKey); } else {// insertion in right subtree // bf of a is -2, rebalance BinaryTreeNode b =3D a.rightChild; if (elementKey.greaterThan(((Data) b.element).key)) {// RR case fixBF(b.rightChild, r, elementKey); rrRotate(pa, a, b); } else {// RL case fixBF(b.leftChild, r, elementKey); rlRotate(pa, a, b); } } else // bf =3D +1 before insertion if (elementKey.greaterThan(aData.key)) {// insertion in right subtree // height of right subtree has increased by 1 // new bf of a is 0, no rebalancing ((AVLElement) aData.element).bf =3D 0; // fix bf on path from a to r fixBF(a.rightChild, r, elementKey); } else {// insertion in left subtree // bf of a is +2, rebalance BinaryTreeNode b =3D a.leftChild; if (elementKey.lessThan(((Data) b.element).key)) {// LL case fixBF(b.leftChild, r, elementKey); llRotate(pa, a, b); } else {// LR case fixBF(b.rightChild, r, elementKey); lrRotate(pa, a, b); } } } else // a is null, no rebalancing fixBF(root, r, elementKey); } =20 /** @return matching element and remove it * @return null if no matching element */ public Object remove(Object theKey) { Comparable searchKey =3D (Comparable) theKey; =20 // define a stack to hold path taken from root // to physically deleted node java.util.Stack stack =3D new java.util.Stack(); =20 // p will eventually to point to node with key theKey BinaryTreeNode p =3D root; // search pointer while (p !=3D null && !theKey.equals(((Data) p.element).key)) {// move to a child of p stack.push(p); if (searchKey.lessThan(((Data) p.element).key)) p =3D p.leftChild; else p =3D p.rightChild; } if (p =3D=3D null) // no element with key theKey return null; =20 // save element that will be removed Object theElement =3D ((AVLElement) ((Data) = p.element).element).element; =20 // restructure tree // handle case when p has two children if (p.leftChild !=3D null && p.rightChild !=3D null) {// p has two children, convert to 0 or 1 child case // find largest element in left subtree of p stack.push(p); BinaryTreeNode s =3D p.leftChild; while (s.rightChild !=3D null) {// move to larger element stack.push(s); s =3D s.rightChild; } =20 // move largest from s to p ((Data) p.element).key =3D ((Data) s.element).key; ((AVLElement) ((Data) p.element).element).element =3D ((AVLElement) ((Data) s.element).element).element; p =3D s; } =20 // p has at most one child // save child pointer in c BinaryTreeNode c; if (p.leftChild !=3D null) c =3D p.leftChild; else c =3D p.rightChild; =20 // delete p if (p =3D=3D root) root =3D c; else // is p a left or right child? if (p =3D=3D ((BinaryTreeNode) stack.peek()).leftChild) ((BinaryTreeNode) stack.peek()).leftChild =3D c; else ((BinaryTreeNode) stack.peek()).rightChild =3D c; Comparable pKey =3D ((Data) p.element).key; // pKey may not equal theKey =20 // rebalance tree and correct balance factors // use stack to retrace path to root // set q to parent of deleted node BinaryTreeNode q; try {q =3D (BinaryTreeNode) stack.pop();} catch (Exception e) {return theElement;} // root was deleted =20 while (q !=3D null) { Data qData =3D (Data) q.element; AVLElement qAVL =3D (AVLElement) qData.element; if (!pKey.greaterThan(qData.key)) {// node p was deleted from the left subtree of q // height of left subtree reduced by 1 qAVL.bf--; if (qAVL.bf =3D=3D -1) // height of q is unchanged, nothing more to do return theElement; if (qAVL.bf =3D=3D -2) {// q is unbalanced, classify unbalance and rotate BinaryTreeNode b =3D q.rightChild, pa; // q is a node // pa is parent of a try {pa =3D (BinaryTreeNode) stack.pop();} catch (Exception e) {pa =3D null;} // stack empty AVLElement bAVL =3D (AVLElement) ((Data) = b.element).element; switch (bAVL.bf) { case 0: // L0 imbalance rrRotate(pa, q, b); bAVL.bf =3D 1; qAVL.bf =3D -1; // q is a node return theElement; case 1: // L1 imbalance rlRotate(pa, q, b); break; // must continue on path to root case -1: // L-1 imbalance rrRotate(pa, q, b); } q =3D pa; } else // qAVL.bf is 0 try {q =3D (BinaryTreeNode) stack.pop();} catch (Exception e) {q =3D null;} // stack empty } else {// pKey > qData.key // deleted from right subtree of q // height of right subtree reduced by 1 qAVL.bf++; if (qAVL.bf =3D=3D 1) // height of q is unchanged, nothing more to do return theElement; if (qAVL.bf =3D=3D 2) {// q is unbalanced // classify imbalance and rotate BinaryTreeNode b =3D q.leftChild, pa; // q is a node // pa is parent of a try {pa =3D (BinaryTreeNode) stack.pop();} catch (Exception e) {pa =3D null;} // stack empty AVLElement bAVL =3D (AVLElement) ((Data) = b.element).element; switch (bAVL.bf) { case 0: // R0 imbalance llRotate(pa, q, b); bAVL.bf =3D -1; qAVL.bf =3D 1; // q is a node return theElement; case 1: // R1 imbalance llRotate(pa, q, b); break; // must continue on path to = root case -1: // R-1 imbalance lrRotate(pa, q, b); } q =3D pa; } else // qAVL.bf is 0 try {q =3D (BinaryTreeNode) stack.pop();} catch (Exception e) {q =3D null;} // stack empty } =20 } =20 =20 return theElement; } } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="BinarySearchTree.java" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="BinarySearchTree.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Dr. Sahni's code /** binary search tree */ public class BinarySearchTree extends LinkedBinaryTree implements BSTree { // top-level nested class static class Data { // data members Object element; // element in node Comparable key; // its key // constructor Data(Comparable theKey, Object theElement) { key =3D theKey; element =3D theElement; } public String toString() {return element.toString();} } /** @return element with specified key * @return null if no matching element */ public Object get(Object theKey) { // pointer p starts at the root and moves through // the tree looking for an element with key theKey BinaryTreeNode p =3D root; Comparable searchKey =3D (Comparable) theKey; while (p !=3D null) // examine p.element.key if (searchKey.lessThan(((Data) p.element).key)) p =3D p.leftChild; else if (searchKey.greaterThan(((Data) p.element).key)) p =3D p.rightChild; else // found matching element return ((Data) p.element).element; // no matching element return null; } =20 /** insert an element with the specified key * overwrite old element if there is already an * element with the given key */ public void put(Object theKey, Object theElement) { BinaryTreeNode p =3D root, // search pointer pp =3D null; // parent of p Comparable elementKey =3D (Comparable) theKey; // find place to insert theElement while (p !=3D null) {// examine p.element.key pp =3D p; // move p to a child if (elementKey.lessThan(((Data) p.element).key)) p =3D p.leftChild; else if (elementKey.greaterThan(((Data) p.element).key)) p =3D p.rightChild; else {// overwrite element with same key ((Data) p.element).element =3D theElement; return; } } =20 // get a node for theElement and attach to pp BinaryTreeNode r =3D new BinaryTreeNode (new Data(elementKey, theElement)); if (root !=3D null) // the tree is not empty if (elementKey.lessThan(((Data) pp.element).key)) pp.leftChild =3D r; else pp.rightChild =3D r; else // insertion into empty tree root =3D r; } =20 /** @return matching element and remove it * @return null if no matching element */ public Object remove(Object theKey) { Comparable searchKey =3D (Comparable) theKey; // set p to point to node with key searchKey BinaryTreeNode p =3D root, // search pointer pp =3D null; // parent of p while (p !=3D null && !((Data) p.element).key.equals(searchKey)) {// move to a child of p pp =3D p; if (searchKey.lessThan(((Data) p.element).key)) p =3D p.leftChild; else p =3D p.rightChild; } if (p =3D=3D null) // no element with key searchKey return null; =20 // save element to be removed Object theElement =3D ((Data) p.element).element;=20 =20 // restructure tree // handle case when p has two children if (p.leftChild !=3D null && p.rightChild !=3D null) {// two children // convert to zero or one child case // find element with largest key in left subtree of p BinaryTreeNode s =3D p.leftChild, ps =3D p; // parent of s while (s.rightChild !=3D null) {// move to larger element ps =3D s; s =3D s.rightChild; } =20 // move largest element from s to p p.element =3D s.element; p =3D s; pp =3D ps; } =20 // p has at most one child, save this child in c BinaryTreeNode c; if (p.leftChild =3D=3D null) c =3D p.rightChild; else c =3D p.leftChild; =20 // remove node p if (p =3D=3D root) root =3D c; else {// is p left or right child of pp? if (p =3D=3D pp.leftChild) pp.leftChild =3D c; else pp.rightChild =3D c; } =20 return theElement; } /** output elements in ascending order of key */ public void ascend() {inOrderOutput();} // Outputs the BST in the shape of a binary tree public String toString() { int L =3D height(), w =3D 1 << (L - 1), // w =3D 2 ^ (L - 1) width =3D 4 * w - 1, // Width =3D # chars in the lowest level = =3D 4 * w - 1 temp =3D L << 1; char [][]output =3D new char[temp][width]; StringBuffer s =3D new StringBuffer(); // Initialize the matrix with spaces for(int i =3D 0; i < temp; i++) for(int j =3D 0; j < width; j++) output[i][j] =3D ' '; // Output the tree to the char matrix preOrderOutput(root, 0, 0, L, output); // Convert the char matrix to a string and return it for(int i =3D 0; i < temp; i++) { s.append(new String(output[i])); s.append('\n'); } return s.toString(); } // Outputs all the nodes into the char array (InvrtLevel =3D level # = counting backwards (down -> up)) private void preOrderOutput(BinaryTreeNode bnode, int row, int pos, = int InvrtLevel, char [][]output) { if (bnode !=3D null) { int start =3D ((1 << (InvrtLevel)) - 2), // Start =3D 2 ^ = (InvrtLevel) - 2 width =3D (1 << (InvrtLevel + 1)); // Width =3D 2 ^ = (InvrtLevel + 1) =3D spacing + 3 outputNodeAt(bnode, row, start + pos * width, output); preOrderOutput(bnode.getLeftChild(), row + 2, pos * 2, = InvrtLevel - 1, output); preOrderOutput(bnode.getRightChild(), row + 2, pos * 2 + 1, = InvrtLevel - 1, output); } } // Outputs the node at the given position in the output matrix private void outputNodeAt(BinaryTreeNode bnode, int row, int col, = char [][]output) { String txt =3D bnode.element.toString(); if (txt.length() =3D=3D 1) txt =3D " " + txt + " "; else if (txt.length() =3D=3D 2) txt =3D " " + txt; // Transfer the first three characters of the integer for(int i =3D 0; i < 3; i++) output[row][col + i] =3D txt.charAt(i); // Put the branches there if children exist if (bnode.getLeftChild() !=3D null) output[row + 1][col] =3D '/'; if (bnode.getRightChild() !=3D null) output[row + 1][col + 2] =3D '\\'; } } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="BinaryTree.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="BinaryTree.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Dr. Sahni's code /** binary tree interface */ import java.lang.reflect.*; public interface BinaryTree { public boolean isEmpty(); public Object root(); public void makeTree(Object root, Object left, Object right); public BinaryTree removeLeftSubtree(); public BinaryTree removeRightSubtree(); public void preOrder(Method visit); public void inOrder(Method visit); public void postOrder(Method visit); public void levelOrder(Method visit); } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="BinaryTreeNode.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="BinaryTreeNode.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Dr. Sahni's code /** class for nodes used in a binary tree */ public class BinaryTreeNode { // package visible data members Object element; BinaryTreeNode leftChild; // left subtree BinaryTreeNode rightChild; // right subtree // constructors public BinaryTreeNode() {} public BinaryTreeNode(Object theElement) {element = theElement;} public BinaryTreeNode(Object theElement, BinaryTreeNode theleftChild, BinaryTreeNode therightChild) { element = theElement; leftChild = theleftChild; rightChild = therightChild; } // accessor methods public BinaryTreeNode getLeftChild() {return leftChild;} public BinaryTreeNode getRightChild() {return rightChild;} public Object getElement() {return element;} // mutator methods public void setLeftChild(BinaryTreeNode theLeftChild) {leftChild = theLeftChild;} public void setRightChild(BinaryTreeNode theRightChild) {rightChild = theRightChild;} public void setElement(Object theElement) {element = theElement;} // output method public String toString() {return element.toString();} } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="BSTree.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="BSTree.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Dr. Sahni's code /** binary search tree */ public interface BSTree extends Dictionary { public void ascend(); } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="Chain.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="Chain.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Dr. Sahni's code /** linked implementation of LinearList */ import java.util.*; import ChainNode; public class Chain implements LinearList { // data members protected ChainNode firstNode; protected int size; // constructors /** create a list that is empty */ public Chain(int initialCapacity) { // the default initial values of firstNode and size // are null and 0, respectively } public Chain() { this(0); } // methods /** @return true iff list is empty */ public boolean isEmpty() { return size == 0; } /** @return current number of elements in list */ public int size() { return size; } /** @return element with specified index * @exception IllegalArgumentException thrown * if index is not between 0 and size - 1 */ public Object elementAt(int index) { if (index < 0 || index >= size) // invalid list position throw new IllegalArgumentException ("Chain.elementAt: " + "index must be between 0 and size - 1"); // move to desired node ChainNode currentNode = firstNode; for (int i = 0; i < index; i++) currentNode = currentNode.next; return currentNode.element; } /** @return index of first occurrence of elem, * return -1 if elem not in list */ public int indexOf(Object elem) { // search the chain for elem ChainNode currentNode = firstNode; int index = 0; // index of currentNode while (currentNode != null && !currentNode.element.equals(elem)) { // move to next node currentNode = currentNode.next; index++; } // make sure we found matching element if (currentNode == null) return -1; else return index; } /** Remove the element with specified index. * All elements with higher index have their * index reduced by 1. * @exception IllegalArgumentException thrown * if index is not between 0 and size - 1 */ public void removeElementAt(int index) { if (index < 0 || index >= size) // invalid list position throw new IllegalArgumentException ("Chain.removeElementAt: " + "index must be between 0 and size - 1"); if (index == 0) // remove node 0 firstNode = firstNode.next; else { // use q to get to node index-1 ChainNode q = firstNode; for (int i = 0; i < index - 1; i++) q = q.next; q.next = q.next.next; // remove node index from chain } size--; } /** Insert an element with specified index. * All elements with equal or higher index * have their index increased by 1. * @exception IllegalArgumentException thrown * if index is not between 0 and size */ public void insertElementAt(Object obj, int index) { if (index < 0 || index > size) // invalid list position throw new IllegalArgumentException ("FormulaBasedLinearList.insertElementAt: " + "index must be between 0 and size"); if (index == 0) // insert at front firstNode = new ChainNode(obj, firstNode); else { // find index - 1'th node ChainNode p = firstNode; for (int i = 0; i < index - 1; i++) p = p.next; // insert after p p.next = new ChainNode(obj, p.next); } size++; } /** convert to a string */ public String toString() { StringBuffer s = new StringBuffer("["); if (firstNode != null) {// nonempty chain // do first element s.append(firstNode.element.toString()); // do remaining elements ChainNode currentNode = firstNode.next; while(currentNode != null) { s.append(", " + currentNode.element.toString()); currentNode = currentNode.next; } } s.append("]"); // create equivalent String return new String(s); } /** create and return an enumerator */ public Enumeration elements() { return new Enumerator(); } /** chain enumerator */ private class Enumerator implements Enumeration { // data member private ChainNode nextNode; // constructor public Enumerator() { nextNode = firstNode; } // methods /** @return true iff list has more elements */ public boolean hasMoreElements() { return nextNode != null; } /** @return next element in list * @exception NoSuchElementException * thrown if there is no next element */ public Object nextElement() { if (nextNode != null) { Object obj = nextNode.element; nextNode = nextNode.next; return obj; } else throw new NoSuchElementException ("Enumerator.nextElement: No next element"); } } } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="ChainNode.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="ChainNode.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Dr. Sahni's code /** Node class used by linked structures. * This class and its data members are * visible only within the package dataStructures. */ class ChainNode { // package visible data members Object element; ChainNode next; // package visible constructors ChainNode() {} ChainNode(Object element) {this.element = element;} ChainNode(Object element, ChainNode next) {this.element = element; this.next = next;} } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="Comparable.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="Comparable.java" // Ashish Myles // COP3530 // Fri 07/23/99 public interface Comparable { public boolean greaterThan(Object x); public boolean lessThan(Object x); } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="Dictionary.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="Dictionary.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Dr. Sahni's code public interface Dictionary { public Object get(Object key); public void put(Object key, Object theElement); public Object remove(Object key); } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="LinearList.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="LinearList.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Dr. Sahni's code /** interface for linear lists */ public interface LinearList { public boolean isEmpty(); public int size(); public Object elementAt(int index); public int indexOf(Object elem); public void removeElementAt(int index); public void insertElementAt(Object obj, int index); public String toString(); } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="LinkedBinaryTree.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="LinkedBinaryTree.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Dr. Sahni's code /** linked binary trees */ import java.lang.reflect.*; public class LinkedBinaryTree implements BinaryTree { // instance data member BinaryTreeNode root; // root node // class data members static Method visit; // visit method to use during a traversal static Object [] visitArgs = new Object [1]; // parameters of visit method static int count; // counter static Class [] paramType = {BinaryTreeNode.class}; // type of parameter for visit static Method theAdd1; // method to increment count by 1 static Method theOutput; // method to output node element // method to initialize class data members static { try { Class lbt = LinkedBinaryTree.class; theAdd1 = lbt.getMethod("add1", paramType); theOutput = lbt.getMethod("output", paramType); } catch (Exception e) {} // exception not possible } // only default constructor available // class methods /** visit method that outputs element */ public static void output(BinaryTreeNode t) {System.out.print(t.element + " ");} /** visit method to count nodes */ public static void add1(BinaryTreeNode t) {count++;} // instance methods /** @return true iff tree is empty */ public boolean isEmpty() {return root == null;} /** @return root element if tree is not empty * @return null if tree is empty */ public Object root() {return (root == null) ? null : root.element;} // Return the root NODE (only for the purposes of BFS and DFS traversal public BinaryTreeNode rootNode() { return root; } /** set this to the tree with the given root and subtrees */ public void makeTree(Object root, Object left, Object right) { this.root = new BinaryTreeNode(root, ((LinkedBinaryTree) left).root, ((LinkedBinaryTree) right).root); } /** remove the left subtree * @exception IllegalArgumentException if tree is empty * @return removed subtree */ public BinaryTree removeLeftSubtree() { if (root == null) throw new IllegalArgumentException ("LinkedBinaryTree.removeLeftSubtree: tree is empty"); // detach left subtree and save in leftSubtree LinkedBinaryTree leftSubtree = new LinkedBinaryTree(); leftSubtree.root = root.leftChild; root.leftChild = null; return (BinaryTree) leftSubtree; } /** remove the right subtree * @exception IllegalArgumentException if tree is empty * @return removed subtree */ public BinaryTree removeRightSubtree() { if (root == null) throw new IllegalArgumentException ("LinkedBinaryTree.removeRightSubtree: tree is empty"); // detach right subtree and save in rightSubtree LinkedBinaryTree rightSubtree = new LinkedBinaryTree(); rightSubtree.root = root.rightChild; root.rightChild = null; return (BinaryTree) rightSubtree; } /** preorder traversal */ public void preOrder(Method visit) { this.visit = visit; thePreOrder(root); } /** actual preorder traversal method */ static void thePreOrder(BinaryTreeNode t) { if (t != null) { visitArgs[0] = t; try {visit.invoke(null, visitArgs);} // visit tree root catch (Exception e) {System.out.println(e);} thePreOrder(t.leftChild); // do left subtree thePreOrder(t.rightChild); // do right subtree } } /** inorder traversal */ public void inOrder(Method visit) { this.visit = visit; theInOrder(root); } /** actual inorder traversal method */ static void theInOrder(BinaryTreeNode t) { if (t != null) { theInOrder(t.leftChild); // do left subtree visitArgs[0] = t; try {visit.invoke(null, visitArgs);} // visit tree root catch (Exception e) {System.out.println(e);} theInOrder(t.rightChild); // do right subtree } } /** postorder traversal */ public void postOrder(Method visit) { this.visit = visit; thePostOrder(root); } /** actual postorder traversal method */ static void thePostOrder(BinaryTreeNode t) { if (t != null) { thePostOrder(t.leftChild); // do left subtree thePostOrder(t.rightChild); // do right subtree visitArgs[0] = t; try {visit.invoke(null, visitArgs);} // visit tree root catch (Exception e) {System.out.println(e);} } } /** level order traversal */ public void levelOrder(Method visit) { LinkedQueue q = new LinkedQueue(); BinaryTreeNode t = root; while (t != null) { visitArgs[0] = t; try {visit.invoke(null, visitArgs);} // visit tree root catch (Exception e) {System.out.println(e);} // put t's children on queue if (t.leftChild != null) q.put(t.leftChild); if (t.rightChild != null) q.put(t.rightChild); // get next node to visit t = (BinaryTreeNode) q.remove(); } } /** output elements in preorder */ public void preOrderOutput() {preOrder(theOutput);} /** output elements in inorder */ public void inOrderOutput() {inOrder(theOutput);} /** output elements in postorder */ public void postOrderOutput() {postOrder(theOutput);} /** output elements in level order */ public void levelOrderOutput() {levelOrder(theOutput);} /** count number of nodes in tree */ public int size() { count = 0; preOrder(theAdd1); return count; } /** @return tree height */ public int height() {return theHeight(root);} /** @return height of subtree rooted at t */ static int theHeight(BinaryTreeNode t) { if (t == null) return 0; int hl = theHeight(t.leftChild); // height of left subtree int hr = theHeight(t.rightChild); // height of right subtree if (hl > hr) return ++hl; else return ++hr; } } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="LinkedQueue.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="LinkedQueue.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Sahni's code /** a linked queue class */ import ChainNode; import Chain; public class LinkedQueue implements Queue { // data members protected ChainNode front; protected ChainNode rear; // constructors /** create an empty queue */ public LinkedQueue(int initialCapacity) { // the default initial value of front is null } public LinkedQueue() { this(0); } // methods /** @return true iff queue is empty */ public boolean isEmpty() { return front == null; } /** @return the element at the front of the queue * @return null if the queue is empty */ public Object getFrontElement() { if (isEmpty()) return null; else return front.element; } /** @return the element at the rear of the queue * @return null if the queue is empty */ public Object getRearElement() { if (isEmpty()) return null; else return rear.element; } /** insert theElement at the rear of the queue */ public void put(Object theElement) { // create a node for theElement ChainNode p = new ChainNode(theElement, null); // append p to the chain if (front == null) front = p; // empty queue else rear.next = p; // nonempty queue rear = p; } /** remove an element from the front of the queue * @return removed element * @return null if the queue is empty */ public Object remove() { if (isEmpty()) return null; Object frontElement = front.element; front = front.next; return frontElement; } } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="ListInterface.java" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="ListInterface.java" // Ashish Myles // COP3530 // Fri 6/11/99 import java.util.*; public interface ListInterface { public abstract boolean isEmpty(); // Returns true iff = list is empty public abstract int size(); // Returns size of = list public abstract Object elementAt(int index); // Returns = list[index] public abstract int indexOf(Object elem); // Returns index of = first occurrence of elem or -1 public abstract void removeElementAt(int index); // Removes = list[index] public abstract void insertElementAt(Object obj, int index); // = Inserts obj at list[index] public abstract void insertElementAt(Object obj, Enumeration e); // = Inserts obj at Enumeration e // = which now points to the node // = with obj public abstract void replaceElementAt(Object obj, int index); // = Replaces list[index] with obj public abstract void replaceElementAt(Object obj, Enumeration e); // = Replaces list[e] with obj public abstract String toString(); // Converts list to = string public abstract Enumeration elements(); // Returns = enumeration to list public abstract void reverse(); // Reverses the = order of the elements in the list public abstract void scramble(); // Scrambles the = list in a predetermined manner public abstract void makeEmpty(); // Empties the list public void append(Object obj); // Appends object to = list } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="MyInput.java" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="MyInput.java" // Ashish Myles // COP3530 // Fri 6/11/99 import java.io.*; import java.util.*; import ListInterface; public class MyInput { private static boolean BadIntFormat =3D false; private static boolean EOFReached =3D false; private static boolean isSeparator(char ch) // Returns true iff ch is one of the separators { return ((ch =3D=3D ' ') || (ch =3D=3D ',') || (ch =3D=3D '\n') || = (ch =3D=3D '\r') || (ch =3D=3D '\t') || (ch =3D=3D '\f')); } private static char getChar(Reader r) throws IOException // Returns a char from the standard input, or in the case of an EOF = it will // throw an IOException) { int i; if ((i =3D (int)r.read()) =3D=3D -1) throw new IOException(); else return (char)i; } =20 public static int readInt(Reader r) // Reads an integer from the standard input stream { String s =3D new String(""); char ch; BadIntFormat =3D false; =20 try { // Empty out all the separators if there are any while (isSeparator(ch =3D getChar(r))); // Add characters to string until a separator is reached while (!isSeparator(ch)) { // Append to s all the non-separator characters s +=3D ch; // Read the next character in the input stream ch =3D getChar(r); } // Convert to integer and return return Integer.parseInt(s.trim()); } // Comes here if the integer input is bad catch(NumberFormatException e) { BadIntFormat =3D true; return 0; } // Comes here when an EOF is reached catch(IOException e) { EOFReached =3D true; // If there is anything in the buffer (s) convert it to an int try { return Integer.parseInt(s); } catch(NumberFormatException e2) { BadIntFormat =3D true; return 0; } } } public static void readIntArray(Reader r, ListInterface list) // Reads the integer array from the standard input { int i; // Read in integers one by one until either EOF is reached or an = invalid // integer is reached while (true) { i =3D readInt(r); =20 if (!BadIntFormat) // Add the integer to the list unless it = isn't valid list.insertElementAt(new Integer(i), list.size()); else // Stop reading more if the integer isn't = valid break; =20 if (EOFReached) // EOF =3D> done break; } } public static boolean badIntFormat() // Returns BadIntFormat { return BadIntFormat; } // Test procedure public static void main(String[] args) { } } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="MyInt.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="MyInt.java" // Ashish Myles // COP3530 // Fri 07/23/99 import java.lang.*; import Comparable; public class MyInt implements Comparable { Integer value; // Constructors public MyInt() { value = new Integer(0); } public MyInt(int val) { value = new Integer(val); } public MyInt(String s) { value = new Integer(s); } // Other methods public int intValue() // Returns the in stored in the wrapper { return value.intValue(); } public boolean greaterThan(Object x) // Returns true iff current object == x { return (value.intValue() > ((MyInt)x).intValue()); } public boolean lessThan(Object x) // Returns true iff current object < x { return (value.intValue() < ((MyInt)x).intValue()); } public boolean equals(Object x) // Returns true iff current object < x { return (value.intValue() == ((MyInt)x).intValue()); } public String toString() // Converts the object to a string for output { return value.toString(); } } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="Proj4.java" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="Proj4.java" // Ashish Myles // COP3530 // Fri 07/23/99 import java.lang.*; import java.util.*; import java.io.*; import MyInput; import ListInterface; import Array; import BinarySearchTree; import AVLtree; import Traverser; import TreeBFS; import TreeDFS; import MyInt; public class Proj4 { // Storage of command line argument information and constants final private static String dswitches =3D new String("ab"); final private static String aswitches =3D new String("bd"); private static StringBuffer DataTypeName =3D new StringBuffer(); private static StringBuffer TraversalAlgorithm =3D new = StringBuffer(); private static Traverser Traverse; private static BufferedReader fin; private static BinarySearchTree BST; private static ListInterface list =3D new Array(); static void CheckArgs(String[] args) throws IllegalArgumentException // Checks the command-line arguments and returns false iff they are = not valid { // Throw exception if the switches are not valid if ((args.length !=3D 2) || (args[0].length() !=3D 2) || = (args[0].charAt(0) !=3D '-') || (dswitches.indexOf(args[0].charAt(1)) =3D=3D -1) || = (args[1].length() !=3D 2) || (args[1].charAt(0) !=3D '-') || = (aswitches.indexOf(args[1].charAt(1)) =3D=3D -1)) throw new IllegalArgumentException("USAGE: java Proj2 = "); // Assign the dswitch switch (args[0].charAt(1)) { case 'a': BST =3D new AVLtree(); DataTypeName.append("AVL Tree"); break; case 'b': BST =3D new BinarySearchTree(); DataTypeName.append("Binary Search Tree"); break; } // Assign the aswitch switch (args[1].charAt(1)) { case 'b': Traverse =3D new TreeBFS(); TraversalAlgorithm.append("BFS"); break; case 'd': Traverse =3D new TreeDFS(); TraversalAlgorithm.append("DFS"); break; } } static void main(String[] args) { try { CheckArgs(args); } =20 // Display USAGE if the command line arguments are bad catch(IllegalArgumentException e) { System.out.println(e.getMessage()); return; } // Open standard input for buffered input fin =3D new BufferedReader(new InputStreamReader(System.in)); // Read in array MyInput.readIntArray(fin, list); // Display header System.out.println("Ashish Myles SSN: xxx-xx-xxxx" + "\n23 July 1999 COP3530-C99-Proj4\n"); // Output type of data and the input sequence System.out.println("Data Structure: " + DataTypeName); System.out.println("Traversal Algorithm: " + TraversalAlgorithm); System.out.println("\nNumbers read in: " + list.size()); System.out.println("\nInput Sequence:\n" + list); // Put the list into a binary search tree int i; MyInt tmp; for(i =3D 0; i < list.size(); i++) { tmp =3D new MyInt(((Integer)list.elementAt(i)).intValue()); BST.put(tmp, tmp); } // Output the tree and the results of the traversal System.out.println("\n" + DataTypeName + "\n" + BST); System.out.println(TraversalAlgorithm + " output:\n" + = Traverse.traverse(BST) + "\n"); // Delete the node and output the tree and the results of the = traversal i =3D MyInput.readInt(fin); if (MyInput.badIntFormat()) System.out.println("You have entered an incorrect symbol (must = be 0-9 or E)"); else { tmp =3D (MyInt)BST.remove(new MyInt(i)); if (tmp =3D=3D null) System.out.println("The number you specified is not in the = tree"); else { System.out.println("The number has been found and deleted = from the tree"); System.out.println("\n" + DataTypeName + "\n" + BST); System.out.println(TraversalAlgorithm + " output:\n" + = Traverse.traverse(BST) + "\n"); } } } } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="Queue.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="Queue.java" // Ashish Myles // COP3530 // Fri 07/23/99 // Adaptation of Sahni's code public interface Queue { public boolean isEmpty(); public Object getFrontElement(); public Object getRearElement(); public void put(Object theObject); public Object remove(); } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="Traverser.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="Traverser.java" // Ashish Myles // COP3530 // Fri 07/23/99 import java.util.*; public interface Traverser { public Array traverse(LinkedBinaryTree btree); } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="TreeBFS.java" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="TreeBFS.java" // Ashish Myles // COP3530 // Fri 07/23/99 import Traverser; import Array; import LinkedBinaryTree; import BinaryTreeNode; import LinkedQueue; public class TreeBFS implements Traverser { // Run the BFS traversal and output the result public Array traverse(LinkedBinaryTree btree) { Array traversalOutput = new Array(); BFS(btree, traversalOutput); return traversalOutput; } // Iterative BFS procedure private void BFS(LinkedBinaryTree btree, Array traversalOutput) { if (btree.isEmpty()) return; BinaryTreeNode bnode; // Initialize the queue to contain the root node LinkedQueue Q = new LinkedQueue(); Q.put(btree.rootNode()); while (!Q.isEmpty()) { bnode = (BinaryTreeNode)Q.remove(); traversalOutput.append(bnode); // Output the node if (bnode.getLeftChild() != null) Q.put(bnode.getLeftChild()); if (bnode.getRightChild() != null) Q.put(bnode.getRightChild()); } } } ------=_NextPart_000_0007_01BEDC9D.872752B0 Content-Type: text/java; name="Array.java" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="Array.java" // Ashish Myles // COP3530 // Fri 6/11/99 import java.util.*; import java.lang.*; import ListInterface; // Implements an expandable array public class Array implements ListInterface { Object [] list; int numelem; int resizeInc; // Constructors public Array(int size, int resizeIncrement) { if (size < 1) throw new IllegalArgumentException("Array constructor: initial = size should be >=3D 1"); list =3D new Object[size]; numelem =3D 0; resizeInc =3D resizeIncrement; } public Array(int size) { this(size, 10); } public Array() { this(10, 10); } // Returns true iff list is empty public boolean isEmpty() { return (numelem =3D=3D 0); }; // Returns size of list public int size() { return numelem; }; // Returns list[index] public Object elementAt(int index) { if ((index < 0) || (index >=3D numelem)) throw new IllegalArgumentException("Array.elementAt: index = should be within range"); return list[index]; } // Returns index of first occurrence of elem or -1 if not found public int indexOf(Object elem) { int i; for(i =3D 0; (i < numelem) && (!elem.equals(list[i])); i++); // = Scan for element if (i < numelem) return i; // Return element else return -1; // Element not found } =20 // Removes list[i] public void removeElementAt(int index) { if ((index < 0) || (index >=3D numelem)) throw new IllegalArgumentException("Array.removeElementAt: = index should be within range"); // Shift all the elements to the right of index to the left one = step int i; numelem--; for (i =3D index; i < numelem; i++) list[i] =3D list[i + 1]; // Decrease array size if number of elements is much lower than = the array size if (numelem < (list.length - (2 * resizeInc))) resize(list.length - resizeInc); } // Resizes the array to new size private void resize(int newsize) { // Check new size if (newsize < 1) throw new IllegalArgumentException("Array.resize: new size = should be >=3D 1"); int i; Object [] temp =3D new Object[newsize]; // Copy list to temp numelem =3D (numelem < newsize) ? numelem : newsize; for(i =3D 0; i < numelem; i++) temp[i] =3D list[i]; list =3D temp; // Assign temp (resized list) to list } // Inserts obj at list[i] public void insertElementAt(Object obj, int index) { if ((index < 0) || (index > numelem)) throw new IllegalArgumentException("Array.removeElementAt: = index should be within range"); // Check if the array needs to be resized to increase capacity if (numelem >=3D list.length) resize(list.length + resizeInc); =20 // Shift all the elements to the right of index to the left one = step and add the element int i; for (i =3D numelem; i > index; i--) list[i] =3D list[i - 1]; list[index] =3D obj; numelem++; } // Replaces list[index] with obj public void replaceElementAt(Object obj, int index) { if ((index < 0) || (index >=3D numelem)) throw new IllegalArgumentException("Array.removeElementAt: = index should be within range"); // Replace list[index] list[index] =3D obj; } // Converts list to string public String toString() { if (numelem =3D=3D 0) return new String(""); int i =3D 0, j; StringBuffer s =3D new StringBuffer(" "); String tmp =3D new String(); // Output the rest of the elements to the string (max char space = for each element is // assumed to be 4). Max number of objects per line is 10. do { if (((i % 10) =3D=3D 0) && (i > 0)) // Add a new line after = every 10 elements s.append("\n "); =20 tmp =3D list[i].toString(); =20 for(j =3D 4; (j > tmp.length()); j--) // Pre-trail output with = spaces s.append(' '); s.append(tmp); // Append the current = number and increment i i++; } while (i < numelem); return s.toString(); } =20 // Returns an enumerator to the first element public Enumeration elements() { return new Enumerator(); } // Array Enumerator private class Enumerator implements Enumeration { // Data member private int nextElem; =20 // Constructor public Enumerator() { nextElem =3D 0; } =20 // Returns true iff there are more elements to return public boolean hasMoreElements() { return (nextElem < numelem); } =20 // Returns the next element or throws the NoSuchElementException public Object nextElement() { if (nextElem < numelem) return list[nextElem++]; else throw new NoSuchElementException ("Enumerator.nextElement: No next element"); } } // Inserts an element at the position pointed by the enumeration public void insertElementAt(Object obj, Enumeration e) { insertElementAt(obj, ((Array.Enumerator)e).nextElem); } // Replaces list[e] with obj public void replaceElementAt(Object obj, Enumeration e) { replaceElementAt(obj, ((Array.Enumerator)e).nextElem); } // Reverses the order of the elements in the list public void reverse() { int i, n =3D numelem / 2; Object t; for (i =3D 0; i < n; i++) // swap all list[i] with list[numelem - = 1 - i] { t =3D list[i]; list[i] =3D list[numelem - 1 - i]; list[numelem - 1 - i] =3D t; } } // Scrambles the list in a predetermined manner (swap chunks of three = with the adjacent // chunks of three) public void scramble() { int i, j, tmp, n =3D numelem / 6; Object t; for(i =3D 0; i < n; i++) { for(j =3D 0; j < 3; j++) { tmp =3D 6 * i + j; // tmp is the position of the first = element in the chunk t =3D list[tmp]; // swap list[6i + j] with list[6i + j = + 3] list[tmp] =3D list[tmp + 3]; list[tmp + 3] =3D t; } } } // Empties the list public void makeEmpty() { int i; for (i =3D 0; i < numelem; i++) // Make entries null so that the = space is dellocated list[i] =3D null; numelem =3D 0; } // Appends object to the list public void append(Object obj) { insertElementAt(obj, numelem); } // Test procedure public static void main(String[] args) { Array a =3D new Array(); int i; for (i =3D 0; i < 11; i++) a.insertElementAt(new Integer(i), i); System.out.println(a.size()); System.out.println(a); a.reverse(); System.out.println(a); a.scramble(); System.out.println(a); } } ------=_NextPart_000_0007_01BEDC9D.872752B0--