Final Exam 2024 Exercise

Main1.java

import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Scanner;

class NoElementExceptionInStackException extends RuntimeException {
    public NoElementExceptionInStackException() {
        super("No element in stack to pop");
    }
}

class MyStack {
    private ArrayList<Integer> data;
    int top;

    public MyStack() {
        data = new ArrayList<>();
        top = -1;
    }

    public void push(int value) {
        data.add(value);
        top++;
    }

    public int pop() throws NoElementExceptionInStackException {
        if (top == -1) {
            throw new NoElementExceptionInStackException();
        }

        int value = data.get(top);
        data.remove(top);
        top--;
        return value;
    }

    @Override
    public String toString() {
        return data.toString();
    }
}

class ElementDuplicationException extends RuntimeException {
    public ElementDuplicationException() {
        super("The element is already in the binary search tree");
    }
}

class BinarySearchTree {
    private class Node {
        int data;
        Node left;
        Node right;
    }

    private Node root;
    private int size = 0;

    public void insert(int value) {
        if (root == null) {
            root = new Node();
            root.data = value;
            size++;
        } else {
            insert(root, value);
        }
    }

    public void insert(Node node, int value) {
        if (value < node.data) {
            if (node.left == null) {
                Node newNode = new Node();
                newNode.data = value;
                node.left = newNode;
                size++;
            } else {
                insert(node.left, value);
            }
        } else if (value > node.data) {
            if (node.right == null) {
                Node newNode = new Node();
                newNode.data = value;
                node.right = newNode;
                size++;
            } else {
                insert(node.right, value);
            }
        } else {
            throw new ElementDuplicationException();
        }
    }

    public String inOrder() {
        return inOrder(root, "");
    }

    public String inOrder(Node node, String prev) {
        String str = "";
        if (node != null) {
            str += inOrder(node.left, prev);
            str += node.data + " ";
            str += inOrder(node.right, prev);
        }
        return prev + str;
    }

    public String widthFirstLn() {
        return widthFirstLn(root);
    }

    public String widthFirstLn(Node root) {
        String str = "";

        if (root == null) {
            return str;
        }

        Node[] queue = new Node[size];
        int rear = 0, front = 0;
        queue[rear++] = root;
        int lvl = rear;
        Node n;
        while (front < rear) {
            n = queue[front];
            str += queue[front++].data + " ";
            if (n.left != null) queue[rear++] = n.left;
            if (n.right != null) queue[rear++] = n.right;
            if (front == lvl) {
                str += "\n";
                lvl = rear;
            }
        }

        return str;
    }
}

public class Main {
    public static void main(String[] args) {
        try {
            Scanner console = new Scanner(System.in);
            FileWriter fileWriter = new FileWriter("bst-output.txt");

            MyStack stack = new MyStack();

            while (true) {
                System.out.print("Enter a number, or nothing to quit: ");
                String input = console.nextLine();

                if (input.isEmpty()) {
                    break;
                }

                try {
                    int number = Integer.parseInt(input);
                    stack.push(number);
                    System.out.println("Pushed " + number + ". stack: " + stack);
                } catch (NumberFormatException e) {
                    System.out.println("Invalid number");
                }
            }

            BinarySearchTree bst = new BinarySearchTree();
            while (stack.top != -1) {
                int number = stack.pop();
                System.out.println("Popped " + number + ". stack: " + stack);
                try {
                    bst.insert(number);
                } catch (ElementDuplicationException e) {
                    System.out.println(e.getMessage());
                    System.out.println("Skipping " + number + "...");
                }
            }

            fileWriter.write("In order traversal:\n");
            fileWriter.write(bst.inOrder());
            fileWriter.write("\n");

            fileWriter.write("\nWidth first traversal:\n");
            fileWriter.write(bst.widthFirstLn());
            fileWriter.write("\n");

            fileWriter.close();
            console.close();
        } catch (Exception e) {
            System.out.println("Exception: " + e.getMessage());
        }
    }
}

Main2.java

import java.io.File;
import java.util.ArrayList;
import java.util.Scanner;

class Human {
    private String name;
    private int age;

    public Human(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Human{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

class Patient extends Human {
    public Patient(String name, int age) {
        super(name, age);
    }

    @Override
    public String toString() {
        return "Patient{" +
                "name='" + getName() + '\'' +
                ", age=" + getAge() +
                '}';
    }
}

class NoElementInQueueException extends RuntimeException {
    public NoElementInQueueException() {
        super("No element in queue to dequeue");
    }
}

class MyQueue<T> {
    private ArrayList<T> data = new ArrayList<T>();
    int front = 0, rear = -1, size = 0;

    public void enqueue(T item) {
        data.add(item);
        rear++;
        size++;
    }

    public T dequeue() {
        if (size == 0) {
            throw new IllegalStateException("Queue is empty");
        }
        T item = data.get(front);
        front++;
        size--;
        return item;
    }

    @Override
    public String toString() {
        String result = "";

        for (int i = front; i < rear; i++) {
            result += data.get(i) + ", ";
        }
        result += data.get(rear);

        return result;
    }

    public T recursiveJumpSearch(String name) {
        ArrayList<T> sorted = new ArrayList<T>();
        for (int i = front; i <= rear; i++) {
            sorted.add(data.get(i));
        }
        sorted.sort((o1, o2) -> {
            String name1 = ((Human) o1).getName();
            String name2 = ((Human) o2).getName();
            return name1.compareTo(name2);
        });
        return recursiveJumpSearch(sorted, name, front, (int) Math.sqrt(size));
    }

    public T recursiveJumpSearch(ArrayList<T> sorted, String name, int index, int step) {
        if (index >= sorted.size() || ((Human) sorted.get(index)).getName().compareTo(name) > 0) {
            if (step == 1) {
                return null;
            }
            return recursiveJumpSearch(sorted, name, index - step, 1);
        }

        if (((Human) sorted.get(index)).getName().equals(name)) {
            return sorted.get(index);
        }

        return recursiveJumpSearch(sorted, name, index + step, step);
    }
}

public class Main {
    public static void main(String[] args) {
        try {
            File file = new File("patients.txt");
            Scanner scanner = new Scanner(file);

            MyQueue<Patient> queue = new MyQueue<Patient>();
            while (scanner.hasNextLine()) {
                String line = scanner.nextLine();
                String[] parts = line.split(" ");
                String name = parts[0];
                int age = Integer.parseInt(parts[1]);
                Patient patient = new Patient(name, age);
                queue.enqueue(patient);
            }

            System.out.println("Patients all inputted, queue:" + queue);

            Scanner console = new Scanner(System.in);

            boolean run = true;
            while (run) {
                System.out.println("Options:");
                System.out.println("1. Show patient queue");
                System.out.println("2. Remove patient from queue");
                System.out.println("3. Show number of patients in queue");
                System.out.println("4. Search for patient in queue");
                System.out.println("5. Exit");
                char option = console.next().charAt(0);

                switch (option) {
                    case '1' -> System.out.println("Queue: " + queue);
                    case '2' -> {
                        Patient patient = queue.dequeue();
                        System.out.println("Patient removed: " + patient);
                    }
                    case '3' -> System.out.println("Number of patients in queue: " + queue.size);
                    case '4' -> {
                        System.out.println("Enter patient name to search:");
                        String name = console.next();
                        Patient patient = queue.recursiveJumpSearch(name);
                        if (patient == null) {
                            System.out.println("Patient not found");
                        } else {
                            System.out.println("Patient found: " + patient);
                        }
                    }
                    case '5' -> run = false;
                    default -> System.out.println("Invalid option");
                }
            }
        } catch (Exception e) {
            System.out.println("Exception: " + e.getMessage());
        }
    }
}

patients.txt

John 34
Alex 23
Austin 45
Michael 19
Justin 34
Julia 21
Hannah 32
Ethan 25