1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
/**************************************************************************
* *
* Regina - A Normal Surface Theory Calculator *
* Computational Engine *
* *
* Copyright (c) 1999-2011, Ben Burton *
* For further details contact Ben Burton (bab@debian.org). *
* *
* This program is free software; you can redistribute it and/or *
* modify it under the terms of the GNU General Public License as *
* published by the Free Software Foundation; either version 2 of the *
* License, or (at your option) any later version. *
* *
* This program is distributed in the hope that it will be useful, but *
* WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
* General Public License for more details. *
* *
* You should have received a copy of the GNU General Public *
* License along with this program; if not, write to the Free *
* Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, *
* MA 02110-1301, USA. *
* *
**************************************************************************/
/* end stub */
/*! \file utilities/nmarkedvector.h
* \brief Provides space-efficient arrays with fast object-to-index lookup.
*/
#ifndef __NMARKEDVECTOR_H
#ifndef __DOXYGEN
#define __NMARKEDVECTOR_H
#endif
#include <vector>
#include "regina-core.h"
namespace regina {
/**
* \weakgroup utilities
* @{
*/
/**
* A base class for elements of NMarkedVector.
*
* NMarkedVector is a vector class that provides fast, space-efficient
* reverse lookup of array indices (i.e., given an object, find the
* index at which it is stored). The way it does this is to store the
* array indices in the object themselves.
*
* As a result, any type to be stored in an NMarkedVector must be derived
* from this class. This class provides a space to store the
* corresponding array index, and looks after access control so that
* only NMarkedVector can edit this index.
*
* Since indices are stored with the objects, it is possible to perform
* this reverse lookup by querying the object alone, without any
* reference to the actual vector. This can be done through the public
* routine markedIndex().
*
* The trade-off of course is that any object may not belong to more
* than one NMarkedVector at a time. Any attempt to do this will result
* in undefined behaviour.
*
* See NMarkedVector for further information.
*
* \ifacespython Not present.
*/
class REGINA_API NMarkedElement {
private:
long marking;
/**< The index in the NMarkedVector at which this object is
stored. If the object does not belong to an NMarkedVector,
the value of this field is undefined. */
public:
/**
* Returns the index at which this object is stored in an
* NMarkedVector. If this object does not belong to an
* NMarkedVector, the return value is undefined.
*
* @return the index at which this object is stored.
*/
inline long markedIndex() const;
template <typename T>
friend class NMarkedVector;
/**< Allow only NMarkedVector to edit the array index. */
};
/**
* A vector of objects with fast, space-efficient reverse lookup of
* array indices.
*
* This class derives from std::vector, and so provides fast forward
* lookups from array indices to objects. What NMarkedVector provides
* in addition to this is fast reverse lookups from objects back to
* array indices.
*
* The way this class is able to provide fast constant-time reverse
* lookups without consuming a great deal of space (unlike NIndexedArray
* and its space-hungry hash tables) is by storing array indices
* inside the objects themselves. As a result, there are two
* significant constraints:
*
* - This class can only store objects derived from NMarkedElement
* (which provides space for storing the array indices and handles
* their access control). In particular, it cannot store native types
* such as \c int or predefined types such as \c std::string.
*
* - An object can only belong to one NMarkedVector at a time. Any
* attempt to insert an object into more than one NMarkedVector at the
* same time results in undefined behaviour.
*
* Using this class is fairly simple. The class provides a restricted
* subset of the std::vector functionality, including \a iterator,
* \a const_iterator, \a begin, \a end, \a size, \a empty, \a front,
* \a back, operator [], and \a clear (this subset may grow over
* time if required). In addition, any const method of std::vector can
* be accessed through an explicit cast to const std::vector&. To
* perform a reverse lookup (find the index at which an array is stored),
* simply call the object's inherited method NMarkedElement::markedIndex().
*
* Note that, like its parent std::vector, this class performs no memory
* management. In particular, elements (which are pointers to real objects)
* are not destroyed when they are removed from a vector or when the vector
* is eventually destroyed.
*
* \pre The type \a T is a class derived from NMarkedElement.
*
* \ifacespython Not present.
*/
template <typename T>
class NMarkedVector : private std::vector<T*> {
public:
using typename std::vector<T*>::iterator;
using typename std::vector<T*>::const_iterator;
using typename std::vector<T*>::size_type;
using std::vector<T*>::begin;
using std::vector<T*>::end;
using std::vector<T*>::size;
using std::vector<T*>::empty;
using std::vector<T*>::operator [];
using std::vector<T*>::front;
using std::vector<T*>::back;
using std::vector<T*>::clear;
/**
* Constructs a new empty vector.
*/
inline NMarkedVector() {}
/**
* Casts this vector to a const std::vector, thus providing
* access to the entire const functionality of std::vector.
*
* @return a reference to this vector, cast as a const std::vector.
*/
inline const std::vector<T*>& operator ()() const {
return *this;
}
/**
* Pushes the given item onto the end of this vector. The array
* index stored inside \a item will be modified accordingly.
*
* The caller retains reponsibility for the ownership of \a item.
* This class will make no attempt to deallocate \a item when it
* is removed or when this vector is eventually destroyed.
*
* \pre The given item does not already belong to some other
* NMarkedVector.
*
* @param item the item to add to this vector.
*/
inline void push_back(T* item) {
item->marking = size();
std::vector<T*>::push_back(item);
}
/**
* Erases the item at the given position in this vector.
*
* The item will not be destroyed, and the (now irrelevant)
* index stored inside it will not be modified.
*
* \pre The given iterator points to an element of this vector.
*
* @param pos an iterator pointing to the element to erase.
* @return an iterator pointing to the element immediately
* after the element that was erased.
*/
inline typename std::vector<T*>::iterator erase(
typename std::vector<T*>::iterator pos) {
typename std::vector<T*>::iterator it = pos;
for (++it; it != end(); ++it)
--((*it)->marking);
return std::vector<T*>::erase(pos);
}
/**
* Erases all items in the given range in this vector.
*
* The items will not be destroyed, and the (now irrelevant)
* indices stored inside them will not be modified.
*
* \pre The given iterators describe a valid range in this vector.
*
* @param first an iterator pointing to the first element to erase.
* @param last an iterator pointing just beyond the last element
* to erase.
* @return an iterator pointing to the element immediately
* after the elements that were erased.
*/
inline typename std::vector<T*>::iterator erase(
typename std::vector<T*>::iterator first,
typename std::vector<T*>::iterator last) {
for (typename std::vector<T*>::iterator it = last;
it != end(); ++it)
(*it)->marking -= (first - last);
return std::vector<T*>::erase(first, last);
}
/**
* Swaps the contents of this and the given vector.
*
* @param other the vector whose contents are to be swapped with this.
*/
inline void swap(NMarkedVector<T>& other) {
std::vector<T*>::swap(other);
}
};
/*@}*/
// Inline functions for NMarkedElement
inline long NMarkedElement::markedIndex() const {
return marking;
}
} // namespace regina
#endif
|
