MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved > Class Template Reference

#include </home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/MutablePriorityQueue.hpp>

Public Types
using	address = SkipHeapAddressing<blocking>

Public Member Functions
	MutableSkipHeapPriorityQueue (IndexSetter &&index_setter, LessPredicate &&less_predicate)
	~MutableSkipHeapPriorityQueue ()
void	clear ()
void	reserve (size_t cnt)
void	push (const T &item)
void	push (T &&item)
void	pop ()
T &	top ()
void	remove (size_t idx)
void	update (size_t idx)
size_t	size () const noexcept
bool	empty () const
T &	operator[] (std::size_t idx) noexcept
const T &	operator[] (std::size_t idx) const noexcept

Protected Member Functions
void	update_heap_up (size_t top, size_t bottom)
void	update_heap_down (size_t top, size_t bottom)
void	pop_back () noexcept

Private Attributes
std::vector< T >	m_heap
IndexSetter	m_index_setter
LessPredicate	m_less_predicate

Detailed Description

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>
class MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >

Member Typedef Documentation

address

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

using MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::address = SkipHeapAddressing<blocking>

Constructor & Destructor Documentation

MutableSkipHeapPriorityQueue()

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::MutableSkipHeapPriorityQueue ( IndexSetter && index_setter, LessPredicate && less_predicate )

inline

                                                                                           :
    m_index_setter(std::forward<IndexSetter>(index_setter)), 
    m_less_predicate(std::forward<LessPredicate>(less_predicate)) 
    {}

References m_index_setter, and m_less_predicate.

~MutableSkipHeapPriorityQueue()

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::~MutableSkipHeapPriorityQueue ( )

inline

{ clear(); }

References clear().

Here is the call graph for this function:

Member Function Documentation

clear()

template<class T, class LessPredicate, class IndexSetter, std::size_t blocking, const bool ResetIndexWhenRemoved>

void MutableSkipHeapPriorityQueue< T, LessPredicate, IndexSetter, blocking, ResetIndexWhenRemoved >::clear ( )

inline

{ 
#ifdef NDEBUG
  // Only mark as removed from the queue in release mode, if configured so.
  if (ResetIndexWhenRemoved)
#endif /* NDEBUG */
  {
    for (size_t idx = 0; idx < m_heap.size(); ++ idx)
      // Mark as removed from the queue.
      if (! address::is_padding(idx))
        m_index_setter(m_heap[idx], std::numeric_limits<size_t>::max());
  }
  m_heap.clear();
}

References SkipHeapAddressing< blocking >::is_padding(), m_heap, and m_index_setter.

Referenced by ~MutableSkipHeapPriorityQueue().

Here is the call graph for this function:

Here is the caller graph for this function:

empty()

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

bool MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::empty ( ) const

inline

{ return m_heap.empty(); }

References m_heap.

operator[]() [1/2]

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

const T & MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::operator[] ( std::size_t idx ) const

inlinenoexcept

{ assert(! address::is_padding(idx)); return m_heap[idx]; }

References SkipHeapAddressing< blocking >::is_padding(), and m_heap.

Here is the call graph for this function:

operator[]() [2/2]

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

T & MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::operator[] ( std::size_t idx )

inlinenoexcept

{ assert(! address::is_padding(idx)); return m_heap[idx]; }

References SkipHeapAddressing< blocking >::is_padding(), and m_heap.

Here is the call graph for this function:

pop()

template<class T, class LessPredicate, class IndexSetter, std::size_t blocking, const bool ResetIndexWhenRemoved>

void MutableSkipHeapPriorityQueue< T, LessPredicate, IndexSetter, blocking, ResetIndexWhenRemoved >::pop ( )

inline

{
  assert(! m_heap.empty());
#ifdef NDEBUG
  // Only mark as removed from the queue in release mode, if configured so.
  if (ResetIndexWhenRemoved)
#endif /* NDEBUG */
  {
    // Mark as removed from the queue.
    m_index_setter(m_heap[1], std::numeric_limits<size_t>::max());
  }
  // Zero'th element is padding, thus non-empty queue must have at least two elements.
  if (m_heap.size() > 2) {
    m_heap[1] = m_heap.back();
    this->pop_back();
    m_index_setter(m_heap[1], 1);
    update_heap_down(1, m_heap.size() - 1);
  } else
    m_heap.clear();
}

References m_heap, m_index_setter, pop_back(), and update_heap_down().

Here is the call graph for this function:

pop_back()

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

void MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::pop_back ( )

inlineprotectednoexcept

                                {
    assert(m_heap.size() > 1);
    assert(! address::is_padding(m_heap.size() - 1));
    m_heap.pop_back();
    if (address::is_padding(m_heap.size() - 1))
      m_heap.pop_back();
  }

References SkipHeapAddressing< blocking >::is_padding(), and m_heap.

Referenced by pop(), and remove().

Here is the call graph for this function:

Here is the caller graph for this function:

push() [1/2]

template<class T, class LessPredicate, class IndexSetter, std::size_t blocking, const bool ResetIndexWhenRemoved>

void MutableSkipHeapPriorityQueue< T, LessPredicate, IndexSetter, blocking, ResetIndexWhenRemoved >::push ( const T & item )

inline

{
  if (address::is_padding(m_heap.size()))
    m_heap.emplace_back(T());
  size_t idx = m_heap.size();
  m_heap.emplace_back(item);
  m_index_setter(m_heap.back(), idx);
  update_heap_up(1, idx);
}

References SkipHeapAddressing< blocking >::is_padding(), m_heap, m_index_setter, and update_heap_up().

Referenced by update().

Here is the call graph for this function:

Here is the caller graph for this function:

push() [2/2]

template<class T, class LessPredicate, class IndexSetter, std::size_t blocking, const bool ResetIndexWhenRemoved>

void MutableSkipHeapPriorityQueue< T, LessPredicate, IndexSetter, blocking, ResetIndexWhenRemoved >::push ( T && item )

inline

{
  if (address::is_padding(m_heap.size()))
    m_heap.emplace_back(T());
  size_t idx = m_heap.size();
  m_heap.emplace_back(std::move(item));
  m_index_setter(m_heap.back(), idx);
  update_heap_up(1, idx);
}

References SkipHeapAddressing< blocking >::is_padding(), m_heap, m_index_setter, and update_heap_up().

Here is the call graph for this function:

remove()

template<class T, class LessPredicate, class IndexSetter, std::size_t blocking, const bool ResetIndexWhenRemoved>

void MutableSkipHeapPriorityQueue< T, LessPredicate, IndexSetter, blocking, ResetIndexWhenRemoved >::remove ( size_t idx )

inline

{
  assert(idx < m_heap.size());
  assert(! address::is_padding(idx));
#ifdef NDEBUG
  // Only mark as removed from the queue in release mode, if configured so.
  if (ResetIndexWhenRemoved)
#endif /* NDEBUG */
  {
    // Mark as removed from the queue.
    m_index_setter(m_heap[idx], std::numeric_limits<size_t>::max());
  }
  if (idx + 1 == m_heap.size()) {
    this->pop_back();
    return;
  }
  m_heap[idx] = m_heap.back();
  m_index_setter(m_heap[idx], idx);
  this->pop_back();
  update_heap_down(idx, m_heap.size() - 1);
  update_heap_up(1, idx);
}

References SkipHeapAddressing< blocking >::is_padding(), m_heap, m_index_setter, pop_back(), update_heap_down(), and update_heap_up().

Referenced by update().

Here is the call graph for this function:

Here is the caller graph for this function:

reserve()

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

void MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::reserve ( size_t cnt )

inline

{ m_heap.reserve(cnt + ((cnt + (address::block_size - 1)) / (address::block_size - 1))); }

References SkipHeapAddressing< blocking >::block_size, and m_heap.

size()

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

size_t MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::size ( ) const

inlinenoexcept

{ return m_heap.size() - (m_heap.size() + address::block_size - 1) / address::block_size; }

References SkipHeapAddressing< blocking >::block_size, and m_heap.

top()

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

T & MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::top ( )

inline

{ return m_heap[1]; }

References m_heap.

Referenced by update_heap_down(), and update_heap_up().

Here is the caller graph for this function:

update()

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

void MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::update ( size_t idx )

inline

{ assert(! address::is_padding(idx)); T item = m_heap[idx]; remove(idx); push(item); }

References SkipHeapAddressing< blocking >::is_padding(), m_heap, push(), and remove().

Here is the call graph for this function:

update_heap_down()

template<class T, class LessPredicate, class IndexSetter, std::size_t blocking, const bool ResetIndexWhenRemoved>

void MutableSkipHeapPriorityQueue< T, LessPredicate, IndexSetter, blocking, ResetIndexWhenRemoved >::update_heap_down ( size_t top, size_t bottom )

inlineprotected

{
  assert(! address::is_padding(top));
  assert(! address::is_padding(bottom));
  size_t parentIdx = top;
  T *parent = &m_heap[parentIdx];
  for (;;) {
    size_t childIdx = address::child_of(parentIdx);
    if (childIdx > bottom)
      break;
    T *child = &m_heap[childIdx];
    size_t child2Idx = childIdx + (address::is_block_leaf(parentIdx) ? address::block_size : 1);
    if (child2Idx <= bottom) {
      T *child2 = &m_heap[child2Idx];
      if (! m_less_predicate(*child, *child2)) {
        child = child2;
        childIdx = child2Idx;
      }
    }
    if (m_less_predicate(*parent, *child))
      return;
    // switch nodes
    T tmp = *parent;
    m_index_setter(tmp,    childIdx);
    m_index_setter(*child, parentIdx);
    m_heap[parentIdx] = *child;
    m_heap[childIdx]  = tmp;
    // shift down
    parentIdx = childIdx;
    parent = child;
  }
}

References SkipHeapAddressing< blocking >::block_size, SkipHeapAddressing< blocking >::child_of(), SkipHeapAddressing< blocking >::is_block_leaf(), SkipHeapAddressing< blocking >::is_padding(), m_heap, m_index_setter, m_less_predicate, and top().

Referenced by pop(), and remove().

Here is the call graph for this function:

Here is the caller graph for this function:

update_heap_up()

template<class T, class LessPredicate, class IndexSetter, std::size_t blocking, const bool ResetIndexWhenRemoved>

void MutableSkipHeapPriorityQueue< T, LessPredicate, IndexSetter, blocking, ResetIndexWhenRemoved >::update_heap_up ( size_t top, size_t bottom )

inlineprotected

{
  assert(! address::is_padding(top));
  assert(! address::is_padding(bottom));
  size_t childIdx = bottom;
  T *child = &m_heap[childIdx];
  for (;;) {
    size_t parentIdx = address::parent_of(childIdx);
    if (childIdx == 1 || parentIdx < top)
      break;
    T *parent = &m_heap[parentIdx];
    // switch nodes
    if (! m_less_predicate(*parent, *child)) {
      T tmp = *parent;
      m_index_setter(tmp,    childIdx);
      m_index_setter(*child, parentIdx);
      m_heap[parentIdx] = *child;
      m_heap[childIdx]  = tmp;
    }
    // shift up
    childIdx = parentIdx;
    child = parent;
  }
}

References SkipHeapAddressing< blocking >::is_padding(), m_heap, m_index_setter, m_less_predicate, SkipHeapAddressing< blocking >::parent_of(), and top().

Referenced by push(), push(), and remove().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

m_heap

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

std::vector<T> MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::m_heap

private

Referenced by clear(), empty(), operator[](), operator[](), pop(), pop_back(), push(), push(), remove(), reserve(), size(), top(), update(), update_heap_down(), and update_heap_up().

m_index_setter

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

IndexSetter MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::m_index_setter

private

Referenced by MutableSkipHeapPriorityQueue(), clear(), pop(), push(), push(), remove(), update_heap_down(), and update_heap_up().

m_less_predicate

template<typename T, typename IndexSetter, typename LessPredicate, std::size_t blocking = 32, const bool ResetIndexWhenRemoved = false>

LessPredicate MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::m_less_predicate

private

Referenced by MutableSkipHeapPriorityQueue(), update_heap_down(), and update_heap_up().

---

The documentation for this class was generated from the following file:

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/MutablePriorityQueue.hpp