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

Revision 10764, 14.6 kB (checked in by robert, 5 years ago)

<iterator>, <stdlib.h> and <ctype.h> includes required for QNX compiler

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