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

#include <src/libslic3r/MutablePriorityQueue.hpp>

Public Types
using	address = SkipHeapAddressing< blocking >

Public Member Functions
	MutableSkipHeapPriorityQueue (IndexSetter &&index_setter, LessPredicate &&less_predicate)
	~MutableSkipHeapPriorityQueue ()
	MutableSkipHeapPriorityQueue (MutableSkipHeapPriorityQueue &&)=default
MutableSkipHeapPriorityQueue &	operator= (MutableSkipHeapPriorityQueue &&)=default
	MutableSkipHeapPriorityQueue (const MutableSkipHeapPriorityQueue &)=delete
MutableSkipHeapPriorityQueue &	operator= (const MutableSkipHeapPriorityQueue &)=delete
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
size_t	heap_size () const noexcept
bool	empty () const
T &	operator[] (std::size_t idx) noexcept
const T &	operator[] (std::size_t idx) const noexcept

Static Public Member Functions
static constexpr size_t	invalid_id ()

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 Slic3r::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 Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::address = SkipHeapAddressing<blocking>

Constructor & Destructor Documentation

MutableSkipHeapPriorityQueue() [1/3]

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

Slic3r::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)) 
    {}

~MutableSkipHeapPriorityQueue()

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

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

inline

{ clear(); }

References Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::clear().

Here is the call graph for this function:

MutableSkipHeapPriorityQueue() [2/3]

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

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

default

MutableSkipHeapPriorityQueue() [3/3]

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

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

delete

Member Function Documentation

clear()

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

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

inline

{ 
  if constexpr (ResetIndexWhenRemoved) {
    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], this->invalid_id());
  }
  m_heap.clear();
}

Referenced by Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::~MutableSkipHeapPriorityQueue().

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 Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::empty ( ) const

inline

{ return m_heap.empty(); }

References Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::m_heap.

heap_size()

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

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

inlinenoexcept

{ return m_heap.size(); }

References Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::m_heap.

invalid_id()

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

static constexpr size_t Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::invalid_id ( )

inlinestaticconstexpr

{ return InvalidQueueID; }

References Slic3r::InvalidQueueID.

operator=() [1/2]

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

MutableSkipHeapPriorityQueue & Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::operator= ( const MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved > &  )

delete

operator=() [2/2]

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

MutableSkipHeapPriorityQueue & Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::operator= ( MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved > &&  )

default

operator[]() [1/2]

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

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

inlinenoexcept

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

References Slic3r::SkipHeapAddressing< blocking >::is_padding(), and Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::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 & Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::operator[] ( std::size_t  idx )

inlinenoexcept

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

References Slic3r::SkipHeapAddressing< blocking >::is_padding(), and Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::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 Slic3r::MutableSkipHeapPriorityQueue< T, LessPredicate, IndexSetter, blocking, ResetIndexWhenRemoved >::pop

inline

{
  assert(! m_heap.empty());
  if constexpr (ResetIndexWhenRemoved) {
    // Mark as removed from the queue.
        m_index_setter(m_heap[1], this->invalid_id());
  }
  // 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();
}

pop_back()

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

void Slic3r::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 Slic3r::SkipHeapAddressing< blocking >::is_padding(), and Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::m_heap.

Here is the call graph for this function:

push() [1/2]

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

void Slic3r::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);
}

Referenced by Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::update().

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 Slic3r::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);
}

remove()

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

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

inline

{
  assert(idx < m_heap.size());
  assert(! address::is_padding(idx));
  if constexpr (ResetIndexWhenRemoved) {
    // Mark as removed from the queue.
        m_index_setter(m_heap[idx], this->invalid_id());
  }
  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);
}

Referenced by Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::update().

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 Slic3r::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 Slic3r::SkipHeapAddressing< blocking >::block_size, and Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::m_heap.

size()

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

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

inlinenoexcept

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

References Slic3r::SkipHeapAddressing< blocking >::block_size, and Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::m_heap.

top()

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

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

inline

{ return m_heap[1]; }

References Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::m_heap.

update()

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

void Slic3r::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 Slic3r::SkipHeapAddressing< blocking >::is_padding(), Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::m_heap, Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::push(), and Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::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 Slic3r::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;
  }
}

update_heap_up()

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

void Slic3r::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;
  }
}

Member Data Documentation

m_heap

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

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

private

Referenced by Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::empty(), Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::heap_size(), Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::operator[](), Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::operator[](), Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::pop_back(), Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::reserve(), Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::size(), Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::top(), and Slic3r::MutableSkipHeapPriorityQueue< T, IndexSetter, LessPredicate, blocking, ResetIndexWhenRemoved >::update().

m_index_setter

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

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

private

m_less_predicate

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

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

private

---

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

• src/libslic3r/MutablePriorityQueue.hpp