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