/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;

/**
 *
 * @author mhussain3
 */
public class Tree {

    RootNode root = null;
    public int[][] table = null;
    ArrayList<String> cellArray = new ArrayList<String>();
    ArrayList<String> expandCellArray = new ArrayList<String>();

    public Tree() {
        makeTable();
        expandCell();
//        RootNode rootNode = new RootNode();
//        NonLeafNode nonLeafNode = null;
//        LeafNode leafNode = null;
//        for (int i = 0; i < Node.min; i++) {
//            nonLeafNode = new NonLeafNode();
//            for (int j = 0; j < Node.min; j++) {
//                leafNode = new LeafNode();
//                nonLeafNode.pointers.add(leafNode);
//            }
//            rootNode.pointers.add(nonLeafNode);
//        }
    }

    public void searchObject(int value) {
        if (root == null) {
            System.out.println("No Element in the Tree");

        } else {
            boolean found = false;
            for (int i = 0; i < root.pointers.size(); i++) {
                NonLeafNode get = root.pointers.get(i);
                for (int j = 0; j < get.pointers.size(); j++) {
                    LeafNode get1 = get.pointers.get(j);
                    for (int k = 0; k < get1.data.size(); k++) {
                        if (get1.data.get(k) == value) {
                            System.out.println("Object is found ");
                            System.out.println("Non Leaf Node" + j);
                            System.out.println("Leaf Node" + k);
                            System.out.println("RC Max : " + get.Rc_max);
                            System.out.println("RC Min : " + get.Rc_min);
                            System.out.println("Leaf Data Size : " + get1.data.size());
                            System.out.println("LE Val : " + get1.LE);
                            found = true;
                            break;
                        }
                    }

                }
            }
            if (!found) {
                System.out.println("Object is not found");
            }
        }
    }

    public String findNearestCell(String cell) {
        int index = getIndex(cell);
        String ret = "";
        for (int i = index; i > 0; i--) {
            if (expandCellArray.contains("c" + i)) {
                ret = "C" + i;
                break;
            }
        }
        if (ret.equals("")) {
            for (int i = index; i < expandCellArray.size(); i++) {
                if (expandCellArray.contains("c" + i)) {
                    ret = "C" + i;
                    break;
                }
            }
        }
        return ret;
    }

    public void insert(String cell, int value) {
        if (root == null) { // if root is null
            RootNode rootNode = new RootNode();
            NonLeafNode nonLeafNode = new NonLeafNode();
            rootNode.pointers.add(nonLeafNode);
            LeafNode leafNode = new LeafNode();
            nonLeafNode.pointers.add(leafNode);

            if (expandCellArray.contains(cell.toLowerCase())) {
                nonLeafNode.Rc_max = cell;
                nonLeafNode.Rc_min = cell;
                leafNode.LE = cell;
            } else {
                String findNearestCell = findNearestCell(cell);
                nonLeafNode.Rc_max = findNearestCell;
                nonLeafNode.Rc_min = findNearestCell;
                leafNode.LE = findNearestCell;
            }
            leafNode.data.add(value);
            root = rootNode;
        } else { //if root is not null
            ArrayList<Integer> findLeafNode = findLeafNode(cell);
            NonLeafNode nonLeafNode = root.pointers.get(findLeafNode.get(0));
            LeafNode leafNode = nonLeafNode.pointers.get(findLeafNode.get(1));

            if (leafNode.data.size() == Node.max) { // if leadNode is full

                if (nonLeafNode.pointers.size() == Node.max) // if NonLeafNode is full
                {

                    NonLeafNode newnonLeafNode = new NonLeafNode();
                     for (int i = 1; i < Node.min; i++) {
                        newnonLeafNode.pointers.add(nonLeafNode.pointers.remove(nonLeafNode.pointers.size() - i));
                    }
                    
                    root.pointers.add(newnonLeafNode);
                    LeafNode newleafNode = new LeafNode();
                    newnonLeafNode.pointers.add(newleafNode);
                    if (expandCellArray.contains(cell.toLowerCase())) {
                        newnonLeafNode.Rc_max = cell;
                        newnonLeafNode.Rc_min = cell;
                        newleafNode.LE = cell;
                    } else {
                        String findNearestCell = findNearestCell(cell);
                        newnonLeafNode.Rc_max = findNearestCell;
                        newnonLeafNode.Rc_min = findNearestCell;
                        newleafNode.LE = findNearestCell;
                    }
                    newleafNode.data.add(value);

                } else // make another leaf node
                {
                    LeafNode newNode = new LeafNode();
                    nonLeafNode.pointers.add(newNode);


                    //add min node to this leaf node
                    for (int i = 1; i < Node.min; i++) {
                        newNode.data.add(leafNode.data.remove(leafNode.data.size() - i));
                    }
                    newNode.data.add(value);

                    if (expandCellArray.contains(cell.toLowerCase())) {

                        int rcmax = 0;
                        int rcmin = 0;
                        int cellindex = 0;

                        rcmax = expandCellArray.indexOf(nonLeafNode.Rc_max.toLowerCase());
                        rcmin = expandCellArray.indexOf(nonLeafNode.Rc_min.toLowerCase());
                        cellindex = expandCellArray.indexOf(cell.toLowerCase());
                        if (cellindex > rcmin) {
                            nonLeafNode.Rc_min = cell;
                        } else if (cellindex < rcmax) {
                            nonLeafNode.Rc_max = cell;
                        }
                        newNode.LE = cell;

                    } else {
                        String findNearestCell = findNearestCell(cell);
                        newNode.LE = findNearestCell;
                        
                        int rcmax = 0;
                        int rcmin = 0;
                        int cellindex = 0;

                        rcmax = expandCellArray.indexOf(nonLeafNode.Rc_max.toLowerCase());
                        rcmin = expandCellArray.indexOf(nonLeafNode.Rc_min.toLowerCase());
                        cellindex = expandCellArray.indexOf(findNearestCell.toLowerCase());
                        if (cellindex > rcmin) {
                            nonLeafNode.Rc_min = findNearestCell;
                        } else if (cellindex < rcmax) {
                            nonLeafNode.Rc_max = findNearestCell;
                        }

                    }

                }

            } else { //add value to leaf node
                leafNode.data.add(value);
                if (expandCellArray.contains(cell.toLowerCase())) {

                    int rcmax = 0;
                    int rcmin = 0;
                    int cellindex = 0;

                    rcmax = expandCellArray.indexOf(nonLeafNode.Rc_max.toLowerCase());
                    rcmin = expandCellArray.indexOf(nonLeafNode.Rc_min.toLowerCase());
                    cellindex = expandCellArray.indexOf(cell.toLowerCase());
                    if (cellindex > rcmin) {
                        nonLeafNode.Rc_min = cell;
                    } else if (cellindex < rcmax) {
                        nonLeafNode.Rc_max = cell;
                    }
                    if (cellindex < expandCellArray.indexOf(leafNode.LE.toLowerCase())) {
                        leafNode.LE = cell;
                    }

                } else {
                    String findNearestCell = findNearestCell(cell);
                    if (nonLeafNode.Rc_min.equals("")) {
                        nonLeafNode.Rc_max = findNearestCell;
                        nonLeafNode.Rc_min = findNearestCell;
                        leafNode.LE = findNearestCell;
                    } else {
                        int rcmax = 0;
                        int rcmin = 0;
                        int cellindex = 0;

                        rcmax = expandCellArray.indexOf(nonLeafNode.Rc_max.toLowerCase());
                        rcmin = expandCellArray.indexOf(nonLeafNode.Rc_min.toLowerCase());
                        cellindex = expandCellArray.indexOf(findNearestCell.toLowerCase());
//                        System.out.println("    cell index "+cellindex);
//                        System.out.println("    max cell index "+rcmax);
//                        System.out.println("    min cell index "+rcmin);
                        if (cellindex > rcmin) {
                            nonLeafNode.Rc_min = findNearestCell;
                        } else if (cellindex < rcmax) {
                            nonLeafNode.Rc_max = findNearestCell;
                        }
                        if (cellindex < expandCellArray.indexOf(leafNode.LE.toLowerCase())) {
                            leafNode.LE = findNearestCell;
                        }
                    }

                }
            }
        }
    }

    public ArrayList<Integer> findLeafNode(String cell) {
        List<NonLeafNode> nonLeafs = root.pointers;
        int nonLeafIndex = 0;
        int nonLeafValue = 0;
        for (int i = 0; i < nonLeafs.size(); i++) {
            NonLeafNode get = nonLeafs.get(i);
            if (get.Rc_max == null || get.Rc_min == null) {
                continue;
            }
            //System.out.println("Min : " + cell + " , " + get.Rc_min);
            //System.out.println("Max : " + cell + " , " + get.Rc_max);
            int rcmin = compare_method(cell, get.Rc_min);
            int rcmax = compare_method(cell, get.Rc_max);
            int minvalue = rcmax;
            if (rcmin <= rcmax) {
                minvalue = rcmin;
            }
            if (i == 0) {
                nonLeafValue = minvalue;
            } else {
                if (minvalue < nonLeafValue) {
                    nonLeafValue = minvalue;
                    nonLeafIndex = i;
                }
            }
        }
        NonLeafNode selectedNonLeafNode = nonLeafs.get(nonLeafIndex);

        List<LeafNode> leafNodes = selectedNonLeafNode.pointers;
        int leafIndex = 0;
        int leafValue = 0;
        for (int i = 0; i < leafNodes.size(); i++) {
            LeafNode get = leafNodes.get(i);
            if (get.LE == null) {
                continue;
            }
            int lemin = compare_method(cell, get.LE);
            if (lemin <= leafValue) {
                leafValue = lemin;
                leafIndex = i;
            }
        }


        ArrayList<Integer> leafNonLeafIndex = new ArrayList<Integer>();
        leafNonLeafIndex.add(nonLeafIndex);
        leafNonLeafIndex.add(leafIndex);


        return leafNonLeafIndex;
    }

    public int compare_method(String cell1, String cell2) {

        int i = getIndex(cell1);
        int j = getIndex(cell2);

        return this.table[i][j];
    }

    public int getIndex(String cell) {
        int index = -1;
        try {
            index = Integer.parseInt(cell.substring(cell.toLowerCase().indexOf("c") + 1));
        } catch (Exception ex) {
            System.out.println(ex.toString());
        }
        return index - 1;
    }

    private void makeTable() {
        String filename = "table.txt";
        FileInputStream fstream = null;

        try {
            int count = count(filename);
            count++;
            table = new int[count][count];
            fstream = new FileInputStream(filename);
            DataInputStream in = new DataInputStream(fstream);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            String strLine;
            int i = 0;
            while ((strLine = br.readLine()) != null) {
                String[] split = strLine.split("\\s+");
                for (int j = 0; j < split.length; j++) {
                    table[i][j] = Integer.parseInt(split[j].trim());
                }

                i++;

            }
            for (int j = 1; j <= count; j++) {
                cellArray.add("C" + j);
            }

        } catch (IOException ex) {
        } finally {
            try {
                fstream.close();
            } catch (IOException ex) {
            }
        }

    }

    private int count(String filename) throws IOException {
        InputStream is = new BufferedInputStream(new FileInputStream(filename));
        try {
            byte[] c = new byte[1024];
            int count = 0;
            int readChars = 0;
            while ((readChars = is.read(c)) != -1) {
                for (int i = 0; i < readChars; ++i) {
                    if (c[i] == '\n') {
                        ++count;
                    }
                }
            }
            return count;
        } finally {
            is.close();
        }
    }

    private void expandCell() {
        String filename = "expandcell.txt";
        FileInputStream fstream = null;

        try {
            fstream = new FileInputStream(filename);
            DataInputStream in = new DataInputStream(fstream);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            String strLine;
            while ((strLine = br.readLine()) != null) {
                expandCellArray.add(strLine.trim().toLowerCase());
            }

        } catch (IOException ex) {
        } finally {
            try {
                fstream.close();
            } catch (IOException ex) {
            }
        }
    }

    public void printTable() {
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[i].length; j++) {
                if (j == 0) {
                    System.out.print(table[i][j]);
                } else {
                    System.out.print("\t" + table[i][j]);
                }
            }
            System.out.println("");
        }
    }

    public void printTree() {
        for (int i = 0; i < root.pointers.size(); i++) {
            NonLeafNode get = root.pointers.get(i);
            System.out.println("______________________________________");
            System.out.println("Non Leaf " + i);
            System.out.println("RC Max : " + get.Rc_max);
            System.out.println("RC Min : " + get.Rc_min);
            for (int j = 0; j < get.pointers.size(); j++) {
                LeafNode get1 = get.pointers.get(j);
                System.out.println("=================================");
                System.out.println("Leaf " + j);
                System.out.println("Leaf Data Size : " + get1.data.size());
                System.out.println("LE Val : " + get1.LE);

                for (int k = 0; k < get1.data.size(); k++) {

                    System.out.println("Data" + k + " : " + get1.data.get(k));

                }
                System.out.println("=================================");
            }
            System.out.println("______________________________________");
        }
    }
}
