michael@0: /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef GFX_DIRECTEDGRAPH_H
michael@0: #define GFX_DIRECTEDGRAPH_H
michael@0: 
michael@0: #include "gfxTypes.h"
michael@0: #include "nsTArray.h"
michael@0: 
michael@0: namespace mozilla {
michael@0: namespace layers {
michael@0: 
michael@0: template <typename T>
michael@0: class DirectedGraph {
michael@0: public:
michael@0: 
michael@0:   class Edge {
michael@0:     public:
michael@0:     Edge(T aFrom, T aTo) : mFrom(aFrom), mTo(aTo) {}
michael@0: 
michael@0:     bool operator==(const Edge& aOther) const
michael@0:     {
michael@0:       return mFrom == aOther.mFrom && mTo == aOther.mTo;
michael@0:     }
michael@0: 
michael@0:     T mFrom;
michael@0:     T mTo;
michael@0:   };
michael@0: 
michael@0:   class RemoveEdgesToComparator 
michael@0:   {
michael@0:   public:
michael@0:     bool Equals(const Edge& a, T const& b) const { return a.mTo == b; }
michael@0:   };
michael@0: 
michael@0:   /**
michael@0:    * Add a new edge to the graph.
michael@0:    */
michael@0:   void AddEdge(Edge aEdge)
michael@0:   {
michael@0:     NS_ASSERTION(!mEdges.Contains(aEdge), "Adding a duplicate edge!");
michael@0:     mEdges.AppendElement(aEdge);
michael@0:   }
michael@0: 
michael@0:   void AddEdge(T aFrom, T aTo)
michael@0:   {
michael@0:     AddEdge(Edge(aFrom, aTo));
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Get the list of edges.
michael@0:    */
michael@0:   const nsTArray<Edge>& GetEdgeList() const
michael@0:   {
michael@0:     return mEdges; 
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Remove the given edge from the graph.
michael@0:    */
michael@0:   void RemoveEdge(Edge aEdge)
michael@0:   {
michael@0:     mEdges.RemoveElement(aEdge);
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Remove all edges going into aNode.
michael@0:    */
michael@0:   void RemoveEdgesTo(T aNode)
michael@0:   {
michael@0:     RemoveEdgesToComparator c;
michael@0:     while (mEdges.RemoveElement(aNode, c)) {}
michael@0:   }
michael@0:   
michael@0:   /**
michael@0:    * Get the number of edges going into aNode.
michael@0:    */
michael@0:   unsigned int NumEdgesTo(T aNode)
michael@0:   {
michael@0:     unsigned int count = 0;
michael@0:     for (unsigned int i = 0; i < mEdges.Length(); i++) {
michael@0:       if (mEdges.ElementAt(i).mTo == aNode) {
michael@0:         count++;
michael@0:       }
michael@0:     }
michael@0:     return count;
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Get the list of all edges going from aNode
michael@0:    */
michael@0:   void GetEdgesFrom(T aNode, nsTArray<Edge>& aResult)
michael@0:   {
michael@0:     for (unsigned int i = 0; i < mEdges.Length(); i++) {
michael@0:       if (mEdges.ElementAt(i).mFrom == aNode) {
michael@0:         aResult.AppendElement(mEdges.ElementAt(i));
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Get the total number of edges.
michael@0:    */
michael@0:   unsigned int GetEdgeCount() { return mEdges.Length(); }
michael@0: 
michael@0: private:
michael@0: 
michael@0:   nsTArray<Edge> mEdges;
michael@0: };
michael@0: 
michael@0: }
michael@0: }
michael@0: 
michael@0: #endif // GFX_DIRECTEDGRAPH_H