HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GU_OrderedIndexGroup.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: GU_OrderedIndexGroup.h ( GU Library, C++)
7  *
8  * COMMENTS: This is a helper class for GU_Selection derivatives to keep
9  * selection as an ordered group of indices, rather than offsets,
10  * so that selection can remain GA_Detail invariant.
11  */
12 
13 #ifndef __GU_OrderedIndexGroup__
14 #define __GU_OrderedIndexGroup__
15 
16 #include <UT/UT_Array.h>
17 #include <UT/UT_Map.h>
18 #include <iterator>
19 
20 // Tombstone value for the index type, so that we can mark a dead value as
21 // distinct from a potentially valid value.
22 template<typename INDEX>
23 inline INDEX
24 tombstone() { return INDEX(); }
25 
26 template<typename INDEX>
28 {
31 
32 public:
33  typedef INDEX type;
34 
35  GU_OrderedIndexGroup() : myCompact(true) {}
36 
37  void append(const INDEX &idx)
38  {
39  typename IndexMap::iterator it = myIndices.find(idx);
40 
41  if (it == myIndices.end())
42  {
43  exint order = myOrder.append(idx);
44  myIndices.insert(std::make_pair(idx, order));
45  }
46  else
47  {
48  // Just update the order. The newly added entry gets put last.
49  myOrder(it->second) = tombstone<INDEX>();
50  it->second = myOrder.append(idx);
51  }
52  }
53 
54  // This method is safe to use while iterating over this ordered group
55  // because it doesn't change the size of myOrder. Should this ever
56  // change, all calling code will need to be examined to determine if
57  // it needs to be updated.
58  bool erase(const INDEX &idx)
59  {
60  typename IndexMap::const_iterator it = myIndices.find(idx);
61 
62  if (it == myIndices.end())
63  return false;
64 
65  exint order = it->second;
66  myOrder(order) = tombstone<INDEX>();
67 
68  myIndices.erase(it);
69  myCompact = false;
70 
71  return true;
72  }
73 
74  void clear()
75  {
76  myIndices.clear();
77  myOrder.clear();
78  myCompact = true;
79  }
80 
81  bool contains(const INDEX &idx) const
82  {
83  // The order doesn't matter for is-member search.
84  return myIndices.find(idx) != myIndices.end();
85  }
86 
87  bool contains(const INDEX &idx, INDEX &contained_idx) const
88  {
89  // The order doesn't matter for is-member search.
90  typename IndexMap::const_iterator it = myIndices.find(idx);
91 
92  if (it != myIndices.end())
93  {
94  contained_idx = myOrder(it->second);
95  return true;
96  }
97 
98  return false;
99  }
100 
101  // For sizing, the index list is the most authoritative one.
102  size_t size() const { return myIndices.size(); }
103 
104  bool empty() const { return myIndices.empty(); }
105 
106  // Simple adapter to skip over tombstones when iterating over indices
107  class const_iterator : public std::iterator<std::forward_iterator_tag, const INDEX>
108  {
109  public:
110  const INDEX &operator *() { return *myIt; }
111 
112  bool operator==(const const_iterator &it) { return myIt == it.myIt; }
113  bool operator!=(const const_iterator &it) { return myIt != it.myIt; }
114 
116  {
117  // Skip over tombstones so our user doesn't see them.
118  do { ++myIt; } while(myIt != myEnd && *myIt == tombstone<INDEX>());
119  return *this;
120  }
121  protected:
122  friend class GU_OrderedIndexGroup;
124  const typename IndexOrder::const_iterator &end)
125  : myIt(it), myEnd(end)
126  {
127  // Fast forward until we're no longer looking at tombstones
128  while(myIt != myEnd && *myIt == tombstone<INDEX>())
129  ++myIt;
130  }
131  private:
132  typename IndexOrder::const_iterator myIt, myEnd;
133  };
134  typedef const_iterator iterator;
135 
136  const_iterator begin() const
137  {
138  return const_iterator(myOrder.begin(), myOrder.end());
139  }
140  const_iterator end() const
141  {
142  return const_iterator(myOrder.end(), myOrder.end());
143  }
144 
145  void dump(std::ostream &os) const
146  {
147  os << "Indices: ";
148  for(const typename IndexMap::value_type &oi : myIndices)
149  os << "[ " << oi.first << ", " << oi.second << "] ";
150  os << "\n";
151  os << "Order: " << myOrder << "\n";
152  }
153 
154 
156  {
157  myIndices.swap(group.myIndices);
158  myOrder.swap(group.myOrder);
159  std::swap(myCompact, group.myCompact);
160  }
161 
162  void compact()
163  {
164  if (myCompact)
165  return;
166 
167  // Create a remapping array for the new order. We use this to move
168  // items in the order list into their new positions and also to modify
169  // the order stored in the index list.
170  UT_Array<exint> order_remap;
171 
172  exint order = 0;
173  order_remap.setSizeNoInit(myOrder.size());
174  for (int i = 0, ie = myOrder.size(); i < ie; i++)
175  {
176  if (myOrder(i) == tombstone<INDEX>())
177  order_remap(i) = -1;
178  else
179  {
180  // Shift entries down in the order array.
181  myOrder(order) = myOrder(i);
182  order_remap(i) = order++;
183  }
184  }
185 
186  myOrder.truncate(order);
187 
188  // Now map the order stored in the index list to the new order as
189  // represented in the order array.
190  // Note that unordered_set iterators are always constant, but since the
191  // order field doesn't contribute to equivalence, it's mutable and we
192  // can change it at will without affecting the order of the set.
193  for(typename IndexMap::value_type &oi : myIndices)
194  {
195  oi.second = order_remap(oi.second);
196  }
197 
198  myCompact = true;
199  }
200 
201  int64 getMemoryUsage(bool inclusive) const
202  {
203  int64 mem = inclusive ? sizeof(*this) : 0;
204  // Compute size of unordered_multiset, see UT_Set.h for original.
205  mem += myIndices.bucket_count() * sizeof(void*);
206  mem += myIndices.size() * (sizeof(size_t) + sizeof(void*) + sizeof(INDEX));
207  mem += myOrder.getMemoryUsage(false);
208  return mem;
209  }
210 
211 private:
212  IndexMap myIndices;
213  IndexOrder myOrder;
214  bool myCompact;
215 };
216 
217 #endif // __GU_OrderedIndexGroup__
bool erase(const INDEX &idx)
const_iterator begin() const
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
Definition: UT_ArraySet.h:1629
bool contains(const INDEX &idx, INDEX &contained_idx) const
void setSizeNoInit(exint newsize)
Definition: UT_Array.h:498
int64 getMemoryUsage(bool inclusive=false) const
Definition: UT_Array.h:462
void append(const INDEX &idx)
exint size() const
Definition: UT_Array.h:451
const_iterator(const typename IndexOrder::const_iterator &it, const typename IndexOrder::const_iterator &end)
int64 getMemoryUsage(bool inclusive) const
GLuint GLdouble GLdouble GLint GLint order
Definition: glew.h:3446
long long int64
Definition: SYS_Types.h:111
int64 exint
Definition: SYS_Types.h:120
void swap(GU_OrderedIndexGroup &group)
INDEX tombstone()
GLuint GLuint end
Definition: glew.h:1253
iterator begin()
Definition: UT_Array.h:787
Base::iterator iterator
Definition: UT_Map.h:93
void dump(std::ostream &os) const
bool operator!=(const const_iterator &it)
const_iterator end() const
bool contains(const INDEX &idx) const
bool operator==(const const_iterator &it)
base_iterator< const INDEX, true > const_iterator
Definition: UT_Array.h:780
exint append(void)
Definition: UT_Array.h:95
void truncate(exint maxsize)
Decreases, but never expands, to the given maxsize.
Definition: UT_Array.h:513
Base::value_type value_type
Definition: UT_Map.h:90
void clear()
Resets list to an empty list.
Definition: UT_Array.h:519
Base::const_iterator const_iterator
Definition: UT_Map.h:94
void swap(UT_Array< T > &other)
Definition: UT_ArrayImpl.h:112
iterator end()
End iterator.
Definition: UT_Array.h:792
GLboolean GLuint group
Definition: glew.h:2745