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

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

Removed throw.

  • 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
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;
[1505]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;
[1474]74
75    typedef graph_array<nodetype, arctype> _mytype;
76   
77
78    // graph_array::arc class
79    class arc
80    {
81    public:
[9655]82        arc() {}
[1474]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
[1505]110    typedef typename std::list<arc>::iterator            out_arc_iterator;
111    typedef typename std::list<arc>::const_iterator        const_out_arc_iterator;
[1474]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
[4006]137        node() : m_Marker(false) { }
[1474]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:
[9630]198
199    graph_array& operator = (const graph_array&) { return *this; }
200
[1474]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>
[1505]212void unmark_arcs_from_node(typename graph_array<nodetype, arctype>::node & N);
[1474]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>
[1705]260inline typename graph_array<nodetype, arctype>::node & graph_array<nodetype, arctype>::operator [] (const nodeid & i) {
[1474]261    return m_Nodes[i];
262}
263
264
265template <class nodetype, class arctype>
[1705]266inline const typename graph_array<nodetype, arctype>::node & graph_array<nodetype, arctype>::operator [] (const nodeid & i) const {
[1474]267    return m_Nodes[i];
268}
269
270
271template <class nodetype, class arctype>
[1705]272inline typename graph_array<nodetype, arctype>::node_iterator graph_array<nodetype, arctype>::begin() {
[1474]273    return m_Nodes.begin();
274}
275
276
277template <class nodetype, class arctype>
[1705]278inline typename graph_array<nodetype, arctype>::node_iterator graph_array<nodetype, arctype>::end() {
[1474]279    return m_Nodes.end();
280}
281
282
283template <class nodetype, class arctype>
[1705]284inline typename graph_array<nodetype, arctype>::const_node_iterator graph_array<nodetype, arctype>::begin() const {
[1474]285    return m_Nodes.begin();
286}
287
288
289template <class nodetype, class arctype>
[1705]290inline typename graph_array<nodetype, arctype>::const_node_iterator graph_array<nodetype, arctype>::end() const {
[1474]291    return m_Nodes.end();
292}
293
294
295template <class nodetype, class arctype>
[1705]296inline typename graph_array<nodetype, arctype>::node_reverse_iterator graph_array<nodetype, arctype>::rbegin() {
[1474]297    return m_Nodes.rbegin();
298}
299
300
301template <class nodetype, class arctype>
[1705]302inline typename graph_array<nodetype, arctype>::node_reverse_iterator graph_array<nodetype, arctype>::rend() {
[1474]303    return m_Nodes.rend();
304}
305
306
307template <class nodetype, class arctype>
[1705]308inline typename graph_array<nodetype, arctype>::const_node_reverse_iterator graph_array<nodetype, arctype>::rbegin() const {
[1474]309    return m_Nodes.rbegin();
310}
311
312
313template <class nodetype, class arctype>
[1705]314inline typename graph_array<nodetype, arctype>::const_node_reverse_iterator graph_array<nodetype, arctype>::rend() const {
[1474]315    return m_Nodes.rend();
316}
317
318
319template <class nodetype, class arctype>
320inline size_t graph_array<nodetype, arctype>::number_of_arcs() const {
321    return m_NbArcs;
322}
323
324
325template <class nodetype, class arctype>
[1705]326inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::insert_arc(const nodeid & Initial, const nodeid & Terminal) {
[1474]327    return (insert(begin() + Initial, begin() + Terminal));
328}
329
330
331template <class nodetype, class arctype>
[1705]332inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::insert_arc(const nodeid & Initial, const nodeid & Terminal, const arctype & Elem) {
[1474]333    return (insert(begin() + Initial, begin() + Terminal, Elem));
334}
335
336
337template <class nodetype, class arctype>
[1705]338inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::insert_arc(const node_iterator & Initial, const node_iterator & Terminal) {
[1474]339    ++m_NbArcs;
340    Initial->m_OutArcs.push_back(arc(Initial, Terminal));
341    return (--(Initial->m_OutArcs.end()));
342}
343
344
345template <class nodetype, class arctype>
[1705]346inline 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]347    ++m_NbArcs;
348    Initial->m_OutArcs.push_back(arc(Initial, Terminal, Elem));
349    return (--(Initial->m_OutArcs.end()));
350}
351
352
353template <class nodetype, class arctype>
[1705]354inline typename graph_array<nodetype, arctype>::out_arc_iterator graph_array<nodetype, arctype>::erase_arc(const out_arc_iterator & Pos) {
[1474]355    --m_NbArcs;
356    return (Pos->initial()->m_OutArcs.erase(Pos));
357}
358
359
360template <class nodetype, class arctype>
361inline void graph_array<nodetype, arctype>::erase_arcs(const node_iterator & Initial) {
362    m_NbArcs -= (Initial->m_OutArcs.size());
363    Initial->m_OutArcs.clear();
364}
365
366
367template <class nodetype, class arctype>
368inline void graph_array<nodetype, arctype>::erase_arcs() {
369    m_NbArcs = 0;
[3208]370    for (nodeid i = 0; i < this->Size(); ++i)
[1474]371        m_Nodes[i].m_OutArcs.clear();
372}
373
374
375template <class nodetype, class arctype>
376inline void graph_array<nodetype, arctype>::swap(_mytype & Right) {
377    std::swap(m_NbArcs, Right.m_NbArcs);
378    std::swap(m_Nodes, Right.m_Nodes);
379}
380
381
382
383//////////////////////////////////////////////////////////////////////////
384// additional functions
385//////////////////////////////////////////////////////////////////////////
386
387template <class nodetype, class arctype>
388void unmark_nodes(graph_array<nodetype, arctype> & G)
389{
[2085]390    typedef typename graph_array<nodetype, arctype>::node_iterator node_it;
[1474]391
392    for (node_it NodeIt = G.begin(); NodeIt != G.end(); ++NodeIt)
393        NodeIt->unmark();
394}
395
396
397template <class nodetype, class arctype>
[1505]398void unmark_arcs_from_node(typename graph_array<nodetype, arctype>::node & N)
[1474]399{
[2085]400    typedef typename graph_array<nodetype, arctype>::out_arc_iterator arc_it;
[1474]401
402    for (arc_it ArcIt = N.out_begin(); ArcIt != N.out_end(); ++ArcIt)
403        ArcIt->unmark();
404}
405
406
407template <class nodetype, class arctype>
408void unmark_arcs(graph_array<nodetype, arctype> & G)
409{
[2085]410    typedef typename graph_array<nodetype, arctype>::node_iterator node_it;
[1474]411
412    for (node_it NodeIt = G.begin(); NodeIt != G.end(); ++NodeIt)
413        unmark_arcs_from_node(* NodeIt);
414}
415
416
417
418
[1562]419} // namespace common_structures
[1474]420
421#endif
Note: See TracBrowser for help on using the browser.