/**
 * This file is part of Eclipse Steady.
 *
 * 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.
 *
 * SPDX-License-Identifier: Apache-2.0
 * SPDX-FileCopyrightText: Copyright (c) 2018-2020 SAP SE or an SAP affiliate company and Eclipse Steady contributors
 */
package org.eclipse.steady.cg;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

import org.apache.logging.log4j.Logger;

/**
 * <p>PathSimilarity class.</p>
 */
public class PathSimilarity {

  private static final Logger log =
      org.apache.logging.log4j.LogManager.getLogger(PathSimilarity.class);

  // ArrayList: every path has a unique index
  ArrayList<LinkedList<String>> paths = null;

  // group all paths based on the node joint, the map key is the qname of the node joint, the value
  // are all paths id in this group, id is read from ArrayList paths
  HashMap<String, HashSet<Integer>> groupedPaths = null;

  /**
   * <p>Constructor for PathSimilarity.</p>
   *
   * @param _p a {@link java.util.ArrayList} object.
   */
  public PathSimilarity(ArrayList<LinkedList<String>> _p) {
    this.paths = _p;
  }

  /**
   * <p>addPath.</p>
   *
   * @param _p a {@link java.util.LinkedList} object.
   */
  public void addPath(LinkedList<String> _p) {
    this.paths.add(_p);
  }

  /**
   * <p>groupPathsByJointNode.</p>
   */
  public void groupPathsByJointNode() {
    this.groupedPaths = new HashMap<String, HashSet<Integer>>();
    for (int i = 0; i < this.paths.size(); i++) {
      LinkedList<String> p = this.paths.get(i);
      for (String s : p) {
        if (!this.groupedPaths.containsKey(s)) {
          HashSet<Integer> tmp = new HashSet<Integer>();
          tmp.add(i);
          this.groupedPaths.put(s, tmp);
        } else {
          this.groupedPaths.get(s).add(i);
        }
      }
    }
  }

  // return all the overlapping paths (linked edges)
  private HashSet<List<String>> overlapPath(LinkedList<String> _path1, LinkedList<String> _path2) {
    LinkedList<String> shortpath = new LinkedList<String>();
    LinkedList<String> longpath = new LinkedList<String>();
    if (_path1.size() >= _path2.size()) {
      shortpath.addAll(_path2);
      longpath.addAll(_path1);
    } else {
      shortpath.addAll(_path1);
      longpath.addAll(_path2);
    }
    HashSet<List<String>> results = new HashSet<List<String>>();
    List<String> overlap = new LinkedList<String>();
    int length = 1, pointer = 0;
    // complexity: looping only once by increasing / decreasing i and j
    for (int i = 0, j = 0; i < shortpath.size() && j < longpath.size(); ) {
      String node = shortpath.get(i);
      if (node.equals(longpath.get(j))) {
        overlap.add(node);
        i++;
        j++;
      } else {
        if (!overlap.isEmpty()) {
          List<String> newoverlap = new LinkedList<String>();
          newoverlap.addAll(overlap);
          if (newoverlap.size() > length) length = newoverlap.size();
          results.add(newoverlap);
          overlap.clear();
          i = pointer;
        } else {
          if (i != (shortpath.size() - 1) && j == (longpath.size() - 1)) {
            i = i + length;
            pointer = i;
            j = 0;
            length = 1;
          } else j++;
        }
      }
    }
    if (!overlap.isEmpty()) results.add(overlap);
    PathSimilarity.log.info("Results: " + results);
    return results;
  }

  // one way to compute the similarity between two paths
  /**
   * <p>pathSimilarity.</p>
   *
   * @param _path1 a {@link java.util.LinkedList} object.
   * @param _path2 a {@link java.util.LinkedList} object.
   */
  public void pathSimilarity(LinkedList<String> _path1, LinkedList<String> _path2) {
    int count = 0;
    HashSet<List<String>> overlaps = overlapPath(_path1, _path2);
    for (List<String> sp : overlaps) count += sp.size();
    PathSimilarity.log.info(
        "The lengths of two paths are "
            + _path1.size()
            + " and "
            + _path2.size()
            + " separately; overlapping [ "
            + count
            + " nodes ] distributed in [ "
            + overlaps.size()
            + " subpaths ]");
  }
}
