Computer Lab: Binary Trees and Hashing - Please help me on this lab ASAP! It will be greatly appreciated!

Attached are pictures of the lab instructions, the classes and interfaces we are provided for the lab, and the input text file.

Don't bother doing program documentation. I can do that. Also the extra credit portions are unnecessary but will also be greatly appreciated if completed.

Please try and comment your code also.

Thank you so much in advance to whomever does this! (Will make sure to give thumbs up if correct)

//getty.txt

Four score and seven years ago our fathers brought forth, upon this continent, a new nation, conceived in liberty, and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war, testing whether that nation, or any nation, so conceived, and so dedicated, can long endure. We are met here on a great battlefield of that war. We have come to dedicate a portion of it as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this. But in a larger sense we can not dedicate - we can not consecrate - we can not hallow this ground. The brave men, living and dead, who struggled here, have consecrated it far above our poor power to add or detract. The world will little note, nor long remember, what we say here, but can never forget what they did here. It is for us, the living, rather to be dedicated here to the unfinished work which they have, thus far, so nobly carried on. It is rather for us to be here dedicated to the great task remaining before us that from these honored dead we take increased devotion to that cause for which they here gave the last full measure of devotion - that we here highly resolve that these dead shall not have died in vain; that this nation shall have a new birth of freedom; and that this government of the people, by the people, for the people, shall not perish from the earth.

//ObjectListNodeInterface.java

public interface ObjectListNodeInterface { void setInfo(Object o); Object getInfo(); void setNext(ObjectListNode p); ObjectListNode getNext(); } 

// ObjectListNode.java

public class ObjectListNode { private Object info; private ObjectListNode next; // Default ctor public ObjectListNode() { info = null; next = null; }

// One-arg ctor public ObjectListNode (Object o) { info = o; next = null; } // Two-arg ctor public ObjectListNode (Object o, ObjectListNode p) { info = o; next = p; }

// Sets info field public void setInfo(Object o) { info = o; }

// Returns object in info field public Object getInfo() { return info; }

// Sets next field public void setNext(ObjectListNode p) { next = p; }

// Returns object in info field public ObjectListNode getNext() { return next; } }

//ObjectListInterface.java

public interface ObjectListInterface { ObjectListNode getFirstNode(); ObjectListNode getLastNode(); Object getFirst(); Object getLast(); void addFirst(Object o); void addFirst(ObjectListNode p); void addLast(Object o); void addLast(ObjectListNode p); Object removeFirst(); Object removeLast(); void insertAfter(ObjectListNode p, Object o); void insertAfter(ObjectListNode p, ObjectListNode q); Object deleteAfter(ObjectListNode p); void insert(Object o); void insert(ObjectListNode r); Object remove(Object o); boolean contains(Object o); ObjectListNode select(Object o); boolean isEmpty(); void clear(); int size(); ObjectList copyList(); void reverse(); } 

// ObjectList.java

public class ObjectList implements ObjectListInterface{ private ObjectListNode list; private ObjectListNode last; // Constructs an empty list public ObjectList() { list = null; last = null; }

// Returns the first node in the list public ObjectListNode getFirstNode() { return list; } // Returns the last node in the list public ObjectListNode getLastNode() { return last; }

// Returns the first object in the list public Object getFirst() { if (list == null) { System.out.println("Runtime Error: getFirst()"); System.exit(1); } return list.getInfo(); }

// Returns the last object in the list public Object getLast() { if (list == null) { System.out.println("Runtime Error: getLast()"); System.exit(1); } return last.getInfo(); }

// Adds an object to the front of a list public void addFirst(Object o) { ObjectListNode p = new ObjectListNode(o, list); if (list == null) last = p; list = p; }

// Adds a node to the front of the list public void addFirst(ObjectListNode p) { if (p == null) { System.out.println("Runtime Error: addFirst()"); System.exit(1); } p.setNext(list); if (list == null) last = p; list = p; } // Adds an object to the end of the list public void addLast(Object o) { ObjectListNode p = new ObjectListNode(o); if (list == null) list = p; else last.setNext(p); last = p; }

// Adds a node to the end of the list public void addLast(ObjectListNode p) { if (p == null) { System.out.println("Runtime Error: addLast()"); System.exit(1); } p.setNext(null); if (list == null) list = p; else last.setNext(p); last = p; }

// Removes the first object from the list public Object removeFirst() { if (list == null) { System.out.println("Runtime Error: removeFirst()"); System.exit(1); } ObjectListNode p = list; list = p.getNext(); if (list == null) last = null; return p.getInfo(); }

// Removes the last object from the list public Object removeLast() { if (list == null) { System.out.println("Runtime Error: removeLast()"); System.exit(1); } ObjectListNode p = list; ObjectListNode q = null; while (p.getNext() != null) { q = p; p = p.getNext(); } if (q == null) { list = null; last = null; } else { q.setNext(null); last = q; } return p.getInfo(); }

// Inserts an object after the node referenced by p public void insertAfter (ObjectListNode p, Object o) { if (list == null || p == null) { System.out.println("Runtime Error: insertAfter()"); System.exit(1); } ObjectListNode q = new ObjectListNode(o, p.getNext()); p.setNext(q); if (q.getNext() == null) last = q; }

// Inserts a node after the node referenced by p public void insertAfter(ObjectListNode p, ObjectListNode q) { if (list == null || p == null || q == null) { System.out.println("Runtime Error: insertAfter()"); System.exit(1); } q.setNext(p.getNext()); p.setNext(q); if (last.getNext() != null) last = q; } // Deletes the node after the node referenced by p public Object deleteAfter(ObjectListNode p) { if (list == null || p == null || p.getNext() == null) { System.out.println("Runtime Error: deleteAfter()"); System.exit(1); } ObjectListNode q = p.getNext(); p.setNext(q.getNext()); if (p.getNext() == null) last = p; return q.getInfo(); }

// Inserts an item into its correct location within an ordered list public void insert(Object o) { ObjectListNode p = list; ObjectListNode q = null; while (p != null && ((Comparable)o).compareTo(p.getInfo()) > 0) { q = p; p = p.getNext(); } if (q == null) addFirst(o); else insertAfter(q, o); }

// Inserts a node into its correct location within an ordered list public void insert(ObjectListNode r) { ObjectListNode p = list; ObjectListNode q = null; while (p != null && ((Comparable)r.getInfo()).compareTo(p.getInfo()) > 0) { q = p; p = p.getNext(); } if (q == null) addFirst(r); else insertAfter(q, r); }

// Removes the first occurrence of an item in a list public Object remove(Object o) { ObjectListNode p = list; ObjectListNode q = null; while (p != null && ((Comparable)o).compareTo(p.getInfo()) != 0) { q = p; p = p.getNext(); } if (p == null) return null; else return q == null ? removeFirst() : deleteAfter(q); }

// Returns true if the item is found in the list public boolean contains(Object o) { ObjectListNode p = list; while (p != null && ((Comparable)o).compareTo(p.getInfo()) != 0) p = p.getNext(); return p != null; }

// Returns a reference to the node with the requested value // Returns null otherwise public ObjectListNode select(Object o) { ObjectListNode p = list; while (p != null) if (((Comparable)o).compareTo(p.getInfo()) == 0) return p; else p = p.getNext(); return null; }

// Determines whether or not a list is empty public boolean isEmpty() { return list == null; }

// Removes all elements from a list public void clear() { list = null; last = null; }

// Returns the number of elements in the list public int size() { int count = 0; ObjectListNode p = list; while (p != null) { ++count; p = p.getNext(); } return count; }

// Makes a copy of a list public ObjectList copyList() { ObjectListNode p = null; ObjectListNode q = null; // to satisfy compiler; ObjectListNode r = list; if (isEmpty()) return null; ObjectList newList = new ObjectList(); while (r != null) { p = new ObjectListNode(r.getInfo()); if (newList.isEmpty()) newList.addFirst(p); else q.setNext(p); q = p; r = r.getNext(); } newList.last = p; return newList; } // Reverses a list public void reverse() { ObjectListNode p = list; ObjectListNode q = null; ObjectListNode r; while (p != null) { r = q; q = p; p = p.getNext(); q.setNext(r); } last = list; list = q; } }

//ObjectTreeNodeInterface.java

public interface ObjectTreeNodeInterface {

 void setInfo(Object o); Object getInfo(); void setLeft(ObjectTreeNode p); ObjectTreeNode getLeft(); void setRight(ObjectTreeNode p); ObjectTreeNode getRight(); } 

// ObjectTreeNode.java

public class ObjectTreeNode { private Object info; private ObjectTreeNode left; private ObjectTreeNode right; public ObjectTreeNode() { info = null; left = null; right = null; } public ObjectTreeNode (Object o) { info = o; left = null; right = null; } public void setInfo(Object o) { info = o; } public Object getInfo() { return info; } public void setLeft(ObjectTreeNode p) { left = p; } public ObjectTreeNode getLeft() { return left; } public void setRight(ObjectTreeNode p) { right = p; } public ObjectTreeNode getRight() { return right; } }

//ObjectBinaryTreeInterface.java

public interface ObjectBinaryTreeInterface { void setLeftChild(ObjectTreeNode parent, ObjectTreeNode r); void setRightChild(ObjectTreeNode parent, ObjectTreeNode r); void insertBST(Object o); void insertBSTDup(Object o); ObjectTreeNode searchBST(Object o); void preTrav(ObjectTreeNode tree); void inTrav(ObjectTreeNode tree); postTrav(ObjectTreeNode tree); void delete(Object o); } 

// ObjectBinaryTree.java

public class ObjectBinaryTree { private ObjectTreeNode root; public ObjectBinaryTree() { root = null; } public ObjectTreeNode getRoot() { return root; } public void setLeftChild(ObjectTreeNode parent, ObjectTreeNode r) { if (parent == null || parent.getLeft() != null) { System.out.println("Runtime Error: setLeftChild()"); System.exit(1); } parent.setLeft(r); } public void setRightChild(ObjectTreeNode parent, ObjectTreeNode r){ if (parent == null || parent.getRight() != null) { System.out.println("Runtime Error: setRightChild()"); System.exit(1); } parent.setRight(r); }

public void insertBST(Object o) { ObjectTreeNode p, q; ObjectTreeNode r = new ObjectTreeNode(o); if (root == null) root = r; else { p = root; q = root; while (q != null) { p = q; if (((TreeComparable)(r.getInfo())).compareTo((TreeComparable)(p.getInfo()))

public void insertBSTDup(Object o) { ObjectTreeNode p, q; ObjectTreeNode r = new ObjectTreeNode(o); if (root == null) root = r; else { p = root; q = root; while (q != null && ((TreeComparable)(r.getInfo())).compareTo((TreeComparable)(p.getInfo())) != 0) { p = q; if (((TreeComparable)(r.getInfo())).compareTo((TreeComparable)(p.getInfo())) 0) setRightChild(p, r); else ((TreeComparable)(p.getInfo())).operate((TreeComparable)(r.getInfo())); } }

public ObjectTreeNode searchBST(Object o) { ObjectTreeNode p; ObjectTreeNode r = new ObjectTreeNode(o); if(root != null) { p = root; while (p != null) { if (((TreeComparable)(r.getInfo())).compareTo((TreeComparable)(p.getInfo())) 0) p = p.getRight(); else return p; } } return null; }

public void preTrav(ObjectTreeNode tree) { if (tree != null) { ((TreeComparable)tree.getInfo()).visit(); preTrav(tree.getLeft()); preTrav(tree.getRight()); } } public void inTrav(ObjectTreeNode tree) { if (tree != null) { inTrav(tree.getLeft()); ((TreeComparable)tree.getInfo()).visit(); inTrav(tree.getRight()); } } public void postTrav(ObjectTreeNode tree) { if (tree != null) { postTrav(tree.getLeft()); postTrav(tree.getRight()); ((TreeComparable)tree.getInfo()).visit(); } }

public void delete(Object o) { ObjectTreeNode s, t, v; boolean found = false; ObjectTreeNode r = new ObjectTreeNode(o); ObjectTreeNode p = root; ObjectTreeNode q = null; // Search for the node with info key, set p to point to that node and set q to point to its parent, if any. while (p != null && !found) { if (((TreeComparable)(r.getInfo())).compareTo((TreeComparable)(p.getInfo())) == 0) found = true; else { q = p; if (((TreeComparable)(r.getInfo())).compareTo((TreeComparable)(p.getInfo()))

//TreeComparable.java

public interface TreeComparable { int compareTo(Object o); void operate(Object o); void visit(); } 

//Comparable.java

public interface Comparable { int compareTo(Object o); } 

Computer Lab: Binary Tree and Hashing Web search engines are programs that search webpages for specified ke and returns a list of relevant webpages where the keywords were found. The main tasks for search engines are matching and ranking. The matchin determines which webpages match a query and the ranking phase determines the relevance of each of the matches. Note that search queries can produ thousands or millions of picking the most relevant results (ranking). two ce hits (matches) and a search engine must be capable of cept of an index is the most fundamental idea behind any search engine. The con The index for a search engine works the same way as a book's index. The oages" of the book are now webpages and search engines assign a different e number to every single page on the web. The search engine builds up an pag index by first making a list of all the words that appear in any page, making a note of the page number in which each word appears, and then sorts that list in alphabetical order. So if a query is made on the word "computer", the search engine can quickly jump to the entry for "computer" in the word list and extract the pages for that entry Rather than build an index for webpages, this lab will build an index, or a cross- reference listing, for text-based documents. The lab will display the number of times each word appears in the document, the line numbers in which each word appears and the position of each word in the line. The lab will also allow us to query the document for specific words and will display the number of times the word appears in the document, the line numbers in which the word appears and the position of the word in the line. nelt At the outset we do not know how many different words are in the text, nor do we know in how many different lines a word may appear. Our approach will be to use an object binary search tree whose nodes provide for the following fields: a Word object two references to the left and right children of the current node Note that while the ObjectTreeNode class is built to hold a generic object, De creating a Word class whose objects will be placed in the ojectTreeNodes of the object binary search tree Focus on Data Structures Page 453