root/OpenSceneGraph/trunk/src/osgUtil/tristripper/include/detail/graph_array.h @ 10894

Revision 10894, 9.2 kB (checked in by robert, 4 years ago)

From Tanguy Fautre and Robert Osfield, updated tristripper code to use the latest tristripper_r94 code.

Line 
1//
2// Copyright (C) 2004 Tanguy Fautré.
3// For conditions of distribution and use,
4// see copyright notice in tri_stripper.h
5//
6//////////////////////////////////////////////////////////////////////
7// SVN: $Id: graph_array.h 93 2009-11-24 20:01:19Z gpsnoopy $
8//////////////////////////////////////////////////////////////////////
9
10#ifndef TRI_STRIPPER_HEADER_GUARD_GRAPH_ARRAY_H
11#define TRI_STRIPPER_HEADER_GUARD_GRAPH_ARRAY_H
12
13#include <cassert>
14#include <algorithm>
15#include <functional>
16#include <limits>
17#include <vector>
18
19
20
21
22namespace triangle_stripper {
23
24        namespace detail {
25
26
27
28
29// graph_array main class
30template <class nodetype>
31class graph_array
32{
33public:
34
35        class arc;
36        class node;
37
38        // New types
39        typedef size_t                                                                                  nodeid;
40        typedef nodetype                                                                                value_type;
41        typedef std::vector<node>                                                               node_vector;
42        typedef typename node_vector::iterator                                  node_iterator;
43        typedef typename node_vector::const_iterator                    const_node_iterator;
44        typedef typename node_vector::reverse_iterator                  node_reverse_iterator;
45        typedef typename node_vector::const_reverse_iterator    const_node_reverse_iterator;
46
47        typedef graph_array<nodetype> graph_type;
48       
49
50        // graph_array::arc class
51        class arc
52        {
53        public:
54                node_iterator terminal() const;
55
56        protected:
57                friend class graph_array<nodetype>;
58
59                arc(node_iterator Terminal);
60       
61                node_iterator   m_Terminal;
62        };
63
64
65        // New types
66        typedef std::vector<arc>                                        arc_list;
67        typedef typename arc_list::iterator                     out_arc_iterator;
68        typedef typename arc_list::const_iterator       const_out_arc_iterator;
69
70
71        // graph_array::node class
72        class node
73        {
74        public:
75                void mark();
76                void unmark();
77                bool marked() const;
78
79                bool out_empty() const;
80                size_t out_size() const;
81
82                out_arc_iterator out_begin();
83                out_arc_iterator out_end();
84                const_out_arc_iterator out_begin() const;
85                const_out_arc_iterator out_end() const;
86
87                value_type & operator * ();
88                value_type * operator -> ();
89                const value_type & operator * () const;
90                const value_type * operator -> () const;
91
92                value_type & operator = (const value_type & Elem);
93
94        protected:
95                friend class graph_array<nodetype>;
96                friend class std::vector<node>;
97
98                node(arc_list & Arcs);
99
100                arc_list &              m_Arcs;
101                size_t                  m_Begin;
102                size_t                  m_End;
103
104                value_type              m_Elem;
105                bool                    m_Marker;
106        };
107
108
109        graph_array();
110        explicit graph_array(size_t NbNodes);
111
112        // Node related member functions
113        bool empty() const;
114        size_t size() const;
115
116        node & operator [] (nodeid i);
117        const node & operator [] (nodeid i) const;
118
119        node_iterator begin();
120        node_iterator end();
121        const_node_iterator begin() const;
122        const_node_iterator end() const;
123
124        node_reverse_iterator rbegin();
125        node_reverse_iterator rend();
126        const_node_reverse_iterator rbegin() const;
127        const_node_reverse_iterator rend() const;
128
129        // Arc related member functions
130        out_arc_iterator insert_arc(nodeid Initial, nodeid Terminal);
131        out_arc_iterator insert_arc(node_iterator Initial, node_iterator Terminal);
132
133        // Optimized (overloaded) functions
134        void swap(graph_type & Right);
135        friend void swap(graph_type & Left, graph_type & Right)                                                                         { Left.swap(Right); }
136
137protected:
138        graph_array(const graph_type &);
139        graph_type & operator = (const graph_type &);
140
141        node_vector             m_Nodes;
142        arc_list                m_Arcs;
143};
144
145
146
147// Additional "low level", graph related, functions
148template <class nodetype>
149void unmark_nodes(graph_array<nodetype> & G);
150
151
152
153
154
155//////////////////////////////////////////////////////////////////////////
156// graph_array::arc inline functions
157//////////////////////////////////////////////////////////////////////////
158
159template <class N>
160inline graph_array<N>::arc::arc(node_iterator Terminal)
161        : m_Terminal(Terminal) { }
162
163
164template <class N>
165inline typename graph_array<N>::node_iterator graph_array<N>::arc::terminal() const
166{
167        return m_Terminal;
168}
169
170
171
172//////////////////////////////////////////////////////////////////////////
173// graph_array::node inline functions
174//////////////////////////////////////////////////////////////////////////
175
176template <class N>
177inline graph_array<N>::node::node(arc_list & Arcs)
178        : m_Arcs(Arcs),
179          m_Begin((std::numeric_limits<size_t>::max)()),
180          m_End((std::numeric_limits<size_t>::max)()),
181          m_Marker(false)
182{
183
184}
185
186
187template <class N>
188inline void graph_array<N>::node::mark()
189{
190        m_Marker = true;
191}
192
193
194template <class N>
195inline void graph_array<N>::node::unmark()
196{
197        m_Marker = false;
198}
199
200
201template <class N>
202inline bool graph_array<N>::node::marked() const
203{
204        return m_Marker;
205}
206
207
208template <class N>
209inline bool graph_array<N>::node::out_empty() const
210{
211        return (m_Begin == m_End);
212}
213
214
215template <class N>
216inline size_t graph_array<N>::node::out_size() const
217{
218        return (m_End - m_Begin);
219}
220
221
222template <class N>
223inline typename graph_array<N>::out_arc_iterator graph_array<N>::node::out_begin()
224{
225        return (m_Arcs.begin() + m_Begin);
226}
227
228
229template <class N>
230inline typename graph_array<N>::out_arc_iterator graph_array<N>::node::out_end()
231{
232        return (m_Arcs.begin() + m_End);
233}
234
235
236template <class N>
237inline typename graph_array<N>::const_out_arc_iterator graph_array<N>::node::out_begin() const
238{
239        return (m_Arcs.begin() + m_Begin);
240}
241
242
243template <class N>
244inline typename graph_array<N>::const_out_arc_iterator graph_array<N>::node::out_end() const
245{
246        return (m_Arcs.begin() + m_End);
247}
248
249
250template <class N>
251inline N & graph_array<N>::node::operator * ()
252{
253        return m_Elem;
254}
255
256
257template <class N>
258inline N * graph_array<N>::node::operator -> ()
259{
260        return &m_Elem;
261}
262
263
264template <class N>
265inline const N & graph_array<N>::node::operator * () const
266{
267        return m_Elem;
268}
269
270
271template <class N>
272inline const N * graph_array<N>::node::operator -> () const
273{
274        return &m_Elem;
275}
276
277
278template <class N>
279inline N & graph_array<N>::node::operator = (const N & Elem)
280{
281        return (m_Elem = Elem);
282}
283
284
285
286//////////////////////////////////////////////////////////////////////////
287// graph_array inline functions
288//////////////////////////////////////////////////////////////////////////
289
290template <class N>
291inline graph_array<N>::graph_array() { }
292
293
294template <class N>
295inline graph_array<N>::graph_array(const size_t NbNodes)
296        : m_Nodes(NbNodes, node(m_Arcs))
297{
298        // optimisation: we consider that, averagely, a triangle may have at least 2 neighbours
299        // otherwise we are just wasting a bit of memory, but not that much
300        m_Arcs.reserve(NbNodes * 2);
301}
302
303
304template <class N>
305inline bool graph_array<N>::empty() const
306{
307        return m_Nodes.empty();
308}
309
310
311template <class N>
312inline size_t graph_array<N>::size() const 
313{
314        return m_Nodes.size();
315}
316
317
318template <class N>
319inline typename graph_array<N>::node & graph_array<N>::operator [] (const nodeid i)
320{
321        assert(i < size());
322
323        return m_Nodes[i];
324}
325
326
327template <class N>
328inline const typename graph_array<N>::node & graph_array<N>::operator [] (const nodeid i) const
329{
330        assert(i < size());
331
332        return m_Nodes[i];
333}
334
335
336template <class N>
337inline typename graph_array<N>::node_iterator graph_array<N>::begin()
338{
339        return m_Nodes.begin();
340}
341
342
343template <class N>
344inline typename graph_array<N>::node_iterator graph_array<N>::end()
345{
346        return m_Nodes.end();
347}
348
349
350template <class N>
351inline typename graph_array<N>::const_node_iterator graph_array<N>::begin() const
352{
353        return m_Nodes.begin();
354}
355
356
357template <class N>
358inline typename graph_array<N>::const_node_iterator graph_array<N>::end() const
359{
360        return m_Nodes.end();
361}
362
363
364template <class N>
365inline typename graph_array<N>::node_reverse_iterator graph_array<N>::rbegin()
366{
367        return m_Nodes.rbegin();
368}
369
370
371template <class N>
372inline typename graph_array<N>::node_reverse_iterator graph_array<N>::rend()
373{
374        return m_Nodes.rend();
375}
376
377
378template <class N>
379inline typename graph_array<N>::const_node_reverse_iterator graph_array<N>::rbegin() const
380{
381        return m_Nodes.rbegin();
382}
383
384
385template <class N>
386inline typename graph_array<N>::const_node_reverse_iterator graph_array<N>::rend() const
387{
388        return m_Nodes.rend();
389}
390
391
392template <class N>
393inline typename graph_array<N>::out_arc_iterator graph_array<N>::insert_arc(const nodeid Initial, const nodeid Terminal)
394{
395        assert(Initial < size());
396        assert(Terminal < size());
397
398        return insert_arc(m_Nodes.begin() + Initial, m_Nodes.begin() + Terminal);
399}
400
401
402template <class N>
403inline typename graph_array<N>::out_arc_iterator graph_array<N>::insert_arc(const node_iterator Initial, const node_iterator Terminal)
404{
405        assert((Initial >= begin()) && (Initial < end()));
406        assert((Terminal >= begin()) && (Terminal < end()));
407
408        node & Node = * Initial;
409
410        if (Node.out_empty()) {
411
412                Node.m_Begin = m_Arcs.size();
413                Node.m_End = m_Arcs.size() + 1;
414
415        } else {
416
417                // we optimise here for make_connectivity_graph()
418                // we know all the arcs for a given node are successively and sequentially added
419                assert(Node.m_End == m_Arcs.size());
420               
421                ++(Node.m_End);
422        }
423
424        m_Arcs.push_back(arc(Terminal));
425
426        out_arc_iterator it = m_Arcs.end();
427        return (--it);
428}
429
430
431template <class N>
432inline void graph_array<N>::swap(graph_type & Right)
433{
434        std::swap(m_Nodes, Right.m_Nodes);
435        std::swap(m_Arcs, Right.m_Arcs);
436}
437
438
439
440//////////////////////////////////////////////////////////////////////////
441// additional functions
442//////////////////////////////////////////////////////////////////////////
443
444template <class N>
445inline void unmark_nodes(graph_array<N> & G)
446{
447        std::for_each(G.begin(), G.end(), std::mem_fun_ref(&graph_array<N>::node::unmark));
448}
449
450
451
452
453        } // namespace detail
454
455} // namespace triangle_stripper
456
457
458
459
460#endif // TRI_STRIPPER_HEADER_GUARD_GRAPH_ARRAY_H
Note: See TracBrowser for help on using the browser.