HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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  bool erase(const INDEX &idx)
55  {
56  typename IndexMap::const_iterator it = myIndices.find(idx);
57 
58  if (it == myIndices.end())
59  return false;
60 
61  exint order = it->second;
62  myOrder(order) = tombstone<INDEX>();
63 
64  myIndices.erase(it);
65  myCompact = false;
66 
67  return true;
68  }
69 
70  void clear()
71  {
72  myIndices.clear();
73  myOrder.clear();
74  myCompact = true;
75  }
76 
77  bool contains(const INDEX &idx) const
78  {
79  // The order doesn't matter for is-member search.
80  return myIndices.find(idx) != myIndices.end();
81  }
82 
83  bool contains(const INDEX &idx, INDEX &contained_idx) const
84  {
85  // The order doesn't matter for is-member search.
86  typename IndexMap::const_iterator it = myIndices.find(idx);
87 
88  if (it != myIndices.end())
89  {
90  contained_idx = myOrder(it->second);
91  return true;
92  }
93 
94  return false;
95  }
96 
97  // For sizing, the index list is the most authoritative one.
98  size_t size() const { return myIndices.size(); }
99 
100  bool empty() const { return myIndices.empty(); }
101 
102  // Simple adapter to skip over tombstones when iterating over indices
103  class const_iterator : public std::iterator<std::forward_iterator_tag, const INDEX>
104  {
105  public:
106  const INDEX &operator *() { return *myIt; }
107 
108  bool operator==(const const_iterator &it) { return myIt == it.myIt; }
109  bool operator!=(const const_iterator &it) { return myIt != it.myIt; }
110 
112  {
113  // Skip over tombstones so our user doesn't see them.
114  do { ++myIt; } while(myIt != myEnd && *myIt == tombstone<INDEX>());
115  return *this;
116  }
117  protected:
118  friend class GU_OrderedIndexGroup;
120  const typename IndexOrder::const_iterator &end)
121  : myIt(it), myEnd(end)
122  {
123  // Fast forward until we're no longer looking at tombstones
124  while(myIt != myEnd && *myIt == tombstone<INDEX>())
125  ++myIt;
126  }
127  private:
128  typename IndexOrder::const_iterator myIt, myEnd;
129  };
130  typedef const_iterator iterator;
131 
132  const_iterator begin() const
133  {
134  return const_iterator(myOrder.begin(), myOrder.end());
135  }
136  const_iterator end() const
137  {
138  return const_iterator(myOrder.end(), myOrder.end());
139  }
140 
141  void dump(std::ostream &os) const
142  {
143  os << "Indices: ";
144  for(const typename IndexMap::value_type &oi : myIndices)
145  os << "[ " << oi.first << ", " << oi.second << "] ";
146  os << "\n";
147  os << "Order: " << myOrder << "\n";
148  }
149 
150 
152  {
153  myIndices.swap(group.myIndices);
154  myOrder.swap(group.myOrder);
155  std::swap(myCompact, group.myCompact);
156  }
157 
158  void compact()
159  {
160  if (myCompact)
161  return;
162 
163  // Create a remapping array for the new order. We use this to move
164  // items in the order list into their new positions and also to modify
165  // the order stored in the index list.
166  UT_Array<exint> order_remap;
167 
168  exint order = 0;
169  order_remap.setSizeNoInit(myOrder.size());
170  for (int i = 0, ie = myOrder.size(); i < ie; i++)
171  {
172  if (myOrder(i) == tombstone<INDEX>())
173  order_remap(i) = -1;
174  else
175  {
176  // Shift entries down in the order array.
177  myOrder(order) = myOrder(i);
178  order_remap(i) = order++;
179  }
180  }
181 
182  myOrder.truncate(order);
183 
184  // Now map the order stored in the index list to the new order as
185  // represented in the order array.
186  // Note that unordered_set iterators are always constant, but since the
187  // order field doesn't contribute to equivalence, it's mutable and we
188  // can change it at will without affecting the order of the set.
189  for(typename IndexMap::value_type &oi : myIndices)
190  {
191  oi.second = order_remap(oi.second);
192  }
193 
194  myCompact = true;
195  }
196 
197  int64 getMemoryUsage(bool inclusive) const
198  {
199  int64 mem = inclusive ? sizeof(*this) : 0;
200  // Compute size of unordered_multiset, see UT_Set.h for original.
201  mem += myIndices.bucket_count() * sizeof(void*);
202  mem += myIndices.size() * (sizeof(size_t) + sizeof(void*) + sizeof(INDEX));
203  mem += myOrder.getMemoryUsage(false);
204  return mem;
205  }
206 
207 private:
208  IndexMap myIndices;
209  IndexOrder myOrder;
210  bool myCompact;
211 };
212 
213 #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:1561
bool contains(const INDEX &idx, INDEX &contained_idx) const
void setSizeNoInit(exint newsize)
Definition: UT_Array.h:485
int64 getMemoryUsage(bool inclusive=false) const
Definition: UT_Array.h:455
void append(const INDEX &idx)
png_uint_32 i
Definition: png.h:2877
exint size() const
Definition: UT_Array.h:444
const_iterator(const typename IndexOrder::const_iterator &it, const typename IndexOrder::const_iterator &end)
int64 getMemoryUsage(bool inclusive) const
long long int64
Definition: SYS_Types.h:100
int64 exint
Definition: SYS_Types.h:109
void swap(GU_OrderedIndexGroup &group)
GLuint GLuint end
Definition: glcorearb.h:474
INDEX tombstone()
iterator begin()
Definition: UT_Array.h:772
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:765
exint append(void)
Definition: UT_Array.h:95
void truncate(exint maxsize)
Decreases, but never expands, to the given maxsize.
Definition: UT_Array.h:500
Base::value_type value_type
Definition: UT_Map.h:90
void clear()
Resets list to an empty list.
Definition: UT_Array.h:506
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:777