/*
 * Copyright 2005 by Oracle USA
 * 500 Oracle Parkway, Redwood Shores, California, 94065, U.S.A.
 * All rights reserved.
 */
package javax.ide.menu.spi;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;


/**
 * A map that tracks Positionable items. Provides utilities for getting the
 * items in their "resolved" order.
 */
final class PositionMap 
{
  // Ordering of items is essentially a graph problem. We build a graph of items
  // where the (directed) edges are their required positions in relation to each
  // other. The correct order of the items is a topological sort of this graph.
  
  private Map _idsToVertices = new LinkedHashMap();
  private Map _undefinedItemMap = new LinkedHashMap();
  private Vertex _currentAncestor;
  
  private List _sortedList;
  
  /**
   * Adds a positionable to the map.
   * 
   * @param p the positionable to add.
   */
  public void add( Positionable p )
  {
    // Invalidate the sorted list if required.
    _sortedList = null;
    
    Vertex thisVertex = getVertex( p.getID() );
    if ( thisVertex == null )
    {
      thisVertex = new Vertex( p );
      _idsToVertices.put( p.getID(), thisVertex );
    }
  }
  
  private Vertex getVertex( String name )
  {
    Vertex vertex = (Vertex) _idsToVertices.get( name );
    if ( vertex == null )
    {
      vertex = (Vertex) _undefinedItemMap.get( name );
    }
    return vertex;
  }
  
  private void addToGraph( Vertex thisVertex )
  {
    Positionable p = thisVertex.getPositionable();
    
    String before = p.getBefore();
    String after = p.getAfter();
    
    if ( after == null && before == null && _currentAncestor != null )
    {
      after = _currentAncestor.getName();
      // The current vertex might already be attached before its ancestor. 
      // In which case, we don't need to add it again.
      Vertex afterVertex = getVertex( after );
      if ( afterVertex != null && afterVertex.getFromEdges().contains( thisVertex ))
      {
        _currentAncestor = thisVertex;
        return;
      }
    }
    
    if ( after != null )
    {
      Vertex afterVertex = getVertex( after );
      if ( afterVertex == null )
      {
        afterVertex = new Vertex( after );    
        _undefinedItemMap.put( after, afterVertex );
      }
            
      // Anything after the afterVertex must also be after this vertex.
      thisVertex.attachAfter( afterVertex.getToEdges() );

      afterVertex.attachAfter( thisVertex );

      if ( thisVertex.isUndefinedReference() )
      {
        // Anything before thisVertex (except afterVertex itself) 
        // must also be after afterVertex.
        for ( Iterator i = thisVertex.getFromEdges().iterator(); i.hasNext();  )
        {
          Vertex v = (Vertex) i.next();
          if ( afterVertex != v )
          {
            afterVertex.attachAfter( v );
          }
        }
        thisVertex.setPositionable( p );
      }

    }
    
    if ( before != null )
    {
      Vertex beforeVertex = getVertex( before );
      if ( beforeVertex == null )
      {
        beforeVertex = new Vertex( before );
        _undefinedItemMap.put( before, beforeVertex );
      }
      
      // Anything before the beforeVertex must be before this vertex.
      thisVertex.attachBefore( beforeVertex.getFromEdges() );
      
      beforeVertex.attachBefore( thisVertex );

      if ( thisVertex.isUndefinedReference() )
      {
        // Anything after thisVertex (except beforeVertex itself) 
        // must also be before beforeVertex.
        for ( Iterator i = thisVertex.getToEdges().iterator(); i.hasNext();  )
        {
          Vertex v = (Vertex) i.next();
          if ( beforeVertex != v )
          {
            beforeVertex.attachBefore( v );
          }
        }      
        thisVertex.setPositionable( p );
      }
    }
    _currentAncestor = thisVertex;
  }
  
  /**
   * Gets items in the correct, sorted order.
   * 
   * @return the items in the correct, sorted order.
   */
  public List getSortedItems()
  {
    if ( _sortedList == null )
    {
      _sortedList = sort();
    }
    return _sortedList;
  }
  
  /**
   * Get a positionable by its id.
   * 
   * @param id the id of a positionable
   * @return the Positionable with the specified id, or null if no such 
   *    Positionable has been added.
   */
  public Positionable get( String id )
  {
    Vertex vertex = getVertex( id );
    if ( vertex == null || vertex.isUndefinedReference() )
    {
      return null;
    }
    return vertex.getPositionable();
  }
  
  /**
   * Build a sorted list of all items.
   * 
   * @return a sorted list of all items.
   */
  private List sort()
  {
    // Build the graph.
//    List vertices = new ArrayList( _idsToVertices.values() );
    for ( Iterator i = _idsToVertices.values().iterator(); i.hasNext(); )
    {
      Vertex vertex = (Vertex) i.next();
      addToGraph( vertex );
    }
  
    Map colorings = new HashMap();
    List topo = new ArrayList();
    
    // Now visit remaining items.
    for ( Iterator i = _idsToVertices.values().iterator(); i.hasNext(); )
    {
      Vertex vertex = (Vertex) i.next();
      Object color = colorings.get( vertex );
      if ( color == null )
      {
        visit( colorings, vertex, topo );
      }
    }

    
    // Reverse the list, removing any unresolved items.
    ArrayList sorted = new ArrayList( topo.size() );
    for ( ListIterator li = topo.listIterator( topo.size() ); li.hasPrevious(); )
    {
      Vertex v = (Vertex) li.previous();
      if ( !v.isUndefinedReference() )
      {
        sorted.add( v.getPositionable() );
      }
    }
    return sorted;
  }
  
  private void visit( Map colorings, Vertex vertex, List topo )
  {
    colorings.put( vertex, COLOR_VISITING );
    
    for ( Iterator children = vertex.getToEdges().iterator(); children.hasNext(); )
    {
      Vertex child = (Vertex) children.next();
      Object color = colorings.get( child );
      if ( color == COLOR_VISITING )
      {
        // Cycle detected. Skip this child.
        continue;
      }
      else if ( color != COLOR_VISITED )
      {
        visit( colorings, child, topo );
      }
    }
    
    // Have visited all children, now add to the topo list.
    topo.add( vertex );
    colorings.put( vertex, COLOR_VISITED ); 
  }
  
  
  private final static Object COLOR_VISITING = "visiting";
  private final static Object COLOR_VISITED = "visited";
  
  
  
  /**
   * A vertex in the graph. Each vertex represents a Positionable and its back
   * and forward references to other vertices. An undefined reference is a 
   * vertex for which the positionable has not yet been encountered (such cases
   * occur when an item defines itself to be before or after another item which
   * has not yet been defined)
   */
  private class Vertex
  {
    private List _toEdges = new ArrayList();
    private List _fromEdges = new ArrayList();
    private final String _name;
    private Positionable _positionable;
  
    public Vertex( String name )
    {
      _name = name;
    }
    
    public Vertex( Positionable positionable )
    {
      _name = positionable.getID();
      _positionable = positionable;
    }
    
    
    public void setPositionable( Positionable p )
    {
      _positionable = p;
    }
    
    public Positionable getPositionable()
    {
      return _positionable;
    }
    
    public boolean isUndefinedReference()
    {
      return _positionable == null;
    }
    
    public String getName()
    {
      return _name;
    }
    
    public Collection getFromEdges()
    {
      return _fromEdges;
    }
    
    public Collection getToEdges()
    {
      return _toEdges;
    }
    
    public void attachBefore( Vertex otherVertex )
    {
      if ( _fromEdges.contains( otherVertex ) || otherVertex == this )
      {
        return;
      }
      _fromEdges.add( otherVertex );
      otherVertex._toEdges.add( this );
    }
    
    public void attachAfter( Vertex otherVertex )
    {
      if ( _toEdges.contains( otherVertex ) || otherVertex == this )
      {
        return;
      }
      _toEdges.add( otherVertex );
      otherVertex._fromEdges.add( this );
    }
    
    public void attachAfter( Collection vertices )
    {
      for ( Iterator i = vertices.iterator(); i.hasNext(); )
      {
        Vertex v = (Vertex) i.next();
        attachAfter( v );
      }
    }

    public void attachBefore( Collection vertices )
    {
      for ( Iterator i = vertices.iterator(); i.hasNext(); )
      {
        Vertex v = (Vertex) i.next();
        attachBefore( v );
      }
    }
  }  
}