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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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