Initial revisionv2.25

10 files changed, 1518 insertions, 0 deletions

diff --git a/intern/container/CTR_List.h b/intern/container/CTR_List.h
new file mode 100644
index 00000000000..29d7c2f8de1
--- /dev/null
+++ b/intern/container/CTR_List.h
@@ -0,0 +1,144 @@
+/**
+ * $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 *****
+ */
+
+/**
+ * $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 CTR_LIST_H
+#define CTR_LIST_H
+
+class CTR_Link {
+public:
+    CTR_Link(
+	) ;
+
+    CTR_Link(
+		CTR_Link *next,
+		CTR_Link *prev
+	) ;
+    
+		CTR_Link *
+	getNext(
+	) const ;
+  
+		CTR_Link *
+	getPrev(
+	) const ;
+
+		bool 
+	isHead(
+	) const ;
+
+		bool 
+	isTail(
+	) const ;
+
+		void 
+	insertBefore(
+		CTR_Link *link
+	) ;
+
+		void 
+	insertAfter(
+		CTR_Link *link
+	) ;
+
+		void 
+	remove(
+	) ;
+
+private:  
+    CTR_Link  *m_next;
+    CTR_Link  *m_prev;
+};
+
+class CTR_List {
+public:
+
+    CTR_List(
+	) ;
+
+		CTR_Link *
+	getHead(
+	) const ;
+ 
+		CTR_Link *
+	getTail(
+	) const ;
+
+		void 
+	addHead(
+		CTR_Link *link
+	) ;
+
+		void 
+	addTail(
+		CTR_Link *link
+	) ;
+    
+private:
+    CTR_Link m_head;
+    CTR_Link m_tail;
+};
+
+#endif
+
+
+
diff --git a/intern/container/CTR_Map.h b/intern/container/CTR_Map.h
new file mode 100644
index 00000000000..348807212b6
--- /dev/null
+++ b/intern/container/CTR_Map.h
@@ -0,0 +1,152 @@
+/**
+ * $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 CTR_MAP_H
+
+#define CTR_MAP_H
+
+template <class Key, class Value>
+class CTR_Map {
+private:
+    struct Entry {
+        Entry (Entry *next, Key key, Value value) :
+            m_next(next),
+            m_key(key),
+            m_value(value) {}
+
+        Entry *m_next;
+        Key    m_key;
+        Value  m_value;
+    };
+ 
+public:
+    CTR_Map(int num_buckets = 100) : m_num_buckets(num_buckets) {
+        m_buckets = new Entry *[num_buckets];
+        for (int i = 0; i < num_buckets; ++i) {
+            m_buckets[i] = 0;
+        }
+    }
+    
+    int size() { 
+        int count=0;
+        for (int i=0;i<m_num_buckets;i++)
+        {
+            Entry* bucket = m_buckets[i];
+            while(bucket)
+            {
+                bucket = bucket->m_next;
+                count++;
+            }
+        }
+        return count;
+    }
+    
+    Value* at(int index) {
+        int count=0;
+        for (int i=0;i<m_num_buckets;i++)
+        {
+            Entry* bucket = m_buckets[i];
+            while(bucket)
+            {
+                if (count==index)
+                {
+                    return &bucket->m_value;
+                }
+                bucket = bucket->m_next;
+                count++;
+            }
+        }
+        return 0;
+    }
+    
+    void clear() {
+        for (int i = 0; i < m_num_buckets; ++i) {
+            Entry *entry_ptr = m_buckets[i];
+            
+            while (entry_ptr != 0) {
+                Entry *tmp_ptr = entry_ptr->m_next;
+                delete entry_ptr;
+                entry_ptr = tmp_ptr;
+            }
+            m_buckets[i] = 0;
+        }
+    }
+    
+    ~CTR_Map() {
+        clear();
+        delete [] m_buckets;
+    }
+    
+    void insert(const Key& key, const Value& value) {
+        Entry *entry_ptr = m_buckets[key.hash() % m_num_buckets];
+        while ((entry_ptr != 0) && !(key == entry_ptr->m_key)) {
+            entry_ptr = entry_ptr->m_next;
+        }
+        
+        if (entry_ptr != 0) {
+            entry_ptr->m_value = value;
+        }
+        else {
+            Entry **bucket = &m_buckets[key.hash() % m_num_buckets];
+            *bucket = new Entry(*bucket, key, value);
+        }
+    }
+
+    void remove(const Key& key) {
+        Entry **entry_ptr = &m_buckets[key.hash() % m_num_buckets];
+        while ((*entry_ptr != 0) && !(key == (*entry_ptr)->m_key)) {
+            entry_ptr = &(*entry_ptr)->m_next;
+        }
+        
+        if (*entry_ptr != 0) {
+            Entry *tmp_ptr = (*entry_ptr)->m_next;
+            delete *entry_ptr;
+            *entry_ptr = tmp_ptr;
+        }
+    }
+
+    Value *operator[](Key key) {
+        Entry *bucket = m_buckets[key.hash() % m_num_buckets];
+        while ((bucket != 0) && !(key == bucket->m_key)) {
+            bucket = bucket->m_next;
+        }
+        return bucket != 0 ? &bucket->m_value : 0;
+    }
+    
+private:
+    int     m_num_buckets;
+    Entry **m_buckets;
+};
+
+#endif
+
+
+
diff --git a/intern/container/CTR_TaggedIndex.h b/intern/container/CTR_TaggedIndex.h
new file mode 100644
index 00000000000..026819d465c
--- /dev/null
+++ b/intern/container/CTR_TaggedIndex.h
@@ -0,0 +1,226 @@
+/**
+ * $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 *****
+ */
+
+/**
+
+ * $Id$
+ * Copyright (C) 2001 NaN Technologies B.V.
+ * Simple tagged index class.
+ */
+
+#ifndef NAN_INCLUDED_CTR_TaggedIndex_h
+#define NAN_INCLUDED_CTR_TaggedIndex_h
+
+/**
+ * This class is supposed to be a simple tagged index class. If these
+ * were indices into a mesh then we would never need 32 bits for such indices.
+ * It is often handy to have a few extra bits around to mark objects etc. We
+ * steal a few bits of CTR_TaggedIndex objects for this purpose. From the outside
+ * it will behave like a standard unsigned int but just carry the extra tag
+ * information around with it.
+ */
+
+#include <functional>
+
+enum {
+
+	empty_tag = 0x0,
+	empty_index = 0xffffffff
+};
+
+template <
+	int tag_shift, 
+	int index_mask
+> class CTR_TaggedIndex {
+public:
+	CTR_TaggedIndex(
+	) : 
+		m_val ((empty_tag << tag_shift) | (empty_index & index_mask))
+	{
+	}
+
+	CTR_TaggedIndex(
+		const int val
+	) :
+		m_val ((val & index_mask) | ((empty_tag << tag_shift) & (~index_mask))) {
+	}
+
+	CTR_TaggedIndex(
+		const unsigned int val
+	) :
+		m_val ((val & index_mask) | ((empty_tag << tag_shift) & (~index_mask))) {
+	}
+
+	CTR_TaggedIndex(
+		const long int val
+	) :
+		m_val ( ((long int) val & index_mask)
+				| ( (empty_tag << tag_shift)
+					& (~index_mask)) ) {
+	}
+
+	CTR_TaggedIndex(
+		const long unsigned int val
+	) :
+		m_val ( ((long unsigned int)val & index_mask)
+				| ( (empty_tag << tag_shift)
+					& (~index_mask) ) ) {
+	}
+
+
+	CTR_TaggedIndex(
+		const CTR_TaggedIndex &my_index
+	):
+		m_val(my_index.m_val)
+	{
+	}
+
+		bool 
+	operator == (
+		const CTR_TaggedIndex& rhs
+	) const {
+
+		return ((this->m_val & index_mask) == (rhs.m_val & index_mask));
+	}		
+
+	operator unsigned int () const {
+		return m_val & index_mask;
+	}
+
+	operator unsigned long int () const {
+		return (unsigned long int)(m_val & index_mask);
+	}
+
+	operator int () const {
+		return int(m_val & index_mask);
+	}
+
+	operator long int () const {
+		return (long int)(m_val & index_mask);
+	}
+
+		bool
+	IsEmpty(
+	) const {
+		return ((m_val & index_mask) == (empty_index & index_mask));
+	}
+
+
+	static
+		CTR_TaggedIndex
+	Empty(
+	) {
+		return CTR_TaggedIndex();
+	}
+
+		void
+	Invalidate(
+	) {
+		m_val = (empty_tag << tag_shift) | (empty_index & index_mask);
+	}
+
+
+		unsigned int 
+	Tag (
+	) const {
+		return m_val >> tag_shift;
+	}
+	
+		void
+	SetTag(
+		unsigned int tag
+	) {
+		m_val = (m_val & index_mask) | ((tag << tag_shift) & (~index_mask));
+	}
+
+		void
+	EmptyTag(
+	) {
+		m_val = (m_val & index_mask) | ((empty_tag << tag_shift) & (~index_mask));
+	}
+
+		bool
+	IsEmptyTag(
+	) const {
+		return (Tag() == Empty().Tag());
+	}
+	
+	// functionals 
+
+	struct greater : std::binary_function<CTR_TaggedIndex, CTR_TaggedIndex, bool>
+	{
+			bool 
+		operator()(
+			const CTR_TaggedIndex& a,
+			const CTR_TaggedIndex& b
+		) const {
+			return (int(a) > int(b));
+		}
+	};
+	
+	
+private :
+	CTR_TaggedIndex(
+		const CTR_TaggedIndex *index
+	) {}; 
+
+	unsigned int m_val;
+
+
+};			
+
+
+#endif
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
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
+
diff --git a/intern/container/CTR_UHeap.h b/intern/container/CTR_UHeap.h
new file mode 100644
index 00000000000..251e020aba3
--- /dev/null
+++ b/intern/container/CTR_UHeap.h
@@ -0,0 +1,303 @@
+/**
+ * $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 *****
+ */
+
+/**
+
+ * $Id$
+ * Copyright (C) 2001 NaN Technologies B.V.
+ *
+ * @author Laurence
+ * @mainpage CTR_UHeap an updatable heap template class (also
+ * known as an updatable priority queue)
+ *
+ * Todo: Make CTR_UHeapable a template class with m_key the
+ * template parameter, so that arbitrary value types with
+ * operators (=,>) defined can be used.
+ *
+ */
+
+#ifndef NAN_INCLUDED_CTR_UHeap_h
+#define NAN_INCLUDED_CTR_UHeap_h
+
+#include <vector>
+#include "MEM_NonCopyable.h"
+
+class CTR_UHeapable {
+
+public :
+		int &
+	HeapPos(
+	){
+		return m_ind;
+	};
+		float &
+	HeapKey(
+	) {
+		return m_key;
+	};
+
+	const 
+		float &
+	HeapKey(
+	) const {
+		return m_key;
+	};
+
+	const 
+		int &
+	HeapPos(
+	) const {
+		return m_ind;
+	};
+
+private :
+
+	float m_key;
+	int m_ind;
+
+protected :
+
+	CTR_UHeapable(
+	) : m_key (0),
+		m_ind (0)
+	{
+	};
+
+	~CTR_UHeapable(
+	){
+	};
+};
+	
+template <class HeapType> 	
+class CTR_UHeap : public MEM_NonCopyable
+{
+
+public:		
+
+	static
+		CTR_UHeap *
+	New(
+	) {
+		return new CTR_UHeap();
+	}
+
+		void
+	MakeHeap(
+		HeapType *base
+	) {
+		int i;
+		int start = Parent(m_vector.size()-1);
+		for (i = start; i >=0; --i) {
+			DownHeap(base,i);
+		}
+	}; 
+	
+		void
+	Insert(
+		HeapType *base,
+		int elem
+	) {
+		// add element to vector
+		m_vector.push_back(elem);
+		base[elem].HeapPos() = m_vector.size()-1;
+
+		// push the element up the heap
+		UpHeap(base,m_vector.size()-1);
+	}
+
+	// access to the vector for initial loading of elements
+
+		std::vector<int> &
+	HeapVector(
+	) {
+		return m_vector;
+	};
+
+
+		void
+	Remove(
+		HeapType *base,
+		int i
+	) {
+	
+		// exchange with last element - pop last
+		// element and move up or down the heap as appropriate
+		if (m_vector.empty()) {
+			assert(false);
+		}
+
+		if (i  != int(m_vector.size())-1) {
+			
+			Swap(base,i,m_vector.size() - 1);
+			m_vector.pop_back();
+
+			if (!m_vector.empty()) {
+				UpHeap(base,i);
+				DownHeap(base,i);
+			}
+		} else {
+			m_vector.pop_back();
+		}
+	}
+
+		int
+	Top(
+	) const {
+		if (m_vector.empty()) return -1;
+		return m_vector[0];
+	}
+		
+
+		void
+	SC_Heap(
+		HeapType *base
+	) {
+		int i;
+		for (i = 1; i < int(m_vector.size()) ; i++) {
+			
+			CTR_UHeapable * elem = base + m_vector[i];			
+			CTR_UHeapable * p_elem = base + m_vector[Parent(i)];			
+
+			assert(p_elem->HeapKey() >= elem->HeapKey());
+			assert(elem->HeapPos() == i);
+		}
+
+	};
+			
+
+	~CTR_UHeap(
+	) {
+	};	
+
+
+private:
+
+	CTR_UHeap(
+	) {
+	};
+
+
+	std::vector<int> m_vector;
+		
+private:
+		void 
+	Swap(
+		HeapType *base,
+		int i, 
+		int j
+	){
+		std::swap(m_vector[i],m_vector[j]);
+		
+		CTR_UHeapable *heap_i = base + m_vector[i];
+		CTR_UHeapable *heap_j = base + m_vector[j];
+		
+		// Exchange heap positions
+		heap_i->HeapPos() = i;
+		heap_j->HeapPos() = j;
+	}
+
+		int 
+	Parent(
+		unsigned int i
+	) {
+		 return (i-1) >> 1; 
+	}
+		int 
+	Left(
+		int i
+	) {
+		return (i<<1)+1; 
+	}
+
+		int 
+	Right(
+		int i
+	) {
+		return (i<<1)+2;
+	}
+
+		float
+	HeapVal(
+		HeapType *base,
+		int i
+	) {
+		return base[m_vector[i]].HeapKey();
+	}
+
+		void
+	DownHeap(
+		HeapType *base,		
+		int i
+	) {
+		int heap_size = m_vector.size();
+
+		int l = Left(i);
+		int r = Right(i);
+
+		int largest;
+		if (l < heap_size && HeapVal(base,l) > HeapVal(base,i)) {
+			largest = l;
+		} else {
+			largest = i;
+		}
+
+		if (r < heap_size && HeapVal(base,r) > HeapVal(base,largest)) {
+			largest = r;
+		}	
+
+		if (largest != i) {
+			// exchange i and largest
+			Swap(base,i,largest);
+			DownHeap(base,largest);
+		}
+	}
+
+		void
+	UpHeap(
+		HeapType *base,
+		int i
+	) {
+
+		// swap parents untill it's found a place in the heap < it's parent or
+		// top of heap
+
+		while (i > 0) {
+			int p = Parent(i);
+			if (HeapVal(base,i) < HeapVal(base,p)) {
+				break;
+			}
+			Swap(base,p,i);
+			i = p;
+		}
+	}		
+};
+
+#endif
diff --git a/intern/container/Makefile b/intern/container/Makefile
new file mode 100644
index 00000000000..31ca8e8ae1a
--- /dev/null
+++ b/intern/container/Makefile
@@ -0,0 +1,52 @@
+#
+# $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 *****
+# container main makefile.
+#
+
+include nan_definitions.mk
+
+LIBNAME = container
+SOURCEDIR = intern/$(LIBNAME)
+DIR = $(OCGDIR)/$(SOURCEDIR)
+DIRS = intern
+#not yet TESTDIRS = test
+ 
+include nan_subdirs.mk
+
+install: all debug
+	@[ -d $(NAN_CONTAINER) ] || mkdir $(NAN_CONTAINER)
+	@[ -d $(NAN_CONTAINER)/include ] || mkdir $(NAN_CONTAINER)/include
+	@[ -d $(NAN_CONTAINER)/lib ] || mkdir $(NAN_CONTAINER)/lib
+	@[ -d $(NAN_CONTAINER)/lib/debug ] || mkdir $(NAN_CONTAINER)/lib/debug
+	cp -f $(DIR)/libcontainer.a $(NAN_CONTAINER)/lib/
+	cp -f $(DIR)/debug/libcontainer.a $(NAN_CONTAINER)/lib/debug
+	cp -f *.h $(NAN_CONTAINER)/include/
+
diff --git a/intern/container/intern/CTR_List.cpp b/intern/container/intern/CTR_List.cpp
new file mode 100644
index 00000000000..2e8c1bb13d2
--- /dev/null
+++ b/intern/container/intern/CTR_List.cpp
@@ -0,0 +1,149 @@
+/**
+ * $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 *****
+ */
+
+#include "CTR_List.h"
+
+
+CTR_Link::
+CTR_Link(
+) : 
+	m_next(0), 
+	m_prev(0) 
+{
+}
+
+CTR_Link::
+CTR_Link(
+	CTR_Link *next,
+	CTR_Link *prev
+) : 
+	m_next(next), 
+	m_prev(prev) 
+{
+}
+
+	CTR_Link *
+CTR_Link::
+getNext(
+) const {
+	return m_next; 
+}
+
+	CTR_Link *
+CTR_Link::
+getPrev(
+) const { 
+	return m_prev; 
+}  
+
+	bool 
+CTR_Link::
+isHead(
+) const { 
+	return m_prev == 0; 
+}
+
+	bool 
+CTR_Link::
+isTail(
+) const { 
+	return m_next == 0; 
+}
+
+	void 
+CTR_Link::
+insertBefore(
+	CTR_Link *link
+) {
+    m_next         = link;
+    m_prev         = link->m_prev;
+    m_next->m_prev = this;
+    m_prev->m_next = this;
+} 
+
+	void 
+CTR_Link::
+insertAfter(
+	CTR_Link *link
+) {
+    m_next         = link->m_next;
+    m_prev         = link;
+    m_next->m_prev = this;
+    m_prev->m_next = this;
+} 
+
+	void 
+CTR_Link::
+remove(
+) { 
+    m_next->m_prev = m_prev; 
+    m_prev->m_next = m_next;
+}
+
+
+CTR_List::
+CTR_List(
+) : 
+	m_head(&m_tail, 0), 
+	m_tail(0, &m_head) 
+{
+}
+
+	CTR_Link *
+CTR_List::
+getHead(
+) const { 
+	return m_head.getNext(); 
+}
+
+	CTR_Link *
+CTR_List::
+getTail(
+) const { 
+	return m_tail.getPrev();
+} 
+
+	void 
+CTR_List::
+addHead(
+	CTR_Link *link
+) { 
+	link->insertAfter(&m_head); 
+}
+
+	void 
+CTR_List::
+addTail(
+	CTR_Link *link
+) { 
+	link->insertBefore(&m_tail); 
+}
+
diff --git a/intern/container/intern/Makefile b/intern/container/intern/Makefile
new file mode 100644
index 00000000000..292df5b7cbc
--- /dev/null
+++ b/intern/container/intern/Makefile
@@ -0,0 +1,42 @@
+#
+# $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 *****
+# container intern Makefile
+#
+
+LIBNAME = container
+DIR = $(OCGDIR)/intern/$(LIBNAME)
+
+include nan_compile.mk
+
+CCFLAGS += $(LEVEL_2_CPP_WARNINGS)
+
+CPPFLAGS += -I..
+
diff --git a/intern/container/make/msvc_6_0/container.dsp b/intern/container/make/msvc_6_0/container.dsp
new file mode 100644
index 00000000000..05faf85d1d3
--- /dev/null
+++ b/intern/container/make/msvc_6_0/container.dsp
@@ -0,0 +1,133 @@
+# Microsoft Developer Studio Project File - Name="container" - Package Owner=<4>
+# Microsoft Developer Studio Generated Build File, Format Version 6.00
+# ** DO NOT EDIT **
+
+# TARGTYPE "Win32 (x86) Static Library" 0x0104
+
+CFG=container - Win32 Debug
+!MESSAGE This is not a valid makefile. To build this project using NMAKE,
+!MESSAGE use the Export Makefile command and run
+!MESSAGE 
+!MESSAGE NMAKE /f "container.mak".
+!MESSAGE 
+!MESSAGE You can specify a configuration when running NMAKE
+!MESSAGE by defining the macro CFG on the command line. For example:
+!MESSAGE 
+!MESSAGE NMAKE /f "container.mak" CFG="container - Win32 Debug"
+!MESSAGE 
+!MESSAGE Possible choices for configuration are:
+!MESSAGE 
+!MESSAGE "container - Win32 Release" (based on "Win32 (x86) Static Library")
+!MESSAGE "container - Win32 Debug" (based on "Win32 (x86) Static Library")
+!MESSAGE 
+
+# Begin Project
+# PROP AllowPerConfigDependencies 0
+# PROP Scc_ProjName ""
+# PROP Scc_LocalPath ""
+CPP=cl.exe
+RSC=rc.exe
+
+!IF  "$(CFG)" == "container - Win32 Release"
+
+# PROP BASE Use_MFC 0
+# PROP BASE Use_Debug_Libraries 0
+# PROP BASE Output_Dir "Release"
+# PROP BASE Intermediate_Dir "Release"
+# PROP BASE Target_Dir ""
+# PROP Use_MFC 0
+# PROP Use_Debug_Libraries 0
+# PROP Output_Dir "Release"
+# PROP Intermediate_Dir "Release"
+# PROP Target_Dir ""
+LINK32=link.exe -lib
+# ADD BASE CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_MBCS" /D "_LIB" /YX /FD /c
+# ADD CPP /nologo /MT /W3 /GX /O2 /Ob2 /D "WIN32" /D "NDEBUG" /D "_MBCS" /D "_LIB" /YX /FD /c
+# ADD BASE RSC /l 0x413 /d "NDEBUG"
+# ADD RSC /l 0x413 /d "NDEBUG"
+BSC32=bscmake.exe
+# ADD BASE BSC32 /nologo
+# ADD BSC32 /nologo
+LIB32=link.exe -lib
+# ADD BASE LIB32 /nologo
+# ADD LIB32 /nologo /out:"Release\libcontainer.lib"
+# Begin Special Build Tool
+SOURCE="$(InputPath)"
+PostBuild_Cmds=ECHO Copying header files	COPY "..\..\*.h" "..\..\..\..\lib\windows\container\include\"	ECHO Copying lib	COPY "Release\libcontainer.lib" "..\..\..\..\lib\windows\container\lib\libcontainer.a"	ECHO Done
+# End Special Build Tool
+
+!ELSEIF  "$(CFG)" == "container - Win32 Debug"
+
+# PROP BASE Use_MFC 0
+# PROP BASE Use_Debug_Libraries 1
+# PROP BASE Output_Dir "Debug"
+# PROP BASE Intermediate_Dir "Debug"
+# PROP BASE Target_Dir ""
+# PROP Use_MFC 0
+# PROP Use_Debug_Libraries 1
+# PROP Output_Dir "Debug"
+# PROP Intermediate_Dir "Debug"
+# PROP Target_Dir ""
+LINK32=link.exe -lib
+# ADD BASE CPP /nologo /W3 /Gm /GX /ZI /Od /D "WIN32" /D "_DEBUG" /D "_MBCS" /D "_LIB" /YX /FD /GZ /c
+# ADD CPP /nologo /MTd /W3 /Gm /GX /ZI /Od /D "WIN32" /D "_DEBUG" /D "_MBCS" /D "_LIB" /YX /FD /GZ /c
+# ADD BASE RSC /l 0x413 /d "_DEBUG"
+# ADD RSC /l 0x413 /d "_DEBUG"
+BSC32=bscmake.exe
+# ADD BASE BSC32 /nologo
+# ADD BSC32 /nologo
+LIB32=link.exe -lib
+# ADD BASE LIB32 /nologo
+# ADD LIB32 /nologo /out:"Debug\libcontainer.lib"
+# Begin Special Build Tool
+SOURCE="$(InputPath)"
+PostBuild_Cmds=ECHO Copying header files	COPY "..\..\*.h" "..\..\..\..\lib\windows\container\include\"	ECHO Copying lib	COPY "Debug\libcontainer.lib" "..\..\..\..\lib\windows\container\lib\debug\libcontainer.a"	ECHO Copying Debug info.	COPY "Debug\vc60.*" "..\..\..\..\lib\windows\container\lib\debug\"	ECHO Done
+# End Special Build Tool
+
+!ENDIF 
+
+# Begin Target
+
+# Name "container - Win32 Release"
+# Name "container - Win32 Debug"
+# Begin Group "intern"
+
+# PROP Default_Filter ""
+# Begin Source File
+
+SOURCE=..\..\intern\CTR_List.cpp
+
+!IF  "$(CFG)" == "container - Win32 Release"
+
+# ADD CPP /I "../extern" /I "../../"
+
+!ELSEIF  "$(CFG)" == "container - Win32 Debug"
+
+# ADD CPP /I "../../"
+
+!ENDIF 
+
+# End Source File
+# End Group
+# Begin Source File
+
+SOURCE=..\..\CTR_List.h
+# End Source File
+# Begin Source File
+
+SOURCE=..\..\CTR_Map.h
+# End Source File
+# Begin Source File
+
+SOURCE=..\..\CTR_TaggedIndex.h
+# End Source File
+# Begin Source File
+
+SOURCE=..\..\CTR_TaggedSetOps.h
+# End Source File
+# Begin Source File
+
+SOURCE=..\..\CTR_UHeap.h
+# End Source File
+# End Target
+# End Project
diff --git a/intern/container/make/msvc_6_0/container.dsw b/intern/container/make/msvc_6_0/container.dsw
new file mode 100644
index 00000000000..adaf6dd202e
--- /dev/null
+++ b/intern/container/make/msvc_6_0/container.dsw
@@ -0,0 +1,30 @@
+Microsoft Developer Studio Workspace File, Format Version 6.00
+# WARNING: DO NOT EDIT OR DELETE THIS WORKSPACE FILE!
+
+###############################################################################
+
+Project: "container"=.\container.dsp - Package Owner=<4>
+
+Package=<5>
+{{{
+}}}
+
+
+Package=<4>
+{{{
+}}}
+
+###############################################################################
+
+Global:
+
+Package=<5>
+{{{
+}}}
+
+Package=<3>
+{{{
+}}}
+
+###############################################################################
+