Untitled

import java.util.*;
import java.util.concurrent.*;

class TreeNode {
    public String value;
    private ArrayList<TreeNode> children;
    private boolean lock;
    public int parentLockCount;
    public int childLockCount;
    private TreeNode parentNode;
    private int userId;

    public TreeNode (String value, TreeNode parentNode) {
        this.value = value;
        this.parentNode = parentNode;
        // defaults
        this.lock = false;
        this.parentLockCount = 0;
        this.childLockCount = 0;
        this.children = new ArrayList<>();
        this.userId = -1;
    }

    public void addChild(TreeNode child) {
        this.children.add(child);
    }

    public synchronized boolean isLocked() {
        return this.lock;
    }

    public TreeNode getParent() {
        return this.parentNode;
    }

    public synchronized void lockNode(int userId) {
        this.lock = true;
        this.userId = userId;
    }

    public synchronized void unlockNode() {
        this.lock = false;
        this.userId = -1;
    }

    public synchronized int getLocker() {
        return this.userId;
    }

    public synchronized void changeParentCount(int count) {
        this.parentLockCount += count;
    }

    public synchronized void changeChildCount(int count) {
        this.childLockCount += count;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "value='" + value + '\'' +
                ", lock=" + lock +
                ", parentLockCount=" + parentLockCount +
                ", childLockCount=" + childLockCount +
                ", parentNode=" + (parentNode == null ? "NULL" : parentNode.value) +
                ", userId=" + userId +
                '}';
    }

    public ArrayList<TreeNode> getChildren() {
        return this.children;
    }
}

public class Main {

    private HashMap<String, TreeNode> store = new HashMap<>();

    private synchronized TreeNode generateTree (ArrayList<String> strings, int m) {
        TreeNode root = new TreeNode(strings.get(0), null);
        store.put(strings.get(0), root);

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        int idx = 1;

        while(!queue.isEmpty()) {
            TreeNode current = queue.poll();

            if (idx >= strings.size()) continue;

            // children
            for (int i = idx; i < idx + m; i++) {
                TreeNode currChild = new TreeNode(strings.get(i), current);
                store.put(strings.get(i), currChild);
                queue.add(currChild);
                current.addChild(currChild);
            }
            idx+=m;
        }

        return root;
    }

    private void printTree(TreeNode root) {
        if (root == null) return;

        System.out.println(root);
        ArrayList<TreeNode> children = root.getChildren();
        for (TreeNode child : children) {
            printTree(child);
        }
    }

    // utility
    private void propoagateToChild (TreeNode current, int value) {
        synchronized (this) {
            Queue<TreeNode> queue = new ArrayDeque<>();

            queue.add(current);
            while (!queue.isEmpty()) {
                TreeNode curr = queue.poll();
                if (current != curr)
                    curr.changeParentCount(value);
                ArrayList<TreeNode> children = curr.getChildren();
                queue.addAll(children);
            }
        }
    }

    private boolean checkChildLocks (TreeNode current, int userId, ArrayList<TreeNode> lockedNodes) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(current);

        while(!queue.isEmpty()) {
            TreeNode curr = queue.poll();

            ArrayList<TreeNode> children = curr.getChildren();
            for (TreeNode child : children) {
                if (child.isLocked()) {
                    if (child.getLocker() == userId) {
                        lockedNodes.add(child);
                    } else {
                        return false;
                    }
                }
                queue.add(child);
            }
        }
        return true;
    }

    public synchronized boolean lock (String value, int userId) {
        if (!store.containsKey(value)) return false;
        TreeNode current = store.get(value);

        // check node and parents
        if (current.parentLockCount != 0) return false;
        // check children
        if (current.childLockCount != 0) return false;

        // lock the node
        current.lockNode(userId);

        // propagate the lock to parent and child nodes
        TreeNode prntNode = current.getParent();
        while(prntNode != null) {
//            prntNode.childLockCount++;
            prntNode.changeChildCount(+1);
            prntNode = prntNode.getParent();
        }
        propoagateToChild(current, 1);
        return true;
    }

    public synchronized String verboseLock(String value, int userId) {
        System.out.println("lock>>" + Thread.currentThread().getName() + "  [Value : " + value + " userid : " + userId + "]");
        if (!store.containsKey(value)) return "[LOCK]Node > " + value + " status > FAILED";
        TreeNode current = store.get(value);

        // check node and parents
        if (current.parentLockCount != 0) return "[LOCK]Node > " + value + " status > FAILED";
        // check children
        if (current.childLockCount != 0) return "[LOCK]Node > " + value + " status > FAILED";

        // lock the node
        current.lockNode(userId);

        // propagate the lock to parent and child nodes
        TreeNode prntNode = current.getParent();
        while(prntNode != null) {
//            prntNode.childLockCount++;
            prntNode.changeChildCount(+1);
            prntNode = prntNode.getParent();
        }
        propoagateToChild(current, 1);
        return "[LOCK]Node > " + value + " status > PASS";
    }

    public synchronized boolean unlock(String value, int userId) {
        if (!store.containsKey(value)) return false;

        TreeNode current = store.get(value);
        if (!current.isLocked()) return false;
        if (current.isLocked() && current.getLocker() != userId) return false;

        // lock the node
        current.unlockNode();

        // propagate the unlock to parent and child
        TreeNode prntNode = current.getParent();
        while(prntNode != null) {
//            prntNode.childLockCount--;
            prntNode.changeChildCount(-1);
            prntNode = prntNode.getParent();
        }

        propoagateToChild(current, -1);
        return true;
    }

    public synchronized String verboseUnlock (String value, int userId) {
//        System.out.println("[Value : " + value + " userid : " + userId + "]");
        System.out.println("Unlock>>" + Thread.currentThread().getName() + "  [Value : " + value + " userid : " + userId + "]");
        if (!store.containsKey(value)) return "[UNLOCK]Node > " + value + " status > FAILED";

        TreeNode current = store.get(value);
        if (!current.isLocked()) return "[UNLOCK]Node > " + value + " status > FAILED";
        if (current.isLocked() && current.getLocker() != userId) return "[UNLOCK]Node > " + value + " status > FAILED";

        // lock the node
        current.unlockNode();

        // propagate the unlock to parent and child
        TreeNode prntNode = current.getParent();
        while(prntNode != null) {
//            prntNode.childLockCount--;
            prntNode.changeChildCount(-1);
            prntNode = prntNode.getParent();
        }

        propoagateToChild(current, -1);
        return "[UNLOCK]Node > " + current.value + " status > PASS";
    }

    public synchronized boolean upgrade(String value, int userId) {
        if (!store.containsKey(value)) return false;

        TreeNode current = store.get(value);

        if (current.isLocked()) return false;

        // check if any ancestor is locked
        if (current.parentLockCount != 0) return false;

        // check child nodes
        if (current.childLockCount != 0) {
            ArrayList<TreeNode> lockedChildNodes = new ArrayList<>();
            boolean childLocksValid = checkChildLocks(current, userId, lockedChildNodes);
            if (childLocksValid) {
                // unlock all the child nodes
                for (TreeNode childNodes : lockedChildNodes) {
                    unlock(childNodes.value, userId);
                }
            } else {
                return false; // all child nodes are not of the same lock
            }
        } else {
            return false; // no locked child nodes are there
        }

        lock(value, userId);
        return true; // child nodes unlocked.
    }

    public synchronized String verboseUpgrade(String value, int userId) {
//        System.out.println("[Value : " + value + " userid : " + userId + "]");
        System.out.println("upgrade>>" + Thread.currentThread().getName() +  "  [Value : " + value + " userid : " + userId + "]");
        if (!store.containsKey(value)) return "[UPGRADE]Node > " + value + " status > FAILED";

        TreeNode current = store.get(value);

        if (current.isLocked()) return "[UPGRADE]Node > " + value + " status > FAILED";

        // check if any ancestor is locked
        if (current.parentLockCount != 0) return "[UPGRADE]Node > " + value + " status > FAILED";

        // check child nodes
        if (current.childLockCount != 0) {
            ArrayList<TreeNode> lockedChildNodes = new ArrayList<>();
            boolean childLocksValid = checkChildLocks(current, userId, lockedChildNodes);
            if (childLocksValid) {
                // unlock all the child nodes
                for (TreeNode childNodes : lockedChildNodes) {
                    unlock(childNodes.value, userId);
                }
            } else {
                return "[UPGRADE]Node > " + value + " status > FAILED"; // all child nodes are not of the same lock
            }
        } else {
            return "[UPGRADE]Node > " + value + " status > FAILED"; // no locked child nodes are there
        }

        lock(value, userId);
        return "[UPGRADE]Node > " + value + " status > PASS"; // child nodes unlocked.
    }

    public static void main(String[] args) {
        int n = 7, m = 2, q = 4;
        String[] arr = new String[] {
                "World", "Asia", "Africa", "India", "China", "SouthAfrica", "Egypt"
        };
        ArrayList<String> arrLst = new ArrayList<>();
        Collections.addAll(arrLst, arr);
        /*
                    "World", 0
                  /              \
             "Asia", 1          "Africa", 2
             /    \             /               \
     "India", 3   "China", 4 "SouthAfrica",5  "Egypt", 6
        */

        Main object = new Main();

        System.out.println(arrLst + " : " + arrLst.size());

        TreeNode root = object.generateTree(arrLst, m);

        //out.println("Tree generated : ");
        //object.printTree(root);


        // QUERIES
        String[] queries = new String[] {
                "1 China 9",
                "2 India 9",
                "3 Asia 9",
                "2 India 9"
        };

        String[] queries2 = new String[] {
                "1 Asia 122",
                "1 SouthAfrica 122",
                "3 World 122",
                "2 Asia 122",
                "1 SouthAfrica 123",
                "1 India 126",
                "2 World 122",
                "1 China 122",
                "1 Egypt 122",
                "3 Africa 122"
        };

        q = queries2.length;

        // DEBUG
//        System.out.println(object.lock("Asia", 122));
//        System.out.println(object.lock("SouthAfrica", 122));
//        System.out.println(object.upgrade("World", 122));



        // Create threads
        // # of threads = # of queries
//        ExecutorService executors = Executors.newFixedThreadPool(q);
//        List<Callable<Boolean>> callableTasks = new ArrayList<>(); // stores the tasks.

        long startTime = System.currentTimeMillis();

        // Testing ..
        ExecutorService executors = Executors.newFixedThreadPool(q);
        List<Callable<String>> callableTasks = new ArrayList<>();

        // operations
        for (int i = 0; i < q; i++) {
            // parse the string.
            String[] parsed = queries2[i].split("\\s");

            int operationCode = Integer.parseInt(parsed[0])-1;
            String value = parsed[1];
            int userId = Integer.parseInt(parsed[2]);

            callableTasks.add(() ->
                    switch (operationCode) {
                        case 0 -> object.verboseLock(value, userId);
                        case 1 -> object.verboseUnlock(value, userId);
                        case 2 -> object.verboseUpgrade(value, userId);
                        default -> "INVALID";
                    }
            );
        }

//        List<Future<Boolean>> futureResults = new ArrayList<>();
//        try {
//            futureResults = executors.invokeAll(callableTasks);
//        } catch (InterruptedException e) {
//            System.err.println("ERROR : " + e.getLocalizedMessage());
//            e.printStackTrace();
//        }
//
//        List<Boolean> results = new ArrayList<>();
//        for (Future<Boolean> futureResult : futureResults) {
//            boolean res = false;
//            try {
//                res = futureResult.get(500, TimeUnit.MILLISECONDS);
//            } catch (Exception e) {
//                System.err.println("error : " + e.getLocalizedMessage());
//                e.printStackTrace();
//            }
//            results.add(res);
//        }

        // testing.
        List<Future<String>> futureResults = new ArrayList<>();
        try {
            futureResults = executors.invokeAll(callableTasks);
        } catch (InterruptedException e) {
            System.err.println("ERROR : " + e.getLocalizedMessage());
            e.printStackTrace();
        }

        List<String> results = new ArrayList<>();
        for (Future<String> futureResult : futureResults) {
            String res = null;
            try {
                res = futureResult.get(5000, TimeUnit.MILLISECONDS);
            } catch (Exception e) {
                System.err.println("Error : " + e.getLocalizedMessage());
                e.printStackTrace();
            }
            results.add(res);
        }

        // close the executors
        executors.shutdown();
        try {
            if(!executors.awaitTermination(5, TimeUnit.SECONDS)) {
                executors.shutdownNow();
            }
        } catch (Exception e) {
            executors.shutdownNow();
            System.out.println("Error : " + e.getLocalizedMessage());
            e.printStackTrace();
        }

        long endTime = System.currentTimeMillis();

        System.err.println("Time elapsed : " + (endTime - startTime) / 1000.0 + "sec.");

        System.out.println("result : ");
        for (String res : results) {
            System.out.println(res);
        }
        // tests
        //out.println(object.lock("China", 9));
        // object.printTree(root);
        //
        //out.println(object.lock("India", 9));
        //object.printTree(root);
        //
        //out.println(object.upgrade("Asia", 9));
        //
        // System.out.println(object.unlock("India", 9));
        System.out.println("\nfinal state : ");
        object.printTree(root);
        //
        // System.out.println(object.unlock("China", 9));
        // object.printTree(root);
    }
}