content: /*
   * Copyright 2009 Stephen Winnall, CH-8143 Stallikon. All rights reserved.
   *
   * Licensed under the Apache License, Version 2.0 (the "Licence");
   * you may not use this file except in compliance with the Licence.
   * You may obtain a copy of the Licence at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the Licence is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the Licence for the specific language governing permissions and
   * limitations under the Licence.
   *
   */
  
  /*
   * All matters arising in law from the use of this software are subject
   * exclusively to the jurisdiction and venue of the courts located in
   * Zurich, Switzerland. See
   *
   *	http://www.vimia.org/licences/JURISDICTION-1.0
   *
   */
  
  
  package org.allaymc.server.datastruct.dag;
  
  import com.google.common.base.Preconditions;
  
  import java.util.*;
  
  
  /**
   * HashDirectedAcyclicGraph is an implementation of a <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph">directed acyclic graph</a>
   * that conforms to {@link Set}.
   *
   * @param <B> Node type
   */
  public class HashDirectedAcyclicGraph<B> extends HashSet<B> implements DirectedAcyclicGraph<B> {
      //~ Instance fields ========================================================
  
      private final NodeMap nodeMap;
      private final NodePathSet nodePathSet;
  
      //~ Constructors ===========================================================
  
      /**
       * Creates a new DAG object.
       */
      public HashDirectedAcyclicGraph() {
          nodeMap = new NodeMap();
          nodePathSet = new NodePathSet();
      }
  
      /**
       * Creates a new DAG object, which initially contains the members specified
       * its parameter list.
       *
       * @param member list of members, which may be empty, which are initially contained by the DAG object
       */
      @SafeVarargs
      public HashDirectedAcyclicGraph(B... member) {
          this(Arrays.asList(member));
      }
  
      /**
       * Creates a new DAG object, which initially contains the members specified
       * its parameter list.
       *
       * @param collection collection of members, which may be empty, which are initially contained by the DAG object
       */
      public HashDirectedAcyclicGraph(Collection<? extends B> collection) {
          this();
          addAll(collection);
      }
  
      //~ Methods ================================================================
  
      public void setBefore(B before, B after) throws DAGCycleException {
          Preconditions.checkArgument(nodeMap.containsKey(after), "The \"after\" node is not in the DAG graph.");
          Preconditions.checkArgument(nodeMap.containsKey(before), "The \"before\" node is not in the DAG graph.");
          assertNoLoop(before, after);
          nodeMap.get(before).addAfter(after);
          nodeMap.get(after).addBefore(before);
      }
  
      public Set<B> getBefore(B member) {
          Preconditions.checkArgument(nodeMap.containsKey(member), "The \"member\" node is not in the DAG graph.");
          return nodeMap.get(member).getBeforeSet();
      }
  
      public boolean isBefore(B before, B after) {
          Preconditions.checkArgument(nodeMap.containsKey(before), "The \"before\" node is not in the DAG graph.");
          Preconditions.checkArgument(nodeMap.containsKey(after), "The \"after\" node is not in the DAG graph.");
          return isBeforeWorker(before, after);
      }
  
      public List<B> getSortedList() {
          return new TopologicalSort(nodeMap).sort();
      }
  
      @Override
      public boolean add(B member) {
          Preconditions.checkNotNull(member);
  
          if (!contains(member)) {
              return (nodeMap.put(member, new Node(member)) == null) & super.add(member);
          }
  
          return false;
      }
  
      @Override
      public boolean remove(Object member) {
          if (contains(member)) {
              if ((nodeMap.remove(member) != null) & super.remove(member)) {
                  return this.nodePathSet.remove(member);
              } else return false;
          }
  
          return false;
      }
  
      private boolean isBeforeWorker(B before, final B after) {
          Set<B> followers = nodeMap.get(before).getAfterSet();
  
          if (followers.contains(after)) {
              return true;
          } else {
              for (B follower : followers) {
                  if (isBeforeWorker(follower, after)) {
                      return true;
                  }
              }
          }
  
          return false;
      }
  
      private void assertNoLoop(B before, B after) throws DAGCycleException {
          if (before != after) {
              // recursion terminates when afterSet.isEmpty(), i.e. the following loop
              // has zero iterations
              for (B follower : nodeMap.get(after).getAfterSet()) {
                  assertNoLoop(before, follower);
              }
  
              return;
          }
  
          throw new DAGCycleException(before, after);
      }
  
      //~ Inner Classes ==========================================================
  
      /**
       * Node contains the beforeSet and afterSet of a set member, i.e.
       * the set of other members which are immediate predecessors of the
       * member, and the set of other members which are immediate followers of
       * the member.
       */
      protected class Node {
          //~ Instance fields ====================================================
  
          B self;
          private Set<B> afterSet;
          private Set<B> beforeSet;
  
          //~ Constructors =======================================================
  
          /**
           * Constructs a copy of a node.
           *
           * @param node the node to copy
           */
          protected Node(Node node) {
              beforeSet = new HashSet<>(node.beforeSet);
              afterSet = new HashSet<>(node.afterSet);
              self = node.self;
          }
  
          Node() {
          }
  
          Node(B member) {
              beforeSet = new HashSet<>();
              afterSet = new HashSet<>();
              self = member;
              notifyChange();
          }
  
          //~ Methods ============================================================
  
          public Set<B> getAfterSet() {
              return afterSet;
          }
  
          public Set<B> getBeforeSet() {
              return beforeSet;
          }
  
          public B getSelf() {
              return self;
          }
  
          public boolean addAfter(B member) {
              boolean result = afterSet.add(member);
  
              if (result) {
                  notifyChange();
              }
  
              return result;
          }
  
          public boolean addBefore(B member) {
              boolean result = beforeSet.add(member);
  
              if (result) {
                  notifyChange();
              }
  
              return result;
          }
  
          public boolean removeAfter(B member) {
              boolean result = afterSet.remove(member);
  
              if (result) {
                  notifyChange();
              }
  
              return result;
          }
  
          public boolean removeBefore(B member) {
              boolean result = beforeSet.remove(member);
  
              if (result) {
                  notifyChange();
              }
  
              return result;
          }
  
          private void notifyChange() {
              nodePathSet.update(this);
          }
      }
  
      /**
       * NodeMap contains all the members of the PartiallyOrderedSetX.
       */
      protected class NodeMap extends HashMap<B, Node> {
          //~ Methods ============================================================
  
          @Override
          public Node get(Object key) {
              return super.get(key);
          }
  
          @Override
          public Node remove(Object key) {
              Node member = get(key);
  
              // remove any references to this key
              // remove it from afterSet of antecedents
              for (B before : member.getBeforeSet()) {
                  get(before).removeAfter((B) key);
              }
  
              // remove it from the beforeSet of followers
              for (B after : member.getAfterSet()) {
                  get(after).removeBefore((B) key);
              }
  
              return super.remove(key);
          }
      }
  
      /**
       * NodePathSet contains all elements of DAG where
       * beforeSet.isEmpty(), i.e. the first elements of all the sublists of
       * DAG.
       */
      protected class NodePathSet extends HashSet<B> {
          //~ Constructors =======================================================
  
          NodePathSet() {
          }
  
          //~ Methods ============================================================
  
          public void update(Node node) {
              if (node.getBeforeSet().isEmpty()) {
                  add(node.self);
              } else {
                  remove(node.self);
              }
          }
      }
  
      /**
       * <a href="https://en.wikipedia.org/wiki/Topological_sorting">Topological_sorting</a>
       */
      protected class TopologicalSort extends HashMap<B, Node> {
          //~ Constructors =======================================================
  
          TopologicalSort(NodeMap nodeMap) {
              for (B member : nodeMap.keySet()) {
                  // create a copy to preserve the user's original
                  put(member, new Node(nodeMap.get(member)));
              }
          }
  
          //~ Methods ============================================================
  
          List<B> sort() {
              return sort(nodePathSet);
          }
  
          List<B> sort(NodePathSet nodePathSet) {
              List<B> result = new ArrayList<>();
              List<B> initialNodes = new LinkedList<>(nodePathSet);
  
              while (!initialNodes.isEmpty()) {
                  B initialNode = initialNodes.removeFirst();
                  result.add(initialNode);
  
                  Iterator<B> iterator = get(initialNode).getAfterSet().iterator();
  
                  while (iterator.hasNext()) {
                      B after = iterator.next();
                      iterator.remove();
                      get(after).getBeforeSet().remove(initialNode);
  
                      if (get(after).getBeforeSet().isEmpty()) {
                          initialNodes.add(after);
                      }
                  }
              }
  
              return result;
          }
      }
  }