diff options
author | Hans Lambermont <hans@lambermont.dyndns.org> | 2002-10-12 15:37:38 +0400 |
---|---|---|
committer | Hans Lambermont <hans@lambermont.dyndns.org> | 2002-10-12 15:37:38 +0400 |
commit | 12315f4d0e0ae993805f141f64cb8c73c5297311 (patch) | |
tree | 59b45827cd8293cfb727758989c7a74b40183974 /intern/container |
Initial revisionv2.25
Diffstat (limited to 'intern/container')
-rw-r--r-- | intern/container/CTR_List.h | 144 | ||||
-rw-r--r-- | intern/container/CTR_Map.h | 152 | ||||
-rw-r--r-- | intern/container/CTR_TaggedIndex.h | 226 | ||||
-rw-r--r-- | intern/container/CTR_TaggedSetOps.h | 287 | ||||
-rw-r--r-- | intern/container/CTR_UHeap.h | 303 | ||||
-rw-r--r-- | intern/container/Makefile | 52 | ||||
-rw-r--r-- | intern/container/intern/CTR_List.cpp | 149 | ||||
-rw-r--r-- | intern/container/intern/Makefile | 42 | ||||
-rw-r--r-- | intern/container/make/msvc_6_0/container.dsp | 133 | ||||
-rw-r--r-- | intern/container/make/msvc_6_0/container.dsw | 30 |
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> +{{{ +}}} + +############################################################################### + |