/*
 * Copyright 2010-2012 Luca Garulli (l.garulli--at--orientechnologies.com)
 *
 * Licensed 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 com.orientechnologies.orient.graph.sql.functions;

import com.orientechnologies.orient.core.command.OCommandContext;
import com.orientechnologies.orient.core.id.ORID;
import com.orientechnologies.orient.core.sql.functions.math.OSQLFunctionMathAbstract;
import com.tinkerpop.blueprints.Direction;
import com.tinkerpop.blueprints.Vertex;
import com.tinkerpop.blueprints.impls.orient.OrientBaseGraph;
import com.tinkerpop.blueprints.impls.orient.OrientVertex;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

/**
 * Abstract class to find paths between nodes.
 * 
 * @author Luca Garulli (l.garulli--at--orientechnologies.com)
 * 
 */
public abstract class OSQLFunctionPathFinder extends OSQLFunctionMathAbstract {
  protected OrientBaseGraph         db;
  protected Set<OrientVertex>       unSettledNodes;
  protected Map<ORID, OrientVertex> predecessors;
  protected Map<ORID, Float>        distance;

  protected OrientVertex            paramSourceVertex;
  protected OrientVertex            paramDestinationVertex;
  protected Direction               paramDirection = Direction.OUT;
  protected OCommandContext         context;

  protected static final float      MIN            = 0f;
  protected static final float      DISTANCE       = 1f;

  public OSQLFunctionPathFinder(final String iName, final int iMinParams, final int iMaxParams) {
    super(iName, iMinParams, iMaxParams);
  }

  public Object execute(final Object[] iParameters, final OCommandContext iContext) {
    context = iContext;
    unSettledNodes = new HashSet<OrientVertex>();
    distance = new HashMap<ORID, Float>();
    predecessors = new HashMap<ORID, OrientVertex>();
    distance.put(paramSourceVertex.getIdentity(), getMinimumDistance());
    unSettledNodes.add(paramSourceVertex);

    int maxDistances = 0;
    int maxSettled = 0;
    int maxUnSettled = 0;
    int maxPredecessors = 0;

    while (continueTraversing()) {
      final OrientVertex node = getMinimum(unSettledNodes);
      unSettledNodes.remove(node);
      findMinimalDistances(node);

      if (distance.size() > maxDistances)
        maxDistances = distance.size();
      if (unSettledNodes.size() > maxUnSettled)
        maxUnSettled = unSettledNodes.size();
      if (predecessors.size() > maxPredecessors)
        maxPredecessors = predecessors.size();

      if( !isVariableEdgeWeight() && distance.containsKey(paramDestinationVertex.getIdentity()))
        // FOUND
        break;

      if (!context.checkTimeout())
        break;
    }

    context.setVariable("maxDistances", maxDistances);
    context.setVariable("maxSettled", maxSettled);
    context.setVariable("maxUnSettled", maxUnSettled);
    context.setVariable("maxPredecessors", maxPredecessors);

    distance = null;

    return getPath();
  }

  protected boolean isVariableEdgeWeight() {
    return false;
  }

  /*
   * This method returns the path from the source to the selected target and NULL if no path exists
   */
  public LinkedList<OrientVertex> getPath() {
    final LinkedList<OrientVertex> path = new LinkedList<OrientVertex>();
    OrientVertex step = paramDestinationVertex;
    // Check if a path exists
    if (predecessors.get(step.getIdentity()) == null)
      return null;

    path.add(step);
    while (predecessors.get(step.getIdentity()) != null) {
      step = predecessors.get(step.getIdentity());
      path.add(step);
    }
    // Put it into the correct order
    Collections.reverse(path);
    return path;
  }

  public boolean aggregateResults() {
    return false;
  }

  @Override
  public Object getResult() {
    return getPath();
  }

  protected void findMinimalDistances(final OrientVertex node) {
    for (OrientVertex target : getNeighbors(node)) {
      final float d = sumDistances(getShortestDistance(node), getDistance(node, target));

      if (getShortestDistance(target) > d) {
        distance.put(target.getIdentity(), d);
        predecessors.put(target.getIdentity(), node);
        unSettledNodes.add(target);
      }
    }

  }

  protected Set<OrientVertex> getNeighbors(final Vertex node) {
    context.incrementVariable("getNeighbors");

    final Set<OrientVertex> neighbors = new HashSet<OrientVertex>();
    if (node != null) {
      for (Vertex v : node.getVertices(paramDirection)) {
        final OrientVertex ov = (OrientVertex) v;
        if (ov != null && !isSettled(ov))
          neighbors.add(ov);
      }
    }
    return neighbors;
  }

  protected OrientVertex getMinimum(final Set<OrientVertex> vertexes) {
    OrientVertex minimum = null;
    Float minimumDistance = null;
    for (OrientVertex vertex : vertexes) {
      if (minimum == null || getShortestDistance(vertex) < minimumDistance) {
        minimum = vertex;
        minimumDistance = getShortestDistance(minimum);
      }
    }
    return minimum;
  }

  protected boolean isSettled(final OrientVertex vertex) {
    return distance.containsKey(vertex.getIdentity());
  }

  protected boolean continueTraversing() {
    return unSettledNodes.size() > 0;
  }

  protected float getShortestDistance(final OrientVertex destination) {
    if (destination == null)
      return Float.MAX_VALUE;

    final Float d = distance.get(destination.getIdentity());
    return d == null ? Float.MAX_VALUE : d;
  }

  protected Float getMinimumDistance() {
    return MIN;
  }

  protected float sumDistances(final float iDistance1, final float iDistance2) {
    return iDistance1 + iDistance2;
  }

  protected float getDistance(final OrientVertex node, final OrientVertex target) {
    return DISTANCE;
  }
}
