Source code: javax/ide/menu/spi/PositionMap.java

   package javax.ide.menu.spi;
   
   import java.util.ArrayList;
   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 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 = (Vertex) _idsToVertices.get( p.getID() );
      if ( thisVertex == null )
      {
        thisVertex = new Vertex( p );
        _idsToVertices.put( p.getID(), thisVertex );
      }
    }
    
    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();
      }
      
      if ( after != null )
      {
        Vertex afterVertex = (Vertex) _idsToVertices.get( after );
        if ( afterVertex == null )
        {
          afterVertex = new Vertex( after );    
          _idsToVertices.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(); i.hasNext();  )
          {
            Vertex v = (Vertex) i.next();
            if ( afterVertex != v )
            {
              afterVertex.attachAfter( v );
            }
          }
          thisVertex.setPositionable( p );
        }
  
      }
      
      if ( before != null )
      {
        Vertex beforeVertex = (Vertex) _idsToVertices.get( before );
        if ( beforeVertex == null )
        {
          beforeVertex = new Vertex( before );
          _idsToVertices.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(); 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 = (Vertex) _idsToVertices.get( 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.
     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(); 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 Iterator getFromEdges()
     {
       return _fromEdges.iterator();
     }
     
     public Iterator getToEdges()
     {
       return _toEdges.iterator();
     }
     
     public void attachBefore( Vertex otherVertex )
     {
       if ( otherVertex == this )
       {
         throw new IllegalArgumentException( "Cannot connect a vertex to itself" );
       }
       _fromEdges.add( otherVertex );
       otherVertex._toEdges.add( this );
     }
     
     public void attachAfter( Vertex otherVertex )
     {
       if ( otherVertex == this )
       {
         throw new IllegalArgumentException( "Cannot connect a vertex to itself" );
       }
       _toEdges.add( otherVertex );
       otherVertex._fromEdges.add( this );
     }
     
     public void attachAfter( Iterator vertices )
     {
       while ( vertices.hasNext() )
       {
         Vertex v = (Vertex) vertices.next();
         attachAfter( v );
       }
     }
 
     public void attachBefore( Iterator vertices )
     {
       while ( vertices.hasNext() )
       {
         Vertex v = (Vertex) vertices.next();
         attachBefore( v );
       }
     }
   }  
 }