1 files changed, 287 insertions, 0 deletions
diff --git a/intern/container/CTR_TaggedSetOps.h b/intern/container/CTR_TaggedSetOps.h
new file mode 100644
index 00000000000..fc12f6fed04
--- /dev/null
+++ b/intern/container/CTR_TaggedSetOps.h
@@ -0,0 +1,287 @@
+/**
+ * $Id$
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+
+#ifndef NAN_INCLUDED_LOD_TaggedSetOps_h
+
+#define NAN_INCLUDED_LOD_TaggedSetOps_h
+
+#include "MEM_NonCopyable.h"
+#include <vector>
+
+/**
+ * This class contains some utility functions for finding the intersection,
+ * union, and difference of a collection of stl vector of indices into
+ * a set of primitives.
+ *
+ * These are mainly used as helper functions in the decimation and bsp
+ * libraries.
+ *
+ * This template class assumes that each value of type IndexType encountered
+ * in the list is a valid index into an array of primitives. This is not
+ * checked at run-time and is left to the user to insure. Prmitives of
+ * type ObjectType must have the following public methods to be used by
+ * this template class:
+ *
+ * 	int
+ * OpenTag(void) --- return a persistent tag value for the primitive
+ *
+ *	void
+ * SetOpenTag(int bla) --- set the persistent tag value for this primitive to bla.
+ *
+ *	bool
+ * SelectTag() --- return a persistent boolean tag for this primitive
+ *
+ *	void
+ * SetSelectTag(bool bla) --- set the persistent boolean tag for this primitive to bla.
+ *
+ * Here persistent means that the tag should be associated with the object for the
+ * entire lifetime of the primitive. Again none of this stuff is enforced you have
+ * to make sure that your primitives do the right thing. Often these tags can be
+ * cunningly stowed away inside some of the spare bits in the primitive. See
+ * CTR_TaggedIndex for such a class.
+ *
+ */
+
+template 
+<class IndexType, class ObjectType>
+class CTR_TaggedSetOps : public MEM_NonCopyable {
+
+public :
+
+	static
+		void
+	Intersect(
+		const std::vector< std::vector<IndexType> > &index_list,
+		std::vector<ObjectType> &primitives,
+		std::vector<IndexType> &output,
+		unsigned int mask,
+		unsigned int shift
+	) {
+
+		// iterate through vectors in index_list
+		// iterate through individual members of each vector
+		// mark each obejct that the index points to 
+
+		std::vector< std::vector<IndexType> >::const_iterator last_vector = index_list.end();
+		std::vector< std::vector<IndexType> >::const_iterator start_vector = index_list.begin();
+
+		// FIXME some temporary space
+
+		std::vector<IndexType> temp_union;
+		temp_union.reserve(64);
+
+		int tag_num = 0;
+
+		for (; start_vector != last_vector; ++start_vector) {
+
+			std::vector<IndexType>::const_iterator last_index = start_vector->end();
+			std::vector<IndexType>::const_iterator start_index = start_vector->begin();
+
+			for (; start_index != last_index; ++start_index) {
+
+				ObjectType & prim = primitives[*start_index];
+
+				if (!prim.OpenTag()) {
+					// compute the union
+					temp_union.push_back(*start_index);
+				}
+				int tag = prim.OpenTag();
+				tag = (tag & mask) >> shift;
+				tag += 1;
+				prim.SetOpenTag((prim.OpenTag() & ~mask)| ((tag << shift) & mask));
+			}
+
+			++tag_num;
+		}
+				
+		// now iterate through the union and pull out all those with the right tag
+		
+		std::vector<IndexType>::const_iterator last_index = temp_union.end();
+		std::vector<IndexType>::const_iterator start_index = temp_union.begin();
+
+		for (; start_index != last_index; ++start_index) {
+
+			ObjectType & prim = primitives[*start_index];
+
+			if (prim.OpenTag() == tag_num) {
+				//it's part of the intersection!
+
+				output.push_back(*start_index);
+				// because we're iterating through the union 
+				// it's safe to remove the tag at this point
+
+				prim.SetOpenTag(prim.OpenTag() & ~mask);
+			}
+		}
+	};
+		
+	// note not a strict set intersection!
+	// if x appears twice in b and is part of the intersection
+	// it will appear twice in the intersection
+
+	static
+		void
+	IntersectPair(
+		const std::vector<IndexType> &a,
+		const std::vector<IndexType> &b,
+		std::vector<ObjectType> &primitives,
+		std::vector<IndexType> &output
+	) {
+		
+		std::vector<IndexType>::const_iterator last_index = a.end();
+		std::vector<IndexType>::const_iterator start_index = a.begin();
+
+		for (; start_index != last_index; ++start_index) {
+			ObjectType & prim = primitives[*start_index];
+			prim.SetSelectTag(true);
+		}
+		last_index = b.end();
+		start_index = b.begin();
+
+		for (; start_index != last_index; ++start_index) {
+			ObjectType & prim = primitives[*start_index];
+			if (prim.SelectTag()) {
+				output.push_back(*start_index);
+			}
+		}
+		// deselect
+		last_index = a.end();
+		start_index = a.begin();
+
+		for (; start_index != last_index; ++start_index) {
+			ObjectType & prim = primitives[*start_index];
+			prim.SetSelectTag(false);
+		}
+	};
+
+
+	static	
+		void
+	Union(
+		std::vector< std::vector<IndexType> > &index_list,
+		std::vector<ObjectType> &primitives,
+		std::vector<IndexType> &output
+	) {
+	
+		// iterate through vectors in index_list
+		// iterate through individual members of each vector
+		// mark each obejct that the index points to 
+
+		std::vector< std::vector<IndexType> >::const_iterator last_vector = index_list.end();
+		std::vector< std::vector<IndexType> >::iterator start_vector = index_list.begin();
+
+		for (; start_vector != last_vector; ++start_vector) {
+
+			std::vector<IndexType>::const_iterator last_index = start_vector->end();
+			std::vector<IndexType>::iterator start_index = start_vector->begin();
+
+			for (; start_index != last_index; ++start_index) {
+
+				ObjectType & prim = primitives[*start_index];
+
+				if (!prim.SelectTag()) {
+					// compute the union
+					output.push_back(*start_index);
+					prim.SetSelectTag(true);
+				}
+			}
+		}
+				
+		// now iterate through the union and reset the tags
+		
+		std::vector<IndexType>::const_iterator last_index = output.end();
+		std::vector<IndexType>::iterator start_index = output.begin();
+
+		for (; start_index != last_index; ++start_index) {
+
+			ObjectType & prim = primitives[*start_index];
+			prim.SetSelectTag(false);
+		}			
+	}
+
+
+	static
+		void
+	Difference(
+		std::vector< IndexType> &a,
+		std::vector< IndexType> &b,
+		std::vector<ObjectType> &primitives,
+		std::vector< IndexType> &output
+	) {
+
+		// iterate through b mark all
+		// iterate through a and add to output all unmarked 
+
+		std::vector<IndexType>::const_iterator last_index = b.end();
+		std::vector<IndexType>::iterator start_index = b.begin();
+
+		for (; start_index != last_index; ++start_index) {
+
+			ObjectType & prim = primitives[*start_index];
+			prim.SetSelectTag(true);
+		}
+			
+		last_index = a.end();
+		start_index = a.begin();
+
+		for (; start_index != last_index; ++start_index) {
+
+			ObjectType & prim = primitives[*start_index];
+			if (!prim.SelectTag()) {
+				output.push_back(*start_index);
+			}
+		}
+
+		// clean up the tags
+	
+		last_index = b.end();
+		start_index = b.begin();
+
+		for (; start_index != last_index; ++start_index) {
+
+			ObjectType & prim = primitives[*start_index];
+			prim.SetSelectTag(false);
+		}
+	};
+
+private :
+
+	// private constructor - this class is not meant for
+	// instantiation
+
+	CTR_TaggedSetOps();
+
+};
+
+
+
+#endif
+