[ 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 typename Alloc::const_reference 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 // memeber 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());
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);
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;
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 a sequence of elements with a hint for the position
392///
393/// \param position iterator to the position
394/// \param value element to insert
395template<class Key, class Compare, class Alloc>
396inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
397RandomAccessSet<Key,Compare,Alloc>::insert
398(
399 typename RandomAccessSet<Key,Compare,Alloc>::const_iterator position,
400 const typename RandomAccessSet<Key,Compare,Alloc>::value_type& value
401)
402{
403 if((position == begin() || this->operator()(*(position-1),value))
404 && (position == end() || this->operator()(value, *position))) {
405 return vector_.insert(position, value);
406 }
407 return insert(value).first;
408}
409
410/// erase an element
411/// \param position iterator to the position
412template<class Key, class Compare, class Alloc>
413inline void
414RandomAccessSet<Key,Compare,Alloc>::erase
415(
416 typename RandomAccessSet<Key,Compare,Alloc>::iterator position
417)
418{
419 vector_.erase(position);
420}
421
422/// erease and element
423/// \param x element
424template<class Key, class Compare, class Alloc>
425inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
426RandomAccessSet<Key,Compare,Alloc>::erase
427(
428 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& x
429)
430{
431 iterator i =find(x);
432 if(i!=vector_.end())
433 {
434 erase(i);
435 return 1;
436 }
437 return 0;
438}
439
440/// erase a sequence of elements
441/// \param first iterator to the beginning of the sequence to erase
442/// \param last iterator to the end of the sequence to erase
443template<class Key, class Compare, class Alloc>
444inline void
445RandomAccessSet<Key,Compare,Alloc>::erase
446(
447 const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator first,
448 const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator last
449)
450{
451 vector_.erase(first,last);
452}
453
454/// swap random access sets
455/// \param rhs set to swap with
456template<class Key, class Compare, class Alloc>
457inline void
458RandomAccessSet<Key,Compare,Alloc>::swap
459(
460 RandomAccessSet<Key,Compare,Alloc>& rhs
461)
462{
463 vector_.swap(rhs.vector_);
464 std::swap(compare_, rhs.compare_);
465}
466
467/// clear the set
468///
469/// erases all elements
470template<class Key, class Compare, class Alloc>
471inline void
472RandomAccessSet<Key,Compare,Alloc>::clear()
473{
474 vector_.clear();
475}
476
477/// key comparator
478/// \return key comparator
479template<class Key, class Compare, class Alloc>
480inline typename RandomAccessSet<Key,Compare,Alloc>::key_compare
481RandomAccessSet<Key,Compare,Alloc>::key_comp() const
482{
483 return compare_;
484}
485
486/// value comparator
487/// \return value comparator
488template<class Key, class Compare, class Alloc>
489inline typename RandomAccessSet<Key,Compare,Alloc>::value_compare
490RandomAccessSet<Key,Compare,Alloc>::value_comp() const
491{
492 return compare_;
493}
494
495/// find an element
496/// \param value element
497/// \return const_iterator to the position where element was found or end
498/// iterator if the element was not found
499template<class Key, class Compare, class Alloc>
500inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
501RandomAccessSet<Key,Compare,Alloc>::find
502(
503 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
504) const
505{
506 const_iterator i(lower_bound(value));
507 if (i != end() && compare_(value, *i))
508 {
509 i = end();
510 }
511 return i;
512}
513
514/// find an element
515/// \param value element
516/// \return iterator to the position where the element was found or end
517/// iterator if the element was not found
518template<class Key, class Compare, class Alloc>
519inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
520RandomAccessSet<Key,Compare,Alloc>::find
521(
522 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
523)
524{
525 iterator i(lower_bound(value));
526 if (i != end() && compare_(value, *i))
527 {
528 i = end();
529 }
530 return i;
531}
532
533/// count elements
534/// \param element
535/// \return zero or one
536template<class Key, class Compare, class Alloc>
537inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
538RandomAccessSet<Key,Compare,Alloc>::count
539(
540 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
541) const
542{
543 return find(value) != end() ? 1 : 0;
544}
545
546/// lower bound
547/// \param value
548/// \return iterator to lower bound
549template<class Key, class Compare, class Alloc>
550inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
551RandomAccessSet<Key,Compare,Alloc>::lower_bound
552(
553 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
554) const
555{
556 return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
557}
558
559/// lower bound
560/// \param value
561/// \return iterator to lower bound
562template<class Key, class Compare, class Alloc>
563inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
564RandomAccessSet<Key,Compare,Alloc>::lower_bound
565(
566 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
567)
568{
569 return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
570}
571
572/// upper bound
573/// \param value
574/// \return iterator to upper bound
575template<class Key, class Compare, class Alloc>
576inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
577RandomAccessSet<Key,Compare,Alloc>::upper_bound
578(
579 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
580) const
581{
582 return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
583}
584
585/// upper bound
586/// \param value
587/// \return iterator to upper bound
588template<class Key, class Compare, class Alloc>
589inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
590RandomAccessSet<Key,Compare,Alloc>::upper_bound
591(
592 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
593)
594{
595 return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
596}
597
598/// equal range
599/// \param value
600/// \return iterator pair to lower equal range
601template<class Key, class Compare, class Alloc>
602inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::const_iterator,typename RandomAccessSet<Key,Compare,Alloc>::const_iterator>
603RandomAccessSet<Key,Compare,Alloc>::equal_range
604(
605 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
606) const
607{
608 return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
609}
610
611/// equal range
612/// \param value
613/// \return iterator pair to lower equal range
614template<class Key, class Compare, class Alloc>
615inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::iterator,typename RandomAccessSet<Key,Compare,Alloc>::iterator>
616RandomAccessSet<Key,Compare,Alloc>::equal_range
617(
618 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
619)
620{
621 return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
622}
623/// allocators
624/// \return allocator
625template<class Key, class Compare, class Alloc>
626inline typename RandomAccessSet<Key,Compare,Alloc>::allocator_type
627RandomAccessSet<Key,Compare,Alloc>::get_allocator() const
628{
629 return vector_.get_allocator();
630}
631
632} // namespace vigra
633
634#endif // VIGRA_RANDOM_ACCESS_SET_HXX
635//! @endcond
RGBValue()
Definition rgbvalue.hxx:209
Base::iterator iterator
Definition rgbvalue.hxx:144
Base::value_type value_type
Definition rgbvalue.hxx:141
Base::const_iterator const_iterator
Definition rgbvalue.hxx:147
size_type size() const
Definition tinyvector.hxx:913
reference operator[](difference_type i)
Definition tinyvector.hxx:845
iterator end()
Definition tinyvector.hxx:864
iterator begin()
Definition tinyvector.hxx:861

© 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.11.1