priority_deque.h

Go to the documentation of this file.

/*
 * nvbio
 * Copyright (c) 2011-2014, NVIDIA CORPORATION. All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *    * Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *    * Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *    * Neither the name of the NVIDIA CORPORATION nor the
 *      names of its contributors may be used to endorse or promote products
 *      derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

//
// This software is a modification of:
//
//   https://github.com/nmcclatchey/Priority-Deque/blob/master/priority_deque.hpp
//
//

/*----------------------------------------------------------------------------*\
|   Copyright (C) 2012-2013 Nathaniel McClatchey                               |
|   Released under the Boost Software License Version 1.0, which may be found  |
| at http://www.boost.org/LICENSE_1_0.txt                                      |
\*----------------------------------------------------------------------------*/

#pragma once

#include <nvbio/basic/types.h>
#include <nvbio/basic/interval_heap.h>

//  Default comparison (std::less)
#include <functional>
//  Default container (std::vector)
#include <vector>

namespace nvbio {




template <typename Type, typename Sequence =std::vector<Type>,
          typename Compare =::std::less<typename Sequence::value_type> >
class priority_deque;

template <typename Type, typename Sequence, typename Compare>
void swap (priority_deque<Type, Sequence, Compare>& deque1,
           priority_deque<Type, Sequence, Compare>& deque2);

//----------------------------Priority Deque Class-----------------------------|
template <typename Type, typename Sequence, typename Compare>
class priority_deque {
//----------------------------------Public-------------------------------------|
 public:
//---------------------------------Typedefs------------------------------------|
  typedef Sequence                                    container_type;
  typedef typename container_type::value_type         value_type;
  typedef Compare                                     value_compare;
  typedef typename container_type::size_type          size_type;
  typedef typename container_type::const_reference    const_reference;
  typedef typename container_type::reference          reference;
  typedef typename container_type::pointer            pointer;
  typedef pointer                                     const_pointer;
  typedef typename container_type::const_iterator     const_iterator;
  typedef const_iterator                              iterator;
  typedef typename container_type::difference_type    difference_type;
//-------------------------------Constructors----------------------------------|
  enum Constructed { CONSTRUCTED };

  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  explicit priority_deque             (const Compare&  =Compare(),
                                       const Sequence& =Sequence());

  template <typename InputIterator>
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  priority_deque                      (InputIterator first, InputIterator last,
                                       const Compare&  =Compare(),
                                       const Sequence& =Sequence());

  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  priority_deque(const Sequence& seq, const bool constructed = false);

  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  priority_deque(const Sequence& seq, const Constructed flag) :
      sequence_(seq) {}

//-----------------------------Restricted Access-------------------------------|
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  void                    push        (const value_type&);

  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  const_reference         maximum     (void) const;
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  const_reference         minimum     (void) const;
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  const_reference  top         (void) const  { return maximum(); };
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  const_reference  bottom      (void) const  { return bottom(); };
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  void                    pop_top    (void);
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  void                    pop_bottom (void);
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  void                    pop        (void)        { pop_top(); };

//--------------------------------Deque Size-----------------------------------|
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  bool                    empty       (void) const  {return sequence_.empty();};
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  size_type               size        (void) const  {return sequence_.size(); };
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  size_type               max_size    (void) const  {return sequence_.max_size();};

//--------------------------Whole-Deque Operations-----------------------------|
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  void                    clear       (void)        { sequence_.clear();      };
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  void                    swap        (priority_deque<Type, Sequence,Compare>&);
  template <typename InputIterator>
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  void                    merge       (InputIterator first, InputIterator last);
  template <typename SourceContainer>
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  void                    merge       (const SourceContainer& source) { merge(source.begin(), source.end()); }

//-------------------------------Random Access---------------------------------|
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  const_iterator          begin       (void) const  {return sequence_.begin();};
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  const_iterator          end         (void) const  { return sequence_.end(); };
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  void                    update      (const_iterator, const value_type&);
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  void                    erase       (const_iterator);

//---------------------------Boost.Heap Concepts-------------------------------|
// size() has constant complexity
  static const bool constant_time_size    = true;
// priority deque does not have ordered iterators
  static const bool has_ordered_iterators = false;
// priority deque is efficiently mergable
  static const bool is_mergable           = true;
// priority deque does not have a stable heap order
  static const bool is_stable             = false;
// priority deque does not have a reserve() member
  static const bool has_reserve           = false;

//--------------------------------Protected------------------------------------|
 protected:
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  container_type&        sequence  (void)        { return sequence_; };
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  const container_type&  sequence  (void) const  { return sequence_; };
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  value_compare&         compare   (void)        { return compare_; };
  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
  const value_compare&   compare   (void) const  { return compare_; };
//---------------------------------Private-------------------------------------|
 private:
  Sequence sequence_;
  Compare  compare_;
};

//-------------------------------Constructors----------------------------------|
//----------------------------Default Constructor------------------------------|
template <typename T, typename S, typename C>
priority_deque<T, S, C>::priority_deque (const C& comp, const S& seq)
  : sequence_(seq), compare_(comp)
{
  heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
}

template <typename T, typename S, typename C>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
priority_deque<T, S, C>::priority_deque(const S& seq, const bool constructed)
  : sequence_(seq)
{
  if (!constructed)
    heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
}

//---------------------------Create from Iterators-----------------------------|
template <typename T, typename S, typename C>
template <typename InputIterator>
priority_deque<T, S, C>::priority_deque (InputIterator first,InputIterator last,
                                         const C& comp, const S& seq)
: sequence_(seq), compare_(comp)
{
    sequence_.insert(sequence_.end(), first, last);
    heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
}

//-----------------------------Restricted Access-------------------------------|
//------------------------------Insert / Emplace-------------------------------|
template <typename T, typename Sequence, typename Compare>
void priority_deque<T, Sequence, Compare>::push (const value_type& value) {
  sequence_.push_back(value);
  heap::push_interval_heap(sequence_.begin(), sequence_.end(), compare_);
}

//---------------------------Observe Maximum/Minimum---------------------------|
template <typename T, typename Sequence, typename Compare>
typename priority_deque<T, Sequence, Compare>::const_reference
  priority_deque<T, Sequence, Compare>::maximum  (void) const
{
  NVBIO_CUDA_DEBUG_ASSERT(!empty(),
    "Empty priority deque has no maximal element. Reference undefined.");
  const_iterator it = sequence_.begin() + 1;
  return (it == sequence_.end()) ? sequence_.front() : *it;
}
template <typename T, typename Sequence, typename Compare>
typename priority_deque<T, Sequence, Compare>::const_reference
  priority_deque<T, Sequence, Compare>::minimum  (void) const
{
  NVBIO_CUDA_DEBUG_ASSERT(!empty(),
    "Empty priority deque has no minimal element. Reference undefined.");
  return sequence_.front();
}
//---------------------------Remove Maximum/Minimum----------------------------|
template <typename T, typename Sequence, typename Compare>
void priority_deque<T, Sequence, Compare>::pop_bottom (void) {
  NVBIO_CUDA_DEBUG_ASSERT(!empty(),
    "Empty priority deque has no maximal element. Removal impossible.");
  heap::pop_interval_heap_min(sequence_.begin(), sequence_.end(), compare_);
  sequence_.pop_back();
}
template <typename T, typename Sequence, typename Compare>
void priority_deque<T, Sequence, Compare>::pop_top (void) {
  NVBIO_CUDA_DEBUG_ASSERT(!empty(),
    "Empty priority deque has no minimal element. Removal undefined.");
  heap::pop_interval_heap_max(sequence_.begin(), sequence_.end(), compare_);
  sequence_.pop_back();
}

//--------------------------Whole-Deque Operations-----------------------------|
//-----------------------------------Merge-------------------------------------|
template <typename T, typename S, typename C>
template <typename InputIterator>
void priority_deque<T, S, C>::merge (InputIterator first, InputIterator last) {
  sequence_.insert(sequence_.end(), first, last);
  heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
}

//----------------------------Swap Specialization------------------------------|
template <typename T, typename S, typename C>
void priority_deque<T, S, C>::swap (priority_deque<T, S, C>& other) {
  sequence_.swap(other.sequence_);
}

template <typename T, typename S, typename C>
void swap (priority_deque<T, S, C>& deque1,
                  priority_deque<T, S, C>& deque2)
{
  deque1.swap(deque2);
}

//---------------------------Random-Access Mutators----------------------------|
template <typename T, typename S, typename C>
void priority_deque<T, S, C>::update (const_iterator random_it,
                                      const value_type& value)
{
  const difference_type index = random_it - begin();
  NVBIO_CUDA_DEBUG_ASSERT((0 <= index) &&
    (index < end() - begin()), "Iterator out of bounds; can't set element.");
//  Providing the strong guarantee would require saving a copy.
  *(sequence_.begin() + index) = value;
  heap::update_interval_heap(sequence_.begin(),sequence_.end(),index,compare_);
}

template <typename T, typename Sequence, typename Compare>
void priority_deque<T, Sequence, Compare>::erase (const_iterator random_it) {
  const difference_type index = random_it - begin();
  NVBIO_CUDA_DEBUG_ASSERT((0 <= index) &&
    (index < end() - begin()), "Iterator out of bounds; can't erase element.");
  heap::pop_interval_heap(sequence_.begin(), sequence_.end(),index,compare_);
  sequence_.pop_back();
}


} // namespace nvbio