Simbody  3.5
StableArray.h
Go to the documentation of this file.
1 #ifndef SimTK_SimTKCOMMON_STABLEARRAY_H_
2 #define SimTK_SimTKCOMMON_STABLEARRAY_H_
3 
4 /* -------------------------------------------------------------------------- *
5  * Simbody(tm): SimTKcommon *
6  * -------------------------------------------------------------------------- *
7  * This is part of the SimTK biosimulation toolkit originating from *
8  * Simbios, the NIH National Center for Physics-Based Simulation of *
9  * Biological Structures at Stanford, funded under the NIH Roadmap for *
10  * Medical Research, grant U54 GM072970. See https://simtk.org/home/simbody. *
11  * *
12  * Portions copyright (c) 2005-12 Stanford University and the Authors. *
13  * Authors: Michael Sherman *
14  * Contributors: *
15  * *
16  * Licensed under the Apache License, Version 2.0 (the "License"); you may *
17  * not use this file except in compliance with the License. You may obtain a *
18  * copy of the License at http://www.apache.org/licenses/LICENSE-2.0. *
19  * *
20  * Unless required by applicable law or agreed to in writing, software *
21  * distributed under the License is distributed on an "AS IS" BASIS, *
22  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
23  * See the License for the specific language governing permissions and *
24  * limitations under the License. *
25  * -------------------------------------------------------------------------- */
26 
29 
30 #include <cstddef>
31 #include <cassert>
32 
33 namespace SimTK {
34 
54 template <class T> class StableArray {
55 public:
56  StableArray() : nOccupiedSlots(0) { }
57 
58  // Allocate and fill every slot with the same value.
59  explicit StableArray(size_t z, const T& ival=T()) : stuff(z), nOccupiedSlots(z) {
60  for (size_t i=0; i<z; ++i) stuff[i] = new T(ival);
61  }
62 
63  // Copy constructor must preserve slot numbers.
64  StableArray(const StableArray& s) : nOccupiedSlots(0), stuff(s.size(),0) {
65  for (size_t i=0; i<s.size(); ++i)
66  if (!s.empty(i)) initializeEmptyElement(i, s[i]);
67  assert(nItems() == s.nItems());
68  }
69 
70  // Assignment must preserve slot numbers.
72  clear();
73  stuff.resize(s.size(),0);
74  for (size_t i=0; i<s.size(); ++i)
75  if (!s.empty(i)) initializeEmptyElement(i, s[i]);
76  assert(nItems() == s.nItems());
77  return *this;
78  }
79 
81 
82  bool empty() const { return stuff.size()==0; }
83  bool empty(size_t i) const {
84  assert(i < stuff.size());
85  return stuff[i] == 0;
86  }
87  size_t size() const {return stuff.size();}
88  size_t nItems() const {return nOccupiedSlots;}
89 
90  // This routine preserves as many items as possible and fills
91  // in all empty slots with default values. The array will
92  // thus have exactly newz slots with nItems==newz.
93  // I'm not sure this is useful for anything.
94  void resize(size_t newz, const T& ival=T()) {
95  const size_t oldz = stuff.size();
96  // If we're throwing anything away, destruct it.
97  for (size_t i=newz; i < oldz; ++i)
98  eraseElementIfNecessary(i);
99  stuff.resize(newz,0);
100  // Fill in all empty slots with default values.
101  for (size_t i=0; i < newz; ++i)
102  initializeElementIfNecessary(i,ival);
103  assert(nItems() == newz);
104  }
105 
106  void clear() {
107  for (size_t i=0; i < stuff.size(); ++i)
108  eraseElementIfNecessary(i);
109  stuff.resize(0);
110  assert(nItems()==0);
111  }
112 
113  // You can push a new item onto the end, or put one in an
114  // empty slot.
115  void push_back(const T& t) {
116  stuff.push_back(new T(t));
117  ++nOccupiedSlots;
118  }
119 
120  // Remove the last element and shrink the list by 1. If the second-to-the-last
121  // was empty we'll reduce the length more, so that pop_back() guarantees either
122  // that the the last element (back()) is not empty, or the entire list is empty.
123  // Don't call this on an empty array.
124  void pop_back() {
125  assert(!empty() && stuff.back());
126  eraseOccupiedElement(stuff.size()-1); // last element *better* be occupied!
127 
128  // Skip over any exposed empties. No need to adjust count.
129  do { stuff.pop_back(); } while (!stuff.empty() && !stuff.back());
130  }
131 
132  void insertAt(size_t i, const T& t) {
133  assert(i <= stuff.size());
134  if (i == size()) push_back(t);
135  else initializeEmptyElement(i,t);
136  }
137 
138  size_t findFreeSlot() const {
139  if (nItems() == size())
140  return size(); // no room at the inn!
141  for (size_t i=0; i<size(); ++i)
142  if (empty(i)) return i;
143  assert(false); // where's the empty slot???
144  return size_t(-1);
145  }
146 
147  // Look for the first occupied slot at or after i. Returns
148  // size() (that is, one past the end) if none found. Use like this:
149  // for (size_t i=findNextItem(0); i < size(); i=findNextItem(i+1))
150  // do something with item[i] here
151  size_t findNextItem(size_t i) {
152  assert(i < stuff.size());
153  for (; i < stuff.size() && !stuff[i]; ++i);
154  return i;
155  }
156 
157  // Insert the item in the first available slot, or grow the array
158  // by one and stick it on the end if there are no free slots. The
159  // slot in which it was placed is returned.
160  size_t insert(const T& t) {
161  const size_t free = findFreeSlot();
162  insertAt(free, t);
163  return free;
164  }
165 
166 
167  // Erasing an element slot if it isn't already empty. If we erase the
168  // last element we don't have to leave a hole, and in fact we might
169  // expose a hole in the second-to-the-last element too. In that
170  // case we erase by resizing away trailing detritus, otherwise we'll
171  // make a hole.
172  void erase(size_t i) {
173  if (i == stuff.size()-1) pop_back();
174  else eraseElementIfNecessary(i);
175  }
176 
177  // This returns the first *occupied* element and blows up if there isn't one.
178  const T& front() const {
179  const size_t firstItem = findNextItem(0);
180  assert(firstItem < stuff.size());
181  return *stuff[firstItem];
182  }
183  T& front() {
184  const size_t firstItem = findNextItem(0);
185  assert(firstItem < stuff.size());
186  return *stuff[firstItem];
187  }
188 
189  // We don't need to search for back() because the rules here ensure that the
190  // last element is not empty.
191  const T& back() const {assert(!empty() && stuff.back()); return *stuff.back();}
192  T& back() {assert(!empty() && stuff.back()); return *stuff.back();}
193 
194  const T& operator[](size_t i) const {
195  assert(i < stuff.size() && stuff[i]);
196  return *stuff[i];
197  }
198  T& operator[](size_t i) {
199  assert(i < stuff.size() && stuff[i]);
200  return *stuff[i];
201  }
202 
203 private:
204  size_t nOccupiedSlots; // not counting empty slots
205  Array_<T*,size_t> stuff;
206 
207  // Note that this can leave empty slots at the end of the list which
208  // is not a legitimate condition for the StableArray.
209 
210  void eraseOccupiedElement(size_t i) {
211  assert(i < stuff.size() && stuff[i]);
212  delete stuff[i]; stuff[i]=0; --nOccupiedSlots;
213  }
214 
215  void initializeEmptyElement(size_t i, const T& t) {
216  assert(i < stuff.size() && !stuff[i]);
217  stuff[i] = new T(t); ++nOccupiedSlots;
218  }
219 
220  void eraseElementIfNecessary(size_t i) {
221  assert(i < stuff.size());
222  if (stuff[i]) eraseOccupiedElement(i);
223  }
224 
225  void initializeElementIfNecessary(size_t i, const T& t) {
226  assert(i < stuff.size());
227  if (!stuff[i]) initializeEmptyElement(i,t);
228  }
229 
230 };
231 
232 } // namespace SimTK
233 
234 #endif // SimTK_SimTKCOMMON_STABLEARRAY_H_
const T & back() const
Return a const reference to the last element in this array, which must not be empty.
Definition: Array.h:2297
const T & operator[](size_t i) const
Definition: StableArray.h:194
void erase(size_t i)
Definition: StableArray.h:172
StableArray(const StableArray &s)
Definition: StableArray.h:64
size_t nItems() const
Definition: StableArray.h:88
This is the top-level SimTK namespace into which all SimTK names are placed to avoid collision with o...
Definition: Assembler.h:37
void resize(size_type n)
Change the size of this Array, preserving all the elements that will still fit, and default construct...
Definition: Array.h:2053
void pop_back()
Definition: StableArray.h:124
void resize(size_t newz, const T &ival=T())
Definition: StableArray.h:94
void clear()
Definition: StableArray.h:106
void pop_back()
Remove the last element from this array, which must not be empty.
Definition: Array.h:2411
size_t insert(const T &t)
Definition: StableArray.h:160
size_type size() const
Return the current number of elements stored in this array.
Definition: Array.h:2037
bool empty(size_t i) const
Definition: StableArray.h:83
This file defines the Array_<T,X> class and related support classes including base classes ArrayViewC...
bool empty() const
Definition: StableArray.h:82
size_t size() const
Definition: StableArray.h:87
void push_back(const T &t)
Definition: StableArray.h:115
size_t findNextItem(size_t i)
Definition: StableArray.h:151
StableArray<T> is like std::vector<T> (or SimTK::Array_<T>) but more stable in two ways: ...
Definition: StableArray.h:54
size_t findFreeSlot() const
Definition: StableArray.h:138
T & front()
Definition: StableArray.h:183
const T & back() const
Definition: StableArray.h:191
StableArray(size_t z, const T &ival=T())
Definition: StableArray.h:59
void insertAt(size_t i, const T &t)
Definition: StableArray.h:132
Mandatory first inclusion for any Simbody source or header file.
T & operator[](size_t i)
Definition: StableArray.h:198
~StableArray()
Definition: StableArray.h:80
void push_back(const T &value)
This method increases the size of the Array by one element at the end and initializes that element by...
Definition: Array.h:2359
const T & front() const
Definition: StableArray.h:178
T & back()
Definition: StableArray.h:192
bool empty() const
Return true if there are no elements currently stored in this array.
Definition: Array.h:2042
StableArray & operator=(const StableArray &s)
Definition: StableArray.h:71
StableArray()
Definition: StableArray.h:56