Question

JAVA DATA STRUCTURES:

Reading a Text file of words into two different data structures

1. Use a Binary search tree and then
2.Use a Hash Map.

*USE BOTH BINARY & HASH MAP*

* Get the file name as a user input.*

Present a menu to the user with the below options:
1) Delete the first occurrence of a given word.
2) Delete all the occurrences of a given word.

Answer 1

Test.java

import javafx.util.Pair;
//import weiss.nonstandard.BinarySearchTree;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class Test {

    private static List<List<String>> tokenize(String p) throws IOException {

        FileReader file = new FileReader(p);
        BufferedReader buffer = new BufferedReader(file);

        String line = buffer.readLine();

        StringTokenizer tokenizer;

        List<List<String>> matrix = new ArrayList<>();

        while (line != null) {

            tokenizer = new StringTokenizer(line, " ,.:;?!-_");

            List<String> row = new ArrayList<>();

            while (tokenizer.hasMoreElements()) {

                row.add(tokenizer.nextToken().toLowerCase());

            }

            matrix.add(row);

            line = buffer.readLine();
        }

        return matrix;
    }

    private static ArrayList<Pair<String, String>> proccess() throws IOException {

        ArrayList<Pair<String, String>> word_line_pair = new ArrayList<>();

        List<List<String>> word_matrix = tokenize("D:\\Users\\Enea\\Documents\\Project-2\\src\\sample");

        Set<String> s = new HashSet<>();

        String position = "";

        for (List<String> row : word_matrix) {

            s.addAll(row);
        }

        ArrayList<String> words = new ArrayList<>(s);

        int k = 0;
        while (k < words.size()) {
            for (int i = 0; i < word_matrix.size(); i++) {

                for (int j = 0; j < word_matrix.get(i).size(); j++) {

                    if (words.get(k).equals(word_matrix.get(i).get(j))) {
                        position = position.concat((i + 1) + "");
                    }

                }
            }

            word_line_pair.add(new Pair<>(words.get(k), position));

            position = "";

            k++;
        }

        return word_line_pair;
    }

    public static void main(String[] args) throws IOException {

        BinarySearchTree<String> bst = new BinarySearchTree<>();

        for (Pair word : proccess()) {

            bst.set(word.getValue().toString());
            bst.insert(word.getKey().toString());

        }

        Scanner c = new Scanner(System.in);
        Scanner s = new Scanner(System.in);

        System.out.println("1: Help");
        System.out.println("2: Display number of distinct words");
        System.out.println("3: Display number of occurrences of a particular word");
        System.out.println("4: Print all words that appear more than some number, inputted by the user");
        System.out.println("5: Display the line numbers on which is found a certain word, inputted by the user");
        System.out.println("6: Delete the first occurrence of a given word");
        System.out.println("7: Delete all the occurrences of a given word");
        System.out.println("8: Search for a word that do not exists in the given file");
        System.out.println("0: Exit");

        boolean check = true;

        while (check) {

            int i = c.nextInt();

            switch (i) {

                case 1:
                    System.out.println("Yelp");
                    break;
                case 2:
                    bst.printInOrder();
                    break;
                case 3:
                    System.out.println("Input a word.");
                    bst.freq(s.next().toLowerCase());
                    break;
                case 4:
                    System.out.println("Print words with more than x ocurrences.");
                    System.out.print("Input x: ");
                    bst.more_than(s.nextInt());
                    break;
                case 5:
                    System.out.println("Show lines numbers of a word.");
                    System.out.println("Input word.");
                    String t = s.next();
                    bst.lines(t);
                    break;
                case 6:
                    System.out.println("Deleting first occurrence of word.");
                    System.out.println("Input word.");
                    bst.delete_first(s.next());
                    break;
                case 7:
                    System.out.println("Deleting all occurrences of word.");
                    System.out.println("Input word.");
                    String temp = s.next();
                    bst.remove(temp);
                    System.out.println("All occurrences of " + temp + "removed!");
                    break;
                case 8:
                    System.out.println("Search for word.");
                    System.out.println("Input word.");
                    if (bst.find(s.next()) == null) {
                        System.out.println("Word not found!");
                    } else
                        System.out.println("Word found!");
                    break;
                case 0:
                    check = !check;
                    break;
            }

        }

    }

}

BinarySearchTree.java

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
    /**
     * The tree root.
     */
    protected BinaryNode<AnyType> root;

    /**
     * Construct the tree.
     */
    public BinarySearchTree() {
        root = null;
    }

    // Test program
    public static void main(String[] args) {
    }

    /**
     * Insert into the tree.
     *
     * @param x the item to insert.
     * @throws DuplicateItemException if x is already present.
     */
    public void insert(AnyType x) {
        root = insert(x, root);
    }

    /**
     * Remove from the tree..
     *
     * @param x the item to remove.
     * @throws ItemNotFoundException if x is not found.
     */
    public void remove(AnyType x) {
        root = remove(x, root);
    }

    /**
     * Remove minimum item from the tree.
     *
     * @throws ItemNotFoundException if tree is empty.
     */
    public void removeMin() {
        root = removeMin(root);
    }

    /**
     * Find the smallest item in the tree.
     *
     * @return smallest item or null if empty.
     */
    public AnyType findMin() {
        return elementAt(findMin(root));
    }

    /**
     * Find the largest item in the tree.
     *
     * @return the largest item or null if empty.
     */
    public AnyType findMax() {
        return elementAt(findMax(root));
    }

    public void lines(AnyType x) {

        String temp = find(x, root).getPosition();
        StringBuilder str = new StringBuilder();
        for (char s : temp.toCharArray()) {
            str.append(s).append(",");
        }
        System.out.println("\"" + x.toString() + "\"" + " appears in lines: " + str.toString());
    }

    public void delete_first(AnyType x) {

        find(x, root).setPosition(find(x, root).getPosition().substring(1, 2));
        System.out.println("First occurrence removed!");
    }

    public void more_than(int i) {

        BinaryNode curr = root;
        Stack<BinaryNode> s = new Stack<>();

        while (curr != null || !s.isEmpty()) {

            while (curr != null) {

                s.push(curr);
                curr = curr.left;
            }

            curr = s.pop();

            if (curr.getPosition().length() > i)
                System.out.println("\"" + curr.getElement() + "\"" + " occurs more than " + i + " time(s)!");

            curr = curr.right;
        }

    }

    /**
     * Find an item in the tree.
     *
     * @param x the item to search for.
     * @return the matching item or null if not found.tv
     */
    public AnyType find(AnyType x) {
        return elementAt(find(x, root));
    }

    /**
     * Make the tree logically empty.
     */
    public void makeEmpty() {
        root = null;
    }

    /**
     * Test if the tree is logically empty.
     *
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * Internal method to get element field.
     *
     * @param t the node.
     * @return the element field or null if t is null.
     */
    private AnyType elementAt(BinaryNode<AnyType> t) {
        return t == null ? null : t.element;
    }

    public void freq(AnyType t) {

        int i = find(t, root).position.length();
        System.out.println("Frequency of \"" + t + "\" : " + i);

    }

    public void printInOrder() {

        BinaryNode curr = root;
        Stack<BinaryNode> s = new Stack<>();
        int count = 0;

        while (curr != null || !s.isEmpty()) {

            while (curr != null) {

                s.push(curr);
                curr = curr.left;
            }

            curr = s.pop();

            count++;
            //System.out.println("Word: " + curr.element + " Pos: " + curr.getPosition());

            curr = curr.right;
        }

        System.out.println("Number of distinct words: " + count);
    }

    private String pos = "";

    public void set(String x) {
        this.pos = x;
    }

    /**
     * Internal method to insert into a subtree.
     *
     * @param x the item to insert.
     * @param t the node that roots the tree.
     * @return the new root.
     * @throws DuplicateItemException if x is already present.
     */
    protected BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            t = new BinaryNode<>(x);
            t.setPosition(pos);
        }
        else if (x.compareTo(t.element) < 0)
            t.left = insert(x, t.left);
        else if (x.compareTo(t.element) > 0)
            t.right = insert(x, t.right);
        else
            //t.incCount();
            throw new DuplicateItemException(x.toString()); // Duplicate

        return t;
    }

    /**
     * Internal method to remove from a subtree.
     *
     * @param x the item to remove.
     * @param t the node that roots the tree.
     * @return the new root.
     * @throws ItemNotFoundException if x is not found.
     */
    protected BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
        if (t == null)
            throw new ItemNotFoundException(x.toString());
        if (x.compareTo(t.element) < 0)
            t.left = remove(x, t.left);
        else if (x.compareTo(t.element) > 0)
            t.right = remove(x, t.right);
        else if (t.left != null && t.right != null) // Two children
        {
            t.element = findMin(t.right).element;
            t.right = removeMin(t.right);
        } else
            t = (t.left != null) ? t.left : t.right;
        return t;
    }

    /**
     * Internal method to remove minimum item from a subtree.
     *
     * @param t the node that roots the tree.
     * @return the new root.
     * @throws ItemNotFoundException if t is empty.
     */
    protected BinaryNode<AnyType> removeMin(BinaryNode<AnyType> t) {
        if (t == null)
            throw new ItemNotFoundException();
        else if (t.left != null) {
            t.left = removeMin(t.left);
            return t;
        } else
            return t.right;
    }

    /**
     * Internal method to find the smallest item in a subtree.
     *
     * @param t the node that roots the tree.
     * @return node containing the smallest item.
     */
    protected BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
        if (t != null)
            while (t.left != null)
                t = t.left;

        return t;
    }

    /**
     * Internal method to find the largest item in a subtree.
     *
     * @param t the node that roots the tree.
     * @return node containing the largest item.
     */
    private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
        if (t != null)
            while (t.right != null)
                t = t.right;

        return t;
    }

    /**
     * Internal method to find an item in a subtree.
     *
     * @param x is item to search for.
     * @param t the node that roots the tree.
     * @return node containing the matched item.
     */
    private BinaryNode<AnyType> find(AnyType x, BinaryNode<AnyType> t) {
        while (t != null) {
            if (x.compareTo(t.element) < 0)
                t = t.left;
            else if (x.compareTo(t.element) > 0)
                t = t.right;
            else
                return t;    // Match
        }

        return null;         // Not found
    }
}

BinaryNode.java

class BinaryNode<AnyType> {
    // Data; accessible by other package routines
    AnyType element; // The data in the node
    BinaryNode<AnyType> left;     // Left child
    BinaryNode<AnyType> right;    // Right child
    Integer count;
    String position;

    // Constructor
    BinaryNode(AnyType theElement) {
        element = theElement;
        left = right = null;
    }

    public AnyType getElement() {
        return element;
    }

    public String getPosition() {
        return position;
    }

    public void setPosition(String position) {
        this.position = position;
    }
}

Stack.java
public interface Stack<AnyType>
{
    /**
     * Insert a new item into the stack.
     * @param x the item to insert.
     */
    void    push(AnyType x);

    /**
     * Remove the most recently inserted item from the stack.
     * @return
     * @exception UnderflowException if the stack is empty.
     */
    BinaryNode    pop();
  
    /**
     * Get the most recently inserted item in the stack.
     * Does not alter the stack.
     * @return the most recently inserted item in the stack.
     * @exception UnderflowException if the stack is empty.
     */
    AnyType top();

    /**
     * Return and remove the most recently inserted item
     * from the stack.
     * @return the most recently inserted item in the stack.
     * @exception UnderflowException if the stack is empty.
     */
    AnyType topAndPop();
  
    /**
     * Test if the stack is logically empty.
     * @return true if empty, false otherwise.
     */
    boolean isEmpty();

    /**
     * Make the stack logically empty.
     */
    void    makeEmpty();
}

ItemNotFoundException.java

public class ItemNotFoundException extends RuntimeException
{
    /**
     * Construct this exception object.
     */
    public ItemNotFoundException( )
    {
        super( );
    }
  
    /**
     * Construct this exception object.
     * @param message the error message.
     */
    public ItemNotFoundException( String message )
    {
        super( message );
    }
}

DuplicateItemException.java

public class DuplicateItemException extends RuntimeException
{
    /**
     * Construct this exception object.
     */
    public DuplicateItemException( )
    {
        super( );
    }
    /**
     * Construct this exception object.
     * @param message the error message.
     */
    public DuplicateItemException( String message )
    {
        super( message );
    }
}