/*
Class: cs312
Description: The task is to process a file of text to
produce a list of the words contained in the
document. Further we wish to count the occurrences
of each word within the document. To do this we must
maintain a list of the words in the text, and the
counts of each word. This can, of course, be done
by using an array. But it would not be very efficient.
A better choice is to use a Binary Search Tree.
With the Binary Search Tree, the word list will be
maintained in alphabetical order. Since we need to count
as well, what will be in the data field of the BST node.
Note: This program needs all of the files below so it can work
Separate compilation required and get your own text.file.
Do not expect to do everything for you.
*/
import java.io.*;
import java.util.StringTokenizer;
public class FrequencyList
{
public static void main(String[] args) throws IOException
{
String inLine = null;
String word;
WordRecord wordToTry;
WordRecord wordInTree;
WordRecord wordFromTree;
BinarySearchTree tree = new BinarySearchTree();
StringTokenizer tokenizer;
int numWords = 0;
int numValidWords = 0;
int numValidFreqs = 0;
int treeSize;
int minSize = 1;
int minFreq = 1;
String dataFileName = args[0];
String outFileName = args[1];
BufferedReader dataFile = new BufferedReader(new FileReader(dataFileName));
PrintWriter outFile = new PrintWriter(new FileWriter(outFileName));
inLine = dataFile.readLine();
while (inLine != null)
{
tokenizer = new StringTokenizer(inLine, " \t\n\r\\\"!@#$&*()_-+={}[]:;'<,>.?/1234567890");
while (tokenizer.hasMoreTokens())
{
word = tokenizer.nextToken();
numWords = numWords + 1;
if (word.length() >= minSize)
{
numValidWords = numValidWords + 1;
word = word.toLowerCase();
wordToTry = new WordRecord(word);
wordInTree = (WordRecord)tree.find(wordToTry);
if (wordInTree == null)
{
wordToTry.inc();
tree.insert(wordToTry);
}
else
{
wordInTree.inc();
}
}
}
inLine = dataFile.readLine();
}
treeSize = tree.reset(BinarySearchTree.INORDER);
outFile.println(numWords + " words in the input file. ");
outFile.println(numValidFreqs + " the sum of frequencies " );
outFile.println("Freq Word");
outFile.println("----- -----------------");
for (int count = 1; count <= treeSize; count++)
{
wordFromTree = (WordRecord) tree.getNextItem(BinarySearchTree.INORDER);
if (wordFromTree.CountIs() >= minFreq)
{
numValidFreqs = numValidFreqs + 1;
outFile.println(wordFromTree);
}
}
dataFile.close();
outFile.close();
}
}
/*__________________________________*/
//----------------------------------------------------------------------
// ArrayStack.java
//
// Implementation of the Stack interface using a fixed-length array.
// An exception is thrown if a push operation is attempted when the size
// of the stack is equal to the length of the array.
//----------------------------------------------------------------------
public class LinkedStack implements StackInterface
{
private class StackNode
{
private Object info;
private StackNode link;
}
private StackNode top;
public LinkedStack()
// Constructor
{
top = null;
}
/**
* O(1) time.
*/
public void push(Object item)
{
StackNode newNode = new StackNode();
newNode.info = item;
newNode.link = top;
top = newNode;
}
/**
* O(1) time.
*/
public void pop()
{
if (!isEmpty())
{
top = top.link;
}
else
throw new StackUnderflowException("Stack is Empty.");
}
/**
* O(1) time.
*/
public Object top()
{
if (!isEmpty())
return top.info;
else
throw new StackUnderflowException("Stack is Empty.");
}
/**
* O(1) time.
*/
public boolean isEmpty()
{
if (top == null)
return true;
else
return false;
}
public boolean isFull()
{
return false;
}
}
/*___________________________*/
//--------------------------------------------------------
// QueueInterface.java
//
// Interface for a class that implements a queue of Objects.
// A queue is a first-in, first-out structure.
//---------------------------------------------------------
public interface QueueInterface
{
// Adds Object element to tail of Queue.
public void enqueue(Object element);
// Removes and returns object from front of Queue.
public Object dequeue();
// Returns true if and only if Queue is empty
// false otherwise.
public boolean isEmpty();
// Determines whether this queue is full.
// Return value = (queue is full)
public boolean isFull();
}
/*__________________________________*/
public class StackOverflowException extends RuntimeException
{
public StackOverflowException()
{
}
public StackOverflowException(String message)
{
super(message);
}
}
/*____________________________*/
public class StackUnderflowException extends RuntimeException
{
public StackUnderflowException()
{
}
public StackUnderflowException(String message)
{
super(message);
}
}
/*_________________________________*/
//--------------------------------------------
// WordRecord.java
//
// Defines word-Record pairs
//--------------------------------------------
import java.text.DecimalFormat;
public class WordRecord implements Comparable
{
private String word;
private int Count;
DecimalFormat fmt = new DecimalFormat(" ");
public WordRecord(String newWord)
{
word = newWord;
Count = 0;
}
public void inc()
{
Count = Count + 1;
}
public int compareTo(Object otherWordRec)
{
WordRecord other = (WordRecord)otherWordRec;
return this.word.compareTo(other.word);
}
public String toString()
{
return(fmt.format(Count) + " " + word);
}
public String wordIs()
{
return word;
}
public int CountIs()
{
return Count;
}
}
/*________________________*/
//-----------------------------------------------
// ArrayQueue.java
//-----------------------------------------------
public class ArrayQueue implements QueueInterface
{
private Object[] queue;
private int capacity;
private int size = 0;
private int front = -1;
private int rear = 0;
// Constructors
public ArrayQueue()
{
queue = new Object[100];
capacity = 100;
}
public ArrayQueue(int maxSize)
{
queue = new Object[maxSize];
capacity = maxSize;
}
public void enqueue(Object e)
{
front = (front + 1) % capacity;
queue[front] = e;
size = size + 1;
}
public Object dequeue()
{
Object toReturn = queue[rear];
queue[rear] = null;
rear = (rear + 1) % capacity;
size = size - 1;
return toReturn;
}
public boolean isEmpty()
{
return (size == 0);
}
public boolean isFull()
{
return (size == capacity);
}
}
/*_______________________________*/
//___________________________________________________________________
// BinarySearchTree.java
//___________________________________________________________________
public class BinarySearchTree implements BSTInterface
{
protected class BSTNode
{
protected Comparable info;
protected BSTNode left;
protected BSTNode right;
}
protected BSTNode root;
protected ArrayQueue inOrderQueue;
protected ArrayQueue preOrderQueue;
protected ArrayQueue postOrderQueue;
public BinarySearchTree()
{
root = null;
}
public boolean isEmpty()
{
return (root == null);
}
public boolean isFull()
{
return false;
}
private int recNumberOfNodes(BSTNode tree)
{
if (tree == null)
return 0;
else
return recNumberOfNodes(tree.left) + recNumberOfNodes(tree.right) + 1;
}
public int numberOfNodes()
{
return recNumberOfNodes(root);
}
public int numberOfNodes2()
{
int count = 0;
if (root != null)
{
LinkedStack hold = new LinkedStack();
BSTNode currNode;
hold.push(root);
while (!hold.isEmpty())
{
currNode = (BSTNode) hold.top();
hold.pop();
count++;
if (currNode.left != null)
hold.push(currNode.left);
if (currNode.right != null)
hold.push(currNode.right);
}
}
return count;
}
private boolean recIsThere(Comparable item, BSTNode tree)
{
if (tree == null)
return false;
else if (item.compareTo(tree.info) < 0)
return recIsThere(item, tree.left);
else if (item.compareTo(tree.info) > 0)
return recIsThere(item, tree.right);
else
return true;
}
public boolean isThere (Comparable item)
{
return recIsThere(item, root);
}
private Comparable recRetrieve(Comparable item, BSTNode tree)
{
if (item.compareTo(tree.info) < 0)
return recRetrieve(item, tree.left);
else
if (item.compareTo(tree.info) > 0)
return recRetrieve(item, tree.right);
else
return tree.info;
}
public Comparable retrieve(Comparable item)
{
return recRetrieve(item, root);
}
private BSTNode recInsert(Comparable item, BSTNode tree)
{
if (tree == null)
{
tree = new BSTNode();
tree.right = null;
tree.left = null;
tree.info = item;
}
else if (item.compareTo(tree.info) < 0)
tree.left = recInsert(item, tree.left);
else
tree.right = recInsert(item, tree.right);
return tree;
}
public void insert (Comparable item)
{
root = recInsert(item, root);
}
private Comparable getPredecessor(BSTNode tree)
{
while (tree.right != null)
tree = tree.right;
return tree.info;
}
private BSTNode deleteNode(BSTNode tree)
{
Comparable data;
if (tree.left == null)
return tree.right;
else if (tree.right == null)
return tree.left;
else
{
data = getPredecessor(tree.left);
tree.info = data;
tree.left = recDelete(data, tree.left);
return tree;
}
}
private BSTNode recDelete(Comparable item, BSTNode tree)
{
if (item.compareTo(tree.info) < 0)
tree.left = recDelete(item, tree.left);
else if (item.compareTo(tree.info) > 0)
tree.right = recDelete(item, tree.right);
else
tree = deleteNode(tree);
return tree;
}
public void delete (Comparable item)
{
root = recDelete(item, root);
}
private void inOrder(BSTNode tree)
{
if (tree != null)
{
inOrder(tree.left);
inOrderQueue.enqueue(tree.info);
inOrder(tree.right);
}
}
private void preOrder(BSTNode tree)
{
if (tree != null)
{
preOrderQueue.enqueue(tree.info);
preOrder(tree.left);
preOrder(tree.right);
}
}
private void postOrder(BSTNode tree)
{
if (tree != null)
{
postOrder(tree.left);
postOrder(tree.right);
postOrderQueue.enqueue(tree.info);
}
}
public int reset(int orderType)
{
int numNodes = numberOfNodes();
if (orderType == INORDER)
{
inOrderQueue = new ArrayQueue(numNodes);
inOrder(root);
}
else
if (orderType == PREORDER)
{
preOrderQueue = new ArrayQueue(numNodes);
preOrder(root);
}
if (orderType == POSTORDER)
{
postOrderQueue = new ArrayQueue(numNodes);
postOrder(root);
}
return numNodes;
}
public Comparable getNextItem (int orderType)
{
if (orderType == INORDER)
return (Comparable)inOrderQueue.dequeue();
else
if (orderType == PREORDER)
return (Comparable)preOrderQueue.dequeue();
else
if (orderType == POSTORDER)
return (Comparable)postOrderQueue.dequeue();
else return null;
}
private Comparable recFind(Comparable item, BSTNode tree)
{
if (tree == null)
return null;
else if (item.compareTo(tree.info) < 0)
return recFind(item, tree.left);
else if (item.compareTo(tree.info) > 0)
return recFind(item, tree.right);
else
return tree.info;
}
public Comparable find (Comparable item)
{
return recFind(item, root);
}
}
/*______________________________*/
//_________________________________________________
// BSTInterface.java
//_________________________________________________
public interface BSTInterface
{
public static final int INORDER = 1;
public static final int PREORDER = 2;
public static final int POSTORDER = 3;
public boolean isEmpty();
public boolean isFull();
public int numberOfNodes();
public boolean isThere (Comparable item);
public Comparable retrieve(Comparable item);
public void insert (Comparable item);
public void delete (Comparable item);
public int reset(int orderType);
public Comparable getNextItem (int orderType);
}