/** * BSTCounter implements the DataCounter interface using a binary search tree
ID: 3908400 • Letter: #
Question
/**
* BSTCounter implements the DataCounter interface using a binary search tree to
* store the data items and counts.
*
* @param <E> The type of the data elements. Note that we have strengthened the
* constraints on E such that E is now a Comparable.
*/
public class BinarySearchTree<E extends Comparable<? super E>> implements
DataCounter<E> {
/**
* The root of the binary search tree. root is null if and only if the tree
* is empty.
*/
protected BSTNode overallRoot;
/**
* Number of nodes in the binary search tree.
*/
protected int size;
/**
* Inner (non-static) class to represent a node in the tree. Each node
* includes a String and an integer count. The class is protected so that it
* may be accessed by subclasses of BSTCounter.
*/
protected class BSTNode {
/**
* The left child of this node.
*/
public BSTNode left;
/**
* The right child of this node.
*/
public BSTNode right;
/**
* The data element stored at this node.
*/
public E data;
/**
* The count for this data element.
*/
public int count;
/**
* Create a new data node. Also takes care of incrementing the tree
* size.
*
* @param data data element to be stored at this node.
*/
public BSTNode(E data) {
this.data = data;
count = 1;
left = right = null;
size++;
}
}
/**
* Create an empty binary search tree.
*/
public BinarySearchTree() {
overallRoot = null;
size = 0;
}
/** {@inheritDoc} */
public void incCount(E data) {
if (overallRoot == null) {
overallRoot = new BSTNode(data);
} else {
// traverse the tree
BSTNode currentNode = overallRoot;
while (true) {
// compare the data to be inserted with the data at the current
// node
int cmp = data.compareTo(currentNode.data);
if (cmp == 0) {
// current node is a match
currentNode.count++;
return;
} else if (cmp < 0) {
// new data goes to the left of the current node
if (currentNode.left == null) {
currentNode.left = new BSTNode(data);
return;
}
currentNode = currentNode.left;
} else {
// new data goes to the right of the current node
if (currentNode.right == null) {
currentNode.right = new BSTNode(data);
return;
}
currentNode = currentNode.right;
}
}
}
}
/** {@inheritDoc} */
public int getSize() {
return size;
}
/** {@inheritDoc} */
public DataCount<E>[] getCounts() {
@SuppressWarnings("unchecked")
DataCount<E>[] counts = new DataCount[size];
if (overallRoot != null)
traverse(overallRoot, counts, 0);
return counts;
}
/**
* Do an inorder traversal of the tree, filling in an array of DataCount
* objects with the count of each element. Doing an inorder traversal
* guarantees that the result will be sorted by element. We fill in some
* contiguous block of array elements, starting at index, and return the
* next available index in the array.
*
* @param counts The array to populate.
*/
protected int traverse(BSTNode root, DataCount<E>[] counts, int idx) {
if(root != null) {
idx = traverse(root.left, counts, idx);
counts[idx] = new DataCount<E>(root.data, root.count);
idx = traverse(root.right, counts, idx + 1);
}
return idx;
}
/**
* Dump the contents of the tree to a String (provided for debugging and
* unit testing purposes).
*
* @return a textual representation of the tree.
*/
protected String dump() {
if (overallRoot != null)
return dump(overallRoot);
return "<empty tree>";
}
/**
* Dump the contents of the subtree rooted at this node to a String
* (provided for debugging purposes).
*
* @return a textual representation of the subtree rooted at this node.
*/
protected String dump(BSTNode root) {
if(root == null)
return ".";
String out = "([" + root.data + "," + root.count + "] ";
out += dump(root.left);
out += " ";
out += dump(root.right);
out += ")";
return out;
}
}
----------------------------------------
import java.io.IOException;
/**
* An executable that counts the words in a files and prints out the counts in
* descending order. You will need to modify this file.
*/
public class WordCount {
private static void countWords(String file) {
DataCounter counter = new BinarySearchTree();
try {
FileWordReader reader = new FileWordReader(file);
String word = reader.nextWord();
while (word != null) {
counter.incCount(word);
word = reader.nextWord();
}
} catch (IOException e) {
System.err.println("Error processing " + file + e);
System.exit(1);
}
DataCount[] counts = counter.getCounts();
sortByDescendingCount(counts);
for (DataCount c : counts)
System.out.println(c.count + " " + c.data);
}
/**
* TODO Replace this comment with your own.
*
* Sort the count array in descending order of count. If two elements have
* the same count, they should be in alphabetical order (for Strings, that
* is. In general, use the compareTo method for the DataCount.data field).
*
* This code uses insertion sort. You should modify it to use a different
* sorting algorithm. NOTE: the current code assumes the array starts in
* alphabetical order! You'll need to make your code deal with unsorted
* arrays.
*
* The generic parameter syntax here is new, but it just defines E as a
* generic parameter for this method, and constrains E to be Comparable. You
* shouldn't have to change it.
*
* @param counts array to be sorted.
*/
private static > void sortByDescendingCount(
DataCount[] counts) {
for (int i = 1; i < counts.length; i++) {
DataCount x = counts[i];
int j;
for (j = i - 1; j >= 0; j--) {
if (counts[j].count >= x.count) {
break;
}
counts[j + 1] = counts[j];
}
counts[j + 1] = x;
}
}
public static void main(String[] args) {
if (args.length != 1) {
System.err.println("Usage: filename of document to analyze");
System.exit(1);
}
countWords(args[0]);
}
}
------------------------------------------------------------------
/**
* An example of how to test your binary search tree. You should use this as
* inspiration for your unit tests.
*/
public class TestBinarySearchTree {
public static void main(String[] args) {
boolean dumpall = false, notest = false;
if (args.length > 1
|| (args.length == 1 && args[0].compareTo("dump") != 0 && args[0]
.compareTo("notest") != 0)) {
System.err.println("Arguments: [dump] to dump all output");
System.err.println(" [notest] to skip tests");
System.err.println("No arguments justs tests output");
return;
}
if (args.length == 1) {
dumpall = true;
if (args[0].compareTo("notest") == 0)
notest = true;
}
String[][] tests = {
{ "g", "h", "a", "b", "a", "h", "j", "e", "e", "f" },
{ "5", "3", "1", "2", "7", "6", "0", "8", "9", "4", "3", "5",
"0", "9" }, {} };
String[][] expected = {
{
"([g,1] . .)",
"([g,1] . ([h,1] . .))",
"([g,1] ([a,1] . .) ([h,1] . .))",
"([g,1] ([a,1] . ([b,1] . .)) ([h,1] . .))",
"([g,1] ([a,2] . ([b,1] . .)) ([h,1] . .))",
"([g,1] ([a,2] . ([b,1] . .)) ([h,2] . .))",
"([g,1] ([a,2] . ([b,1] . .)) ([h,2] . ([j,1] . .)))",
"([g,1] ([a,2] . ([b,1] . ([e,1] . .))) ([h,2] . ([j,1] . .)))",
"([g,1] ([a,2] . ([b,1] . ([e,2] . .))) ([h,2] . ([j,1] . .)))",
"([g,1] ([a,2] . ([b,1] . ([e,2] . ([f,1] . .)))) ([h,2] . ([j,1] . .)))",
"a,2 b,1 e,2 f,1 g,1 h,2 j,1 " },
{
"([5,1] . .)",
"([5,1] ([3,1] . .) .)",
"([5,1] ([3,1] ([1,1] . .) .) .)",
"([5,1] ([3,1] ([1,1] . ([2,1] . .)) .) .)",
"([5,1] ([3,1] ([1,1] . ([2,1] . .)) .) ([7,1] . .))",
"([5,1] ([3,1] ([1,1] . ([2,1] . .)) .) ([7,1] ([6,1] . .) .))",
"([5,1] ([3,1] ([1,1] ([0,1] . .) ([2,1] . .)) .) ([7,1] ([6,1] . .) .))",
"([5,1] ([3,1] ([1,1] ([0,1] . .) ([2,1] . .)) .) ([7,1] ([6,1] . .) ([8,1] . .)))",
"([5,1] ([3,1] ([1,1] ([0,1] . .) ([2,1] . .)) .) ([7,1] ([6,1] . .) ([8,1] . ([9,1] . .))))",
"([5,1] ([3,1] ([1,1] ([0,1] . .) ([2,1] . .)) ([4,1] . .)) ([7,1] ([6,1] . .) ([8,1] . ([9,1] . .))))",
"([5,1] ([3,2] ([1,1] ([0,1] . .) ([2,1] . .)) ([4,1] . .)) ([7,1] ([6,1] . .) ([8,1] . ([9,1] . .))))",
"([5,2] ([3,2] ([1,1] ([0,1] . .) ([2,1] . .)) ([4,1] . .)) ([7,1] ([6,1] . .) ([8,1] . ([9,1] . .))))",
"([5,2] ([3,2] ([1,1] ([0,2] . .) ([2,1] . .)) ([4,1] . .)) ([7,1] ([6,1] . .) ([8,1] . ([9,1] . .))))",
"([5,2] ([3,2] ([1,1] ([0,2] . .) ([2,1] . .)) ([4,1] . .)) ([7,1] ([6,1] . .) ([8,1] . ([9,2] . .))))",
"0,2 1,1 2,1 3,2 4,1 5,2 6,1 7,1 8,1 9,2 " },
{ "", "No Data" } };
boolean error = false;
for (int i = 0; i < tests.length; i++) {
BinarySearchTree tree = new BinarySearchTree();
for (int j = 0; j < tests[i].length; j++) {
tree.incCount(tests[i][j]);
String out = tree.dump();
if (notest || out.compareTo(expected[i][j]) != 0)
error = true;
if (dumpall)
System.out.println(out);
}
if (tests[i].length < 1) {
String out = tree.dump();
if (notest || out.compareTo(expected[i][0]) != 0)
error = true;
if (dumpall)
System.out.println(out);
}
DataCount[] cnt = tree.getCounts();
String out = "";
if (cnt != null && cnt.length > 0)
for (int j = 0; j < cnt.length; j++)
out += cnt[j].data + "," + cnt[j].count + " ";
else
out = "No Data";
if (notest
|| out.compareTo(expected[i][expected[i].length - 1]) != 0)
error = true;
if (dumpall)
System.out.println(out);
}
if (!notest) {
if (error)
System.out.println("Test failed!");
else
System.out.println("Test passed.");
}
}
}
------------------------------------------------------------
/**
* TODO Replace this comment with your own.
*
* Stub code for an implementation of a DataCounter that uses a hash table as
* its backing data structure. We included this stub so that it's very clear
* that HashTable works only with Strings, whereas the DataCounter interface is
* generic. You need the String contents to write your hashcode code.
*/
public class HashTable implements DataCounter {
/** {@inheritDoc} */
public DataCount[] getCounts() {
// TODO Auto-generated method stub
return null;
}
/** {@inheritDoc} */
public int getSize() {
// TODO Auto-generated method stub
return 0;
}
/** {@inheritDoc} */
public void incCount(String data) {
// TODO Auto-generated method stub
}
}
------------------------------------------------------
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
/**
* FileWordReader reads words from a file one-by-one, converting to lowercase
* and eliminating punctuation. You can read a file in using:
*
*/
class FileWordReader {
StreamTokenizer tok;
public FileWordReader(String file) throws FileNotFoundException,
IOException {
tok = new StreamTokenizer(new BufferedReader(new InputStreamReader(
new FileInputStream(file))));
tok.eolIsSignificant(false);
tok.lowerCaseMode(true);
tok.wordChars('a', 'z');
tok.wordChars('A', 'Z');
String ws = " .,!;:-[].,;!?*+-=\|/(){}"[]><'";
for (int i = 0; i < ws.length(); i++) {
tok.whitespaceChars(ws.charAt(i), ws.charAt(i));
}
}
public String nextWord() throws IOException {
int ttype = tok.nextToken();
while (ttype != StreamTokenizer.TT_WORD
&& ttype != StreamTokenizer.TT_EOF)
ttype = tok.nextToken();
if (ttype == StreamTokenizer.TT_EOF)
return null;
return tok.sval;
}
};
-------------------------------------------------------
/**
* Simple class to hold a piece of data and its count. The class has package
* access so that the various implementations of DataCounter can access its
* contents, but not client code.
*
* @param <E> type of data whose count we are recording.
*/
class DataCount<E> {
/**
* The data element whose count we are recording.
*/
E data;
/**
* The count for the data element.
*/
int count;
/**
* Create a new data count.
*
* @param data the data element whose count we are recording.
* @param count the count for the data element.
*/
DataCount(E data, int count) {
this.data = data;
this.count = count;
}
}
/**
* Interface for a data structure that allows you to count the number of times
* you see each piece of data.
*
* Although you will be using this interface only with Strings, we have tried to
* "genericize" the code as much as possible. DataCounter counts elements of an
* unconstrained generic type E, and BinarySearchTree restricts E to Comparable
* types. HashTable is String-only, because you'll be implementing your own
* hashcode and will need access to the actual String contents.
*
* @param <E> The type of data to be counted.
*/
public interface DataCounter<E> {
/**
* Increment the count for a particular data element.
*
* @param data data element whose count to increment.
*/
public void incCount(E data);
/**
* The number of unique data elements in the structure.
*
* @return the number of unique data elements in the structure.
*/
public int getSize();
/**
* Get an array of all of the data counts in the DataCounter structure. The
* array should contain exactly one DataCount instance for each unique
* element inserted into the structure. The elements do not need to be in
* any particular order.
*
* @return an array of the data counts.
*/
public DataCount<E>[] getCounts();
}
Explanation / Answer
I assume, you want the implementation for hashtable.. below code should help you:
Thanks,
Let me know if you face any issues. Thanks!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.