Practice #

public class App {
    public static void main(String[] args) throws Exception {
        System.out.println("Hello, World!");
        MyArrayList<Integer> list = new MyArrayList<Integer>();
        list.add(2);
        list.add(1);
        list.add(3);
        System.out.println(list.search(1));
        System.out.println(list.search(2));

        list.delete(2);
        System.out.println(list.search(1));
        System.out.println(list.search(2));
    }
}

interface Query<T> {
  SearchableNode<T> search(T value);
  Query<T> add(T value);
  Query<T> delete(T value);
}

abstract class SearchableNode<T> {
    private T value;

    public T getValue() {
        return value;
    }
    
    public void setValue(T value) {
        this.value = value;
    }
}


class ArrayListNode<T> extends SearchableNode<T> {
    @Override
    public String toString() {
        return "ArrayListNode[" + this.getValue() + "]";
    }
}

class MyArrayList<T> implements Query<T> {
    private ArrayListNode<T>[] data = new ArrayListNode[0];
    
    public SearchableNode<T> search(T value) {
        for(ArrayListNode<T> cur: data) {
            System.out.println("Searching " + cur.toString());
            if (cur.getValue() == value)
                return cur;
        }
        return null;
    }
    
    public Query<T> add(T value) {
        ArrayListNode<T>[] newData = new ArrayListNode[this.data.length+1];
        for(int i = 0; i < data.length; i++) {
            newData[i] = data[i];
        }
        ArrayListNode<T> newNode = new ArrayListNode<T>();
        newNode.setValue(value);
        newData[data.length] = newNode;
        this.data = newData;
        return this;
    }
    
    public Query<T> delete(T value) {
        ArrayListNode<T>[] newData = new ArrayListNode[this.data.length-1];
        int idx = 0;
        for(int i = 0; i < data.length; i++) {
            if (data[i].getValue() != value) {
                newData[idx] = data[i];
                idx++;
            }
        }
        this.data = newData;
        return this;
    }
}

public class App {
    public static void main(String[] args) throws Exception {
        System.out.println("Hello, World!");
        Query<Integer> list = new MyLinkedList<Integer>();
        list.add(2);
        System.out.println("Found " + list.search(2));
        list.delete(2);
        System.out.println("Found " + list.search(2));

        list.add(2);
        list.add(1);
        list.add(3);
        System.out.println("Found " + list.search(1));
        System.out.println("Found " + list.search(2));

        list.delete(2);
        System.out.println("Found " + list.search(1));
        System.out.println("Found " + list.search(2));
    }
}

interface Query<T> {
  SearchableNode<T> search(T value);
  Query<T> add(T value);
  Query<T> delete(T value);
}

abstract class SearchableNode<T> {
    private T value;

    public T getValue() {
        return value;
    }
    
    public void setValue(T value) {
        this.value = value;
    }
}


class LinkedListNode<T> extends SearchableNode<T> {
    private LinkedListNode<T> next;

    @Override
    public String toString() {
        return "LinkedListNode[" + this.getValue() + "]";
    }

    public LinkedListNode<T> getNext() {
        return next;
    }

    public void setNext(LinkedListNode<T> next) {
        this.next = next;
    }
}

class MyLinkedList<T> implements Query<T> {
    private LinkedListNode<T> head = new LinkedListNode<T>();
    private LinkedListNode<T> tail = head;

    public SearchableNode<T> search(T value) {
        LinkedListNode<T> node = head;
        while (node != null) {
            System.out.println("Searching " + node.toString());
            if (node.getValue() == value) {
                return node;
            }
            node = node.getNext();
        }
        return null;
    }
    
    public Query<T> add(T value) {
        LinkedListNode<T> node = new LinkedListNode<T>();
        node.setValue(value);
        tail.setNext(node);
        tail = node;
        return this;
    }
    
    public Query<T> delete(T value) {
        LinkedListNode<T> cur = head;
        while (cur != null) {
            LinkedListNode<T> next = cur.getNext();
            if (next != null && next.getValue() == value) {
                cur.setNext(next.getNext());
            }
            if (next == tail) {
                tail = cur;
            }
            cur = cur.getNext();
        }
        return this;
    }
}

public class App {
    public static void main(String[] args) throws Exception {
        System.out.println("Hello, World!");
        Query<Integer> list = new MyLinkedList<Integer>();
        list.add(2);
        System.out.println("Found " + list.search(2));
        list.delete(2);
        System.out.println("Found " + list.search(2));

        list.add(2);
        list.add(1);
        list.add(3);
        System.out.println("Found " + list.search(1));
        System.out.println("Found " + list.search(2));

        list.delete(2);
        System.out.println("Found " + list.search(1));
        System.out.println("Found " + list.search(2));
    }
}

interface Query<T> {
  SearchableNode<T> search(T value);
  Query<T> add(T value);
  Query<T> delete(T value);
}

abstract class SearchableNode<T> {
    private T value;

    public T getValue() {
        return value;
    }
    
    public void setValue(T value) {
        this.value = value;
    }
}


class LinkedListNode<T> extends SearchableNode<T> {
    private LinkedListNode<T> next;
    private LinkedListNode<T> prev;

    @Override
    public String toString() {
        return "LinkedListNode[" + this.getValue() + "]";
    }

    public LinkedListNode<T> getNext() {
        return next;
    }

    public void setNext(LinkedListNode<T> next) {
        this.next = next;
    }

    public LinkedListNode<T> getPrev() {
        return prev;
    }

    public void setPrev(LinkedListNode<T> prev) {
        this.prev = prev;
    }
}

class MyLinkedList<T> implements Query<T> {
    private LinkedListNode<T> head = new LinkedListNode<T>();
    private LinkedListNode<T> tail = new LinkedListNode<T>();

    public MyLinkedList() {
        head.setNext(tail);
        tail.setPrev(head);
    }

    public SearchableNode<T> search(T value) {
        // front to back
        LinkedListNode<T> node = head.getNext();
        while (node != tail) {
            if (node.getValue().equals(value)) {
                return node;
            }
            node = node.getNext();
        }
        return null;

        // back to front
        LinkedListNode<T> node = tail.getPrev();
        while (node != head) {
            if (node.getValue().equals(value)) {
                return node;
            }
            node = node.getPrev();
        }
        return null;
    }
    
    public Query<T> add(T value) {
        LinkedListNode<T> node = new LinkedListNode<T>();
        node.setValue(value);

        node.setPrev(tail.getPrev());
        node.setNext(tail);

        tail.getPrev().setNext(node);
        tail.setPrev(node);

        return this;
    }
    
    public Query<T> delete(T value) {
        LinkedListNode<T> cur = head.getNext();
        while (cur != tail) {
            if (cur.getValue().equals(value)) {
                cur.getPrev().setNext(cur.getNext());
                cur.getNext().setPrev(cur.getPrev());
                break;
            }
            cur = cur.getNext();
        }
        return this;
    }
}

public class App {
    public static void main(String[] args) throws Exception {
        System.out.println("Hello, World!");
        MyQueue<Integer> queue = new MyQueue<Integer>();
        queue.enqueue(1).enqueue(2).enqueue(3);
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
    }
}

interface QueueInterface<T> {
    QueueInterface<T> enqueue(T value);
    T dequeue();
}

class MyQueue<T> implements QueueInterface<T> {
    private LinkedListNode<T> head = new LinkedListNode<T>();
    private LinkedListNode<T> tail = head;

    public QueueInterface<T> enqueue(T value) {
        LinkedListNode<T> node = new LinkedListNode<T>();
        node.setValue(value);
        tail.setNext(node);
        tail = node;
        return this;
    }
    
    public T dequeue() {
        LinkedListNode<T> node = head.getNext();
        if (node != null) {
            head.setNext(node.getNext());
            if (node == tail) {
                tail = head;
            }
            return node.getValue();
        }
        return null;
    }
}

class MyQueue<T> implements QueueInterface<T> {
    private LinkedListNode<T> head = new LinkedListNode<T>();
    private LinkedListNode<T> tail = new LinkedListNode<T>();

    public MyQueue() {
        head.setNext(tail);
        tail.setPrev(head);
    }

    public QueueInterface<T> enqueue(T value) {
        LinkedListNode<T> node = new LinkedListNode<T>();
        node.setValue(value);

        node.setPrev(tail.getPrev());
        node.setNext(tail);

        // add to tail
        tail.getPrev().setNext(node);
        tail.setPrev(node);

        return this;
    }
    
    public T dequeue() {
        if (head.getNext() != tail) {
            LinkedListNode<T> node = head.getNext();
            // remove from head
            head.setNext(node.getNext());
            node.getNext().setPrev(head);
            return node.getValue();
        }
        return null;
    }
}

interface Query<T> {
  SearchableNode<T> search(T value);
  Query<T> add(T value);
  Query<T> delete(T value);
}

abstract class SearchableNode<T> {
    private T value;

    public T getValue() {
        return value;
    }
    
    public void setValue(T value) {
        this.value = value;
    }
}

public class App {
    public static void main(String[] args) {
        System.out.println("Hello world");

        MyStack<Integer> stack = new MyStack<Integer>();

        stack.push(1).push(2).push(3);

        System.out.println("Popped: " + stack.pop());
        System.out.println("Popped: " + stack.pop());

        stack.push(4);

        System.out.println("Popped: " + stack.pop());
        System.out.println("Popped: " + stack.pop());

        System.out.println("Popped: " + stack.pop());
    }
}

interface StackInterface<T> {
    StackInterface<T> push(T value);
    T pop();
}
class MyStack<T> implements StackInterface<T> {
    private LinkedListNode<T> head = new LinkedListNode<T>();
    private LinkedListNode<T> tail = new LinkedListNode<T>();

    public MyStack() {
        head.setNext(tail);
        tail.setPrev(head);
    }

    public StackInterface<T> push(T value) {
        LinkedListNode<T> node = new LinkedListNode<T>();
        node.setValue(value);

        node.setPrev(tail.getPrev());
        node.setNext(tail);

        tail.getPrev().setNext(node);
        tail.setPrev(node);

        return this;
    }
    
    public T pop() {
        if (tail.getPrev() != head) {
            LinkedListNode<T> node = tail.getPrev();
            node.getPrev().setNext(tail);
            tail.setPrev(node.getPrev());
            return node.getValue();
        }
        return null;
    }
}

public class App {
    public static void main(String[] args) {
        System.out.println("Hello world");

        MyStack<Integer> stack = new MyStack<Integer>(10);

        stack.push(1).push(2).push(3);

        System.out.println("Popped: " + stack.pop());
        System.out.println("Popped: " + stack.pop());

        stack.push(4);

        System.out.println("Popped: " + stack.pop());
        System.out.println("Popped: " + stack.pop());

        System.out.println("Popped: " + stack.pop());
    }
}

interface StackInterface<T> {
    StackInterface<T> push(T value);
    T pop();
}

class MyStack<T> implements StackInterface<T> {
    private T[] stackArray;
    private int top;
    private int capacity;

    public MyStack(int size) {
        capacity = size;
        stackArray = (T[]) new Object[capacity];
        top = -1;
    }

    public StackInterface<T> push(T value) {
        if (top < capacity - 1) {
            top++;
            stackArray[top] = value;
            return this;
        } else {
            System.out.println("Stack Overflow");
            return this;
        }
    }

    public T pop() {
        if (top >= 0) {
            T value = stackArray[top];
            top--;
            return value;
        } else {
            System.out.println("Stack Underflow");
            return null;
        }
    }
}

public class App {
    public static void main(String[] args) {
        System.out.println("Hello world");

        int[] arr = {1, 2, 3, 5, 6, 7, 8, 9, 10, 11};

        System.out.println("Found at idx: " + binarySearch(arr, 5));
        System.out.println("Found at idx: " + binarySearch(arr, 10));
        System.out.println("Found at idx: " + binarySearch(arr, 4));
    }

    public static int binarySearch(int[] arr, int value) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            System.out.println("Left idx: " + left + " Right idx: " + right + " Mid idx: " + mid);
            System.out.println("Mid value: " + arr[mid]);
            if (arr[mid] == value) {
                return mid;
            } else if (arr[mid] < value) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

public class App {
    public static void main(String[] args) {
        System.out.println("Hello world");

        BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
        bst.insert(5).insert(3).insert(7).insert(2).insert(4).insert(6).insert(8);

        System.out.println("Found: " + bst.search(2));
        System.out.println("Found: " + bst.search(8));
        System.out.println("Found: " + bst.search(1));
    }
}

class BinarySearchTree<T extends Comparable<T>> {
    private BinarySearchTreeNode<T> root;

    public BinarySearchTree<T> insert(T value) {
        if (root == null) {
            root = new BinarySearchTreeNode<T>();
            root.setValue(value);
        } else {
            root.insert(value);
        }
        return this;
    }

    public BinarySearchTreeNode<T> search(T value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }
}

class BinarySearchTreeNode<T extends Comparable<T>> {
    private T value;
    private BinarySearchTreeNode<T> left;
    private BinarySearchTreeNode<T> right;
    
    public String toString() {
        return "BinarySearchTreeNode[value="+this.value+"]";
    }

    public BinarySearchTreeNode<T> search(T value) {
        System.out.println("Searching current node: " + this.value);
        if (this.value == value) {
            return this;
        } else if (this.value.compareTo(value) < 0) {
            System.out.println("Going right");
            if (right == null) {
                return null;
            } else {
                return right.search(value);
            }
        } else {
            System.out.println("Going left");
            if (left == null) {
                return null;
            } else {
                return left.search(value);
            }
        }
    }

    public BinarySearchTreeNode<T> insert(T value) {
        if (this.value.compareTo(value) < 0) {
            if (right == null) {
                right = new BinarySearchTreeNode<T>();
                right.setValue(value);
                return right;
            } else {
                return right.insert(value);
            }
        } else {
            if (left == null) {
                left = new BinarySearchTreeNode<T>();
                left.setValue(value);
                return left;
            } else {
                return left.insert(value);
            }
        }
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public BinarySearchTreeNode<T> getLeft() {
        return left;
    }

    public void setLeft(BinarySearchTreeNode<T> left) {
        this.left = left;
    }

    public BinarySearchTreeNode<T> getRight() {
        return right;
    }

    public void setRight(BinarySearchTreeNode<T> right) {
        this.right = right;
    }
}

import java.util.Map;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;
import java.util.Collections;

public class App {
    public static void main(String[] args) {
        System.out.println("Hello world");

        HuffmanTree tree = generateHuffmanTree("Hello world! This is a test message.");
        tree.print();
        System.out.println("Encoded (H): " + tree.encode("H"));
        System.out.println("Encoded (space): " + tree.encode(" "));
        System.out.println("Encoded (e): " + tree.encode("e"));
        
        String encoded = tree.encode("Hello world! This is a test message.");
        System.out.println("Encoded: " + encoded);
        
        System.out.println("Decoded: " + tree.decode(encoded));
    }

    public static HuffmanTree generateHuffmanTree(String message) {
        // calculate the frequencies of characters
        Map<Character, Integer> frequencyMap = new HashMap<Character, Integer>();
        for (char c: message.toCharArray()) {
            if (frequencyMap.containsKey(c)) {
                frequencyMap.put(c, frequencyMap.get(c) + 1);
            } else {
                frequencyMap.put(c, 1);
            }
        }

        // create the tree nodes
        List<HuffmanTreeNode> queue = new ArrayList<HuffmanTreeNode>();
        for (Map.Entry<Character, Integer> entry: frequencyMap.entrySet()) {
            queue.add(new HuffmanTreeNode(entry.getKey(), entry.getValue()));
        }

        // sort the nodes by frequency
        Collections.sort(queue, new Comparator<HuffmanTreeNode>() {
            @Override
            public int compare(HuffmanTreeNode o1, HuffmanTreeNode o2) {
                return o1.getFrequency() - o2.getFrequency();
            }
        });

        // when we still have more than 1 item in the queue
        while (queue.size() > 1) {
            // merge the two nodes with the lowest frequency
            HuffmanTreeNode left = queue.remove(0);
            HuffmanTreeNode right = queue.remove(0);
            HuffmanTreeNode parent = new HuffmanTreeNode('\0', left.getFrequency() + right.getFrequency(), left, right);

            // add the parent node back to the queue and sort again
            queue.add(parent);
            Collections.sort(queue, new Comparator<HuffmanTreeNode>() {
                @Override
                public int compare(HuffmanTreeNode o1, HuffmanTreeNode o2) {
                    return o1.getFrequency() - o2.getFrequency();
                }
            });
        }
        return new HuffmanTree(queue.get(0));
    }
}

class HuffmanTree {
    private HuffmanTreeNode root;

    public HuffmanTree(HuffmanTreeNode root) {
        this.root = root;
    }

    public String encode(String message) {
        StringBuilder sb = new StringBuilder();
        for (char c: message.toCharArray()) {
            sb.append(root.encode(c));
        }
        return sb.toString();
    }

    public String decode(String encoded) {
        StringBuilder sb = new StringBuilder();

        // search from the root
        HuffmanTreeNode cur = root;
        for (char c: encoded.toCharArray()) {
            if (c == '0') {
                cur = cur.getLeft();
            } else {
                cur = cur.getRight();
            }
            if (cur.isLeaf()) {
                // leaf node includes the character
                sb.append(cur.getValue());

                // reset the current node to the root
                cur = root;
            }
        }
        return sb.toString();
    }

    public void print() {
        root.print();
    }
}

class HuffmanTreeNode {
    private char value;
    private int frequency;
    private HuffmanTreeNode left;
    private HuffmanTreeNode right;

    public HuffmanTreeNode(char value, int frequency) {
        this.value = value;
        this.frequency = frequency;
    }

    public HuffmanTreeNode(char value, int frequency, HuffmanTreeNode left, HuffmanTreeNode right) {
        this.value = value;
        this.frequency = frequency;
        this.left = left;
        this.right = right;
    }

    public boolean isLeaf() {
        return left == null && right == null;
    }

    public String encode(char c) {
        if (isLeaf()) {
            return value == c ? "" : null;
        } else {
            String left = this.left.encode(c);
            if (left != null) {
                return "0" + left;
            }
            String right = this.right.encode(c);
            if (right != null) {
                return "1" + right;
            }
            return null;
        }
    }

    public void print() {
        print("", true);
    }

    private void print(String prefix, boolean isTail) {
        System.out.println(prefix + (isTail ? "\\-- " : "|-- ") + "Node[value=" + value + ", freq=" + frequency + "]");
        if (left != null) {
            left.print(prefix + (isTail ? "    " : "|   "), right == null);
        }
        if (right != null) {
            right.print(prefix + (isTail ? "    " : "|   "), true);
        }
    }

    private void print(int level) {
        for (int i = 0; i < level; i++) {
            System.out.print("  ");
        }
        System.out.println("HuffmanTreeNode[value=" + value + ", frequency=" + frequency + ", leaf=" + isLeaf() + "]");
        if (left != null) {
            left.print(level + 1);
        }
        if (right != null) {
            right.print(level + 1);
        }
    }

    public char getValue() {
        return value;
    }

    public void setValue(char value) {
        this.value = value;
    }

    public int getFrequency() {
        return frequency;
    }

    public void setFrequency(int frequency) {
        this.frequency = frequency;
    }

    public HuffmanTreeNode getLeft() {
        return left;
    }

    public void setLeft(HuffmanTreeNode left) {
        this.left = left;
    }

    public HuffmanTreeNode getRight() {
        return right;
    }

    public void setRight(HuffmanTreeNode right) {
        this.right = right;
    }
}

import java.util.List;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;

public class App {
    public static void main(String[] args) {
        System.out.println("Hello world");

        Graph<Integer> graph = new Graph<Integer>();
        GraphNode<Integer> node1 = graph.addNode(1);
        GraphNode<Integer> node2 = graph.addNode(2);
        GraphNode<Integer> node3 = graph.addNode(3);
        GraphNode<Integer> node4 = graph.addNode(4);
        GraphNode<Integer> node5 = graph.addNode(5);
        GraphNode<Integer> node6 = graph.addNode(6);
        GraphNode<Integer> node7 = graph.addNode(7);

        graph.addEdge(node1, node2);
        graph.addEdge(node1, node3);
        graph.addEdge(node2, node4);
        graph.addEdge(node2, node6);
        graph.addEdge(node6, node7);
        graph.addEdge(node3, node4);
        graph.addEdge(node4, node5);

        System.out.println("DFS:");
        dfs(node1);
    }

    public static void dfs(GraphNode<Integer> node) {
        System.out.println("Visiting node: " + node);
        node.setVisited(true);
        for (GraphNode<Integer> neighbour: node.getNeighbours()) {
            if (!neighbour.isVisited()) {
                dfs(neighbour);
            }
        }
    }
}

class GraphNode<T> {
    private T value;
    private List<GraphNode<T>> neighbours = new ArrayList<GraphNode<T>>();
    private boolean visited;

    public GraphNode(T value) {
        this.value = value;
    }

    public void addNeighbour(GraphNode<T> node) {
        neighbours.add(node);
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public List<GraphNode<T>> getNeighbours() {
        return neighbours;
    }

    public void setNeighbours(List<GraphNode<T>> neighbours) {
        this.neighbours = neighbours;
    }

    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public String toString() {
        return "GraphNode[value=" + value + "]";
    }
}

class Graph<T> {
    private List<GraphNode<T>> nodes = new ArrayList<GraphNode<T>>();

    public GraphNode<T> addNode(T value) {
        GraphNode<T> node = new GraphNode<T>(value);
        nodes.add(node);
        return node;
    }

    public void addEdge(GraphNode<T> node1, GraphNode<T> node2) {
        node1.addNeighbour(node2);
        node2.addNeighbour(node1);
    }

    public List<GraphNode<T>> getNodes() {
        return nodes;
    }

    public void setNodes(List<GraphNode<T>> nodes) {
        this.nodes = nodes;
    }
}

import java.util.List;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;

public class App {
    public static void main(String[] args) {
        System.out.println("Hello world");

        Graph<Integer> graph = new Graph<Integer>();
        GraphNode<Integer> node1 = graph.addNode(1);
        GraphNode<Integer> node2 = graph.addNode(2);
        GraphNode<Integer> node3 = graph.addNode(3);
        GraphNode<Integer> node4 = graph.addNode(4);
        GraphNode<Integer> node5 = graph.addNode(5);
        GraphNode<Integer> node6 = graph.addNode(6);
        GraphNode<Integer> node7 = graph.addNode(7);

        graph.addEdge(node1, node2);
        graph.addEdge(node1, node3);
        graph.addEdge(node2, node4);
        graph.addEdge(node2, node6);
        graph.addEdge(node6, node7);
        graph.addEdge(node3, node4);
        graph.addEdge(node4, node5);

        System.out.println("DFS:");
        dfs(node1, new HashSet<GraphNode<Integer>>());
    }

    public static void dfs(GraphNode<Integer> node, Set<GraphNode<Integer>> visited) {
        System.out.println("Visiting node: " + node);
        visited.add(node);
        for (GraphNode<Integer> neighbour: node.getNeighbours()) {
            if (!visited.contains(neighbour)) {
                dfs(neighbour, visited);
            }
        }
    }
}

class GraphNode<T> {
    private T value;
    private List<GraphNode<T>> neighbours = new ArrayList<GraphNode<T>>();

    public GraphNode(T value) {
        this.value = value;
    }

    public void addNeighbour(GraphNode<T> node) {
        neighbours.add(node);
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public List<GraphNode<T>> getNeighbours() {
        return neighbours;
    }

    public void setNeighbours(List<GraphNode<T>> neighbours) {
        this.neighbours = neighbours;
    }

    public String toString() {
        return "GraphNode[value=" + value + "]";
    }
}

class Graph<T> {
    private List<GraphNode<T>> nodes = new ArrayList<GraphNode<T>>();

    public GraphNode<T> addNode(T value) {
        GraphNode<T> node = new GraphNode<T>(value);
        nodes.add(node);
        return node;
    }

    public void addEdge(GraphNode<T> node1, GraphNode<T> node2) {
        node1.addNeighbour(node2);
        node2.addNeighbour(node1);
    }

    public List<GraphNode<T>> getNodes() {
        return nodes;
    }

    public void setNodes(List<GraphNode<T>> nodes) {
        this.nodes = nodes;
    }
}

import java.util.List;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Queue;

public class App {
    public static void main(String[] args) {
        System.out.println("Hello world");

        Graph<Integer> graph = new Graph<Integer>();
        GraphNode<Integer> node1 = graph.addNode(1);
        GraphNode<Integer> node2 = graph.addNode(2);
        GraphNode<Integer> node3 = graph.addNode(3);
        GraphNode<Integer> node4 = graph.addNode(4);
        GraphNode<Integer> node5 = graph.addNode(5);
        GraphNode<Integer> node6 = graph.addNode(6);
        GraphNode<Integer> node7 = graph.addNode(7);

        graph.addEdge(node1, node2);
        graph.addEdge(node1, node3);
        graph.addEdge(node2, node4);
        graph.addEdge(node2, node6);
        graph.addEdge(node6, node7);
        graph.addEdge(node3, node4);
        graph.addEdge(node4, node5);

        System.out.println("BFS:");
        bfs(node1);
    }

    public static void bfs(GraphNode<Integer> node) {
        Queue<GraphNode<Integer>> queue = new java.util.LinkedList<GraphNode<Integer>>();
        queue.add(node);
        while (!queue.isEmpty()) {
            GraphNode<Integer> cur = queue.remove();
            System.out.println("Current node: " + cur);
            if (cur.isVisited())
                continue;
            System.out.println("Visiting node: " + cur);
            cur.setVisited(true);
            for (GraphNode<Integer> neighbour: cur.getNeighbours()) {
                if (!neighbour.isVisited()) {
                    queue.add(neighbour);
                }
            }
        }
    }
}


class GraphNode<T> {
    private T value;
    private List<GraphNode<T>> neighbours = new ArrayList<GraphNode<T>>();
    private boolean visited;

    public GraphNode(T value) {
        this.value = value;
    }

    public void addNeighbour(GraphNode<T> node) {
        neighbours.add(node);
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public List<GraphNode<T>> getNeighbours() {
        return neighbours;
    }

    public void setNeighbours(List<GraphNode<T>> neighbours) {
        this.neighbours = neighbours;
    }

    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public String toString() {
        return "GraphNode[value=" + value + "]";
    }
}

class Graph<T> {
    private List<GraphNode<T>> nodes = new ArrayList<GraphNode<T>>();

    public GraphNode<T> addNode(T value) {
        GraphNode<T> node = new GraphNode<T>(value);
        nodes.add(node);
        return node;
    }

    public void addEdge(GraphNode<T> node1, GraphNode<T> node2) {
        node1.addNeighbour(node2);
        node2.addNeighbour(node1);
    }

    public List<GraphNode<T>> getNodes() {
        return nodes;
    }

    public void setNodes(List<GraphNode<T>> nodes) {
        this.nodes = nodes;
    }
}

import java.util.List;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Comparator;

public class App {
    public static void main(String[] args) {
        System.out.println("Hello world");

        Graph<Integer> graph = new Graph<Integer>();
        GraphNode<Integer> node1 = graph.addNode(1);
        GraphNode<Integer> node2 = graph.addNode(2);
        GraphNode<Integer> node3 = graph.addNode(3);
        GraphNode<Integer> node4 = graph.addNode(4);
        GraphNode<Integer> node5 = graph.addNode(5);
        GraphNode<Integer> node6 = graph.addNode(6);
        GraphNode<Integer> node7 = graph.addNode(7);

        graph.addEdge(node1, node2, 2);
        graph.addEdge(node1, node3, 4);
        graph.addEdge(node2, node4, 7);
        graph.addEdge(node2, node6, 3);
        graph.addEdge(node6, node7, 1);
        graph.addEdge(node3, node4, 2);
        graph.addEdge(node4, node5, 1);

        System.out.println("Dijkstra:");
        dijkstra(node1);
    }

    public static void dijkstra(GraphNode<Integer> node) {
        node.setDistance(0);
        Queue<GraphNode<Integer>> queue = new PriorityQueue<GraphNode<Integer>>(new Comparator<GraphNode<Integer>>() {
            @Override
            public int compare(GraphNode<Integer> o1, GraphNode<Integer> o2) {
                return o1.getDistance() - o2.getDistance();
            }
        });
        queue.add(node);
        while (!queue.isEmpty()) {
            GraphNode<Integer> cur = queue.remove();
            System.out.println("Current node: " + cur);
            if (cur.isVisited())
                continue;
            System.out.println("Visiting node: " + cur);
            cur.setVisited(true);
            for (GraphEdge<Integer> edge: cur.getEdges()) {
                GraphNode<Integer> neighbour = edge.getTo();
                int distance = cur.getDistance() + edge.getWeight();
                if (distance < neighbour.getDistance()) {
                    neighbour.setDistance(distance);
                    neighbour.setPrevious(cur);
                    queue.add(neighbour);
                }
            }
        }
    }
}

class GraphEdge<T> {
    private GraphNode<T> from;
    private GraphNode<T> to;
    private int weight;

    public GraphEdge(GraphNode<T> from, GraphNode<T> to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    public GraphNode<T> getFrom() {
        return from;
    }

    public void setFrom(GraphNode<T> from) {
        this.from = from;
    }

    public GraphNode<T> getTo() {
        return to;
    }

    public void setTo(GraphNode<T> to) {
        this.to = to;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }
}

class GraphNode<T> {
    private T value;
    private List<GraphEdge<T>> edges = new ArrayList<>();
    private int distance = Integer.MAX_VALUE;
    private GraphNode<T> previous; 
    private boolean visited;

    public GraphNode(T value) {
        this.value = value;
    }

    public void addEdge(GraphEdge<T> edge) {
        edges.add(edge);
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public List<GraphEdge<T>> getEdges() {
        return edges;
    }

    public void setEdges(List<GraphEdge<T>> edges) {
        this.edges = edges;
    }

    public int getDistance() {
        return distance;
    }

    public void setDistance(int distance) {
        this.distance = distance;
    }

    public GraphNode<T> getPrevious() {
        return previous;
    }

    public void setPrevious(GraphNode<T> previous) {
        this.previous = previous;
    }
    
    public boolean isVisited() {
        return visited;
    }
    
    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public String toString() {
        return "GraphNode[value=" + value + ", distance=" + this.getDistance() + ", prev=" + this.getPrevious() + "]";
    }
}

class Graph<T> {
    private List<GraphNode<T>> nodes = new ArrayList<GraphNode<T>>();

    public GraphNode<T> addNode(T value) {
        GraphNode<T> node = new GraphNode<T>(value);
        nodes.add(node);
        return node;
    }

    public void addEdge(GraphNode<T> node1, GraphNode<T> node2, int weight) {
        // undirected graph
        GraphEdge<T> edge1 = new GraphEdge<>(node1, node2, weight);
        GraphEdge<T> edge2 = new GraphEdge<>(node2, node1, weight);
        node1.addEdge(edge1);
        node2.addEdge(edge2);
    }

    public List<GraphNode<T>> getNodes() {
        return nodes;
    }

    public void setNodes(List<GraphNode<T>> nodes) {
        this.nodes = nodes;
    }
}