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

Revision 11181, 9.2 kB (checked in by robert, 5 years ago)

From Laurens Voerman, "my compiler (VC Express 9) gives some warnings (see below) about not being able to generate an assignment operator. As those assignment operators are not used and problably should never be used, I solved this by creating an private (empty) assingment operator.
"

From Robert Osfield, added "return *this;" to Laurens's addition to prevent them generating a warning under gcc...

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        private:
107                node& operator = (const node&) { return *this; }
108        };
109
110
111        graph_array();
112        explicit graph_array(size_t NbNodes);
113
114        // Node related member functions
115        bool empty() const;
116        size_t size() const;
117
118        node & operator [] (nodeid i);
119        const node & operator [] (nodeid i) const;
120
121        node_iterator begin();
122        node_iterator end();
123        const_node_iterator begin() const;
124        const_node_iterator end() const;
125
126        node_reverse_iterator rbegin();
127        node_reverse_iterator rend();
128        const_node_reverse_iterator rbegin() const;
129        const_node_reverse_iterator rend() const;
130
131        // Arc related member functions
132        out_arc_iterator insert_arc(nodeid Initial, nodeid Terminal);
133        out_arc_iterator insert_arc(node_iterator Initial, node_iterator Terminal);
134
135        // Optimized (overloaded) functions
136        void swap(graph_type & Right);
137        friend void swap(graph_type & Left, graph_type & Right)                                                                         { Left.swap(Right); }
138
139protected:
140        graph_array(const graph_type &);
141        graph_type & operator = (const graph_type &);
142
143        node_vector             m_Nodes;
144        arc_list                m_Arcs;
145};
146
147
148
149// Additional "low level", graph related, functions
150template <class nodetype>
151void unmark_nodes(graph_array<nodetype> & G);
152
153
154
155
156
157//////////////////////////////////////////////////////////////////////////
158// graph_array::arc inline functions
159//////////////////////////////////////////////////////////////////////////
160
161template <class N>
162inline graph_array<N>::arc::arc(node_iterator Terminal)
163        : m_Terminal(Terminal) { }
164
165
166template <class N>
167inline typename graph_array<N>::node_iterator graph_array<N>::arc::terminal() const
168{
169        return m_Terminal;
170}
171
172
173
174//////////////////////////////////////////////////////////////////////////
175// graph_array::node inline functions
176//////////////////////////////////////////////////////////////////////////
177
178template <class N>
179inline graph_array<N>::node::node(arc_list & Arcs)
180        : m_Arcs(Arcs),
181          m_Begin((std::numeric_limits<size_t>::max)()),
182          m_End((std::numeric_limits<size_t>::max)()),
183          m_Marker(false)
184{
185
186}
187
188
189template <class N>
190inline void graph_array<N>::node::mark()
191{
192        m_Marker = true;
193}
194
195
196template <class N>
197inline void graph_array<N>::node::unmark()
198{
199        m_Marker = false;
200}
201
202
203template <class N>
204inline bool graph_array<N>::node::marked() const
205{
206        return m_Marker;
207}
208
209
210template <class N>
211inline bool graph_array<N>::node::out_empty() const
212{
213        return (m_Begin == m_End);
214}
215
216
217template <class N>
218inline size_t graph_array<N>::node::out_size() const
219{
220        return (m_End - m_Begin);
221}
222
223
224template <class N>
225inline typename graph_array<N>::out_arc_iterator graph_array<N>::node::out_begin()
226{
227        return (m_Arcs.begin() + m_Begin);
228}
229
230
231template <class N>
232inline typename graph_array<N>::out_arc_iterator graph_array<N>::node::out_end()
233{
234        return (m_Arcs.begin() + m_End);
235}
236
237
238template <class N>
239inline typename graph_array<N>::const_out_arc_iterator graph_array<N>::node::out_begin() const
240{
241        return (m_Arcs.begin() + m_Begin);
242}
243
244
245template <class N>
246inline typename graph_array<N>::const_out_arc_iterator graph_array<N>::node::out_end() const
247{
248        return (m_Arcs.begin() + m_End);
249}
250
251
252template <class N>
253inline N & graph_array<N>::node::operator * ()
254{
255        return m_Elem;
256}
257
258
259template <class N>
260inline N * graph_array<N>::node::operator -> ()
261{
262        return &m_Elem;
263}
264
265
266template <class N>
267inline const N & graph_array<N>::node::operator * () const
268{
269        return m_Elem;
270}
271
272
273template <class N>
274inline const N * graph_array<N>::node::operator -> () const
275{
276        return &m_Elem;
277}
278
279
280template <class N>
281inline N & graph_array<N>::node::operator = (const N & Elem)
282{
283        return (m_Elem = Elem);
284}
285
286
287
288//////////////////////////////////////////////////////////////////////////
289// graph_array inline functions
290//////////////////////////////////////////////////////////////////////////
291
292template <class N>
293inline graph_array<N>::graph_array() { }
294
295
296template <class N>
297inline graph_array<N>::graph_array(const size_t NbNodes)
298        : m_Nodes(NbNodes, node(m_Arcs))
299{
300        // optimisation: we consider that, averagely, a triangle may have at least 2 neighbours
301        // otherwise we are just wasting a bit of memory, but not that much
302        m_Arcs.reserve(NbNodes * 2);
303}
304
305
306template <class N>
307inline bool graph_array<N>::empty() const
308{
309        return m_Nodes.empty();
310}
311
312
313template <class N>
314inline size_t graph_array<N>::size() const 
315{
316        return m_Nodes.size();
317}
318
319
320template <class N>
321inline typename graph_array<N>::node & graph_array<N>::operator [] (const nodeid i)
322{
323        assert(i < size());
324
325        return m_Nodes[i];
326}
327
328
329template <class N>
330inline const typename graph_array<N>::node & graph_array<N>::operator [] (const nodeid i) const
331{
332        assert(i < size());
333
334        return m_Nodes[i];
335}
336
337
338template <class N>
339inline typename graph_array<N>::node_iterator graph_array<N>::begin()
340{
341        return m_Nodes.begin();
342}
343
344
345template <class N>
346inline typename graph_array<N>::node_iterator graph_array<N>::end()
347{
348        return m_Nodes.end();
349}
350
351
352template <class N>
353inline typename graph_array<N>::const_node_iterator graph_array<N>::begin() const
354{
355        return m_Nodes.begin();
356}
357
358
359template <class N>
360inline typename graph_array<N>::const_node_iterator graph_array<N>::end() const
361{
362        return m_Nodes.end();
363}
364
365
366template <class N>
367inline typename graph_array<N>::node_reverse_iterator graph_array<N>::rbegin()
368{
369        return m_Nodes.rbegin();
370}
371
372
373template <class N>
374inline typename graph_array<N>::node_reverse_iterator graph_array<N>::rend()
375{
376        return m_Nodes.rend();
377}
378
379
380template <class N>
381inline typename graph_array<N>::const_node_reverse_iterator graph_array<N>::rbegin() const
382{
383        return m_Nodes.rbegin();
384}
385
386
387template <class N>
388inline typename graph_array<N>::const_node_reverse_iterator graph_array<N>::rend() const
389{
390        return m_Nodes.rend();
391}
392
393
394template <class N>
395inline typename graph_array<N>::out_arc_iterator graph_array<N>::insert_arc(const nodeid Initial, const nodeid Terminal)
396{
397        assert(Initial < size());
398        assert(Terminal < size());
399
400        return insert_arc(m_Nodes.begin() + Initial, m_Nodes.begin() + Terminal);
401}
402
403
404template <class N>
405inline typename graph_array<N>::out_arc_iterator graph_array<N>::insert_arc(const node_iterator Initial, const node_iterator Terminal)
406{
407        assert((Initial >= begin()) && (Initial < end()));
408        assert((Terminal >= begin()) && (Terminal < end()));
409
410        node & Node = * Initial;
411
412        if (Node.out_empty()) {
413
414                Node.m_Begin = m_Arcs.size();
415                Node.m_End = m_Arcs.size() + 1;
416
417        } else {
418
419                // we optimise here for make_connectivity_graph()
420                // we know all the arcs for a given node are successively and sequentially added
421                assert(Node.m_End == m_Arcs.size());
422               
423                ++(Node.m_End);
424        }
425
426        m_Arcs.push_back(arc(Terminal));
427
428        out_arc_iterator it = m_Arcs.end();
429        return (--it);
430}
431
432
433template <class N>
434inline void graph_array<N>::swap(graph_type & Right)
435{
436        std::swap(m_Nodes, Right.m_Nodes);
437        std::swap(m_Arcs, Right.m_Arcs);
438}
439
440
441
442//////////////////////////////////////////////////////////////////////////
443// additional functions
444//////////////////////////////////////////////////////////////////////////
445
446template <class N>
447inline void unmark_nodes(graph_array<N> & G)
448{
449        std::for_each(G.begin(), G.end(), std::mem_fun_ref(&graph_array<N>::node::unmark));
450}
451
452
453
454
455        } // namespace detail
456
457} // namespace triangle_stripper
458
459
460
461
462#endif // TRI_STRIPPER_HEADER_GUARD_GRAPH_ARRAY_H
Note: See TracBrowser for help on using the browser.