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