Counting the most comonly occurring words in a text file. - *** Do not change th
ID: 3763973 • Letter: C
Question
Counting the most comonly occurring words in a text file. - *** Do not change the given code ***
Part A:
Create a binary search tree that can be used as both a min and max priority queue.
Part B:
Min & Max priority queue analysis. State runtime complexity and any dependencies that ma affect it if they don’t hold. What can and can’t it do well?
Part C:
- Implement an industrial strength balanced binary search tree so you can count all the words in a file that appear repeatedly (more than a given number value of times).
- Compare that number of words that meet the number of times criteria to the total number of words in the file for a percentage.
- In alphabetical order, print the common words and the number of times each one appears
//****************Given Code (fill in method with your own code)**********************************************
import java.io.FileNotFoundException;
import java.io.File;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.SortedMap;
public class CommonWords {
// PART A: MIN/MAX QUEUE
static class Node {
Node(int key) {
this.key = key;
}
int key;
Node left, right;
}
private Node root;
// ADD ELEMENT IF NOT ALREADY PRESENT. IGNORE DUPLICATE VALUES
public void add(int key) {
//*****YOUR CODE HERE**************
// PRIVATE NODE ADD METHOD BELOW MUST BE USED HERE IN YOUR CODE.
}
//REMOVE MIN ELEMENT. RETURN ELEMENT REMOVED
public int removeMin() {
//*****YOUR CODE HERE**************
return 0;
}
//REMOVE MAX ELEMENT. RETURN ELEMENT REMOVED
public int removeMax() {
//*****YOUR CODE HERE**************
return 0;
}
//GET QUEUE SIZE. RETURNS SIZE OF QUEUE
public int getSize() {
//*****YOUR CODE HERE**************
return 0;
}
// JUST CHANGE THIS CODE SO IT INCREMENTS THE SIZE, THEN USE IT IN THE ABOVE 'ADD' METHOD
private Node add(Node node, int key) {
if (node == null)
return new Node(key);
if (node.key > key)
node.left = add(node.left, key);
else if (node.key < key)
node.right = add(node.right, key);
return node;
}
/* PART B: MIN & MAX QUEUE ANALYSIS. STATE RUNTIME COMPLEXITY AND ANY DEPENDENCIES THAT MAY
AFFECT IT IF THEY DON'T HOLD
*/
//PART C: COMMON WORD
/**
- IN ALPHABETICAL ORDER, PRINT WORDS IN TEXT FILE THAT OCCUR MORE THAN THE GIVEN NUMBER
OF TIMES. ALSO PRINT EACH WORD'S COUNT.
- CONVERT ALL WORDS READ FROM FILE TO LOWERCASE IGNORING 'EMPTY' WORDS
*/
static void mostCommonWords(String filename, int numOfTimes) { //'filename' is text file name, 'numOfTimes' is occurrence threshold
SortedMap map = new TreeMap();
//***************YOUR CODE HERE************
// USEFUL STRING METHODS TO USE:
// split(), toLowerCase(), trim(), isEmpty()
//ITERATE OVER PAIRS AND PRINT THOSE THAT MEET THE 'numOfTimes' CRITERIA
// System.out.println(word + " " + count);
System.out.println("WORDS TOTAL : " + 0);
System.out.println("NUMBER OF COMMON WORDS: " + 0);
System.out.println("PERCENT OF TOTAL WORDS THAT ARE COMMON WORDS: " + 0);
}
// TEST HERE IN MAIN
public static void main(String[] args) {
/*
EXAMPLE CODE BELOW. WRITE/TEST YOUR OWN HERE
*/
Project5 queue = new Project5();
queue.add(6);
queue.add(8);
queue.add(3);
queue.add(6); // 6 IS IGNORED AS A DUPLICATE
int size = queue.getSize(); // RETURNS 3
int min = queue.removeMin(); // REMOVES AND RETURNS 3
int max = queue.removeMax(); // REMOVES AND RETURNS 6
size = queue.getSize(); // RETURNS 1
System.out.println("Most frequent words:");
mostCommonWords("AnyText.txt", 5);
}
}
Explanation / Answer
import java.io.*;
import java.util.*;
class Node {
Object data;
Node right,left,parent;
int hi;
public Node(){
this(null,null,null,null,0);
}
public Node(Object e,Node p,Node l,Node r,int h){
data=e;
left=l; right=r; parent=p;
hi=h;
}
}
class BinaryTree {
Node root=new Node();
Node currentNode;
int size=0;
public BinaryTree(Object a){
root.data=a;
root.hi=1;
Node Left=new Node(); Node Right=new Node();
root.left=Left; root.right=Right;
Left.parent=root; Right.parent=root;
size++;
}
boolean IsExternal(Node n){
return (n.left==null && n.right==null);
}
int SubTreeSize(Node n){
if (IsExternal(n)) return 0;
else return 1+SubTreeSize(n.left)+SubTreeSize(n.right);
}
boolean op(Object a,Object b){
return (Integer)a<(Integer)b;
}
public int removeMax() {
if (root == null) return 0;
Node temp = root;
while(temp.right != null)
temp = temp.right;
int d = temp.data;
delete(temp);
return d;
}
public int removeMin() {
if (root == null) return 0;
Node temp = root;
while(temp.left != null)
temp = temp.left;
int d = temp.data;
delete(temp);
return d;
}
Node search(Object o){
currentNode=root;
while(!IsExternal(currentNode)){
if((Integer)currentNode.data-(Integer)o==0) { System.out.println("Successfully Found The Desired Result"); return currentNode; }
else if (op(o,currentNode.data)) currentNode=currentNode.left;
else currentNode=currentNode.right;
}
if (currentNode.data!=o) {
System.out.println("NOT FOUND TRY FOR DIFFERENT INTEGER");
return null;
}
else return currentNode;
}
int height(Node n){ if (n==null) return 0; else return n.hi; }
void updatehieght(Node n){ if (n==null) return; else n.hi=Math.max(height(n.left),height(n.right))+1; }
void insert(Object o){
Node temp=new Node();
temp=root;
while (!IsExternal(temp)){
if (op(o,temp.data)) temp=temp.left;
else temp=temp.right;
}
temp.data = o;
temp.hi = 1;
Node Left = new Node(); Node Right = new Node();
temp.left=Left; temp.right=Right;
Left.parent=temp; Right.parent=temp;
size++;
while (temp.parent!=null) {
updatehieght(temp.parent);
temp=temp.parent;
}
}
void delete1(Node n){
if (n.left.data==null && n.right.data==null){
n.data=null;
n.left=null;
n.right=null;
while (n.parent!=null){
updatehieght(n.parent);
n=n.parent;
}
}
else if (!IsExternal(n.right) && n.left.data==null) {
n.right.parent=n.parent;
if (n.parent.right==n) n.parent.right=n.right;
else n.parent.left=n.right;
while (n.parent!=null) {
updatehieght(n.parent);
n=n.parent;
}
}
else if (!IsExternal(n.left) && n.left.data==null){
n.left.parent=n.parent;
if (n.parent.left==n) n.parent.left=n.left;
else n.parent.right=n.left;
while (n.parent!=null) {
updatehieght(n.parent);
n=n.parent;
}
}
}
void delete(Object t){
if (search(t)==null) { System.out.println("NOT HERE Can not delete"); return; }
else {
size--;
Node n=search(t);
if (n.left.data==null && n.right.data==null){
n.data=null;
n.left=null;
n.right=null;
while (n.parent!=null){
updatehieght(n.parent);
n=n.parent;
}
}
else if (!IsExternal(n.right) && n.left.data==null) {
n.right.parent=n.parent;
if (n.parent.right==n) n.parent.right=n.right;
else n.parent.left=n.right;
while (n.parent!=null) {
updatehieght(n.parent);
n=n.parent;
}
}
else if (!IsExternal(n.left) && n.left.data==null){
n.left.parent=n.parent;
if (n.parent.left==n) n.parent.left=n.left;
else n.parent.right=n.left;
while (n.parent!=null) {
updatehieght(n.parent);
n=n.parent;
}
}
else {
Node currentNode1=n.left;
while(!IsExternal(currentNode1)){
currentNode1=currentNode1.right;
}
Object te=currentNode1.parent.data;
currentNode1.parent.data=n.data;
n.data=te;
delete1(currentNode1.parent);
}
System.out.println("Successfully Deleted the Desired Result");
}
}
void printtree(Node n){
if (!IsExternal(n)){
printtree(n.left);
System.out.print("the element is "+n.data+"----");
System.out.println("its hieght is "+n.hi);
printtree(n.right);
}
}
}