/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package org.apache.tuscany.sca.guardian;

import java.util.Collections;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import org.apache.axiom.om.OMAttribute;
import org.apache.axiom.om.OMElement;

public class ResolutionTreeUtils {

    //E: Euler tour of the tree obtained by listing the nodes visited in a depth first search of the tree starting from the root. Contains 2n-1 elements
    private List<String> eulerTour;
    //L: Array of level numbers such that L[i] contains the tree-depth of the node E[i]. Contains 2n-1 elements
    private List<Integer> levels;
    //R: Map of size n such that R<K> contains the index of the first ocurrence of node 'K' in E
    private Map<String, Integer> rMap;
    private OMElement root;
    private int treeSize;

    public ResolutionTreeUtils() {
        init(null);
    }

    public ResolutionTreeUtils(OMElement root) {
        init(root);
    }

    public void setRoot(OMElement root) {
        init(root);
    }

    public List<String> getEulerTourDepthFirstSearch() {

        if (root == null) {
            throw new NullPointerException("The root musn't be null");
        }

        if (eulerTour == null) {
            eulerTour = new LinkedList<String>();
            levels = new LinkedList<Integer>();

            eulerTourDFSRecursive(root, 0);
        }

        return eulerTour;
    }

    public String getLowestCommonAncestor(String node1, String node2) {
        String lca = null;
        Integer indexNode1, indexNode2;

        Map<String, Integer> r = getRMap();

        indexNode1 = r.get(node1);
        indexNode2 = r.get(node2);

        //Check nodes existence
        if (indexNode1 == null && indexNode2 == null) {
            throw new InvalidNodeException("Could not find the specified nodes: " + node1 + " and " + node2);
        } else if (indexNode1 == null) {
            throw new InvalidNodeException("Could not find the specified nodes: " + node1);
        } else if (indexNode2 == null) {
            throw new InvalidNodeException("Could not find the specified nodes: " + node2);
        }

        int indexLCA;
        if (indexNode1 < indexNode2) {
            indexLCA = getRangeMinimumQuery(levels, indexNode1, indexNode2);
        } else {
            indexLCA = getRangeMinimumQuery(levels, indexNode2, indexNode1);
        }

        lca = eulerTour.get(indexLCA);

        return lca;
    }

    //Get the index of the smallest element between beginIndex and endIndex (both inclusive) in the list
    private int getRangeMinimumQuery(List list, int beginIndex, int endIndex) {

        List sublist = list.subList(beginIndex, endIndex + 1);

        Object elem = Collections.min(sublist);

        return sublist.indexOf(elem) + beginIndex;
    }

    private void init(OMElement root) {
        this.root = root;
        eulerTour = null;
        levels = null;
        rMap = null;
        treeSize = 0;
    }

    private void eulerTourDFSRecursive(OMElement node, int level) {
        String classAttribute = ((OMAttribute) node.getAllAttributes().next()).getAttributeValue();
        eulerTour.add(classAttribute);

        levels.add(level);
        treeSize++;

        Iterator children = node.getChildElements();

        OMElement child;
        while (children.hasNext()) {
            child = (OMElement) children.next();
            eulerTourDFSRecursive(child, level + 1);
            eulerTour.add(classAttribute);
            levels.add(level);
        }
    }

    private Map<String, Integer> getRMap() {
        if (rMap == null) {
            rMap = new Hashtable<String, Integer>();

            List<String> tour = getEulerTourDepthFirstSearch();
            for (int i = 0; i < tour.size(); i++) {
                String key = tour.get(i);
                if (!rMap.containsKey(key)) {
                    rMap.put(key, i);
                }

                if (rMap.size() == treeSize) {
                    break;
                }
            }
        }
        return rMap;
    }
}