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

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

Warnings fixes for VS.

  • 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 & mark()                                    { m_Marker = true; return (* this); }
83        arc & unmark()                                    { m_Marker = false; return (* this); }
84        bool marked() const                                { return m_Marker; }
85
86        node_iterator initial() const                    { return m_Initial; }
87        node_iterator terminal() const                    { return m_Terminal; }
88
89        arctype & operator * ()                            { return m_Elem; }
90        const arctype & operator * () const                { return m_Elem; }
91
92    protected:
93        friend class graph_array<nodetype, arctype>;
94
95        arc(const node_iterator & Initial, const node_iterator & Terminal)
96            : m_Initial(Initial), m_Terminal(Terminal), m_Marker(false) { }
97
98        arc(const node_iterator & Initial, const node_iterator & Terminal, const arctype & Elem)
99            : m_Initial(Initial), m_Terminal(Terminal), m_Elem(Elem), m_Marker(false) { }
100   
101        node_iterator    m_Initial;
102        node_iterator    m_Terminal;
103        arctype            m_Elem;
104        bool            m_Marker;
105    };
106
107
108    // New types
109    typedef typename std::list<arc>::iterator            out_arc_iterator;
110    typedef typename std::list<arc>::const_iterator        const_out_arc_iterator;
111
112
113    // graph_array::node class
114    class node
115    {
116    public:
117        node & mark()                                    { m_Marker = true; return (* this); }
118        node & unmark()                                    { m_Marker = false; return (* this); }
119        bool marked() const                                { return m_Marker; }
120
121        bool out_empty() const                            { return m_OutArcs.empty(); }
122        size_t number_of_out_arcs() const                { return m_OutArcs.size(); }
123
124        out_arc_iterator out_begin()                    { return m_OutArcs.begin(); }
125        out_arc_iterator out_end()                        { return m_OutArcs.end(); }
126        const_out_arc_iterator out_begin() const        { return m_OutArcs.begin(); }
127        const_out_arc_iterator out_end() const            { return m_OutArcs.end(); }
128
129        nodetype & operator * ()                        { return m_Elem; }
130        nodetype * operator -> ()                        { return &m_Elem; }
131        const nodetype & operator * () const            { return m_Elem; }
132        const nodetype * operator -> () const            { return &m_Elem; }
133
134        nodetype & operator = (const nodetype & Elem)    { return (m_Elem = Elem); }
135
136        node() : m_Marker(false) { }
137    protected:
138        friend class graph_array<nodetype, arctype>;
139        friend class std::vector<node>;
140
141
142        std::list<arc>    m_OutArcs;
143        nodetype        m_Elem;
144        bool            m_Marker;
145    };
146
147
148    // Construction/Destruction
149    graph_array();
150    explicit graph_array(const size_t NbNodes);
151
152    // Node related member functions
153    void clear();
154    bool empty() const;
155    void setsize(const size_t NbNodes);
156    size_t size() const;
157
158    node & operator [] (const nodeid & i);
159    const node & operator [] (const nodeid & i) const;
160
161    node_iterator begin();
162    node_iterator end();
163    const_node_iterator begin() const;
164    const_node_iterator end() const;
165
166    node_reverse_iterator rbegin();
167    node_reverse_iterator rend();
168    const_node_reverse_iterator rbegin() const;
169    const_node_reverse_iterator rend() const;
170
171    // Arc related member functions
172    size_t number_of_arcs() const;
173
174    void erase_arcs();
175    void erase_arcs(const node_iterator & Initial);
176    out_arc_iterator erase_arc(const out_arc_iterator & Pos);
177
178    out_arc_iterator insert_arc(const nodeid & Initial, const nodeid & Terminal);
179    out_arc_iterator insert_arc(const nodeid & Initial, const nodeid & Terminal, const arctype & Elem);
180    out_arc_iterator insert_arc(const node_iterator & Initial, const node_iterator & Terminal);
181    out_arc_iterator insert_arc(const node_iterator & Initial, const node_iterator & Terminal, const arctype & Elem);
182
183    // Another interface for insert_arc
184    out_arc_iterator insert(const nodeid & Initial, const nodeid & Terminal)                                        { return insert_arc(Initial, Terminal); }
185    out_arc_iterator insert(const nodeid & Initial, const nodeid & Terminal, const arctype & Elem)                    { return insert_arc(Initial, Terminal, Elem); }
186    out_arc_iterator insert(const node_iterator & Initial, const node_iterator & Terminal)                            { return insert_arc(Initial, Terminal); }
187    out_arc_iterator insert(const node_iterator & Initial, const node_iterator & Terminal, const arctype & Elem)    { return insert_arc(Initial, Terminal, Elem); }
188
189    // Optimized (overloaded) functions
190    void swap(_mytype & Right);
191// removed since it was causing g++ 2.95.3 to produce many compile errors
192// presumably due to implicit import of the std::swap implementation.
193// Robert Osfield, Jan 2002.
194//    friend void swap(_mytype & Left, _mytype & Right)    { Left.swap(Right); }
195
196protected:
197
198    graph_array& operator = (const graph_array&) { return *this; }
199
200    size_t                m_NbArcs;
201    std::vector<node>    m_Nodes;
202};
203
204
205
206// Additional "low level", graph related, functions
207template <class nodetype, class arctype>
208void unmark_nodes(graph_array<nodetype, arctype> & G);
209
210template <class nodetype, class arctype>
211void unmark_arcs_from_node(typename graph_array<nodetype, arctype>::node & N);
212
213template <class nodetype, class arctype>
214void unmark_arcs(graph_array<nodetype, arctype> & G);
215
216
217
218
219//////////////////////////////////////////////////////////////////////////
220// graph_array Inline functions
221//////////////////////////////////////////////////////////////////////////
222
223template <class nodetype, class arctype>
224inline graph_array<nodetype, arctype>::graph_array() : m_NbArcs(0) { }
225
226
227template <class nodetype, class arctype>
228inline graph_array<nodetype, arctype>::graph_array(const size_t NbNodes) : m_NbArcs(0), m_Nodes(NbNodes) { }
229
230
231template <class nodetype, class arctype>
232inline void graph_array<nodetype, arctype>::clear() {
233    m_NbArcs = 0;
234    m_Nodes.clear();
235}
236
237
238
239template <class nodetype, class arctype>
240inline bool graph_array<nodetype, arctype>::empty() const {
241    return m_Nodes.empty();
242}
243
244
245template <class nodetype, class arctype>
246inline size_t graph_array<nodetype, arctype>::size() const {
247    return m_Nodes.size();
248}
249
250
251template <class nodetype, class arctype>
252inline void graph_array<nodetype, arctype>::setsize(const size_t NbNodes) {
253    clear();
254    m_Nodes.resize(NbNodes);
255}
256
257
258template <class nodetype, class arctype>
259inline typename graph_array<nodetype, arctype>::node & graph_array<nodetype, arctype>::operator [] (const nodeid & i) {
260    // Debug check
261    // assert(i < size());
262    if (i >= size()) throw "graph_array<nodetype, arctype>::operator [] out of range";
263
264    return m_Nodes[i];
265}
266
267
268template <class nodetype, class arctype>
269inline const typename graph_array<nodetype, arctype>::node & graph_array<nodetype, arctype>::operator [] (const nodeid & i) const {
270    // Debug check
271    // assert(i < size());
272    if (i >= size()) throw "graph_array<nodetype, arctype>::operator [] out of range";
273
274    return m_Nodes[i];
275}
276
277
278template <class nodetype, class arctype>
279inline typename graph_array<nodetype, arctype>::node_iterator graph_array<nodetype, arctype>::begin() {
280    return m_Nodes.begin();
281}
282
283
284template <class nodetype, class arctype>
285inline typename graph_array<nodetype, arctype>::node_iterator graph_array<nodetype, arctype>::end() {
286    return m_Nodes.end();
287}
288
289
290template <class nodetype, class arctype>
291inline typename graph_array<nodetype, arctype>::const_node_iterator graph_array<nodetype, arctype>::begin() const {
292    return m_Nodes.begin();
293}
294
295
296template <class nodetype, class arctype>
297inline typename graph_array<nodetype, arctype>::const_node_iterator graph_array<nodetype, arctype>::end() const {
298    return m_Nodes.end();
299}
300
301
302template <class nodetype, class arctype>
303inline typename graph_array<nodetype, arctype>::node_reverse_iterator graph_array<nodetype, arctype>::rbegin() {
304    return m_Nodes.rbegin();
305}
306
307
308template <class nodetype, class arctype>
309inline typename graph_array<nodetype, arctype>::node_reverse_iterator graph_array<nodetype, arctype>::rend() {
310    return m_Nodes.rend();
311}
312
313
314template <class nodetype, class arctype>
315inline typename graph_array<nodetype, arctype>::const_node_reverse_iterator graph_array<nodetype, arctype>::rbegin() const {
316    return m_Nodes.rbegin();
317}
318
319
320template <class nodetype, class arctype>
321inline typename graph_array<nodetype, arctype>::const_node_reverse_iterator graph_array<nodetype, arctype>::rend() const {
322    return m_Nodes.rend();
323}
324
325
326template <class nodetype, class arctype>
327inline size_t graph_array<nodetype, arctype>::number_of_arcs() const {
328    return m_NbArcs;
329}
330
331
332template <class nodetype, class arctype>
333inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::insert_arc(const nodeid & Initial, const nodeid & Terminal) {
334    return (insert(begin() + Initial, begin() + Terminal));
335}
336
337
338template <class nodetype, class arctype>
339inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::insert_arc(const nodeid & Initial, const nodeid & Terminal, const arctype & Elem) {
340    return (insert(begin() + Initial, begin() + Terminal, Elem));
341}
342
343
344template <class nodetype, class arctype>
345inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::insert_arc(const node_iterator & Initial, const node_iterator & Terminal) {
346    ++m_NbArcs;
347    Initial->m_OutArcs.push_back(arc(Initial, Terminal));
348    return (--(Initial->m_OutArcs.end()));
349}
350
351
352template <class nodetype, class arctype>
353inline 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) {
354    ++m_NbArcs;
355    Initial->m_OutArcs.push_back(arc(Initial, Terminal, Elem));
356    return (--(Initial->m_OutArcs.end()));
357}
358
359
360template <class nodetype, class arctype>
361inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::erase_arc(const out_arc_iterator & Pos) {
362    --m_NbArcs;
363    return (Pos->initial()->m_OutArcs.erase(Pos));
364}
365
366
367template <class nodetype, class arctype>
368inline void graph_array<nodetype, arctype>::erase_arcs(const node_iterator & Initial) {
369    m_NbArcs -= (Initial->m_OutArcs.size());
370    Initial->m_OutArcs.clear();
371}
372
373
374template <class nodetype, class arctype>
375inline void graph_array<nodetype, arctype>::erase_arcs() {
376    m_NbArcs = 0;
377    for (nodeid i = 0; i < this->Size(); ++i)
378        m_Nodes[i].m_OutArcs.clear();
379}
380
381
382template <class nodetype, class arctype>
383inline void graph_array<nodetype, arctype>::swap(_mytype & Right) {
384    std::swap(m_NbArcs, Right.m_NbArcs);
385    std::swap(m_Nodes, Right.m_Nodes);
386}
387
388
389
390//////////////////////////////////////////////////////////////////////////
391// additional functions
392//////////////////////////////////////////////////////////////////////////
393
394template <class nodetype, class arctype>
395void unmark_nodes(graph_array<nodetype, arctype> & G)
396{
397    typedef typename graph_array<nodetype, arctype>::node_iterator node_it;
398
399    for (node_it NodeIt = G.begin(); NodeIt != G.end(); ++NodeIt)
400        NodeIt->unmark();
401}
402
403
404template <class nodetype, class arctype>
405void unmark_arcs_from_node(typename graph_array<nodetype, arctype>::node & N)
406{
407    typedef typename graph_array<nodetype, arctype>::out_arc_iterator arc_it;
408
409    for (arc_it ArcIt = N.out_begin(); ArcIt != N.out_end(); ++ArcIt)
410        ArcIt->unmark();
411}
412
413
414template <class nodetype, class arctype>
415void unmark_arcs(graph_array<nodetype, arctype> & G)
416{
417    typedef typename graph_array<nodetype, arctype>::node_iterator node_it;
418
419    for (node_it NodeIt = G.begin(); NodeIt != G.end(); ++NodeIt)
420        unmark_arcs_from_node(* NodeIt);
421}
422
423
424
425
426} // namespace common_structures
427
428#endif
Note: See TracBrowser for help on using the browser.