root/OpenSceneGraph/trunk/src/osgUtil/TriStrip_graph_array.h @ 9655

Revision 9655, 14.8 kB (checked in by robert, 5 years ago)

From Jean-Sebastien Guay, warning fixes

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
1// graph_array.h: interface for the graph_array class.
2//
3//////////////////////////////////////////////////////////////////////
4//
5//  Copyright (C) 2002 Tanguy Fautré.
6//
7//  This software is provided 'as-is', without any express or implied
8//  warranty.  In no event will the authors be held liable for any damages
9//  arising from the use of this software.
10//
11//  Permission is granted to anyone to use this software for any purpose,
12//  including commercial applications, and to alter it and redistribute it
13//  freely, subject to the following restrictions:
14//
15//  1. The origin of this software must not be misrepresented; you must not
16//     claim that you wrote the original software. If you use this software
17//     in a product, an acknowledgment in the product documentation would be
18//     appreciated but is not required.
19//  2. Altered source versions must be plainly marked as such, and must not be
20//     misrepresented as being the original software.
21//  3. This notice may not be removed or altered from any source distribution.
22//
23//  Tanguy Fautré
24//  softdev@pandora.be
25//
26//////////////////////////////////////////////////////////////////////
27//
28//                        Semi-dynamic directed graph
29//                        ***************************
30//
31// Current version: 3.00 BETA 3 (04/12/2002)
32//
33// Comment: graph_array is equivalent to an array of nodes linked by
34//          arcs.
35//          This means you can't change the size (the number of nodes)
36//          of the graph once you created it (setsize() will delete
37//          any previous nodes and arcs).
38//          But you can add or remove arcs.
39//         
40// History: - 3.00 BETA 3 (04/12/2002) - Added empty()
41//                                     - Changed some parameters from copy to reference
42//                                     - Fixed a bug with erase_arc
43//                                     - Un-inlined external functions
44//                                     - Added "insert_arc" which is equivalent to "insert"
45//          - 3.00 BETA 2 (16/11/2002) - Improved portability
46//          - 3.00 BETA 1 (27/08/2002) - First public release
47//
48//////////////////////////////////////////////////////////////////////
49
50#ifndef TRISTRIP_GRAPH_ARRAY_H
51#define TRISTRIP_GRAPH_ARRAY_H
52
53// namespace common_structures
54namespace common_structures {
55
56
57
58
59// graph_array main class
60template <class nodetype, class arctype>
61class graph_array
62{
63public:
64
65    class arc;
66    class node;
67
68    // New types
69    typedef size_t                                        nodeid;
70    typedef typename std::vector<node>::iterator                    node_iterator;
71    typedef typename std::vector<node>::const_iterator            const_node_iterator;
72    typedef typename std::vector<node>::reverse_iterator            node_reverse_iterator;
73    typedef typename std::vector<node>::const_reverse_iterator    const_node_reverse_iterator;
74
75    typedef graph_array<nodetype, arctype> _mytype;
76   
77
78    // graph_array::arc class
79    class arc
80    {
81    public:
82        arc() {}
83        arc & mark()                                    { m_Marker = true; return (* this); }
84        arc & unmark()                                    { m_Marker = false; return (* this); }
85        bool marked() const                                { return m_Marker; }
86
87        node_iterator initial() const                    { return m_Initial; }
88        node_iterator terminal() const                    { return m_Terminal; }
89
90        arctype & operator * ()                            { return m_Elem; }
91        const arctype & operator * () const                { return m_Elem; }
92
93    protected:
94        friend class graph_array<nodetype, arctype>;
95
96        arc(const node_iterator & Initial, const node_iterator & Terminal)
97            : m_Initial(Initial), m_Terminal(Terminal), m_Marker(false) { }
98
99        arc(const node_iterator & Initial, const node_iterator & Terminal, const arctype & Elem)
100            : m_Initial(Initial), m_Terminal(Terminal), m_Elem(Elem), m_Marker(false) { }
101   
102        node_iterator    m_Initial;
103        node_iterator    m_Terminal;
104        arctype            m_Elem;
105        bool            m_Marker;
106    };
107
108
109    // New types
110    typedef typename std::list<arc>::iterator            out_arc_iterator;
111    typedef typename std::list<arc>::const_iterator        const_out_arc_iterator;
112
113
114    // graph_array::node class
115    class node
116    {
117    public:
118        node & mark()                                    { m_Marker = true; return (* this); }
119        node & unmark()                                    { m_Marker = false; return (* this); }
120        bool marked() const                                { return m_Marker; }
121
122        bool out_empty() const                            { return m_OutArcs.empty(); }
123        size_t number_of_out_arcs() const                { return m_OutArcs.size(); }
124
125        out_arc_iterator out_begin()                    { return m_OutArcs.begin(); }
126        out_arc_iterator out_end()                        { return m_OutArcs.end(); }
127        const_out_arc_iterator out_begin() const        { return m_OutArcs.begin(); }
128        const_out_arc_iterator out_end() const            { return m_OutArcs.end(); }
129
130        nodetype & operator * ()                        { return m_Elem; }
131        nodetype * operator -> ()                        { return &m_Elem; }
132        const nodetype & operator * () const            { return m_Elem; }
133        const nodetype * operator -> () const            { return &m_Elem; }
134
135        nodetype & operator = (const nodetype & Elem)    { return (m_Elem = Elem); }
136
137        node() : m_Marker(false) { }
138    protected:
139        friend class graph_array<nodetype, arctype>;
140        friend class std::vector<node>;
141
142
143        std::list<arc>    m_OutArcs;
144        nodetype        m_Elem;
145        bool            m_Marker;
146    };
147
148
149    // Construction/Destruction
150    graph_array();
151    explicit graph_array(const size_t NbNodes);
152
153    // Node related member functions
154    void clear();
155    bool empty() const;
156    void setsize(const size_t NbNodes);
157    size_t size() const;
158
159    node & operator [] (const nodeid & i);
160    const node & operator [] (const nodeid & i) const;
161
162    node_iterator begin();
163    node_iterator end();
164    const_node_iterator begin() const;
165    const_node_iterator end() const;
166
167    node_reverse_iterator rbegin();
168    node_reverse_iterator rend();
169    const_node_reverse_iterator rbegin() const;
170    const_node_reverse_iterator rend() const;
171
172    // Arc related member functions
173    size_t number_of_arcs() const;
174
175    void erase_arcs();
176    void erase_arcs(const node_iterator & Initial);
177    out_arc_iterator erase_arc(const out_arc_iterator & Pos);
178
179    out_arc_iterator insert_arc(const nodeid & Initial, const nodeid & Terminal);
180    out_arc_iterator insert_arc(const nodeid & Initial, const nodeid & Terminal, const arctype & Elem);
181    out_arc_iterator insert_arc(const node_iterator & Initial, const node_iterator & Terminal);
182    out_arc_iterator insert_arc(const node_iterator & Initial, const node_iterator & Terminal, const arctype & Elem);
183
184    // Another interface for insert_arc
185    out_arc_iterator insert(const nodeid & Initial, const nodeid & Terminal)                                        { return insert_arc(Initial, Terminal); }
186    out_arc_iterator insert(const nodeid & Initial, const nodeid & Terminal, const arctype & Elem)                    { return insert_arc(Initial, Terminal, Elem); }
187    out_arc_iterator insert(const node_iterator & Initial, const node_iterator & Terminal)                            { return insert_arc(Initial, Terminal); }
188    out_arc_iterator insert(const node_iterator & Initial, const node_iterator & Terminal, const arctype & Elem)    { return insert_arc(Initial, Terminal, Elem); }
189
190    // Optimized (overloaded) functions
191    void swap(_mytype & Right);
192// removed since it was causing g++ 2.95.3 to produce many compile errors
193// presumably due to implicit import of the std::swap implementation.
194// Robert Osfield, Jan 2002.
195//    friend void swap(_mytype & Left, _mytype & Right)    { Left.swap(Right); }
196
197protected:
198
199    graph_array& operator = (const graph_array&) { return *this; }
200
201    size_t                m_NbArcs;
202    std::vector<node>    m_Nodes;
203};
204
205
206
207// Additional "low level", graph related, functions
208template <class nodetype, class arctype>
209void unmark_nodes(graph_array<nodetype, arctype> & G);
210
211template <class nodetype, class arctype>
212void unmark_arcs_from_node(typename graph_array<nodetype, arctype>::node & N);
213
214template <class nodetype, class arctype>
215void unmark_arcs(graph_array<nodetype, arctype> & G);
216
217
218
219
220//////////////////////////////////////////////////////////////////////////
221// graph_array Inline functions
222//////////////////////////////////////////////////////////////////////////
223
224template <class nodetype, class arctype>
225inline graph_array<nodetype, arctype>::graph_array() : m_NbArcs(0) { }
226
227
228template <class nodetype, class arctype>
229inline graph_array<nodetype, arctype>::graph_array(const size_t NbNodes) : m_NbArcs(0), m_Nodes(NbNodes) { }
230
231
232template <class nodetype, class arctype>
233inline void graph_array<nodetype, arctype>::clear() {
234    m_NbArcs = 0;
235    m_Nodes.clear();
236}
237
238
239
240template <class nodetype, class arctype>
241inline bool graph_array<nodetype, arctype>::empty() const {
242    return m_Nodes.empty();
243}
244
245
246template <class nodetype, class arctype>
247inline size_t graph_array<nodetype, arctype>::size() const {
248    return m_Nodes.size();
249}
250
251
252template <class nodetype, class arctype>
253inline void graph_array<nodetype, arctype>::setsize(const size_t NbNodes) {
254    clear();
255    m_Nodes.resize(NbNodes);
256}
257
258
259template <class nodetype, class arctype>
260inline typename graph_array<nodetype, arctype>::node & graph_array<nodetype, arctype>::operator [] (const nodeid & i) {
261    // Debug check
262    // assert(i < size());
263    if (i >= size()) throw "graph_array<nodetype, arctype>::operator [] out of range";
264
265    return m_Nodes[i];
266}
267
268
269template <class nodetype, class arctype>
270inline const typename graph_array<nodetype, arctype>::node & graph_array<nodetype, arctype>::operator [] (const nodeid & i) const {
271    // Debug check
272    // assert(i < size());
273    if (i >= size()) throw "graph_array<nodetype, arctype>::operator [] out of range";
274
275    return m_Nodes[i];
276}
277
278
279template <class nodetype, class arctype>
280inline typename graph_array<nodetype, arctype>::node_iterator graph_array<nodetype, arctype>::begin() {
281    return m_Nodes.begin();
282}
283
284
285template <class nodetype, class arctype>
286inline typename graph_array<nodetype, arctype>::node_iterator graph_array<nodetype, arctype>::end() {
287    return m_Nodes.end();
288}
289
290
291template <class nodetype, class arctype>
292inline typename graph_array<nodetype, arctype>::const_node_iterator graph_array<nodetype, arctype>::begin() const {
293    return m_Nodes.begin();
294}
295
296
297template <class nodetype, class arctype>
298inline typename graph_array<nodetype, arctype>::const_node_iterator graph_array<nodetype, arctype>::end() const {
299    return m_Nodes.end();
300}
301
302
303template <class nodetype, class arctype>
304inline typename graph_array<nodetype, arctype>::node_reverse_iterator graph_array<nodetype, arctype>::rbegin() {
305    return m_Nodes.rbegin();
306}
307
308
309template <class nodetype, class arctype>
310inline typename graph_array<nodetype, arctype>::node_reverse_iterator graph_array<nodetype, arctype>::rend() {
311    return m_Nodes.rend();
312}
313
314
315template <class nodetype, class arctype>
316inline typename graph_array<nodetype, arctype>::const_node_reverse_iterator graph_array<nodetype, arctype>::rbegin() const {
317    return m_Nodes.rbegin();
318}
319
320
321template <class nodetype, class arctype>
322inline typename graph_array<nodetype, arctype>::const_node_reverse_iterator graph_array<nodetype, arctype>::rend() const {
323    return m_Nodes.rend();
324}
325
326
327template <class nodetype, class arctype>
328inline size_t graph_array<nodetype, arctype>::number_of_arcs() const {
329    return m_NbArcs;
330}
331
332
333template <class nodetype, class arctype>
334inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::insert_arc(const nodeid & Initial, const nodeid & Terminal) {
335    return (insert(begin() + Initial, begin() + Terminal));
336}
337
338
339template <class nodetype, class arctype>
340inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::insert_arc(const nodeid & Initial, const nodeid & Terminal, const arctype & Elem) {
341    return (insert(begin() + Initial, begin() + Terminal, Elem));
342}
343
344
345template <class nodetype, class arctype>
346inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::insert_arc(const node_iterator & Initial, const node_iterator & Terminal) {
347    ++m_NbArcs;
348    Initial->m_OutArcs.push_back(arc(Initial, Terminal));
349    return (--(Initial->m_OutArcs.end()));
350}
351
352
353template <class nodetype, class arctype>
354inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::insert_arc(const node_iterator & Initial, const node_iterator & Terminal, const arctype & Elem) {
355    ++m_NbArcs;
356    Initial->m_OutArcs.push_back(arc(Initial, Terminal, Elem));
357    return (--(Initial->m_OutArcs.end()));
358}
359
360
361template <class nodetype, class arctype>
362inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::erase_arc(const out_arc_iterator & Pos) {
363    --m_NbArcs;
364    return (Pos->initial()->m_OutArcs.erase(Pos));
365}
366
367
368template <class nodetype, class arctype>
369inline void graph_array<nodetype, arctype>::erase_arcs(const node_iterator & Initial) {
370    m_NbArcs -= (Initial->m_OutArcs.size());
371    Initial->m_OutArcs.clear();
372}
373
374
375template <class nodetype, class arctype>
376inline void graph_array<nodetype, arctype>::erase_arcs() {
377    m_NbArcs = 0;
378    for (nodeid i = 0; i < this->Size(); ++i)
379        m_Nodes[i].m_OutArcs.clear();
380}
381
382
383template <class nodetype, class arctype>
384inline void graph_array<nodetype, arctype>::swap(_mytype & Right) {
385    std::swap(m_NbArcs, Right.m_NbArcs);
386    std::swap(m_Nodes, Right.m_Nodes);
387}
388
389
390
391//////////////////////////////////////////////////////////////////////////
392// additional functions
393//////////////////////////////////////////////////////////////////////////
394
395template <class nodetype, class arctype>
396void unmark_nodes(graph_array<nodetype, arctype> & G)
397{
398    typedef typename graph_array<nodetype, arctype>::node_iterator node_it;
399
400    for (node_it NodeIt = G.begin(); NodeIt != G.end(); ++NodeIt)
401        NodeIt->unmark();
402}
403
404
405template <class nodetype, class arctype>
406void unmark_arcs_from_node(typename graph_array<nodetype, arctype>::node & N)
407{
408    typedef typename graph_array<nodetype, arctype>::out_arc_iterator arc_it;
409
410    for (arc_it ArcIt = N.out_begin(); ArcIt != N.out_end(); ++ArcIt)
411        ArcIt->unmark();
412}
413
414
415template <class nodetype, class arctype>
416void unmark_arcs(graph_array<nodetype, arctype> & G)
417{
418    typedef typename graph_array<nodetype, arctype>::node_iterator node_it;
419
420    for (node_it NodeIt = G.begin(); NodeIt != G.end(); ++NodeIt)
421        unmark_arcs_from_node(* NodeIt);
422}
423
424
425
426
427} // namespace common_structures
428
429#endif
Note: See TracBrowser for help on using the browser.