Simbody 3.7
Loading...
Searching...
No Matches
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
33namespace SimTK {
34
54template <class T> class StableArray {
55public:
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
203private:
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_
This file defines the Array_<T,X> class and related support classes including base classes ArrayViewC...
Mandatory first inclusion for any Simbody source or header file.
The Array_<T> container class is a plug-compatible replacement for the C++ standard template library ...
Definition Array.h:1520
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:2399
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:2091
void pop_back()
Remove the last element from this array, which must not be empty.
Definition Array.h:2487
size_type size() const
Return the current number of elements stored in this array.
Definition Array.h:2075
const T & back() const
Return a const reference to the last element in this array, which must not be empty.
Definition Array.h:2337
bool empty() const
Return true if there are no elements currently stored in this array.
Definition Array.h:2080
StableArray<T> is like std::vector<T> (or SimTK::Array_<T>) but more stable in two ways:
Definition StableArray.h:54
T & front()
Definition StableArray.h:183
size_t nItems() const
Definition StableArray.h:88
StableArray(const StableArray &s)
Definition StableArray.h:64
size_t findFreeSlot() const
Definition StableArray.h:138
StableArray(size_t z, const T &ival=T())
Definition StableArray.h:59
StableArray()
Definition StableArray.h:56
void clear()
Definition StableArray.h:106
bool empty() const
Definition StableArray.h:82
StableArray & operator=(const StableArray &s)
Definition StableArray.h:71
const T & operator[](size_t i) const
Definition StableArray.h:194
void erase(size_t i)
Definition StableArray.h:172
T & back()
Definition StableArray.h:192
void pop_back()
Definition StableArray.h:124
void resize(size_t newz, const T &ival=T())
Definition StableArray.h:94
size_t insert(const T &t)
Definition StableArray.h:160
void push_back(const T &t)
Definition StableArray.h:115
const T & back() const
Definition StableArray.h:191
const T & front() const
Definition StableArray.h:178
T & operator[](size_t i)
Definition StableArray.h:198
bool empty(size_t i) const
Definition StableArray.h:83
size_t findNextItem(size_t i)
Definition StableArray.h:151
size_t size() const
Definition StableArray.h:87
~StableArray()
Definition StableArray.h:80
void insertAt(size_t i, const T &t)
Definition StableArray.h:132
This is the top-level SimTK namespace into which all SimTK names are placed to avoid collision with o...
Definition Assembler.h:37