Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-
       2             :  * This Source Code Form is subject to the terms of the Mozilla Public
       3             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       4             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
       5             : 
       6             : #ifndef GFX_DIRECTEDGRAPH_H
       7             : #define GFX_DIRECTEDGRAPH_H
       8             : 
       9             : #include "gfxTypes.h"
      10             : #include "nsTArray.h"
      11             : 
      12             : namespace mozilla {
      13             : namespace layers {
      14             : 
      15             : template <typename T>
      16           0 : class DirectedGraph {
      17             : public:
      18             : 
      19             :   class Edge {
      20             :     public:
      21           0 :     Edge(T aFrom, T aTo) : mFrom(aFrom), mTo(aTo) {}
      22             : 
      23           0 :     bool operator==(const Edge& aOther) const
      24             :     {
      25           0 :       return mFrom == aOther.mFrom && mTo == aOther.mTo;
      26             :     }
      27             : 
      28             :     T mFrom;
      29             :     T mTo;
      30             :   };
      31             : 
      32             :   class RemoveEdgesToComparator 
      33             :   {
      34             :   public:
      35           0 :     bool Equals(const Edge& a, T const& b) const { return a.mTo == b; }
      36             :   };
      37             : 
      38             :   /**
      39             :    * Add a new edge to the graph.
      40             :    */
      41           0 :   void AddEdge(Edge aEdge)
      42             :   {
      43           0 :     NS_ASSERTION(!mEdges.Contains(aEdge), "Adding a duplicate edge!");
      44           0 :     mEdges.AppendElement(aEdge);
      45           0 :   }
      46             : 
      47           0 :   void AddEdge(T aFrom, T aTo)
      48             :   {
      49           0 :     AddEdge(Edge(aFrom, aTo));
      50           0 :   }
      51             : 
      52             :   /**
      53             :    * Get the list of edges.
      54             :    */
      55           0 :   const nsTArray<Edge>& GetEdgeList() const
      56             :   {
      57           0 :     return mEdges; 
      58             :   }
      59             : 
      60             :   /**
      61             :    * Remove the given edge from the graph.
      62             :    */
      63           0 :   void RemoveEdge(Edge aEdge)
      64             :   {
      65           0 :     mEdges.RemoveElement(aEdge);
      66           0 :   }
      67             : 
      68             :   /**
      69             :    * Remove all edges going into aNode.
      70             :    */
      71           0 :   void RemoveEdgesTo(T aNode)
      72             :   {
      73             :     RemoveEdgesToComparator c;
      74           0 :     while (mEdges.RemoveElement(aNode, c)) {}
      75           0 :   }
      76             :   
      77             :   /**
      78             :    * Get the number of edges going into aNode.
      79             :    */
      80           0 :   unsigned int NumEdgesTo(T aNode)
      81             :   {
      82           0 :     unsigned int count = 0;
      83           0 :     for (unsigned int i = 0; i < mEdges.Length(); i++) {
      84           0 :       if (mEdges.ElementAt(i).mTo == aNode) {
      85           0 :         count++;
      86             :       }
      87             :     }
      88           0 :     return count;
      89             :   }
      90             : 
      91             :   /**
      92             :    * Get the list of all edges going from aNode
      93             :    */
      94           0 :   void GetEdgesFrom(T aNode, nsTArray<Edge>& aResult)
      95             :   {
      96           0 :     for (unsigned int i = 0; i < mEdges.Length(); i++) {
      97           0 :       if (mEdges.ElementAt(i).mFrom == aNode) {
      98           0 :         aResult.AppendElement(mEdges.ElementAt(i));
      99             :       }
     100             :     }
     101           0 :   }
     102             : 
     103             :   /**
     104             :    * Get the total number of edges.
     105             :    */
     106           0 :   unsigned int GetEdgeCount() { return mEdges.Length(); }
     107             : 
     108             : private:
     109             : 
     110             :   nsTArray<Edge> mEdges;
     111             : };
     112             : 
     113             : } // namespace layers
     114             : } // namespace mozilla
     115             : 
     116             : #endif // GFX_DIRECTEDGRAPH_H