package com.wixpress.test.tree;

import java.util.HashSet;

public class BinTree {
    private static final Character LEFT_DELIMITER = '{';
    private static final Character RIGHT_DELIMITER = '}';
    private static final String SINGLE_SPACE = " ";
    private String value;
    private BinTree left;
    private BinTree right;

    public BinTree(String value) {
        this(value, null, null);
    }

    public BinTree(String value, BinTree left, BinTree right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public String getValue() {
        return value;
    }

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

    public BinTree getLeft() {
        return left;
    }

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

    public BinTree getRight() {
        return right;
    }

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

    public String toString() {
        try {
            return serialize();
        } catch (BinTreeSerializationException e) {
            return "failed to represent the tree as a string cause of " + e.getMessage();
        }
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        BinTree binTree = (BinTree) o;

        if (left != null ? !left.equals(binTree.left) : binTree.left != null) return false;
        if (right != null ? !right.equals(binTree.right) : binTree.right != null) return false;
        if (value != null ? !value.equals(binTree.value) : binTree.value != null) return false;

        return true;
    }

    ///////////////////////////
    //                       //
    //      Implement:       //
    //                       //
    ///////////////////////////

    public String serialize() throws BinTreeSerializationException {
        HashSet<BinTree> visitedBinTrees = new HashSet<BinTree>();
        return serialize(visitedBinTrees);
    }

    private String serialize(HashSet<BinTree> visitedBinTrees) throws BinTreeSerializationException {
        if (visitedBinTrees.contains(this)) {
            throw new BinTreeSerializationException("The input is cyclic");
        }
        visitedBinTrees.add(this);
        String serialized = LEFT_DELIMITER
                + SINGLE_SPACE
                + this.getValue()
                + serializeWrapper(this.getLeft(), visitedBinTrees)
                + SINGLE_SPACE
                + serializeWrapper(this.getRight(), visitedBinTrees)
                + RIGHT_DELIMITER;
        return serialized;
    }

    private String serializeWrapper(BinTree binTree, HashSet<BinTree> visitedBinTrees) throws BinTreeSerializationException {
        return (binTree!= null) ? binTree.serialize(visitedBinTrees) : " {} ";
    }

    public static BinTree deserialize(String serialized) throws BinTreeSerializationException {

        if (serialized == null || serialized.isEmpty()) {
            throw new BinTreeSerializationException();
        }

        if ((!serialized.contains(LEFT_DELIMITER + ""))
                || (!serialized.contains(RIGHT_DELIMITER + ""))){
            throw new BinTreeSerializationException();
        }
        String peeledSerialized = peelOuterBrackets(serialized);
        if (peeledSerialized.isEmpty()) {
            return null;
        }
        String nodeValue = peeledSerialized.substring(0, peeledSerialized.indexOf(LEFT_DELIMITER)).trim();
        System.out.println("node Value: " + nodeValue);
        String unparsedInputLeftAndRight = peeledSerialized.substring(nodeValue.length()).trim();
        String left = findLeftComponent(unparsedInputLeftAndRight.substring(unparsedInputLeftAndRight.indexOf(LEFT_DELIMITER))).trim();
        BinTree leftBinTree = BinTree.deserialize(left);
        if (left.length() == unparsedInputLeftAndRight.length()) {
            throw new BinTreeSerializationException();
        }
        String right = unparsedInputLeftAndRight.substring(left.length(), unparsedInputLeftAndRight.length()).trim();
        BinTree rightBinTree = BinTree.deserialize(right);
        return new BinTree(nodeValue, leftBinTree, rightBinTree);
    }

    static String peelOuterBrackets(String serialized) throws BinTreeSerializationException {
        String trimmedSerialized = serialized.trim();
        if ((trimmedSerialized.length() < 2)
                || (trimmedSerialized.indexOf(LEFT_DELIMITER) == -1)
                || (trimmedSerialized.indexOf(RIGHT_DELIMITER) == -1)
                || (trimmedSerialized.charAt(0) != LEFT_DELIMITER)
                || (trimmedSerialized.charAt(trimmedSerialized.length()-1) != RIGHT_DELIMITER)){
            throw new BinTreeSerializationException();
        }
        return trimmedSerialized.substring(1, trimmedSerialized.length()-1).trim();
    }

    static String findLeftComponent(String unparsedInputLeftAndRight) throws BinTreeSerializationException {
        String trimmed = unparsedInputLeftAndRight.trim();
        int balance = 0;
        for (int i = 0; i < trimmed.length(); i++) {
            if (trimmed.charAt(i) == LEFT_DELIMITER) {
                balance++;
            } else if (trimmed.charAt(i) == RIGHT_DELIMITER) {
                balance--;
            }
            if (balance == 0) {
                if (trimmed.charAt(i) != RIGHT_DELIMITER) {
                    throw new BinTreeSerializationException("Cannot get BinTree component");
                } else {
                    return trimmed.substring(0, i+1);
                }
            }
        }
        throw new BinTreeSerializationException("Cannot get BinTree component");
    }
}