A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
sorted_vector.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_UTILS_CONTAINERS_SORTED_VECTOR_H_
2 #define GENESIS_UTILS_CONTAINERS_SORTED_VECTOR_H_
3 
4 /*
5  Genesis - A toolkit for working with phylogenetic data.
6  Copyright (C) 2014-2017 Lucas Czech
7 
8  This program is free software: you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation, either version 3 of the License, or
11  (at your option) any later version.
12 
13  This program is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with this program. If not, see <http://www.gnu.org/licenses/>.
20 
21  Contact:
22  Lucas Czech <lucas.czech@h-its.org>
23  Exelixis Lab, Heidelberg Institute for Theoretical Studies
24  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
25 */
26 
34 #include <algorithm>
35 #include <functional>
36 #include <iterator>
37 #include <vector>
38 
39 namespace genesis {
40 namespace utils {
41 
42 // =================================================================================================
43 // Sorted Vector
44 // =================================================================================================
45 
52 template< class T, class Compare = std::less<T> >
54 {
55 public:
56 
57  // -------------------------------------------------------------------------
58  // Member Types
59  // -------------------------------------------------------------------------
60 
61  using value_type = T;
62 
64  using const_reference = const value_type&;
65  using pointer = value_type*;
66  using const_pointer = const value_type*;
67 
68  using iterator = typename std::vector< value_type >::iterator;
69  using const_iterator = typename std::vector< value_type >::const_iterator;
70 
71  using size_type = size_t;
72  using value_compare = Compare;
73 
74  // -------------------------------------------------------------------------
75  // Constructor and Rule of Five
76  // -------------------------------------------------------------------------
77 
78  SortedVector() = default;
79  ~SortedVector() = default;
80 
81  SortedVector( SortedVector const& ) = default;
82  SortedVector ( SortedVector&& ) = default;
83 
84  SortedVector( std::initializer_list<value_type> il )
85  {
86  content_.reserve( il.size() );
87  for( auto const& elem : il ) {
88  insert( elem );
89  }
90  }
91 
92  SortedVector& operator= ( SortedVector const& ) = default;
93  SortedVector& operator= ( SortedVector&& ) = default;
94 
95  // -------------------------------------------------------------------------
96  // Iterators
97  // -------------------------------------------------------------------------
98 
100  {
101  return content_.begin();
102  }
103 
105  {
106  return content_.cbegin();
107  }
108 
110  {
111  return content_.end();
112  }
113 
115  {
116  return content_.cend();
117  }
118 
120  {
121  return content_.cbegin();
122  }
123 
125  {
126  return content_.cend();
127  }
128 
129  // -------------------------------------------------------------------------
130  // Properties
131  // -------------------------------------------------------------------------
132 
133  size_type size() const
134  {
135  return content_.size();
136  }
137 
138  bool empty() const
139  {
140  return content_.empty();
141  }
142 
143  // -------------------------------------------------------------------------
144  // Find Elements
145  // -------------------------------------------------------------------------
146 
150  bool contains( const_reference value ) const
151  {
152  return std::binary_search( content_.begin(), content_.end(), value, Compare() );
153  }
154 
160  {
161  auto lower = std::lower_bound( content_.begin(), content_.end(), value, Compare() );
162 
163  if( lower == content_.end() || value < *lower ) {
164  return size();
165  } else {
166  return std::distance( content_.begin(), lower );
167  }
168  }
169 
170  // -------------------------------------------------------------------------
171  // Element Access
172  // -------------------------------------------------------------------------
173 
175  {
176  return content_[ index ];
177  }
178 
180  {
181  return content_[ index ];
182  }
183 
185  {
186  return content_.at( index );
187  }
188 
189  const_reference at( size_type index ) const
190  {
191  return content_.at( index );
192  }
193 
195  {
196  return content_.front();
197  }
198 
200  {
201  return content_.front();
202  }
203 
205  {
206  return content_.back();
207  }
208 
210  {
211  return content_.back();
212  }
213 
214  // -------------------------------------------------------------------------
215  // Modifiers
216  // -------------------------------------------------------------------------
217 
223  void insert( const_reference value )
224  {
225  // Find the position where the new value belongs.
226  auto range = std::equal_range( content_.begin(), content_.end(), value, Compare() );
227 
228  // If it is not yet in the list, add it.
229  if( range.first == range.second ) {
230  content_.insert( range.first, value );
231  }
232  }
233 
234 
240  void insert( value_type&& value )
241  {
242  // Find the position where the new value belongs.
243  auto range = std::equal_range( content_.begin(), content_.end(), value, Compare() );
244 
245  // If it is not yet in the list, add it.
246  if( range.first == range.second ) {
247  content_.insert( range.first, std::move( value ));
248  }
249  }
250 
256  template< class InputIterator >
257  void insert( InputIterator first, InputIterator last )
258  {
259  while( first != last ) {
260  insert( *first );
261  ++first;
262  }
263  }
264 
270  void remove( const_reference value )
271  {
272  // Find the position of the value.
273  auto range = std::equal_range( content_.begin(), content_.end(), value, Compare() );
274 
275  // If found, remove it.
276  if( range.first != range.second ) {
277  content_.erase( range.first, range.second );
278  }
279  }
280 
284  void reserve( size_t n )
285  {
286  content_.reserve( n );
287  }
288 
289  void clear()
290  {
291  content_.clear();
292  }
293 
294  // -------------------------------------------------------------------------
295  // Data Members
296  // -------------------------------------------------------------------------
297 
298 private:
299 
300  std::vector< value_type > content_;
301 };
302 
303 } // namespace utils
304 } // namespace genesis
305 
306 #endif // include guard
void reserve(size_t n)
Reserve space in the unterlying vector.
typename std::vector< value_type >::const_iterator const_iterator
const_reference back() const
typename std::vector< value_type >::iterator iterator
const_iterator begin() const
SortedVector(std::initializer_list< value_type > il)
Sorted vector of unique elements.
void insert(value_type &&value)
Insert a value into the container by moving it.
const value_type & const_reference
const value_type * const_pointer
const_reference front() const
reference operator[](size_type index)
size_type index_of(const_reference value) const
Return the index at which a certain value is stored, or size(), if it is not present in the container...
bool contains(const_reference value) const
Return whether a certain value is present in the container.
SortedVector & operator=(SortedVector const &)=default
reference at(size_type index)
void insert(const_reference value)
Insert a value into the container by copying it.
const_reference at(size_type index) const
void insert(InputIterator first, InputIterator last)
Insert values into the container by copying from an InputIterator range.
const_iterator end() const