1 /*
2 * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * All rights reserved. Distributed under the terms of the MIT license.
4 */
5 #ifndef _VECTOR_SET_H
6 #define _VECTOR_SET_H
7
8 #include <stdlib.h>
9 #include <string.h>
10
11 #include <SupportDefs.h>
12
13 #include <util/kernel_cpp.h>
14 #include <Vector.h>
15
16 // element orders
17 namespace VectorSetOrder {
18 template<typename Value> class Ascending;
19 template<typename Value> class Descending;
20 }
21
22 // for convenience
23 #define _VECTOR_SET_TEMPLATE_LIST template<typename Value, \
24 typename ElementOrder>
25 #define _VECTOR_SET_CLASS_NAME VectorSet<Value, ElementOrder>
26 #define _VECTOR_SET_CLASS_TYPE typename VectorSet<Value, ElementOrder>
27
28 /*!
29 \class VectorSet
30 \brief A generic vector-based set implementation.
31
32 The elements of the set are ordered according to the supplied
33 compare function object. Default is ascending order.
34 */
35 template<typename Value,
36 typename ElementOrder = VectorSetOrder::Ascending<Value> >
37 class VectorSet {
38 private:
39 typedef Vector<Value> ElementVector;
40
41 public:
42 typedef typename ElementVector::Iterator Iterator;
43 typedef typename ElementVector::ConstIterator ConstIterator;
44
45 private:
46 static const size_t kDefaultChunkSize = 10;
47 static const size_t kMaximalChunkSize = 1024 * 1024;
48
49 public:
50 VectorSet(size_t chunkSize = kDefaultChunkSize);
51 // TODO: Copy constructor, assignment operator.
52 ~VectorSet();
53
54 status_t Insert(const Value &value, bool replace = true);
55
56 int32 Remove(const Value &value);
57 Iterator Erase(const Iterator &iterator);
58
59 inline int32 Count() const;
60 inline bool IsEmpty() const;
61 void MakeEmpty();
62
63 inline Iterator Begin();
64 inline ConstIterator Begin() const;
65 inline Iterator End();
66 inline ConstIterator End() const;
67 inline Iterator Null();
68 inline ConstIterator Null() const;
69
70 Iterator Find(const Value &value);
71 ConstIterator Find(const Value &value) const;
72 Iterator FindClose(const Value &value, bool less);
73 ConstIterator FindClose(const Value &value, bool less) const;
74
75 private:
76 int32 _FindInsertionIndex(const Value &value, bool &exists) const;
77
78 private:
79 ElementVector fElements;
80 ElementOrder fCompare;
81 };
82
83
84 // VectorSet
85
86 // constructor
87 /*! \brief Creates an empty set.
88 \param chunkSize The granularity for the underlying vector's capacity,
89 i.e. the minimal number of elements the capacity grows or shrinks
90 when necessary.
91 */
92 _VECTOR_SET_TEMPLATE_LIST
VectorSet(size_t chunkSize)93 _VECTOR_SET_CLASS_NAME::VectorSet(size_t chunkSize)
94 : fElements(chunkSize)
95 {
96 }
97
98 // destructor
99 /*! \brief Frees all resources associated with the object.
100
101 The contained elements are destroyed. Note, that, if the element
102 type is a pointer type, only the pointer is destroyed, not the object
103 it points to.
104 */
105 _VECTOR_SET_TEMPLATE_LIST
~VectorSet()106 _VECTOR_SET_CLASS_NAME::~VectorSet()
107 {
108 }
109
110 // Insert
111 /*! \brief Inserts a copy of the the supplied value.
112
113 If an element with the supplied value is already in the set, the
114 operation will not fail, but return \c B_OK. \a replace specifies
115 whether the element shall be replaced with the supplied in such a case.
116 Otherwise \a replace is ignored.
117
118 \param value The value to be inserted.
119 \param replace If the an element with this value does already exist and
120 \a replace is \c true, the element is replaced, otherwise left
121 untouched.
122 \return
123 - \c B_OK: Everything went fine.
124 - \c B_NO_MEMORY: Insufficient memory for this operation.
125 */
126 _VECTOR_SET_TEMPLATE_LIST
127 status_t
Insert(const Value & value,bool replace)128 _VECTOR_SET_CLASS_NAME::Insert(const Value &value, bool replace)
129 {
130 bool exists = false;
131 int32 index = _FindInsertionIndex(value, exists);
132 if (exists) {
133 if (replace)
134 fElements[index] = value;
135 return B_OK;
136 }
137 return fElements.Insert(value, index);
138 }
139
140 // Remove
141 /*! \brief Removes the element with the supplied value.
142 \param value The value of the element to be removed.
143 \return The number of removed occurrences, i.e. \c 1, if the set
144 contained an element with the value, \c 0 otherwise.
145 */
146 _VECTOR_SET_TEMPLATE_LIST
147 int32
Remove(const Value & value)148 _VECTOR_SET_CLASS_NAME::Remove(const Value &value)
149 {
150 bool exists = false;
151 int32 index = _FindInsertionIndex(value, exists);
152 if (!exists)
153 return 0;
154 fElements.Erase(index);
155 return 1;
156 }
157
158 // Erase
159 /*! \brief Removes the element at the given position.
160 \param iterator An iterator referring to the element to be removed.
161 \return An iterator referring to the element succeeding the removed
162 one (End(), if it was the last element that has been
163 removed), or Null(), if \a iterator was an invalid iterator
164 (in this case including End()).
165 */
166 _VECTOR_SET_TEMPLATE_LIST
167 _VECTOR_SET_CLASS_TYPE::Iterator
Erase(const Iterator & iterator)168 _VECTOR_SET_CLASS_NAME::Erase(const Iterator &iterator)
169 {
170 return fElements.Erase(iterator);
171 }
172
173 // Count
174 /*! \brief Returns the number of elements the set contains.
175 \return The number of elements the set contains.
176 */
177 _VECTOR_SET_TEMPLATE_LIST
178 inline
179 int32
Count()180 _VECTOR_SET_CLASS_NAME::Count() const
181 {
182 return fElements.Count();
183 }
184
185 // IsEmpty
186 /*! \brief Returns whether the set is empty.
187 \return \c true, if the set is empty, \c false otherwise.
188 */
189 _VECTOR_SET_TEMPLATE_LIST
190 inline
191 bool
IsEmpty()192 _VECTOR_SET_CLASS_NAME::IsEmpty() const
193 {
194 return fElements.IsEmpty();
195 }
196
197 // MakeEmpty
198 /*! \brief Removes all elements from the set.
199 */
200 _VECTOR_SET_TEMPLATE_LIST
201 void
MakeEmpty()202 _VECTOR_SET_CLASS_NAME::MakeEmpty()
203 {
204 fElements.MakeEmpty();
205 }
206
207 // Begin
208 /*! \brief Returns an iterator referring to the beginning of the set.
209
210 If the set is not empty, Begin() refers to its first element,
211 otherwise it is equal to End() and must not be dereferenced!
212
213 \return An iterator referring to the beginning of the set.
214 */
215 _VECTOR_SET_TEMPLATE_LIST
216 inline
217 _VECTOR_SET_CLASS_TYPE::Iterator
Begin()218 _VECTOR_SET_CLASS_NAME::Begin()
219 {
220 return fElements.Begin();
221 }
222
223 // Begin
224 /*! \brief Returns an iterator referring to the beginning of the set.
225
226 If the set is not empty, Begin() refers to its first element,
227 otherwise it is equal to End() and must not be dereferenced!
228
229 \return An iterator referring to the beginning of the set.
230 */
231 _VECTOR_SET_TEMPLATE_LIST
232 inline
233 _VECTOR_SET_CLASS_TYPE::ConstIterator
Begin()234 _VECTOR_SET_CLASS_NAME::Begin() const
235 {
236 return fElements.Begin();
237 }
238
239 // End
240 /*! \brief Returns an iterator referring to the end of the set.
241
242 The position identified by End() is the one succeeding the last
243 element, i.e. it must not be dereferenced!
244
245 \return An iterator referring to the end of the set.
246 */
247 _VECTOR_SET_TEMPLATE_LIST
248 inline
249 _VECTOR_SET_CLASS_TYPE::Iterator
End()250 _VECTOR_SET_CLASS_NAME::End()
251 {
252 return fElements.End();
253 }
254
255 // End
256 /*! \brief Returns an iterator referring to the end of the set.
257
258 The position identified by End() is the one succeeding the last
259 element, i.e. it must not be dereferenced!
260
261 \return An iterator referring to the end of the set.
262 */
263 _VECTOR_SET_TEMPLATE_LIST
264 inline
265 _VECTOR_SET_CLASS_TYPE::ConstIterator
End()266 _VECTOR_SET_CLASS_NAME::End() const
267 {
268 return fElements.End();
269 }
270
271 // Null
272 /*! \brief Returns an invalid iterator.
273
274 Null() is used as a return value, if something went wrong. It must
275 neither be incremented or decremented nor dereferenced!
276
277 \return An invalid iterator.
278 */
279 _VECTOR_SET_TEMPLATE_LIST
280 inline
281 _VECTOR_SET_CLASS_TYPE::Iterator
Null()282 _VECTOR_SET_CLASS_NAME::Null()
283 {
284 return fElements.Null();
285 }
286
287 // Null
288 /*! \brief Returns an invalid iterator.
289
290 Null() is used as a return value, if something went wrong. It must
291 neither be incremented or decremented nor dereferenced!
292
293 \return An invalid iterator.
294 */
295 _VECTOR_SET_TEMPLATE_LIST
296 inline
297 _VECTOR_SET_CLASS_TYPE::ConstIterator
Null()298 _VECTOR_SET_CLASS_NAME::Null() const
299 {
300 return fElements.Null();
301 }
302
303 // Find
304 /*! \brief Returns an iterator referring to the element with the
305 specified value.
306 \param value The value of the element to be found.
307 \return An iterator referring to the found element, or End(), if the
308 set doesn't contain any element with the given value.
309 */
310 _VECTOR_SET_TEMPLATE_LIST
311 _VECTOR_SET_CLASS_TYPE::Iterator
Find(const Value & value)312 _VECTOR_SET_CLASS_NAME::Find(const Value &value)
313 {
314 bool exists = false;
315 int32 index = _FindInsertionIndex(value, exists);
316 if (!exists)
317 return fElements.End();
318 return fElements.IteratorForIndex(index);
319 }
320
321 // Find
322 /*! \brief Returns an iterator referring to the element with the
323 specified value.
324 \param value The value of the element to be found.
325 \return An iterator referring to the found element, or End(), if the
326 set doesn't contain any element with the given value.
327 */
328 _VECTOR_SET_TEMPLATE_LIST
329 _VECTOR_SET_CLASS_TYPE::ConstIterator
Find(const Value & value)330 _VECTOR_SET_CLASS_NAME::Find(const Value &value) const
331 {
332 bool exists = false;
333 int32 index = _FindInsertionIndex(value, exists);
334 if (!exists)
335 return fElements.End();
336 return fElements.IteratorForIndex(index);
337 }
338
339 // FindClose
340 /*! \brief Returns an iterator referring to the element with a value closest
341 to the specified one.
342
343 If the set contains an element with the specified value, an iterator
344 to it is returned. Otherwise \a less indicates whether an iterator to
345 the directly smaller or greater element shall be returned.
346
347 If \a less is \c true and the first element in the set has a greater
348 value than the specified one, End() is returned. Similarly, when \a less
349 is \c false and the last element is smaller. Find() invoked on an empty
350 set always returns End().
351
352 Note, that the element order used for the set is specified as template
353 argument to the class. Default is ascending order. Descending order
354 inverts the meaning of \a less, i.e. if \c true, greater values will
355 be returned, since they are smaller ones according to the order.
356
357 \param value The value of the element to be found.
358 \return An iterator referring to the found element, or End(), if the
359 set doesn't contain any element with the given value or a close
360 one according to \a less.
361 */
362 _VECTOR_SET_TEMPLATE_LIST
363 _VECTOR_SET_CLASS_TYPE::Iterator
FindClose(const Value & value,bool less)364 _VECTOR_SET_CLASS_NAME::FindClose(const Value &value, bool less)
365 {
366 bool exists = false;
367 int32 index = _FindInsertionIndex(value, exists);
368 // If not found, the index _FindInsertionIndex() returns will point to
369 // an element with a greater value or to End(). So, no special handling
370 // is needed for !less.
371 if (exists || !less)
372 return fElements.IteratorForIndex(index);
373 // An element with a smaller value is desired. The previous one (if any)
374 // will do.
375 if (index > 0)
376 return fElements.IteratorForIndex(index - 1);
377 return fElements.End();
378 }
379
380 // FindClose
381 /*! \brief Returns an iterator referring to the element with a value closest
382 to the specified one.
383
384 If the set contains an element with the specified value, an iterator
385 to it is returned. Otherwise \a less indicates whether an iterator to
386 the directly smaller or greater element shall be returned.
387
388 If \a less is \c true and the first element in the set has a greater
389 value than the specified one, End() is returned. Similarly, when \a less
390 is \c false and the last element is smaller. Find() invoked on an empty
391 set always returns End().
392
393 Note, that the element order used for the set is specified as template
394 argument to the class. Default is ascending order. Descending order
395 inverts the meaning of \a less, i.e. if \c true, greater values will
396 be returned, since they are smaller ones according to the order.
397
398 \param value The value of the element to be found.
399 \return An iterator referring to the found element, or End(), if the
400 set doesn't contain any element with the given value or a close
401 one according to \a less.
402 */
403 _VECTOR_SET_TEMPLATE_LIST
404 _VECTOR_SET_CLASS_TYPE::ConstIterator
FindClose(const Value & value,bool less)405 _VECTOR_SET_CLASS_NAME::FindClose(const Value &value, bool less) const
406 {
407 bool exists = false;
408 int32 index = _FindInsertionIndex(value, exists);
409 // If not found, the index _FindInsertionIndex() returns will point to
410 // an element with a greater value or to End(). So, no special handling
411 // is needed for !less.
412 if (exists || !less)
413 return fElements.IteratorForIndex(index);
414 // An element with a smaller value is desired. The previous one (if any)
415 // will do.
416 if (index > 0)
417 return fElements.IteratorForIndex(index - 1);
418 return fElements.End();
419 }
420
421 // _FindInsertionIndex
422 /*! \brief Finds the index at which the element with the supplied value is
423 located or at which it would need to be inserted.
424 \param value The value.
425 \param exists Is set to \c true, if the set does already contain an
426 element with that value.
427 \return The index at which the element with the supplied value is
428 located or at which it would need to be inserted.
429 */
430 _VECTOR_SET_TEMPLATE_LIST
431 int32
_FindInsertionIndex(const Value & value,bool & exists)432 _VECTOR_SET_CLASS_NAME::_FindInsertionIndex(const Value &value,
433 bool &exists) const
434 {
435 // binary search
436 int32 lower = 0;
437 int32 upper = Count();
438 while (lower < upper) {
439 int32 mid = (lower + upper) / 2;
440 int cmp = fCompare(fElements[mid], value);
441 if (cmp < 0)
442 lower = mid + 1;
443 else
444 upper = mid;
445 }
446 exists = (lower < Count() && fCompare(value, fElements[lower]) == 0);
447 return lower;
448 }
449
450
451 // element orders
452
453 namespace VectorSetOrder {
454
455 // Ascending
456 /*! \brief A compare function object implying and ascending order.
457
458 The < operator must be defined on the template argument.
459 */
460 template<typename Value>
461 class Ascending {
462 public:
operator()463 inline int operator()(const Value &a, const Value &b) const
464 {
465 if (a < b)
466 return -1;
467 else if (b < a)
468 return 1;
469 return 0;
470 }
471 };
472
473 // Descending
474 /*! \brief A compare function object implying and descending order.
475
476 The < operator must be defined on the template argument.
477 */
478 template<typename Value>
479 class Descending {
480 public:
operator()481 inline int operator()(const Value &a, const Value &b) const
482 {
483 if (a < b)
484 return -1;
485 else if (b < a)
486 return 1;
487 return 0;
488 }
489 };
490
491 } // namespace VectorSetOrder
492
493 #endif // _VECTOR_SET_H
494