fixed spacing in the headers to get rid of some warnings and some other
[blender.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
34 #define NAN_INCLUDED_LOD_TaggedSetOps_h
35
36 #include "MEM_NonCopyable.h"
37 #include <vector>
38
39 /**
40  * This class contains some utility functions for finding the intersection,
41  * union, and difference of a collection of stl vector of indices into
42  * a set of primitives.
43  *
44  * These are mainly used as helper functions in the decimation and bsp
45  * libraries.
46  *
47  * This template class assumes that each value of type IndexType encountered
48  * in the list is a valid index into an array of primitives. This is not
49  * checked at run-time and is left to the user to insure. Prmitives of
50  * type ObjectType must have the following public methods to be used by
51  * this template class:
52  *
53  *      int
54  * OpenTag(void) --- return a persistent tag value for the primitive
55  *
56  *      void
57  * SetOpenTag(int bla) --- set the persistent tag value for this primitive to bla.
58  *
59  *      bool
60  * SelectTag() --- return a persistent boolean tag for this primitive
61  *
62  *      void
63  * SetSelectTag(bool bla) --- set the persistent boolean tag for this primitive to bla.
64  *
65  * Here persistent means that the tag should be associated with the object for the
66  * entire lifetime of the primitive. Again none of this stuff is enforced you have
67  * to make sure that your primitives do the right thing. Often these tags can be
68  * cunningly stowed away inside some of the spare bits in the primitive. See
69  * CTR_TaggedIndex for such a class.
70  *
71  */
72
73 template 
74 <class IndexType, class ObjectType>
75 class CTR_TaggedSetOps : public MEM_NonCopyable {
76
77 public :
78
79         static
80                 void
81         Intersect(
82                 const std::vector< std::vector<IndexType> > &index_list,
83                 std::vector<ObjectType> &primitives,
84                 std::vector<IndexType> &output,
85                 unsigned int mask,
86                 unsigned int shift
87         ) {
88
89                 // iterate through vectors in index_list
90                 // iterate through individual members of each vector
91                 // mark each obejct that the index points to 
92
93                 std::vector< std::vector<IndexType> >::const_iterator last_vector = index_list.end();
94                 std::vector< std::vector<IndexType> >::const_iterator start_vector = index_list.begin();
95
96                 // FIXME some temporary space
97
98                 std::vector<IndexType> temp_union;
99                 temp_union.reserve(64);
100
101                 int tag_num = 0;
102
103                 for (; start_vector != last_vector; ++start_vector) {
104
105                         std::vector<IndexType>::const_iterator last_index = start_vector->end();
106                         std::vector<IndexType>::const_iterator 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                 std::vector<IndexType>::const_iterator last_index = temp_union.end();
128                 std::vector<IndexType>::const_iterator start_index = temp_union.begin();
129
130                 for (; start_index != last_index; ++start_index) {
131
132                         ObjectType & prim = primitives[*start_index];
133
134                         if (prim.OpenTag() == tag_num) {
135                                 //it's part of the intersection!
136
137                                 output.push_back(*start_index);
138                                 // because we're iterating through the union 
139                                 // it's safe to remove the tag at this point
140
141                                 prim.SetOpenTag(prim.OpenTag() & ~mask);
142                         }
143                 }
144         };
145                 
146         // note not a strict set intersection!
147         // if x appears twice in b and is part of the intersection
148         // it will appear twice in the intersection
149
150         static
151                 void
152         IntersectPair(
153                 const std::vector<IndexType> &a,
154                 const std::vector<IndexType> &b,
155                 std::vector<ObjectType> &primitives,
156                 std::vector<IndexType> &output
157         ) {
158                 
159                 std::vector<IndexType>::const_iterator last_index = a.end();
160                 std::vector<IndexType>::const_iterator start_index = a.begin();
161
162                 for (; start_index != last_index; ++start_index) {
163                         ObjectType & prim = primitives[*start_index];
164                         prim.SetSelectTag(true);
165                 }
166                 last_index = b.end();
167                 start_index = b.begin();
168
169                 for (; start_index != last_index; ++start_index) {
170                         ObjectType & prim = primitives[*start_index];
171                         if (prim.SelectTag()) {
172                                 output.push_back(*start_index);
173                         }
174                 }
175                 // deselect
176                 last_index = a.end();
177                 start_index = a.begin();
178
179                 for (; start_index != last_index; ++start_index) {
180                         ObjectType & prim = primitives[*start_index];
181                         prim.SetSelectTag(false);
182                 }
183         };
184
185
186         static  
187                 void
188         Union(
189                 std::vector< std::vector<IndexType> > &index_list,
190                 std::vector<ObjectType> &primitives,
191                 std::vector<IndexType> &output
192         ) {
193         
194                 // iterate through vectors in index_list
195                 // iterate through individual members of each vector
196                 // mark each obejct that the index points to 
197
198                 std::vector< std::vector<IndexType> >::const_iterator last_vector = index_list.end();
199                 std::vector< std::vector<IndexType> >::iterator start_vector = index_list.begin();
200
201                 for (; start_vector != last_vector; ++start_vector) {
202
203                         std::vector<IndexType>::const_iterator last_index = start_vector->end();
204                         std::vector<IndexType>::iterator start_index = start_vector->begin();
205
206                         for (; start_index != last_index; ++start_index) {
207
208                                 ObjectType & prim = primitives[*start_index];
209
210                                 if (!prim.SelectTag()) {
211                                         // compute the union
212                                         output.push_back(*start_index);
213                                         prim.SetSelectTag(true);
214                                 }
215                         }
216                 }
217                                 
218                 // now iterate through the union and reset the tags
219                 
220                 std::vector<IndexType>::const_iterator last_index = output.end();
221                 std::vector<IndexType>::iterator start_index = output.begin();
222
223                 for (; start_index != last_index; ++start_index) {
224
225                         ObjectType & prim = primitives[*start_index];
226                         prim.SetSelectTag(false);
227                 }                       
228         }
229
230
231         static
232                 void
233         Difference(
234                 std::vector< IndexType> &a,
235                 std::vector< IndexType> &b,
236                 std::vector<ObjectType> &primitives,
237                 std::vector< IndexType> &output
238         ) {
239
240                 // iterate through b mark all
241                 // iterate through a and add to output all unmarked 
242
243                 std::vector<IndexType>::const_iterator last_index = b.end();
244                 std::vector<IndexType>::iterator start_index = b.begin();
245
246                 for (; start_index != last_index; ++start_index) {
247
248                         ObjectType & prim = primitives[*start_index];
249                         prim.SetSelectTag(true);
250                 }
251                         
252                 last_index = a.end();
253                 start_index = a.begin();
254
255                 for (; start_index != last_index; ++start_index) {
256
257                         ObjectType & prim = primitives[*start_index];
258                         if (!prim.SelectTag()) {
259                                 output.push_back(*start_index);
260                         }
261                 }
262
263                 // clean up the tags
264         
265                 last_index = b.end();
266                 start_index = b.begin();
267
268                 for (; start_index != last_index; ++start_index) {
269
270                         ObjectType & prim = primitives[*start_index];
271                         prim.SetSelectTag(false);
272                 }
273         };
274
275 private :
276
277         // private constructor - this class is not meant for
278         // instantiation
279
280         CTR_TaggedSetOps();
281
282 };
283
284 #endif
285