package org.codehaus.plexus.util.dag;
   
   /*
    * Copyright The Codehaus Foundation.
    *
    * 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.
   */
  
  import java.io.Serializable;
  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  import java.util.Set;
  
  /**
   * DAG = Directed Acyclic Graph
   *
   * @author <a href="michal.maczka@dimatics.com">Michal Maczka</a>
   *
   * TODO this class should be renamed from DAG to Dag
   */
  public class DAG
      implements Cloneable, Serializable
  {
      // ------------------------------------------------------------
      // Fields
      // ------------------------------------------------------------
      /**
       * Nodes will be kept in two data structures at the same time for faster processing
       */
      /**
       * Maps vertex's label to vertex
       */
      private Map<String, Vertex> vertexMap = new HashMap<>();
  
      /**
       * Conatin list of all vertices
       */
      private List<Vertex> vertexList = new ArrayList<>();
  
      // ------------------------------------------------------------
      // Constructors
      // ------------------------------------------------------------
  
      /**
       *
       */
      public DAG()
      {
          super();
      }
  
      // ------------------------------------------------------------
      // Accessors
      // ------------------------------------------------------------
  
      /**
       * @return the vertices
       */
      public List<Vertex> getVertices()
      {
          return vertexList;
      }
  
      /**
       * @deprecated instead use {@link #getVertices()}
       * @return the vertices
       */
      @Deprecated
      public List<Vertex> getVerticies()
      {
          return getVertices();
      }
  
      public Set<String> getLabels()
      {
          return vertexMap.keySet();
      }
  
      // ------------------------------------------------------------
      // Implementation
      // ------------------------------------------------------------
  
      /**
       * Adds vertex to DAG. If vertex of given label already exist in DAG no vertex is added
       *
       * @param label The label of the Vertex
       * @return New vertex if vertex of given label was not present in the DAG or existing vertex if vertex of given
      *         label was already added to DAG
      */
     public Vertex addVertex( final String label )
     {
         Vertex retValue = null;
 
         // check if vertex is already in DAG
         if ( vertexMap.containsKey( label ) )
         {
             retValue = vertexMap.get( label );
         }
         else
         {
             retValue = new Vertex( label );
 
             vertexMap.put( label, retValue );
 
             vertexList.add( retValue );
         }
 
         return retValue;
     }
 
     public void addEdge( final String from, final String to )
         throws CycleDetectedException
     {
         final Vertex v1 = addVertex( from );
 
         final Vertex v2 = addVertex( to );
 
         addEdge( v1, v2 );
     }
 
     public void addEdge( final Vertex from, final Vertex to )
         throws CycleDetectedException
     {
 
         from.addEdgeTo( to );
 
         to.addEdgeFrom( from );
 
         final List<String> cycle = CycleDetector.introducesCycle( to );
 
         if ( cycle != null )
         {
             // remove edge which introduced cycle
 
             removeEdge( from, to );
 
             final String msg = "Edge between '" + from + "' and '" + to + "' introduces to cycle in the graph";
 
             throw new CycleDetectedException( msg, cycle );
         }
     }
 
     public void removeEdge( final String from, final String to )
     {
         final Vertex v1 = addVertex( from );
 
         final Vertex v2 = addVertex( to );
 
         removeEdge( v1, v2 );
     }
 
     public void removeEdge( final Vertex from, final Vertex to )
     {
         from.removeEdgeTo( to );
 
         to.removeEdgeFrom( from );
     }
 
     public Vertex getVertex( final String label )
     {
         final Vertex retValue = vertexMap.get( label );
 
         return retValue;
     }
 
     public boolean hasEdge( final String label1, final String label2 )
     {
         final Vertex v1 = getVertex( label1 );
 
         final Vertex v2 = getVertex( label2 );
 
         final boolean retValue = v1.getChildren().contains( v2 );
 
         return retValue;
 
     }
 
     /**
      * @param label see name
      * @return the childs
      */
     public List<String> getChildLabels( final String label )
     {
         final Vertex vertex = getVertex( label );
 
         return vertex.getChildLabels();
     }
 
     /**
      * @param label see name
      * @return the parents
      */
     public List<String> getParentLabels( final String label )
     {
         final Vertex vertex = getVertex( label );
 
         return vertex.getParentLabels();
     }
 
     /**
      * @see java.lang.Object#clone()
      */
     @Override
     public Object clone()
         throws CloneNotSupportedException
     {
         // this is what's failing..
         final Object retValue = super.clone();
 
         return retValue;
     }
 
     /**
      * Indicates if there is at least one edge leading to or from vertex of given label
      * @param label the label
      * @return <code>true</code> if this vertex is connected with other vertex,<code>false</code> otherwise
      */
     public boolean isConnected( final String label )
     {
         final Vertex vertex = getVertex( label );
 
         final boolean retValue = vertex.isConnected();
 
         return retValue;
 
     }
 
     /**
      * Return the list of labels of successor in order decided by topological sort
      *
      * @param label The label of the vertex whose predecessors are searched
      * @return The list of labels. Returned list contains also the label passed as parameter to this method. This label
      *         should always be the last item in the list.
      */
     public List<String> getSuccessorLabels( final String label )
     {
         final Vertex vertex = getVertex( label );
 
         final List<String> retValue;
 
         // optimization.
         if ( vertex.isLeaf() )
         {
             retValue = new ArrayList<>( 1 );
 
             retValue.add( label );
         }
         else
         {
             retValue = TopologicalSorter.sort( vertex );
         }
 
         return retValue;
     }
 
 }