NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
priority_deque.h
Go to the documentation of this file.
1 /*
2  * nvbio
3  * Copyright (c) 2011-2014, NVIDIA CORPORATION. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  * * Redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer.
9  * * Redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution.
12  * * Neither the name of the NVIDIA CORPORATION nor the
13  * names of its contributors may be used to endorse or promote products
14  * derived from this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19  * DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY
20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  */
27 
28 //
29 // This software is a modification of:
30 //
31 // https://github.com/nmcclatchey/Priority-Deque/blob/master/priority_deque.hpp
32 //
33 //
34 
35 /*----------------------------------------------------------------------------*\
36 | Copyright (C) 2012-2013 Nathaniel McClatchey |
37 | Released under the Boost Software License Version 1.0, which may be found |
38 | at http://www.boost.org/LICENSE_1_0.txt |
39 \*----------------------------------------------------------------------------*/
40 
51 #pragma once
52 
53 #include <nvbio/basic/types.h>
55 
56 // Default comparison (std::less)
57 #include <functional>
58 // Default container (std::vector)
59 #include <vector>
60 
61 namespace nvbio {
62 
99 
102 
106 
108 template <typename Type, typename Sequence =std::vector<Type>,
109  typename Compare =::std::less<typename Sequence::value_type> >
111 
113 template <typename Type, typename Sequence, typename Compare>
116 
117 //----------------------------Priority Deque Class-----------------------------|
151 template <typename Type, typename Sequence, typename Compare>
152 class priority_deque {
153 //----------------------------------Public-------------------------------------|
154  public:
155 //---------------------------------Typedefs------------------------------------|
157  typedef Sequence container_type;
158  typedef typename container_type::value_type value_type;
159  typedef Compare value_compare;
161  typedef typename container_type::size_type size_type;
163  typedef typename container_type::const_reference const_reference;
164  typedef typename container_type::reference reference;
165  typedef typename container_type::pointer pointer;
168  typedef typename container_type::const_iterator const_iterator;
171  typedef typename container_type::difference_type difference_type;
172 //-------------------------------Constructors----------------------------------|
174 
177  explicit priority_deque (const Compare& =Compare(),
178  const Sequence& =Sequence());
179 
180  template <typename InputIterator>
182  priority_deque (InputIterator first, InputIterator last,
183  const Compare& =Compare(),
184  const Sequence& =Sequence());
185 
189  priority_deque(const Sequence& seq, const bool constructed = false);
190 
194  priority_deque(const Sequence& seq, const Constructed flag) :
195  sequence_(seq) {}
196 
197 //-----------------------------Restricted Access-------------------------------|
200  void push (const value_type&);
201 
205  const_reference maximum (void) const;
208  const_reference minimum (void) const;
211  const_reference top (void) const { return maximum(); };
214  const_reference bottom (void) const { return bottom(); };
219  void pop_top (void);
222  void pop_bottom (void);
225  void pop (void) { pop_top(); };
227 
228 //--------------------------------Deque Size-----------------------------------|
232  bool empty (void) const {return sequence_.empty();};
235  size_type size (void) const {return sequence_.size(); };
238  size_type max_size (void) const {return sequence_.max_size();};
240 
241 //--------------------------Whole-Deque Operations-----------------------------|
244  void clear (void) { sequence_.clear(); };
250  template <typename InputIterator>
252  void merge (InputIterator first, InputIterator last);
254  template <typename SourceContainer>
256  void merge (const SourceContainer& source) { merge(source.begin(), source.end()); }
258 
259 //-------------------------------Random Access---------------------------------|
263  const_iterator begin (void) const {return sequence_.begin();};
266  const_iterator end (void) const { return sequence_.end(); };
269  void update (const_iterator, const value_type&);
272  void erase (const_iterator);
274 
275 //---------------------------Boost.Heap Concepts-------------------------------|
276 // size() has constant complexity
277  static const bool constant_time_size = true;
278 // priority deque does not have ordered iterators
279  static const bool has_ordered_iterators = false;
280 // priority deque is efficiently mergable
281  static const bool is_mergable = true;
282 // priority deque does not have a stable heap order
283  static const bool is_stable = false;
284 // priority deque does not have a reserve() member
285  static const bool has_reserve = false;
286 
287 //--------------------------------Protected------------------------------------|
288  protected:
290  container_type& sequence (void) { return sequence_; };
292  const container_type& sequence (void) const { return sequence_; };
294  value_compare& compare (void) { return compare_; };
296  const value_compare& compare (void) const { return compare_; };
297 //---------------------------------Private-------------------------------------|
298  private:
299  Sequence sequence_;
300  Compare compare_;
301 };
302 
303 //-------------------------------Constructors----------------------------------|
304 //----------------------------Default Constructor------------------------------|
311 template <typename T, typename S, typename C>
313  : sequence_(seq), compare_(comp)
314 {
315  heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
316 }
317 
318 template <typename T, typename S, typename C>
320 priority_deque<T, S, C>::priority_deque(const S& seq, const bool constructed)
321  : sequence_(seq)
322 {
323  if (!constructed)
324  heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
325 }
326 
327 //---------------------------Create from Iterators-----------------------------|
336 template <typename T, typename S, typename C>
337 template <typename InputIterator>
338 priority_deque<T, S, C>::priority_deque (InputIterator first,InputIterator last,
339  const C& comp, const S& seq)
340 : sequence_(seq), compare_(comp)
341 {
342  sequence_.insert(sequence_.end(), first, last);
343  heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
344 }
345 
346 //-----------------------------Restricted Access-------------------------------|
347 //------------------------------Insert / Emplace-------------------------------|
354 template <typename T, typename Sequence, typename Compare>
356  sequence_.push_back(value);
357  heap::push_interval_heap(sequence_.begin(), sequence_.end(), compare_);
358 }
359 
360 //---------------------------Observe Maximum/Minimum---------------------------|
367 template <typename T, typename Sequence, typename Compare>
370 {
371  NVBIO_CUDA_DEBUG_ASSERT(!empty(),
372  "Empty priority deque has no maximal element. Reference undefined.");
373  const_iterator it = sequence_.begin() + 1;
374  return (it == sequence_.end()) ? sequence_.front() : *it;
375 }
382 template <typename T, typename Sequence, typename Compare>
385 {
386  NVBIO_CUDA_DEBUG_ASSERT(!empty(),
387  "Empty priority deque has no minimal element. Reference undefined.");
388  return sequence_.front();
389 }
390 //---------------------------Remove Maximum/Minimum----------------------------|
398 template <typename T, typename Sequence, typename Compare>
400  NVBIO_CUDA_DEBUG_ASSERT(!empty(),
401  "Empty priority deque has no maximal element. Removal impossible.");
402  heap::pop_interval_heap_min(sequence_.begin(), sequence_.end(), compare_);
403  sequence_.pop_back();
404 }
412 template <typename T, typename Sequence, typename Compare>
414  NVBIO_CUDA_DEBUG_ASSERT(!empty(),
415  "Empty priority deque has no minimal element. Removal undefined.");
416  heap::pop_interval_heap_max(sequence_.begin(), sequence_.end(), compare_);
417  sequence_.pop_back();
418 }
419 
420 //--------------------------Whole-Deque Operations-----------------------------|
421 //-----------------------------------Merge-------------------------------------|
430 template <typename T, typename S, typename C>
431 template <typename InputIterator>
432 void priority_deque<T, S, C>::merge (InputIterator first, InputIterator last) {
433  sequence_.insert(sequence_.end(), first, last);
434  heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
435 }
436 
437 //----------------------------Swap Specialization------------------------------|
445 template <typename T, typename S, typename C>
447  sequence_.swap(other.sequence_);
448 }
449 
458 template <typename T, typename S, typename C>
460  priority_deque<T, S, C>& deque2)
461 {
462  deque1.swap(deque2);
463 }
464 
465 //---------------------------Random-Access Mutators----------------------------|
478 template <typename T, typename S, typename C>
480  const value_type& value)
481 {
482  const difference_type index = random_it - begin();
483  NVBIO_CUDA_DEBUG_ASSERT((0 <= index) &&
484  (index < end() - begin()), "Iterator out of bounds; can't set element.");
485 // Providing the strong guarantee would require saving a copy.
486  *(sequence_.begin() + index) = value;
487  heap::update_interval_heap(sequence_.begin(),sequence_.end(),index,compare_);
488 }
489 
497 template <typename T, typename Sequence, typename Compare>
499  const difference_type index = random_it - begin();
500  NVBIO_CUDA_DEBUG_ASSERT((0 <= index) &&
501  (index < end() - begin()), "Iterator out of bounds; can't erase element.");
502  heap::pop_interval_heap(sequence_.begin(), sequence_.end(),index,compare_);
503  sequence_.pop_back();
504 }
505 
508 
509 } // namespace nvbio