WebSVN – gelsvn – Diff – /trunk/src/HMesh/ItemVector.h


/* ----------------------------------------------------------------------- *
 * This file is part of GEL, http://www.imm.dtu.dk/GEL
 * Copyright (C) the authors and DTU Informatics
 * For license and list of authors, see ../../doc/intro.pdf
 * ----------------------------------------------------------------------- */
/**
 * @file ItemVector.h
 * @brief Contains the vector type used for the mesh entities.
 */
 
#ifndef __HMESH_ITEMVECTOR_H__
#define __HMESH_ITEMVECTOR_H__
 
#include <cassert>
#include <vector>
#include "ItemID.h"
 
namespace HMesh
{
    /** The ItemVector is a vector of mesh entities.
        An ItemVector is a layer on top of the regular vector class which keeps
        track of the unused elements in a vector. This allows for garbage collection.
        ItemVector is used for storing vectors of Face, HalfEdge, and Vertex type.
     */
    template<typename ITEM>
    class ItemVector
    {
    public:
        typedef ItemID<ITEM> IDType;
        
        
        /// default constructor
        ItemVector(size_t _size = 0, ITEM i = ITEM()); 
        
        /// Get a reference to item i from kernel
        ITEM& get(IDType i);
        /// Get a const reference to item i from kernel
        const ITEM& get(IDType i) const;
        /// Get a reference to item i from kernel
        ITEM& operator[](IDType i);
        /// Get a const reference to item i from kernel
        const ITEM& operator[](IDType i) const;
 
        /// Add an entity to the kernel
        IDType add(const ITEM& i);
 
        /// remove an entity from kernel - entity is NOT erased!
        void remove(IDType i);
 
        /// erase unused entities from the kernel
        void cleanup();
 
        /// active size of vector
        size_t size() const;
 
        /// total size of vector
        size_t allocated_size() const;
 
        /// Resize the kernel NOTE: Sets all active flags to true
        void resize(size_t _size, ITEM i = ITEM());
        /// Request size change in kernel
        void reserve(size_t i);
 
        /// Clear the kernel
        void clear();
 
        /// Check if entity i is used
        bool in_use(IDType i) const;
 
        /// get starting index (default: skip to first active index)
        IDType index_begin(bool skip = true) const;
 
        /// get one past the end index of vector
        IDType index_end() const;
 
        /// get the next index (default: skip to first active index)
        IDType index_next(IDType index, bool skip = true) const;
 
        /// get the previous index (default: skip to first active index)
        IDType index_prev(IDType index, bool skip = true) const;
 
    private:
 
        size_t size_active;
        std::vector<ITEM> items;
 
        /// Memory consideration - objects flagged as unused should be remembered for future use (unless purged)
        std::vector<bool> active_items;
    };
 
    template<typename ITEM>
    inline ItemVector<ITEM>::ItemVector(size_t _size, ITEM i) 
        :   size_active(_size), 
            items(_size, i), 
            active_items(_size, true){}
 
    template<typename ITEM>
    inline ITEM& ItemVector<ITEM>::get(IDType id)
    {
        assert(id.index < items.size());
        return items[id.index];
    }
 
    template<typename ITEM>
    inline const ITEM& ItemVector<ITEM>::get(IDType id) const
    {
        assert(id.index < items.size());
        return items[id.index];
    }
 
    template<typename ITEM>
    inline ITEM& ItemVector<ITEM>::operator [](IDType id)
    {
        assert(id.index < items.size());
        return items[id.index];
    } 
 
    template<typename ITEM>
    inline const ITEM& ItemVector<ITEM>::operator [](IDType id) const
    {
        assert(id.index < items.size());
        return items[id.index];
    }
 
    template<typename ITEM>
    inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::add(const ITEM& item)
    {
        items.push_back(item);
        active_items.push_back(true);
        ++size_active;
        return IDType(items.size() - 1);
    }
 
    template<typename ITEM>
    inline void ItemVector<ITEM>::remove(typename ItemVector<ITEM>::IDType id)
    {
        if(active_items[id.index]){
            --size_active;
            active_items[id.index] = false;
        }
    }
 
    template<typename ITEM>
    inline void ItemVector<ITEM>::cleanup()
    {
        std::vector<ITEM> new_items;
        for(size_t i = 0; i < items.size(); ++i){
            if(active_items[i]) 
                new_items.push_back(items[i]);          
        }
        std::swap(items, new_items);
        active_items = std::vector<bool>(items.size(), true);
        size_active = items.size();
    }
 
    template<typename ITEM>
    inline size_t ItemVector<ITEM>::size() const
    { return size_active; }
 
    template<typename ITEM>
    inline size_t ItemVector<ITEM>::allocated_size() const
    { return items.size(); }
 
    template<typename ITEM>
    inline void ItemVector<ITEM>::resize(size_t _size, ITEM i)
    {
        items.resize(_size, i);
        active_items.resize(_size, true);
        size_active = _size;
    }
 
    template<typename ITEM>
    inline void ItemVector<ITEM>::reserve(size_t i)
    {
        items.reserve(i);
        active_items.reserve(i);
    }
 
    template<typename ITEM>
    inline void ItemVector<ITEM>::clear()
    {
        items.clear();
        active_items.clear();
        size_active = 0;
    }
 
    template<typename ITEM>
    inline bool ItemVector<ITEM>::in_use(typename ItemVector<ITEM>::IDType id) const
    {
        if(id.index < active_items.size())
			return active_items[id.index];
		return false;
    }
 
    template<typename ITEM>
    inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_begin(bool skip) const
    {
        size_t i = 0;
 
        if(!skip)
            return IDType(i);
        
        while(i < active_items.size() && !active_items[i])
            ++i;
 
 
        return IDType(i);
    }
 
    template<typename ITEM>
    inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_end() const
    { return IDType(items.size()); }
 
    template<typename ITEM>
    inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_next(typename ItemVector<ITEM>::IDType id, bool skip) const
    {
        if(id.index < items.size())
            ++id.index;
 
        if(!skip)
            return IDType(id);
 
        while(id.index < items.size() && !active_items[id.index])
           ++id.index;
 
        return id;
    }
 
    template<typename ITEM>
    inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_prev(typename ItemVector<ITEM>::IDType id, bool skip) const
    {
        if(id.index > 0)
            --id.index;
 
        if(!skip)
            return id;
 
        while(!active_items[id.index] && id.index > 0)
            --id.index;
 
        return id;
    }
 
}
 
#endif 
 

Rev 595	Rev 599
1	`/* ----------------------------------------------------------------------- *`	1	`/* ----------------------------------------------------------------------- *`
2	`* This file is part of GEL, http://www.imm.dtu.dk/GEL`	2	`* This file is part of GEL, http://www.imm.dtu.dk/GEL`
3	`* Copyright (C) the authors and DTU Informatics`	3	`* Copyright (C) the authors and DTU Informatics`
4	`* For license and list of authors, see ../../doc/intro.pdf`	4	`* For license and list of authors, see ../../doc/intro.pdf`
5	`* ----------------------------------------------------------------------- */`	5	`* ----------------------------------------------------------------------- */`
6	`/**`	6	`/**`
7	`* @file ItemVector.h`	7	`* @file ItemVector.h`
8	`* @brief Contains the vector type used for the mesh entities.`	8	`* @brief Contains the vector type used for the mesh entities.`
9	`*/`	9	`*/`
10		10
11	`#ifndef __HMESH_ITEMVECTOR_H__`	11	`#ifndef __HMESH_ITEMVECTOR_H__`
12	`#define __HMESH_ITEMVECTOR_H__`	12	`#define __HMESH_ITEMVECTOR_H__`
13		13
14	`#include <cassert>`	14	`#include <cassert>`
15	`#include <vector>`	15	`#include <vector>`
16	`#include "ItemID.h"`	16	`#include "ItemID.h"`
17		17
18	`namespace HMesh`	18	`namespace HMesh`
19	`{`	19	`{`
20	`/** The ItemVector is a vector of mesh entities.`	20	`/** The ItemVector is a vector of mesh entities.`
21	`An ItemVector is a layer on top of the regular vector class which keeps`	21	`An ItemVector is a layer on top of the regular vector class which keeps`
22	`track of the unused elements in a vector. This allows for garbage collection.`	22	`track of the unused elements in a vector. This allows for garbage collection.`
23	`ItemVector is used for storing vectors of Face, HalfEdge, and Vertex type.`	23	`ItemVector is used for storing vectors of Face, HalfEdge, and Vertex type.`
24	`*/`	24	`*/`
25	`template<typename ITEM>`	25	`template<typename ITEM>`
26	`class ItemVector`	26	`class ItemVector`
27	`{`	27	`{`
28	`public:`	28	`public:`
29	`typedef ItemID<ITEM> IDType;`	29	`typedef ItemID<ITEM> IDType;`
30		30
31		31
32	`/// default constructor`	32	`/// default constructor`
33	`ItemVector(size_t _size = 0, ITEM i = ITEM());`	33	`ItemVector(size_t _size = 0, ITEM i = ITEM());`
34		34
35	`/// Get a reference to item i from kernel`	35	`/// Get a reference to item i from kernel`
36	`ITEM& get(IDType i);`	36	`ITEM& get(IDType i);`
37	`/// Get a const reference to item i from kernel`	37	`/// Get a const reference to item i from kernel`
38	`const ITEM& get(IDType i) const;`	38	`const ITEM& get(IDType i) const;`
39	`/// Get a reference to item i from kernel`	39	`/// Get a reference to item i from kernel`
40	`ITEM& operator[](IDType i);`	40	`ITEM& operator[](IDType i);`
41	`/// Get a const reference to item i from kernel`	41	`/// Get a const reference to item i from kernel`
42	`const ITEM& operator[](IDType i) const;`	42	`const ITEM& operator[](IDType i) const;`
43		43
44	`/// Add an entity to the kernel`	44	`/// Add an entity to the kernel`
45	`IDType add(const ITEM& i);`	45	`IDType add(const ITEM& i);`
46		46
47	`/// remove an entity from kernel - entity is NOT erased!`	47	`/// remove an entity from kernel - entity is NOT erased!`
48	`void remove(IDType i);`	48	`void remove(IDType i);`
49		49
50	`/// erase unused entities from the kernel`	50	`/// erase unused entities from the kernel`
51	`void cleanup();`	51	`void cleanup();`
52		52
53	`/// active size of vector`	53	`/// active size of vector`
54	`size_t size() const;`	54	`size_t size() const;`
55		55
56	`/// total size of vector`	56	`/// total size of vector`
57	`size_t allocated_size() const;`	57	`size_t allocated_size() const;`
58		58
59	`/// Resize the kernel NOTE: Sets all active flags to true`	59	`/// Resize the kernel NOTE: Sets all active flags to true`
60	`void resize(size_t _size, ITEM i = ITEM());`	60	`void resize(size_t _size, ITEM i = ITEM());`
61	`/// Request size change in kernel`	61	`/// Request size change in kernel`
62	`void reserve(size_t i);`	62	`void reserve(size_t i);`
63		63
64	`/// Clear the kernel`	64	`/// Clear the kernel`
65	`void clear();`	65	`void clear();`
66		66
67	`/// Check if entity i is used`	67	`/// Check if entity i is used`
68	`bool in_use(IDType i) const;`	68	`bool in_use(IDType i) const;`
69		69
70	`/// get starting index (default: skip to first active index)`	70	`/// get starting index (default: skip to first active index)`
71	`IDType index_begin(bool skip = true) const;`	71	`IDType index_begin(bool skip = true) const;`
72		72
73	`/// get one past the end index of vector`	73	`/// get one past the end index of vector`
74	`IDType index_end() const;`	74	`IDType index_end() const;`
75		75
76	`/// get the next index (default: skip to first active index)`	76	`/// get the next index (default: skip to first active index)`
77	`IDType index_next(IDType index, bool skip = true) const;`	77	`IDType index_next(IDType index, bool skip = true) const;`
78		78
79	`/// get the previous index (default: skip to first active index)`	79	`/// get the previous index (default: skip to first active index)`
80	`IDType index_prev(IDType index, bool skip = true) const;`	80	`IDType index_prev(IDType index, bool skip = true) const;`
81		81
82	`private:`	82	`private:`
83		83
84	`size_t size_active;`	84	`size_t size_active;`
85	`std::vector<ITEM> items;`	85	`std::vector<ITEM> items;`
86		86
87	`/// Memory consideration - objects flagged as unused should be remembered for future use (unless purged)`	87	`/// Memory consideration - objects flagged as unused should be remembered for future use (unless purged)`
88	`std::vector<bool> active_items;`	88	`std::vector<bool> active_items;`
89	`};`	89	`};`
90		90
91	`template<typename ITEM>`	91	`template<typename ITEM>`
92	`inline ItemVector<ITEM>::ItemVector(size_t _size, ITEM i)`	92	`inline ItemVector<ITEM>::ItemVector(size_t _size, ITEM i)`
93	`: size_active(_size),`	93	`: size_active(_size),`
94	`items(_size, i),`	94	`items(_size, i),`
95	`active_items(_size, true){}`	95	`active_items(_size, true){}`
96		96
97	`template<typename ITEM>`	97	`template<typename ITEM>`
98	`inline ITEM& ItemVector<ITEM>::get(IDType id)`	98	`inline ITEM& ItemVector<ITEM>::get(IDType id)`
99	`{`	99	`{`
100	`assert(id.index < items.size());`	100	`assert(id.index < items.size());`
101	`return items[id.index];`	101	`return items[id.index];`
102	`}`	102	`}`
103		103
104	`template<typename ITEM>`	104	`template<typename ITEM>`
105	`inline const ITEM& ItemVector<ITEM>::get(IDType id) const`	105	`inline const ITEM& ItemVector<ITEM>::get(IDType id) const`
106	`{`	106	`{`
107	`assert(id.index < items.size());`	107	`assert(id.index < items.size());`
108	`return items[id.index];`	108	`return items[id.index];`
109	`}`	109	`}`
110		110
111	`template<typename ITEM>`	111	`template<typename ITEM>`
112	`inline ITEM& ItemVector<ITEM>::operator [](IDType id)`	112	`inline ITEM& ItemVector<ITEM>::operator [](IDType id)`
113	`{`	113	`{`
114	`assert(id.index < items.size());`	114	`assert(id.index < items.size());`
115	`return items[id.index];`	115	`return items[id.index];`
116	`}`	116	`}`
117		117
118	`template<typename ITEM>`	118	`template<typename ITEM>`
119	`inline const ITEM& ItemVector<ITEM>::operator [](IDType id) const`	119	`inline const ITEM& ItemVector<ITEM>::operator [](IDType id) const`
120	`{`	120	`{`
121	`assert(id.index < items.size());`	121	`assert(id.index < items.size());`
122	`return items[id.index];`	122	`return items[id.index];`
123	`}`	123	`}`
124		124
125	`template<typename ITEM>`	125	`template<typename ITEM>`
126	`inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::add(const ITEM& item)`	126	`inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::add(const ITEM& item)`
127	`{`	127	`{`
128	`items.push_back(item);`	128	`items.push_back(item);`
129	`active_items.push_back(true);`	129	`active_items.push_back(true);`
130	`++size_active;`	130	`++size_active;`
131	`return IDType(items.size() - 1);`	131	`return IDType(items.size() - 1);`
132	`}`	132	`}`
133		133
134	`template<typename ITEM>`	134	`template<typename ITEM>`
135	`inline void ItemVector<ITEM>::remove(ItemVector<ITEM>::IDType id)`	135	`inline void ItemVector<ITEM>::remove(typename ItemVector<ITEM>::IDType id)`
136	`{`	136	`{`
137	`if(active_items[id.index]){`	137	`if(active_items[id.index]){`
138	`--size_active;`	138	`--size_active;`
139	`active_items[id.index] = false;`	139	`active_items[id.index] = false;`
140	`}`	140	`}`
141	`}`	141	`}`
142		142
143	`template<typename ITEM>`	143	`template<typename ITEM>`
144	`inline void ItemVector<ITEM>::cleanup()`	144	`inline void ItemVector<ITEM>::cleanup()`
145	`{`	145	`{`
146	`std::vector<ITEM> new_items;`	146	`std::vector<ITEM> new_items;`
147	`for(size_t i = 0; i < items.size(); ++i){`	147	`for(size_t i = 0; i < items.size(); ++i){`
148	`if(active_items[i])`	148	`if(active_items[i])`
149	`new_items.push_back(items[i]);`	149	`new_items.push_back(items[i]);`
150	`}`	150	`}`
151	`std::swap(items, new_items);`	151	`std::swap(items, new_items);`
152	`active_items = std::vector<bool>(items.size(), true);`	152	`active_items = std::vector<bool>(items.size(), true);`
153	`size_active = items.size();`	153	`size_active = items.size();`
154	`}`	154	`}`
155		155
156	`template<typename ITEM>`	156	`template<typename ITEM>`
157	`inline size_t ItemVector<ITEM>::size() const`	157	`inline size_t ItemVector<ITEM>::size() const`
158	`{ return size_active; }`	158	`{ return size_active; }`
159		159
160	`template<typename ITEM>`	160	`template<typename ITEM>`
161	`inline size_t ItemVector<ITEM>::allocated_size() const`	161	`inline size_t ItemVector<ITEM>::allocated_size() const`
162	`{ return items.size(); }`	162	`{ return items.size(); }`
163		163
164	`template<typename ITEM>`	164	`template<typename ITEM>`
165	`inline void ItemVector<ITEM>::resize(size_t _size, ITEM i)`	165	`inline void ItemVector<ITEM>::resize(size_t _size, ITEM i)`
166	`{`	166	`{`
167	`items.resize(_size, i);`	167	`items.resize(_size, i);`
168	`active_items.resize(_size, true);`	168	`active_items.resize(_size, true);`
169	`size_active = _size;`	169	`size_active = _size;`
170	`}`	170	`}`
171		171
172	`template<typename ITEM>`	172	`template<typename ITEM>`
173	`inline void ItemVector<ITEM>::reserve(size_t i)`	173	`inline void ItemVector<ITEM>::reserve(size_t i)`
174	`{`	174	`{`
175	`items.reserve(i);`	175	`items.reserve(i);`
176	`active_items.reserve(i);`	176	`active_items.reserve(i);`
177	`}`	177	`}`
178		178
179	`template<typename ITEM>`	179	`template<typename ITEM>`
180	`inline void ItemVector<ITEM>::clear()`	180	`inline void ItemVector<ITEM>::clear()`
181	`{`	181	`{`
182	`items.clear();`	182	`items.clear();`
183	`active_items.clear();`	183	`active_items.clear();`
184	`size_active = 0;`	184	`size_active = 0;`
185	`}`	185	`}`
186		186
187	`template<typename ITEM>`	187	`template<typename ITEM>`
188	`inline bool ItemVector<ITEM>::in_use(ItemVector<ITEM>::IDType id) const`	188	`inline bool ItemVector<ITEM>::in_use(typename ItemVector<ITEM>::IDType id) const`
189	`{`	189	`{`
190	`if(id.index < active_items.size())`	190	`if(id.index < active_items.size())`
191	`return active_items[id.index];`	191	`return active_items[id.index];`
192	`return false;`	192	`return false;`
193	`}`	193	`}`
194		194
195	`template<typename ITEM>`	195	`template<typename ITEM>`
196	`inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_begin(bool skip) const`	196	`inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_begin(bool skip) const`
197	`{`	197	`{`
198	`size_t i = 0;`	198	`size_t i = 0;`
199		199
200	`if(!skip)`	200	`if(!skip)`
201	`return IDType(i);`	201	`return IDType(i);`
202		202
203	`while(i < active_items.size() && !active_items[i])`	203	`while(i < active_items.size() && !active_items[i])`
204	`++i;`	204	`++i;`
205		205
206		206
207	`return IDType(i);`	207	`return IDType(i);`
208	`}`	208	`}`
209		209
210	`template<typename ITEM>`	210	`template<typename ITEM>`
211	`inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_end() const`	211	`inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_end() const`
212	`{ return IDType(items.size()); }`	212	`{ return IDType(items.size()); }`
213		213
214	`template<typename ITEM>`	214	`template<typename ITEM>`
215	`inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_next(ItemVector<ITEM>::IDType id, bool skip) const`	215	`inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_next(typename ItemVector<ITEM>::IDType id, bool skip) const`
216	`{`	216	`{`
217	`if(id.index < items.size())`	217	`if(id.index < items.size())`
218	`++id.index;`	218	`++id.index;`
219		219
220	`if(!skip)`	220	`if(!skip)`
221	`return IDType(id);`	221	`return IDType(id);`
222		222
223	`while(id.index < items.size() && !active_items[id.index])`	223	`while(id.index < items.size() && !active_items[id.index])`
224	`++id.index;`	224	`++id.index;`
225		225
226	`return id;`	226	`return id;`
227	`}`	227	`}`
228		228
229	`template<typename ITEM>`	229	`template<typename ITEM>`
230	`inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_prev(ItemVector<ITEM>::IDType id, bool skip) const`	230	`inline typename ItemVector<ITEM>::IDType ItemVector<ITEM>::index_prev(typename ItemVector<ITEM>::IDType id, bool skip) const`
231	`{`	231	`{`
232	`if(id.index > 0)`	232	`if(id.index > 0)`
233	`--id.index;`	233	`--id.index;`
234		234
235	`if(!skip)`	235	`if(!skip)`
236	`return id;`	236	`return id;`
237		237
238	`while(!active_items[id.index] && id.index > 0)`	238	`while(!active_items[id.index] && id.index > 0)`
239	`--id.index;`	239	`--id.index;`
240		240
241	`return id;`	241	`return id;`
242	`}`	242	`}`
243		243
244	`}`	244	`}`
245		245
246	`#endif`	246	`#endif`
247		247

Subversion Repositories gelsvn

(root)/trunk/src/HMesh/ItemVector.h – Rev 595 → 599