My Project: dynamics.mod/NewtonDynamics/source/core/dgGraph.h Source File

My Project

dgGraph.h
Go to the documentation of this file.
1 /* Copyright (c) <2003-2011> <Julio Jerez, Newton Game Dynamics>
2 *
3 * This software is provided 'as-is', without any express or implied
4 * warranty. In no event will the authors be held liable for any damages
5 * arising from the use of this software.
6 *
7 * Permission is granted to anyone to use this software for any purpose,
8 * including commercial applications, and to alter it and redistribute it
9 * freely, subject to the following restrictions:
10 *
11 * 1. The origin of this software must not be misrepresented; you must not
12 * claim that you wrote the original software. If you use this software
13 * in a product, an acknowledgment in the product documentation would be
14 * appreciated but is not required.
15 *
16 * 2. Altered source versions must be plainly marked as such, and must not be
17 * misrepresented as being the original software.
18 *
19 * 3. This notice may not be removed or altered from any source distribution.
20 */
21
22 /****************************************************************************
23 *
24 * Visual C++ 6.0 created by: Julio Jerez
25 *
26 ****************************************************************************/
27 #ifndef __dgGraph__
28 #define __dgGraph__
29
30 #include "dgStdafx.h"
31 #include "dgRef.h"
32 #include "dgList.h"
33
34
35 template<class dgNodeData, class dgEdgeData> class dgGraphEdge;
36 template<class dgNodeData, class dgEdgeData> class dgGraphNode;
37
38
39 template<class dgNodeData, class dgEdgeData>
40 class dgGraph: public dgList<dgGraphNode<dgNodeData, dgEdgeData> >
41 {
42 public:
43 dgGraph (dgMemoryAllocator* const allocator);
44 ~dgGraph ();
45
46 typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* AddNode ();
47 void DeleteNode (typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node);
48
49 typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* GetNodeFromNodeData(dgNodeData* const nodeData);
50
51 //void Trace () const;
52 };
53
54 template<class dgNodeData, class dgEdgeData>
55 class dgGraphNode: public dgList<dgGraphEdge<dgNodeData, dgEdgeData> >
56 {
57 public:
58 dgGraphNode ();
59 ~dgGraphNode ();
60
61 typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* AddEdge(typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node);
62 void DeleteHalfEdge(typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* const edge);
63 void DeleteEdge(typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* const edge);
64
65 //void Trace () const;
66
67 dgNodeData m_nodeData;
68 };
69
70 template<class dgNodeData, class dgEdgeData>
71 class dgGraphEdge
72 {
73 public:
74 dgGraphEdge();
75 ~dgGraphEdge();
76
77 typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* m_node;
78 dgEdgeData m_edgeData;
79 };
80
81
82
83 template<class dgNodeData, class dgEdgeData>
84 dgGraph<dgNodeData, dgEdgeData>::dgGraph (dgMemoryAllocator* const allocator)
85 :dgList<dgGraphNode<dgNodeData, dgEdgeData> >(allocator)
86 {
87 }
88
89
90 template<class dgNodeData, class dgEdgeData>
91 dgGraph<dgNodeData, dgEdgeData>::~dgGraph ()
92 {
93 }
94
95 template<class dgNodeData, class dgEdgeData>
96 typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* dgGraph<dgNodeData, dgEdgeData>::AddNode ()
97 {
98 typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node = dgGraph<dgNodeData, dgEdgeData>::Append();
99
100 node->GetInfo().SetAllocator(dgGraph<dgNodeData, dgEdgeData>::GetAllocator());
101
102 return node;
103 }
104
105 template<class dgNodeData, class dgEdgeData>
106 void dgGraph<dgNodeData, dgEdgeData>::DeleteNode (typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node)
107 {
108 for (typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* link = node->GetInfo().GetFirst(); link; link = link->GetNext()) {
109 typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const twinNode = link->GetInfo().m_node;
110 for (typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* link1 = twinNode->GetInfo().GetFirst(); link1; link1 = link1->GetNext()) {
111 if (link1->GetInfo().m_node == node) {
112 twinNode->GetInfo().Remove (link1);
113 break;
114 }
115 }
116 }
117 dgList<dgGraphNode<dgNodeData, dgEdgeData> >::Remove (node);
118 }
119
120 template<class dgNodeData, class dgEdgeData>
121 typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* dgGraph<dgNodeData, dgEdgeData>::GetNodeFromNodeData(dgNodeData* const nodeData)
122 {
123 dgInt32 size1 = sizeof (*nodeData);
124 dgInt32 size0 = sizeof (dgGraphNode<dgNodeData, dgEdgeData>);
125 void* const ptr = ((char*)nodeData) - (size0 - size1);
126 dgGraphNode<dgNodeData, dgEdgeData>* const nodeInfo = (dgGraphNode<dgNodeData, dgEdgeData>*) ptr;
127 return this->GetNodeFromInfo(*nodeInfo);
128 }
129
130 /*
131 template<class dgNodeData, class dgEdgeData>
132 void dgGraph<dgNodeData, dgEdgeData>::Trace () const
133 {
134 for (typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* link = dgGraphNode<dgNodeData, dgEdgeData>::GetFirst(); link; link = link->GetNext()) {
135 link->GetInfo().Trace ();
136 dgTrace (("%d: ", link->GetInfo().m_index));
137 for (typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* edge = link->GetInfo().GetFirst(); edge; edge = edge->GetNext()) {
138 dgListNode* const node = edge->GetInfo().m_node;
139 dgTrace (("%d ", node->GetInfo().m_index));
140 }
141 dgTrace (("\n"));
142 }
143 dgTrace (("\n"));
144 }
145 */
146
147 template<class dgNodeData, class dgEdgeData>
148 dgGraphNode<dgNodeData, dgEdgeData>::dgGraphNode()
149 :dgList<dgGraphEdge<dgNodeData, dgEdgeData> >(NULL)
150 {
151
152 }
153
154
155 template<class dgNodeData, class dgEdgeData>
156 dgGraphNode<dgNodeData, dgEdgeData>::~dgGraphNode()
157 {
158
159 }
160
161 template<class dgNodeData, class dgEdgeData>
162 typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* dgGraphNode<dgNodeData, dgEdgeData>::AddEdge (typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node)
163 {
164 typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* const edge = dgGraphNode<dgNodeData, dgEdgeData>::Append();
165
166 edge->GetInfo().m_node = node;
167 return edge;
168 }
169
170 template<class dgNodeData, class dgEdgeData>
171 void dgGraphNode<dgNodeData, dgEdgeData>::DeleteHalfEdge(typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* const edge)
172 {
173 dgList<dgGraphEdge<dgNodeData, dgEdgeData> >::Remove (edge);
174 }
175
176 template<class dgNodeData, class dgEdgeData>
177 void dgGraphNode<dgNodeData, dgEdgeData>::DeleteEdge(typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* const edge)
178 {
179 typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node = edge->GetInfo().m_node;
180
181 for (typename dgGraphNode<dgNodeData, dgEdgeData>::dgListNode* twinEdge = node->GetInfo().GetFirst(); twinEdge; twinEdge = twinEdge->GetNext()) {
182 if (&twinEdge->GetInfo().m_node->GetInfo() == this) {
183 node->GetInfo().DeleteHalfEdge(twinEdge);
184 break;
185 }
186 }
187
188 DeleteHalfEdge(edge);
189 }
190
191 /*
192 template<class dgNodeData, class dgEdgeData>
193 void dgGraphNode<dgNodeData, dgEdgeData>::Trace () const
194 {
195 dgTrace (("%d: ", m_index));
196 for (typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* edge = typename dgGraph<dgNodeData, dgEdgeData>::GetFirst(); edge; edge = edge->GetNext()) {
197 typename dgGraph<dgNodeData, dgEdgeData>::dgListNode* const node;
198 node = edge->GetInfo().m_node;
199 dgTrace (("%d ", node->GetInfo().m_index));
200 }
201 dgTrace (("\n"));
202
203 }
204 */
205
206 template<class dgNodeData, class dgEdgeData>
207 dgGraphEdge<dgNodeData, dgEdgeData>::dgGraphEdge()
208 {
209
210 }
211
212 template<class dgNodeData, class dgEdgeData>
213 dgGraphEdge<dgNodeData, dgEdgeData>::~dgGraphEdge()
214 {
215
216 }
217
218
219
220 #endif
221
dgGraph::AddNode
dgGraph< dgNodeData, dgEdgeData >::dgListNode * AddNode()
Definition: dgGraph.h:96
dgGraph::DeleteNode
void DeleteNode(typename dgGraph< dgNodeData, dgEdgeData >::dgListNode *const node)
Definition: dgGraph.h:106
dgGraph::dgGraph
dgGraph(dgMemoryAllocator *const allocator)
Definition: dgGraph.h:84
dgGraphNode::~dgGraphNode
~dgGraphNode()
Definition: dgGraph.h:156
dgGraph
Definition: dgGraph.h:40
dgList< dgGraphNode< dgNodeData, dgEdgeData > >::Remove
void Remove(dgListNode *const node)
Definition: dgList.h:611
dgGraphEdge::m_node
dgGraph< dgNodeData, dgEdgeData >::dgListNode * m_node
Definition: dgGraph.h:77
dgGraphNode::DeleteHalfEdge
void DeleteHalfEdge(typename dgGraphNode< dgNodeData, dgEdgeData >::dgListNode *const edge)
Definition: dgGraph.h:171
dgGraph::GetNodeFromNodeData
dgGraph< dgNodeData, dgEdgeData >::dgListNode * GetNodeFromNodeData(dgNodeData *const nodeData)
Definition: dgGraph.h:121
dgInt32
int dgInt32
Definition: dgTypes.h:218
dgList< dgGraphNode< dgNodeData, dgEdgeData > >::GetNodeFromInfo
dgListNode * GetNodeFromInfo(dgGraphNode< dgNodeData, dgEdgeData > &m_info) const
Definition: dgList.h:545
dgGraph::~dgGraph
~dgGraph()
Definition: dgGraph.h:91
dgList
Definition: dgList.h:33
dgGraphEdge::dgGraphEdge
dgGraphEdge()
Definition: dgGraph.h:207
dgList< dgGraphNode< dgNodeData, dgEdgeData > >::Append
dgListNode * Append()
Definition: dgList.h:338
dgGraphNode::dgGraphNode
dgGraphNode()
Definition: dgGraph.h:148
dgStdafx.h
dgList.h
dgGraphEdge
Definition: dgGraph.h:35
dgGraphEdge::m_edgeData
dgEdgeData m_edgeData
Definition: dgGraph.h:78
dgGraphNode::m_nodeData
dgNodeData m_nodeData
Definition: dgGraph.h:67
dgGraphNode
Definition: dgGraph.h:36
dgMemoryAllocator
Definition: dgMemory.h:73
dgList< dgGraphNode< dgNodeData, dgEdgeData > >::GetFirst
dgListNode * GetFirst() const
Definition: dgList.h:307
dgGraphNode::AddEdge
dgGraphNode< dgNodeData, dgEdgeData >::dgListNode * AddEdge(typename dgGraph< dgNodeData, dgEdgeData >::dgListNode *const node)
Definition: dgGraph.h:162
dgList< dgGraphNode< dgNodeData, dgEdgeData > >::SetAllocator
void SetAllocator(dgMemoryAllocator *const allocator)
Definition: dgList.h:280
dgGraphEdge::~dgGraphEdge
~dgGraphEdge()
Definition: dgGraph.h:213
dgRef.h
dgGraphNode::DeleteEdge
void DeleteEdge(typename dgGraphNode< dgNodeData, dgEdgeData >::dgListNode *const edge)
Definition: dgGraph.h:177