* return the right error code
[blender-staging.git] / intern / container / CTR_TaggedSetOps.h
1 /**
2  * $Id$
3  * ***** BEGIN GPL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18  *
19  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
20  * All rights reserved.
21  *
22  * The Original Code is: all of this file.
23  *
24  * Contributor(s): none yet.
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 #ifndef NAN_INCLUDED_LOD_TaggedSetOps_h
30 #define NAN_INCLUDED_LOD_TaggedSetOps_h
31
32 #include "MEM_NonCopyable.h"
33 #include <vector>
34
35 /**
36  * This class contains some utility functions for finding the intersection,
37  * union, and difference of a collection of stl vector of indices into
38  * a set of primitives.
39  *
40  * These are mainly used as helper functions in the decimation and bsp
41  * libraries.
42  *
43  * This template class assumes that each value of type IndexType encountered
44  * in the list is a valid index into an array of primitives. This is not
45  * checked at run-time and is left to the user to insure. Prmitives of
46  * type ObjectType must have the following public methods to be used by
47  * this template class:
48  *
49  *      int
50  * OpenTag(void) --- return a persistent tag value for the primitive
51  *
52  *      void
53  * SetOpenTag(int bla) --- set the persistent tag value for this primitive to bla.
54  *
55  *      bool
56  * SelectTag() --- return a persistent boolean tag for this primitive
57  *
58  *      void
59  * SetSelectTag(bool bla) --- set the persistent boolean tag for this primitive to bla.
60  *
61  * Here persistent means that the tag should be associated with the object for the
62  * entire lifetime of the primitive. Again none of this stuff is enforced you have
63  * to make sure that your primitives do the right thing. Often these tags can be
64  * cunningly stowed away inside some of the spare bits in the primitive. See
65  * CTR_TaggedIndex for such a class.
66  *
67  */
68
69 template 
70 <class IndexType, class ObjectType>
71 class CTR_TaggedSetOps : public MEM_NonCopyable {
72
73 public :
74
75         static
76                 void
77         Intersect(
78                 const std::vector< std::vector<IndexType> > &index_list,
79                 std::vector<ObjectType> &primitives,
80                 std::vector<IndexType> &output,
81                 unsigned int mask,
82                 unsigned int shift
83         ) {
84
85                 // iterate through vectors in index_list
86                 // iterate through individual members of each vector
87                 // mark each obejct that the index points to 
88
89                 typename std::vector< std::vector<IndexType> >::const_iterator 
90                         last_vector = index_list.end();
91                 typename std::vector< std::vector<IndexType> >::const_iterator 
92                         start_vector = index_list.begin();
93
94                 // FIXME some temporary space
95
96                 std::vector<IndexType> temp_union;
97                 temp_union.reserve(64);
98
99                 int tag_num = 0;
100
101                 for (; start_vector != last_vector; ++start_vector) {
102
103                         typename std::vector<IndexType>::const_iterator 
104                                 last_index = start_vector->end();
105                         typename std::vector<IndexType>::const_iterator 
106                                 start_index = start_vector->begin();
107
108                         for (; start_index != last_index; ++start_index) {
109
110                                 ObjectType & prim = primitives[*start_index];
111
112                                 if (!prim.OpenTag()) {
113                                         // compute the union
114                                         temp_union.push_back(*start_index);
115                                 }
116                                 int tag = prim.OpenTag();
117                                 tag = (tag & mask) >> shift;
118                                 tag += 1;
119                                 prim.SetOpenTag((prim.OpenTag() & ~mask)| ((tag << shift) & mask));
120                         }
121
122                         ++tag_num;
123                 }
124                                 
125                 // now iterate through the union and pull out all those with the right tag
126                 
127                 typename std::vector<IndexType>::const_iterator last_index = 
128                         temp_union.end();
129                 typename std::vector<IndexType>::const_iterator start_index = 
130                         temp_union.begin();
131
132                 for (; start_index != last_index; ++start_index) {
133
134                         ObjectType & prim = primitives[*start_index];
135
136                         if (prim.OpenTag() == tag_num) {
137                                 //it's part of the intersection!
138
139                                 output.push_back(*start_index);
140                                 // because we're iterating through the union 
141                                 // it's safe to remove the tag at this point
142
143                                 prim.SetOpenTag(prim.OpenTag() & ~mask);
144                         }
145                 }
146         };
147                 
148         // note not a strict set intersection!
149         // if x appears twice in b and is part of the intersection
150         // it will appear twice in the intersection
151
152         static
153                 void
154         IntersectPair(
155                 const std::vector<IndexType> &a,
156                 const std::vector<IndexType> &b,
157                 std::vector<ObjectType> &primitives,
158                 std::vector<IndexType> &output
159         ) {
160                 
161                 typename std::vector<IndexType>::const_iterator last_index = 
162                         a.end();
163                 typename std::vector<IndexType>::const_iterator start_index = 
164                         a.begin();
165
166                 for (; start_index != last_index; ++start_index) {
167                         ObjectType & prim = primitives[*start_index];
168                         prim.SetSelectTag(true);
169                 }
170                 last_index = b.end();
171                 start_index = b.begin();
172
173                 for (; start_index != last_index; ++start_index) {
174                         ObjectType & prim = primitives[*start_index];
175                         if (prim.SelectTag()) {
176                                 output.push_back(*start_index);
177                         }
178                 }
179                 // deselect
180                 last_index = a.end();
181                 start_index = a.begin();
182
183                 for (; start_index != last_index; ++start_index) {
184                         ObjectType & prim = primitives[*start_index];
185                         prim.SetSelectTag(false);
186                 }
187         };
188
189
190         static  
191                 void
192         Union(
193                 std::vector< std::vector<IndexType> > &index_list,
194                 std::vector<ObjectType> &primitives,
195                 std::vector<IndexType> &output
196         ) {
197         
198                 // iterate through vectors in index_list
199                 // iterate through individual members of each vector
200                 // mark each obejct that the index points to 
201
202                 typename std::vector< std::vector<IndexType> >::const_iterator 
203                         last_vector = index_list.end();
204                 typename std::vector< std::vector<IndexType> >::iterator 
205                         start_vector = index_list.begin();
206
207                 for (; start_vector != last_vector; ++start_vector) {
208
209                         typename std::vector<IndexType>::const_iterator 
210                                 last_index = start_vector->end();
211                         typename std::vector<IndexType>::iterator 
212                                 start_index = start_vector->begin();
213
214                         for (; start_index != last_index; ++start_index) {
215
216                                 ObjectType & prim = primitives[*start_index];
217
218                                 if (!prim.SelectTag()) {
219                                         // compute the union
220                                         output.push_back(*start_index);
221                                         prim.SetSelectTag(true);
222                                 }
223                         }
224                 }
225                                 
226                 // now iterate through the union and reset the tags
227                 
228                 typename std::vector<IndexType>::const_iterator last_index = 
229                         output.end();
230                 typename std::vector<IndexType>::iterator start_index = 
231                         output.begin();
232
233                 for (; start_index != last_index; ++start_index) {
234
235                         ObjectType & prim = primitives[*start_index];
236                         prim.SetSelectTag(false);
237                 }                       
238         }
239
240
241         static
242                 void
243         Difference(
244                 std::vector< IndexType> &a,
245                 std::vector< IndexType> &b,
246                 std::vector<ObjectType> &primitives,
247                 std::vector< IndexType> &output
248         ) {
249
250                 // iterate through b mark all
251                 // iterate through a and add to output all unmarked 
252
253                 typename std::vector<IndexType>::const_iterator last_index = 
254                         b.end();
255                 typename std::vector<IndexType>::iterator start_index = 
256                         b.begin();
257
258                 for (; start_index != last_index; ++start_index) {
259
260                         ObjectType & prim = primitives[*start_index];
261                         prim.SetSelectTag(true);
262                 }
263                         
264                 last_index = a.end();
265                 start_index = a.begin();
266
267                 for (; start_index != last_index; ++start_index) {
268
269                         ObjectType & prim = primitives[*start_index];
270                         if (!prim.SelectTag()) {
271                                 output.push_back(*start_index);
272                         }
273                 }
274
275                 // clean up the tags
276         
277                 last_index = b.end();
278                 start_index = b.begin();
279
280                 for (; start_index != last_index; ++start_index) {
281
282                         ObjectType & prim = primitives[*start_index];
283                         prim.SetSelectTag(false);
284                 }
285         };
286
287 private :
288
289         // private constructor - this class is not meant for
290         // instantiation
291
292         CTR_TaggedSetOps();
293
294 };
295
296 #endif
297