1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/layers/DirectedGraph.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,116 @@
1.4 +/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-
1.5 + * This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#ifndef GFX_DIRECTEDGRAPH_H
1.10 +#define GFX_DIRECTEDGRAPH_H
1.11 +
1.12 +#include "gfxTypes.h"
1.13 +#include "nsTArray.h"
1.14 +
1.15 +namespace mozilla {
1.16 +namespace layers {
1.17 +
1.18 +template <typename T>
1.19 +class DirectedGraph {
1.20 +public:
1.21 +
1.22 + class Edge {
1.23 + public:
1.24 + Edge(T aFrom, T aTo) : mFrom(aFrom), mTo(aTo) {}
1.25 +
1.26 + bool operator==(const Edge& aOther) const
1.27 + {
1.28 + return mFrom == aOther.mFrom && mTo == aOther.mTo;
1.29 + }
1.30 +
1.31 + T mFrom;
1.32 + T mTo;
1.33 + };
1.34 +
1.35 + class RemoveEdgesToComparator
1.36 + {
1.37 + public:
1.38 + bool Equals(const Edge& a, T const& b) const { return a.mTo == b; }
1.39 + };
1.40 +
1.41 + /**
1.42 + * Add a new edge to the graph.
1.43 + */
1.44 + void AddEdge(Edge aEdge)
1.45 + {
1.46 + NS_ASSERTION(!mEdges.Contains(aEdge), "Adding a duplicate edge!");
1.47 + mEdges.AppendElement(aEdge);
1.48 + }
1.49 +
1.50 + void AddEdge(T aFrom, T aTo)
1.51 + {
1.52 + AddEdge(Edge(aFrom, aTo));
1.53 + }
1.54 +
1.55 + /**
1.56 + * Get the list of edges.
1.57 + */
1.58 + const nsTArray<Edge>& GetEdgeList() const
1.59 + {
1.60 + return mEdges;
1.61 + }
1.62 +
1.63 + /**
1.64 + * Remove the given edge from the graph.
1.65 + */
1.66 + void RemoveEdge(Edge aEdge)
1.67 + {
1.68 + mEdges.RemoveElement(aEdge);
1.69 + }
1.70 +
1.71 + /**
1.72 + * Remove all edges going into aNode.
1.73 + */
1.74 + void RemoveEdgesTo(T aNode)
1.75 + {
1.76 + RemoveEdgesToComparator c;
1.77 + while (mEdges.RemoveElement(aNode, c)) {}
1.78 + }
1.79 +
1.80 + /**
1.81 + * Get the number of edges going into aNode.
1.82 + */
1.83 + unsigned int NumEdgesTo(T aNode)
1.84 + {
1.85 + unsigned int count = 0;
1.86 + for (unsigned int i = 0; i < mEdges.Length(); i++) {
1.87 + if (mEdges.ElementAt(i).mTo == aNode) {
1.88 + count++;
1.89 + }
1.90 + }
1.91 + return count;
1.92 + }
1.93 +
1.94 + /**
1.95 + * Get the list of all edges going from aNode
1.96 + */
1.97 + void GetEdgesFrom(T aNode, nsTArray<Edge>& aResult)
1.98 + {
1.99 + for (unsigned int i = 0; i < mEdges.Length(); i++) {
1.100 + if (mEdges.ElementAt(i).mFrom == aNode) {
1.101 + aResult.AppendElement(mEdges.ElementAt(i));
1.102 + }
1.103 + }
1.104 + }
1.105 +
1.106 + /**
1.107 + * Get the total number of edges.
1.108 + */
1.109 + unsigned int GetEdgeCount() { return mEdges.Length(); }
1.110 +
1.111 +private:
1.112 +
1.113 + nsTArray<Edge> mEdges;
1.114 +};
1.115 +
1.116 +}
1.117 +}
1.118 +
1.119 +#endif // GFX_DIRECTEDGRAPH_H
