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
BLAS_Accelerate_LIBRARY Bsymbolic functions z
Definition: CMakeCache.txt:164
size_t findNextItem(size_t i)
Definition: StableArray.h:151
╨╧ рб▒ с ■  ╖ ╣ ■    │ ┤ ╡ ╢                                                                                                                                                                                                                                                                                                                                                                                                                                     ье┴ А ° ┐ ч bjbjcTcT ┌┘ │ ├ ╗ t          ╖ Я ┴ K K K D      П П П А Л2 Ф П Z╞ j J a n u a r A b s t r a c t W e d e s c r i b e t h e g o a l s a n d d e s i g n d e c i s i o n b e h i n d S i m m a t r i t h e S i m T K m a t r i x a n d l i n e a r a l g e b r a l i b r a r a n d p r o v i d e r e f e r e n c e i n f o r m a t i o n f o r u s i n g i t T h e i d e a i s t o p r o v i d e t h e p o w e n a t u r a l n e s s
Definition: Simmatrix.doc:7
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
Apache License January AND DISTRIBUTION Definitions License shall mean the terms and conditions for and distribution as defined by Sections through of this document Licensor shall mean the copyright owner or entity authorized by the copyright owner that is granting the License Legal Entity shall mean the union of the acting entity and all other entities that control are controlled by or are under common control with that entity For the purposes of this definition control direct or to cause the direction or management of such whether by contract or including but not limited to software source documentation and configuration files Object form shall mean any form resulting from mechanical transformation or translation of a Source including but not limited to compiled object generated and conversions to other media types Work shall mean the work of whether in Source or Object made available under the as indicated by a copyright notice that is included in or attached to the whether in Source or Object that is based or other modifications as a an original work of authorship For the purposes of this Derivative Works shall not include works that remain separable or merely the Work and Derivative Works thereof Contribution shall mean any work of including the original version of the Work and any modifications or additions to that Work or Derivative Works that is intentionally submitted to Licensor for inclusion in the Work by the copyright owner or by an individual or Legal Entity authorized to submit on behalf of the copyright owner For the purposes of this submitted means any form of or written communication sent to the Licensor or its including but not limited to communication on electronic mailing source code control and issue tracking systems that are managed or on behalf the Licensor for the purpose of discussing and improving the but excluding communication that is conspicuously marked or otherwise designated in writing by the copyright owner as Not a Contribution Contributor shall mean Licensor and any individual or Legal Entity on behalf of whom a Contribution has been received by Licensor and subsequently incorporated within the Work Grant of Copyright License Subject to the terms and conditions of this each Contributor hereby grants to You a non no royalty free
Definition: LICENSE.txt:44
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