gfx/layers/DirectedGraph.h

   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 class DirectedGraph {
  17 public:
  18
  19   class Edge {
  20     public:
  21     Edge(T aFrom, T aTo) : mFrom(aFrom), mTo(aTo) {}
  22
  23     bool operator==(const Edge& aOther) const
  24     {
  25       return mFrom == aOther.mFrom && mTo == aOther.mTo;
  26     }
  27
  28     T mFrom;
  29     T mTo;
  30   };
  31
  32   class RemoveEdgesToComparator
  33   {
  34   public:
  35     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   void AddEdge(Edge aEdge)
  42   {
  43     NS_ASSERTION(!mEdges.Contains(aEdge), "Adding a duplicate edge!");
  44     mEdges.AppendElement(aEdge);
  45   }
  46
  47   void AddEdge(T aFrom, T aTo)
  48   {
  49     AddEdge(Edge(aFrom, aTo));
  50   }
  51
  52   /**
  53    * Get the list of edges.
  54    */
  55   const nsTArray<Edge>& GetEdgeList() const
  56   {
  57     return mEdges;
  58   }
  59
  60   /**
  61    * Remove the given edge from the graph.
  62    */
  63   void RemoveEdge(Edge aEdge)
  64   {
  65     mEdges.RemoveElement(aEdge);
  66   }
  67
  68   /**
  69    * Remove all edges going into aNode.
  70    */
  71   void RemoveEdgesTo(T aNode)
  72   {
  73     RemoveEdgesToComparator c;
  74     while (mEdges.RemoveElement(aNode, c)) {}
  75   }
  76
  77   /**
  78    * Get the number of edges going into aNode.
  79    */
  80   unsigned int NumEdgesTo(T aNode)
  81   {
  82     unsigned int count = 0;
  83     for (unsigned int i = 0; i < mEdges.Length(); i++) {
  84       if (mEdges.ElementAt(i).mTo == aNode) {
  85         count++;
  86       }
  87     }
  88     return count;
  89   }
  90
  91   /**
  92    * Get the list of all edges going from aNode
  93    */
  94   void GetEdgesFrom(T aNode, nsTArray<Edge>& aResult)
  95   {
  96     for (unsigned int i = 0; i < mEdges.Length(); i++) {
  97       if (mEdges.ElementAt(i).mFrom == aNode) {
  98         aResult.AppendElement(mEdges.ElementAt(i));
  99       }
 100     }
 101   }
 102
 103   /**
 104    * Get the total number of edges.
 105    */
 106   unsigned int GetEdgeCount() { return mEdges.Length(); }
 107
 108 private:
 109
 110   nsTArray<Edge> mEdges;
 111 };
 112
 113 }
 114 }
 115
 116 #endif // GFX_DIRECTEDGRAPH_H