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