Branch data Line data Source code
1 : : #ifndef CUBIT_LOOPS_HPP
2 : : #define CUBIT_LOOPS_HPP
3 : :
4 : : #include "CubitDefines.h"
5 : : #include <vector>
6 : : #include <set>
7 : : #include <map>
8 : :
9 : : template <class C, class V>
10 : : class CubitLoops
11 : : {
12 : : public:
13 : : struct CoEdge
14 : : {
15 : : C* curve;
16 : : V* start;
17 : : V* end;
18 : : CubitSense sense;
19 : : };
20 : :
21 : : static bool make_loops(std::vector<CoEdge>& coedges,
22 : : std::vector<std::vector<CoEdge*> >& loops);
23 : :
24 : : private:
25 : :
26 : : static bool recursive_make_loop(V* start_vertex, CoEdge* coedge,
27 : : std::set<CoEdge* >& used_coedges,
28 : : std::multimap<V*, CoEdge*>& start_coedge_map,
29 : : std::vector<CoEdge*>& loop);
30 : : };
31 : :
32 : : template <class C, class V> inline
33 : 330 : bool CubitLoops<C, V>::recursive_make_loop(V* start_vertex, CoEdge* coedge,
34 : : std::set<CoEdge* >& used_coedges,
35 : : std::multimap<V*, CoEdge*>& start_coedge_map,
36 : : std::vector<CoEdge*>& loop)
37 : : {
38 : : V* curr_vertex;
39 [ + + ]: 330 : if (coedge->sense == CUBIT_FORWARD)
40 : 143 : curr_vertex = coedge->end;
41 : : else
42 : 187 : curr_vertex = coedge->start;
43 [ + - ]: 330 : loop.push_back(coedge);
44 [ + - ]: 330 : used_coedges.insert(coedge);
45 : :
46 [ + + ]: 1122 : while (curr_vertex != start_vertex)
47 : : {
48 [ + - ]: 792 : typename std::multimap<V*, CoEdge*>::iterator iter;
49 [ + - ]: 792 : typename std::multimap<V*, CoEdge*>::iterator last;
50 : :
51 [ + - ]: 792 : iter = start_coedge_map.lower_bound(curr_vertex);
52 [ + - ]: 792 : last = start_coedge_map.upper_bound(curr_vertex);
53 : :
54 [ + - ]: 792 : std::vector<CoEdge*> possible_coedges;
55 [ + - ][ + - ]: 1584 : for (/*preinitialized*/; iter != last; iter++)
[ + + ]
56 : : {
57 [ + - ][ + - ]: 792 : if (used_coedges.find(iter->second) == used_coedges.end())
[ + - ][ + - ]
[ + - ]
58 [ + - ][ + - ]: 792 : possible_coedges.push_back(iter->second);
59 : : }
60 : :
61 [ + - ][ - + ]: 792 : if (possible_coedges.size() == 0)
62 : 0 : return false;
63 [ + - ][ + - ]: 792 : else if (possible_coedges.size() == 1)
64 : : {
65 [ + - ]: 792 : coedge = possible_coedges[0];
66 [ + - ]: 792 : loop.push_back(coedge);
67 [ + - ]: 792 : used_coedges.insert(coedge);
68 [ + + ]: 792 : if (coedge->sense == CUBIT_FORWARD)
69 : 440 : curr_vertex = coedge->end;
70 : : else
71 : 792 : curr_vertex = coedge->start;
72 : : }
73 : : else
74 : : {
75 [ # # ][ # # ]: 0 : for (size_t i=0; i<possible_coedges.size(); i++)
[ # # ]
76 : : {
77 [ # # ]: 0 : std::vector<CoEdge*> sub_loop;
78 [ # # ][ # # ]: 0 : if (recursive_make_loop(curr_vertex, possible_coedges[i], used_coedges, start_coedge_map, sub_loop) )
[ # # ]
79 : : {
80 [ # # ][ # # ]: 0 : loop.insert(loop.end(), sub_loop.begin(), sub_loop.end());
[ # # ][ # # ]
81 : : }
82 : : else
83 : : {
84 [ # # ][ # # ]: 0 : for (size_t j=0; j<sub_loop.size(); j++)
85 [ # # ][ # # ]: 0 : used_coedges.erase(sub_loop[j]);
86 [ # # ]: 0 : coedge = possible_coedges[i];
87 : : }
88 : : }
89 [ # # ]: 0 : loop.push_back(coedge);
90 [ # # ]: 0 : used_coedges.insert(coedge);
91 [ # # ]: 0 : if (coedge->sense == CUBIT_FORWARD)
92 : 0 : curr_vertex = coedge->end;
93 : : else
94 [ + - ][ + - ]: 792 : curr_vertex = coedge->start;
95 : : }
96 : : }
97 : :
98 : 330 : return true;
99 : : }
100 : :
101 : : template <class C, class V> inline
102 : 341 : bool CubitLoops<C, V>::make_loops(std::vector<CoEdge>& coedges,
103 : : std::vector<std::vector<CoEdge*> >& loops)
104 : : {
105 [ + - ]: 341 : std::multimap<V*, CoEdge*> start_coedge_map;
106 : :
107 [ + - ][ + + ]: 1463 : for (size_t i=0; i<coedges.size(); i++)
108 : : {
109 [ + - ][ + + ]: 1122 : if (coedges[i].sense == CUBIT_FORWARD)
110 [ + - ][ + - ]: 583 : start_coedge_map.insert(std::make_pair(coedges[i].start, &coedges[i]));
[ + - ][ + - ]
[ + - ]
111 : : else
112 [ + - ][ + - ]: 539 : start_coedge_map.insert(std::make_pair(coedges[i].end, &coedges[i]));
[ + - ][ + - ]
[ + - ]
113 : : }
114 : :
115 [ + - ][ + - ]: 682 : std::set<CoEdge*> used_coedges;
116 [ + - ][ + + ]: 1463 : for (size_t i=0; i<coedges.size(); i++)
117 : : {
118 [ + - ][ + - ]: 1122 : if (used_coedges.find(&coedges[i]) != used_coedges.end())
[ + - ][ + - ]
[ + + ]
119 : 792 : continue;
120 : : V* start_vertex;
121 [ + - ][ + + ]: 330 : if (coedges[i].sense == CUBIT_FORWARD)
122 [ + - ]: 143 : start_vertex = coedges[i].start;
123 : : else
124 [ + - ]: 187 : start_vertex = coedges[i].end;
125 : :
126 [ + - ]: 330 : typename std::multimap<V*, CoEdge*>::iterator iter;
127 [ + - ]: 330 : typename std::multimap<V*, CoEdge*>::iterator last;
128 [ + - ]: 330 : iter = start_coedge_map.lower_bound(start_vertex);
129 [ + - ]: 330 : last = start_coedge_map.upper_bound(start_vertex);
130 [ + - ]: 330 : std::vector<CoEdge*> loop;
131 : :
132 [ + - ][ + - ]: 660 : for (/*preinitialized*/; iter != last; iter++)
[ + - ][ + + ]
133 : : {
134 [ + - ]: 330 : std::vector<CoEdge*> sub_loop;
135 [ + - ][ + - ]: 330 : recursive_make_loop(start_vertex, iter->second, used_coedges,
136 : 330 : start_coedge_map, loop);
137 : : }
138 : :
139 [ + - ][ - + ]: 330 : if (loop.empty())
140 : 0 : return false;
141 [ + - ][ + - ]: 330 : loops.push_back(std::vector<CoEdge*>(loop.begin(), loop.end()) );
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
142 : : }
143 : :
144 [ + - ][ + - ]: 341 : if (coedges.size() != used_coedges.size())
[ - + ]
145 : 0 : return false;
146 : :
147 [ + - ]: 682 : return true;
148 : : }
149 : :
150 : : #endif
|
