← Back to branch summary

~ubuntu-branches/debian/experimental/openscenegraph/experimental

« back to all changes in this revision

Viewing changes to OpenSceneGraph/src/osgUtil/TriStrip_graph_array.h

  • Committer: Bazaar Package Importer
  • Author(s): Alberto Luaces
  • Date: 2011-01-29 11:36:29 UTC
  • mfrom: (1.1.10 upstream)
  • Revision ID: james.westby@ubuntu.com-20110129113629-qisrm2kdqlurc7t3
Tags: 2.9.11-1
http://bugs.debian.org/592420
* Removed bug-555869-ftbfs_with_binutils_gold.dpatch since upstream has
  already taken care of the issue.
* Removed bug-528229.dpatch since the pkgconfig files are now also split
  in upstream.
* Removed explicit dependency on GLU.
* Upstream no longer includes osgIntrospection (Closes: #592420).
* Disabled zip plugin as its implementation stores an embedded copy of
  zlib.
* Enabled Qt support. Thanks James Goppert.
* Enabled SVG and PDF plugins. Thanks James Goppert.

Show diffs side-by-side

added added

removed removed

Lines of Context:
OpenSceneGraph/src/osgUtil/TriStrip_graph_array.h
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
54
 
namespace common_structures {
55
 
 
56
 
 
57
 
 
58
 
 
59
 
// graph_array main class
60
 
template <class nodetype, class arctype>
61
 
class graph_array 
62
 
{
63
 
public:
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
 
 
197
 
protected:
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
208
 
template <class nodetype, class arctype>
209
 
void unmark_nodes(graph_array<nodetype, arctype> & G);
210
 
 
211
 
template <class nodetype, class arctype>
212
 
void unmark_arcs_from_node(typename graph_array<nodetype, arctype>::node & N);
213
 
 
214
 
template <class nodetype, class arctype>
215
 
void unmark_arcs(graph_array<nodetype, arctype> & G);
216
 
 
217
 
 
218
 
 
219
 
 
220
 
//////////////////////////////////////////////////////////////////////////
221
 
// graph_array Inline functions
222
 
//////////////////////////////////////////////////////////////////////////
223
 
 
224
 
template <class nodetype, class arctype>
225
 
inline graph_array<nodetype, arctype>::graph_array() : m_NbArcs(0) { }
226
 
 
227
 
 
228
 
template <class nodetype, class arctype>
229
 
inline graph_array<nodetype, arctype>::graph_array(const size_t NbNodes) : m_NbArcs(0), m_Nodes(NbNodes) { }
230
 
 
231
 
 
232
 
template <class nodetype, class arctype>
233
 
inline void graph_array<nodetype, arctype>::clear() {
234
 
    m_NbArcs = 0;
235
 
    m_Nodes.clear();
236
 
}
237
 
 
238
 
 
239
 
 
240
 
template <class nodetype, class arctype>
241
 
inline bool graph_array<nodetype, arctype>::empty() const {
242
 
    return m_Nodes.empty();
243
 
}
244
 
 
245
 
 
246
 
template <class nodetype, class arctype>
247
 
inline size_t graph_array<nodetype, arctype>::size() const {
248
 
    return m_Nodes.size();
249
 
}
250
 
 
251
 
 
252
 
template <class nodetype, class arctype>
253
 
inline void graph_array<nodetype, arctype>::setsize(const size_t NbNodes) {
254
 
    clear();
255
 
    m_Nodes.resize(NbNodes);
256
 
}
257
 
 
258
 
 
259
 
template <class nodetype, class arctype>
260
 
inline 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
 
 
269
 
template <class nodetype, class arctype>
270
 
inline 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
 
 
279
 
template <class nodetype, class arctype>
280
 
inline typename graph_array<nodetype, arctype>::node_iterator graph_array<nodetype, arctype>::begin() {
281
 
    return m_Nodes.begin();
282
 
}
283
 
 
284
 
 
285
 
template <class nodetype, class arctype>
286
 
inline typename graph_array<nodetype, arctype>::node_iterator graph_array<nodetype, arctype>::end() {
287
 
    return m_Nodes.end();
288
 
}
289
 
 
290
 
 
291
 
template <class nodetype, class arctype>
292
 
inline typename graph_array<nodetype, arctype>::const_node_iterator graph_array<nodetype, arctype>::begin() const {
293
 
    return m_Nodes.begin();
294
 
}
295
 
 
296
 
 
297
 
template <class nodetype, class arctype>
298
 
inline typename graph_array<nodetype, arctype>::const_node_iterator graph_array<nodetype, arctype>::end() const {
299
 
    return m_Nodes.end();
300
 
}
301
 
 
302
 
 
303
 
template <class nodetype, class arctype>
304
 
inline typename graph_array<nodetype, arctype>::node_reverse_iterator graph_array<nodetype, arctype>::rbegin() {
305
 
    return m_Nodes.rbegin();
306
 
}
307
 
 
308
 
 
309
 
template <class nodetype, class arctype>
310
 
inline typename graph_array<nodetype, arctype>::node_reverse_iterator graph_array<nodetype, arctype>::rend() {
311
 
    return m_Nodes.rend();
312
 
}
313
 
 
314
 
 
315
 
template <class nodetype, class arctype>
316
 
inline typename graph_array<nodetype, arctype>::const_node_reverse_iterator graph_array<nodetype, arctype>::rbegin() const {
317
 
    return m_Nodes.rbegin();
318
 
}
319
 
 
320
 
 
321
 
template <class nodetype, class arctype>
322
 
inline typename graph_array<nodetype, arctype>::const_node_reverse_iterator graph_array<nodetype, arctype>::rend() const {
323
 
    return m_Nodes.rend();
324
 
}
325
 
 
326
 
 
327
 
template <class nodetype, class arctype>
328
 
inline size_t graph_array<nodetype, arctype>::number_of_arcs() const {
329
 
    return m_NbArcs;
330
 
}
331
 
 
332
 
 
333
 
template <class nodetype, class arctype>
334
 
inline 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
 
 
339
 
template <class nodetype, class arctype>
340
 
inline 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
 
 
345
 
template <class nodetype, class arctype>
346
 
inline 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
 
 
353
 
template <class nodetype, class arctype>
354
 
inline 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
 
 
361
 
template <class nodetype, class arctype>
362
 
inline 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
 
 
368
 
template <class nodetype, class arctype>
369
 
inline 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
 
 
375
 
template <class nodetype, class arctype>
376
 
inline 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
 
 
383
 
template <class nodetype, class arctype>
384
 
inline 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
 
 
395
 
template <class nodetype, class arctype>
396
 
void 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
 
 
405
 
template <class nodetype, class arctype>
406
 
void 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
 
 
415
 
template <class nodetype, class arctype>
416
 
void 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