Audaspace:
[blender.git] / intern / container / CTR_TaggedSetOps.h
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file container/CTR_TaggedSetOps.h
29  *  \ingroup ctr
30  */
31
32
33 #ifndef __CTR_TAGGEDSETOPS_H__
34 #define __CTR_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                 typename std::vector< std::vector<IndexType> >::const_iterator 
94                         last_vector = index_list.end();
95                 typename std::vector< std::vector<IndexType> >::const_iterator 
96                         start_vector = index_list.begin();
97
98                 /* FIXME some temporary space */
99
100                 std::vector<IndexType> temp_union;
101                 temp_union.reserve(64);
102
103                 int tag_num = 0;
104
105                 for (; start_vector != last_vector; ++start_vector) {
106
107                         typename std::vector<IndexType>::const_iterator 
108                                 last_index = start_vector->end();
109                         typename std::vector<IndexType>::const_iterator 
110                                 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                 typename std::vector<IndexType>::const_iterator last_index = 
132                         temp_union.end();
133                 typename std::vector<IndexType>::const_iterator start_index = 
134                         temp_union.begin();
135
136                 for (; start_index != last_index; ++start_index) {
137
138                         ObjectType & prim = primitives[*start_index];
139
140                         if (prim.OpenTag() == tag_num) {
141                                 /* it's part of the intersection! */
142
143                                 output.push_back(*start_index);
144                                 /* because we're iterating through the union
145                                  * it's safe to remove the tag at this point */
146
147                                 prim.SetOpenTag(prim.OpenTag() & ~mask);
148                         }
149                 }
150         };
151                 
152         /* note not a strict set intersection!
153          * if x appears twice in b and is part of the intersection
154          * it will appear twice in the intersection */
155
156         static
157                 void
158         IntersectPair(
159                 const std::vector<IndexType> &a,
160                 const std::vector<IndexType> &b,
161                 std::vector<ObjectType> &primitives,
162                 std::vector<IndexType> &output
163         ) {
164                 
165                 typename std::vector<IndexType>::const_iterator last_index = 
166                         a.end();
167                 typename std::vector<IndexType>::const_iterator start_index = 
168                         a.begin();
169
170                 for (; start_index != last_index; ++start_index) {
171                         ObjectType & prim = primitives[*start_index];
172                         prim.SetSelectTag(true);
173                 }
174                 last_index = b.end();
175                 start_index = b.begin();
176
177                 for (; start_index != last_index; ++start_index) {
178                         ObjectType & prim = primitives[*start_index];
179                         if (prim.SelectTag()) {
180                                 output.push_back(*start_index);
181                         }
182                 }
183                 /* deselect */
184                 last_index = a.end();
185                 start_index = a.begin();
186
187                 for (; start_index != last_index; ++start_index) {
188                         ObjectType & prim = primitives[*start_index];
189                         prim.SetSelectTag(false);
190                 }
191         };
192
193
194         static  
195                 void
196         Union(
197                 std::vector< std::vector<IndexType> > &index_list,
198                 std::vector<ObjectType> &primitives,
199                 std::vector<IndexType> &output
200         ) {
201         
202                 /* iterate through vectors in index_list
203                  * iterate through individual members of each vector
204                  * mark each obejct that the index points to */
205
206                 typename std::vector< std::vector<IndexType> >::const_iterator 
207                         last_vector = index_list.end();
208                 typename std::vector< std::vector<IndexType> >::iterator 
209                         start_vector = index_list.begin();
210
211                 for (; start_vector != last_vector; ++start_vector) {
212
213                         typename std::vector<IndexType>::const_iterator 
214                                 last_index = start_vector->end();
215                         typename std::vector<IndexType>::iterator 
216                                 start_index = start_vector->begin();
217
218                         for (; start_index != last_index; ++start_index) {
219
220                                 ObjectType & prim = primitives[*start_index];
221
222                                 if (!prim.SelectTag()) {
223                                         /* compute the union */
224                                         output.push_back(*start_index);
225                                         prim.SetSelectTag(true);
226                                 }
227                         }
228                 }
229                                 
230                 /* now iterate through the union and reset the tags */
231
232                 typename std::vector<IndexType>::const_iterator last_index = 
233                         output.end();
234                 typename std::vector<IndexType>::iterator start_index = 
235                         output.begin();
236
237                 for (; start_index != last_index; ++start_index) {
238
239                         ObjectType & prim = primitives[*start_index];
240                         prim.SetSelectTag(false);
241                 }
242         }
243
244
245         static
246                 void
247         Difference(
248                 std::vector< IndexType> &a,
249                 std::vector< IndexType> &b,
250                 std::vector<ObjectType> &primitives,
251                 std::vector< IndexType> &output
252         ) {
253
254                 /* iterate through b mark all
255                  * iterate through a and add to output all unmarked */
256
257                 typename std::vector<IndexType>::const_iterator last_index = 
258                         b.end();
259                 typename std::vector<IndexType>::iterator start_index = 
260                         b.begin();
261
262                 for (; start_index != last_index; ++start_index) {
263
264                         ObjectType & prim = primitives[*start_index];
265                         prim.SetSelectTag(true);
266                 }
267                         
268                 last_index = a.end();
269                 start_index = a.begin();
270
271                 for (; start_index != last_index; ++start_index) {
272
273                         ObjectType & prim = primitives[*start_index];
274                         if (!prim.SelectTag()) {
275                                 output.push_back(*start_index);
276                         }
277                 }
278
279                 /* clean up the tags */
280         
281                 last_index = b.end();
282                 start_index = b.begin();
283
284                 for (; start_index != last_index; ++start_index) {
285
286                         ObjectType & prim = primitives[*start_index];
287                         prim.SetSelectTag(false);
288                 }
289         };
290
291 private :
292
293         /* private constructor - this class is not meant for
294          * instantiation */
295
296         CTR_TaggedSetOps();
297
298 };
299
300 #endif  /* __CTR_TAGGEDSETOPS_H__ */