[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

random_access_set.hxx
1/************************************************************************/
2/* */
3/* Copyright 2014 by Thorsten Beier and Ullrich Koethe */
4/* */
5/* This file is part of the VIGRA computer vision library. */
6/* The VIGRA Website is */
7/* http://hci.iwr.uni-heidelberg.de/vigra/ */
8/* Please direct questions, bug reports, and contributions to */
9/* ullrich.koethe@iwr.uni-heidelberg.de or */
10/* vigra@informatik.uni-hamburg.de */
11/* */
12/* Permission is hereby granted, free of charge, to any person */
13/* obtaining a copy of this software and associated documentation */
14/* files (the "Software"), to deal in the Software without */
15/* restriction, including without limitation the rights to use, */
16/* copy, modify, merge, publish, distribute, sublicense, and/or */
17/* sell copies of the Software, and to permit persons to whom the */
18/* Software is furnished to do so, subject to the following */
19/* conditions: */
20/* */
21/* The above copyright notice and this permission notice shall be */
22/* included in all copies or substantial portions of the */
23/* Software. */
24/* */
25/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27/* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28/* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29/* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30/* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32/* OTHER DEALINGS IN THE SOFTWARE. */
33/* */
34/************************************************************************/
35
36
37//! @cond Doxygen_Suppress
38#pragma once
39#ifndef VIGRA_RANDOM_ACCESS_SET_HXX
40#define VIGRA_RANDOM_ACCESS_SET_HXX
41
42#include <vector>
43#include <algorithm>
44#include <utility>
45
46namespace vigra {
47
48/// set with O(n) insert and O(1) access
49///
50/// \tparam Key key and value type of the set
51/// \tparam Alloc allocator of the set
52/// RandomAccessSet has the same interface as std::set.
53/// In addition, there is operator[].
54/// \warning Values in set must not be changend through the mutable iterator
55/// because doing so would potentially change the order of the values
56/// \\ingroup datastructures
57template<class Key,class Compare=std::less<Key>,class Alloc=std::allocator<Key> >
58class RandomAccessSet {
59private:
60 /// type of the underlying vector
61 typedef std::vector<Key,Alloc> VectorType;
62
63public:
64 // typedefs
65 /// key type of the set
66 typedef Key key_type;
67 /// value type of the set
68 typedef Key ValueType;
69 /// value type of the set
70 typedef Key value_type;
71 /// comperator
72 typedef Compare key_compare;
73 /// value comperator
74 typedef Compare value_compare;
75 /// acclocator
76 typedef Alloc allocator_type;
77 /// const reference type
78 typedef const Key& const_reference;
79 /// iterator type
80 typedef typename VectorType::iterator iterator;
81 /// const iterator type
82 typedef typename VectorType::const_iterator const_iterator;
83 /// size type
84 typedef typename VectorType::size_type size_type;
85 /// difference type
86 typedef typename VectorType::difference_type difference_type;
87 /// const pointer type
88 typedef typename VectorType::const_pointer const_pointer;
89 /// const reverse iterator
90 typedef typename VectorType::const_reverse_iterator const_reverse_iterator;
91
92 // member functions:
93 // constructor
94 RandomAccessSet(const size_t, const Compare& compare=Compare(), const Alloc& alloc=Alloc());
95 RandomAccessSet(const Compare& compare=Compare(), const Alloc& alloc=Alloc());
96 template <class InputIterator>
97 RandomAccessSet(InputIterator, InputIterator, const Compare& compare =Compare(), const Alloc & alloc=Alloc());
98 RandomAccessSet(const RandomAccessSet&);
99
100 // operator=
101 RandomAccessSet& operator=(const RandomAccessSet &);
102 // operator[]
103 const value_type& operator[](const size_type) const;
104 // iterators
105 const_iterator begin() const;
106 const_iterator end() const;
107 const_iterator rbegin() const;
108 const_iterator rend() const;
109
110 iterator begin();
111 iterator end();
112 iterator rbegin();
113 iterator rend();
114 bool empty() const;
115 size_type size() const;
116 size_type max_size() const;
117 std::pair< const_iterator,bool> insert(const value_type&);
118 template <class InputIterator>
119 void insert(InputIterator, InputIterator);
120 const_iterator insert(const_iterator , const value_type&);
121 void erase(iterator position);
122 size_type erase(const key_type& );
123 void erase( const_iterator, const_iterator);
124 void swap(RandomAccessSet&);
125 void clear();
126 key_compare key_comp() const;
127 value_compare value_comp() const;
128 const_iterator find(const key_type&) const;
129 iterator find(const key_type&);
130 size_type count(const key_type&) const;
131 const_iterator lower_bound(const key_type&) const;
132 const_iterator upper_bound(const key_type&) const;
133 std::pair<const_iterator,const_iterator> equal_range(const key_type&) const;
134 iterator lower_bound(const key_type&) ;
135 iterator upper_bound(const key_type&) ;
136 std::pair<iterator,iterator> equal_range(const key_type&) ;
137 allocator_type get_allocator() const;
138
139 // std vector functions
140 void reserve(const size_t size){
141 vector_.reserve(size);
142 }
143 size_t capacity()const{
144 return vector_.capacity();
145 }
146
147 template<class SET>
148 void assignFromSet(const SET & set){
149 vector_.assign(set.begin(),set.end());
150 }
151
152private:
153 std::vector<Key> vector_;
154 Compare compare_;
155};
156
157/// constructor
158/// \param reserveSize reserve /allocate space
159/// \param compare comperator
160/// \param alloc allocator
161template<class Key, class Compare, class Alloc>
162inline
163RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
164(
165 const size_t reserveSize,
166 const Compare& compare,
167 const Alloc& alloc
168)
169: vector_(alloc),
170 compare_(compare) {
171 vector_.reserve(reserveSize);
172}
173
174/// const access values
175/// \param index index of the value in the set
176/// \return value / key at the position index
177template<class Key, class Compare, class Alloc>
178inline const typename RandomAccessSet<Key,Compare,Alloc>::value_type&
179RandomAccessSet<Key,Compare,Alloc>::operator[]
180(
181 const typename RandomAccessSet<Key,Compare,Alloc>::size_type index
182) const
183{
184 return vector_[index];
185}
186
187/// constructor
188/// \param compare comperator
189/// \allloc allocator
190template<class Key, class Compare, class Alloc>
191inline
192RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
193(
194 const Compare& compare,
195 const Alloc& alloc
196)
197: vector_(alloc),
198 compare_(compare)
199{}
200
201/// constructor
202/// \tparam InputIterator (key/value) input iterator
203/// \param beginInput
204/// \param endInput
205template<class Key, class Compare, class Alloc>
206template <class InputIterator>
207inline
208RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
209(
210 InputIterator beginInput,
211 InputIterator endInput,
212 const Compare& compare,
213 const Alloc& alloc
214)
215: vector_(alloc),
216 compare_(compare)
217{
218 while(beginInput!=endInput) {
219 this->insert(*beginInput);
220 ++beginInput;
221 }
222}
223
224/// copy constructor
225/// \param src other random access set
226template<class Key, class Compare, class Alloc>
227inline
228RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
229(
230 const RandomAccessSet<Key,Compare,Alloc>& src
231)
232: vector_(src.vector_),
233 compare_(src.compare_) {
234}
235
236/// assignment operator
237/// \param src other random access set
238template<class Key, class Compare, class Alloc>
239inline RandomAccessSet<Key,Compare,Alloc>&
240RandomAccessSet<Key,Compare,Alloc>::operator=
241(
242 const RandomAccessSet<Key,Compare,Alloc> & src
243)
244{
245 if(this!=&src) {
246 vector_=src.vector_;
247 compare_=src.compare_;
248 }
249 return *this;
250}
251
252/// const begin iterator
253/// \returns begin iterator
254template<class Key, class Compare, class Alloc>
255inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
256RandomAccessSet<Key,Compare,Alloc>::begin() const
257{
258 return vector_.begin();
259}
260
261/// const end iterator
262/// \returns end iterator
263template<class Key, class Compare, class Alloc>
264inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
265RandomAccessSet<Key,Compare,Alloc>::end() const
266{
267 return vector_.end();
268}
269/// reverse const begin iterator
270/// \returns reverse begin iterator
271template<class Key, class Compare, class Alloc>
272inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
273RandomAccessSet<Key,Compare,Alloc>::rbegin() const
274{
275 return vector_.rbegin();
276}
277
278/// reverse const end iterator
279/// \param reverse end iterator
280template<class Key, class Compare, class Alloc>
281inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
282RandomAccessSet<Key,Compare,Alloc>::rend() const
283{
284 return vector_.rend();
285}
286
287/// begin iterator
288/// \param begin iterator
289template<class Key, class Compare, class Alloc>
290inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
291RandomAccessSet<Key,Compare,Alloc>::begin()
292{
293 return vector_.begin();
294}
295
296/// end iterator
297/// \param end iterator
298template<class Key, class Compare, class Alloc>
299inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
300RandomAccessSet<Key,Compare,Alloc>::end()
301{
302 return vector_.end();
303}
304
305/// reverse begin iterator
306/// \param reverse begin iterator
307template<class Key, class Compare, class Alloc>
308inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
309RandomAccessSet<Key,Compare,Alloc>::rbegin()
310{
311 return vector_.rbegin();
312}
313
314/// reverse end iterator
315/// \param reverse end iterator
316template<class Key, class Compare, class Alloc>
317inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
318RandomAccessSet<Key,Compare,Alloc>::rend()
319{
320 return vector_.rend();
321}
322
323/// query if the set is empty
324/// \return true if empty
325template<class Key, class Compare, class Alloc>
326inline bool
327RandomAccessSet<Key,Compare,Alloc>::empty() const
328{
329 return vector_.empty();
330}
331
332/// number of elements of the set
333/// \returns number of elements in the set
334template<class Key, class Compare, class Alloc>
335inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
336RandomAccessSet<Key,Compare,Alloc>::size() const
337{
338 return vector_.size();
339}
340
341/// maximum size of the underlying container
342/// \return the maximum size
343template<class Key, class Compare, class Alloc>
344inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
345RandomAccessSet<Key,Compare,Alloc>::max_size() const
346{
347 return vector_.max_size();
348}
349
350// modifiers
351/// insert an element into the set
352///
353/// \param value element to insert
354/// \return pair in which the first entry is an iterator pointing to inserted
355/// value and the second entry is true iff the value had not already been in the
356/// set
357template<class Key, class Compare, class Alloc>
358inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::const_iterator,bool>
359RandomAccessSet<Key,Compare,Alloc>::insert
360(
361 const typename RandomAccessSet<Key,Compare,Alloc>::value_type& value
362) {
363 bool found(true);
364 iterator i(lower_bound(static_cast<Key>(value)));
365 if(i == end() || compare_(static_cast<Key>(value), *i)) {
366 i = vector_.insert(i, static_cast<Key>(value));
367 found = false;
368 }
369 return std::make_pair(i, !found);
370}
371
372/// insert a sequence of elements
373///
374/// \param first iterator to the first element
375/// \param last iterator to the last element
376template<class Key, class Compare, class Alloc>
377template <class InputIterator>
378inline void
379RandomAccessSet<Key,Compare,Alloc>::insert
380(
381 InputIterator first,
382 InputIterator last
383)
384{
385 while(first!=last) {
386 this->insert(*first);
387 ++first;
388 }
389}
390
391/// insert an element with a hint for the position. If the positional hint is
392/// consistent with value_comp() / the value / the neighbours, the element is
393/// inserted at position, otherwise we fall back to insertion without hint.
394///
395/// \param position iterator to the position
396/// \param value element to insert
397template<class Key, class Compare, class Alloc>
398inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
399RandomAccessSet<Key,Compare,Alloc>::insert
400(
401 typename RandomAccessSet<Key,Compare,Alloc>::const_iterator position,
402 const typename RandomAccessSet<Key,Compare,Alloc>::value_type& value
403)
404{
405 if((position == begin() || value_comp()(*(position-1),value))
406 && (position == end() || value_comp()(value, *position))) {
407 return vector_.insert(position, value);
408 }
409 return insert(value).first;
410}
411
412/// erase an element
413/// \param position iterator to the position
414template<class Key, class Compare, class Alloc>
415inline void
416RandomAccessSet<Key,Compare,Alloc>::erase
417(
418 typename RandomAccessSet<Key,Compare,Alloc>::iterator position
419)
420{
421 vector_.erase(position);
422}
423
424/// erease and element
425/// \param x element
426template<class Key, class Compare, class Alloc>
427inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
428RandomAccessSet<Key,Compare,Alloc>::erase
429(
430 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& x
431)
432{
433 iterator i =find(x);
434 if(i!=vector_.end())
435 {
436 erase(i);
437 return 1;
438 }
439 return 0;
440}
441
442/// erase a sequence of elements
443/// \param first iterator to the beginning of the sequence to erase
444/// \param last iterator to the end of the sequence to erase
445template<class Key, class Compare, class Alloc>
446inline void
447RandomAccessSet<Key,Compare,Alloc>::erase
448(
449 const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator first,
450 const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator last
451)
452{
453 vector_.erase(first,last);
454}
455
456/// swap random access sets
457/// \param rhs set to swap with
458template<class Key, class Compare, class Alloc>
459inline void
460RandomAccessSet<Key,Compare,Alloc>::swap
461(
462 RandomAccessSet<Key,Compare,Alloc>& rhs
463)
464{
465 vector_.swap(rhs.vector_);
466 std::swap(compare_, rhs.compare_);
467}
468
469/// clear the set
470///
471/// erases all elements
472template<class Key, class Compare, class Alloc>
473inline void
474RandomAccessSet<Key,Compare,Alloc>::clear()
475{
476 vector_.clear();
477}
478
479/// key comparator
480/// \return key comparator
481template<class Key, class Compare, class Alloc>
482inline typename RandomAccessSet<Key,Compare,Alloc>::key_compare
483RandomAccessSet<Key,Compare,Alloc>::key_comp() const
484{
485 return compare_;
486}
487
488/// value comparator
489/// \return value comparator
490template<class Key, class Compare, class Alloc>
491inline typename RandomAccessSet<Key,Compare,Alloc>::value_compare
492RandomAccessSet<Key,Compare,Alloc>::value_comp() const
493{
494 return compare_;
495}
496
497/// find an element
498/// \param value element
499/// \return const_iterator to the position where element was found or end
500/// iterator if the element was not found
501template<class Key, class Compare, class Alloc>
502inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
503RandomAccessSet<Key,Compare,Alloc>::find
504(
505 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
506) const
507{
508 const_iterator i(lower_bound(value));
509 if (i != end() && compare_(value, *i))
510 {
511 i = end();
512 }
513 return i;
514}
515
516/// find an element
517/// \param value element
518/// \return iterator to the position where the element was found or end
519/// iterator if the element was not found
520template<class Key, class Compare, class Alloc>
521inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
522RandomAccessSet<Key,Compare,Alloc>::find
523(
524 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
525)
526{
527 iterator i(lower_bound(value));
528 if (i != end() && compare_(value, *i))
529 {
530 i = end();
531 }
532 return i;
533}
534
535/// count elements
536/// \param element
537/// \return zero or one
538template<class Key, class Compare, class Alloc>
539inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
540RandomAccessSet<Key,Compare,Alloc>::count
541(
542 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
543) const
544{
545 return find(value) != end() ? 1 : 0;
546}
547
548/// lower bound
549/// \param value
550/// \return iterator to lower bound
551template<class Key, class Compare, class Alloc>
552inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
553RandomAccessSet<Key,Compare,Alloc>::lower_bound
554(
555 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
556) const
557{
558 return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
559}
560
561/// lower bound
562/// \param value
563/// \return iterator to lower bound
564template<class Key, class Compare, class Alloc>
565inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
566RandomAccessSet<Key,Compare,Alloc>::lower_bound
567(
568 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
569)
570{
571 return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
572}
573
574/// upper bound
575/// \param value
576/// \return iterator to upper bound
577template<class Key, class Compare, class Alloc>
578inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
579RandomAccessSet<Key,Compare,Alloc>::upper_bound
580(
581 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
582) const
583{
584 return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
585}
586
587/// upper bound
588/// \param value
589/// \return iterator to upper bound
590template<class Key, class Compare, class Alloc>
591inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
592RandomAccessSet<Key,Compare,Alloc>::upper_bound
593(
594 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
595)
596{
597 return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
598}
599
600/// equal range
601/// \param value
602/// \return iterator pair to lower equal range
603template<class Key, class Compare, class Alloc>
604inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::const_iterator,typename RandomAccessSet<Key,Compare,Alloc>::const_iterator>
605RandomAccessSet<Key,Compare,Alloc>::equal_range
606(
607 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
608) const
609{
610 return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
611}
612
613/// equal range
614/// \param value
615/// \return iterator pair to lower equal range
616template<class Key, class Compare, class Alloc>
617inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::iterator,typename RandomAccessSet<Key,Compare,Alloc>::iterator>
618RandomAccessSet<Key,Compare,Alloc>::equal_range
619(
620 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
621)
622{
623 return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
624}
625/// allocators
626/// \return allocator
627template<class Key, class Compare, class Alloc>
628inline typename RandomAccessSet<Key,Compare,Alloc>::allocator_type
629RandomAccessSet<Key,Compare,Alloc>::get_allocator() const
630{
631 return vector_.get_allocator();
632}
633
634} // namespace vigra
635
636#endif // VIGRA_RANDOM_ACCESS_SET_HXX
637//! @endcond

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.12.2