#include <src/libslic3r/MutablePriorityQueue.hpp>

Public Types
using	iterator = typename std::vector< T >::iterator

using	const_iterator = typename std::vector< T >::const_iterator

Public Member Functions
	MutablePriorityQueue (IndexSetter &&index_setter, LessPredicate &&less_predicate)

	~MutablePriorityQueue ()

	MutablePriorityQueue (MutablePriorityQueue &&)=default

MutablePriorityQueue &	operator= (MutablePriorityQueue &&)=default

	MutablePriorityQueue (const MutablePriorityQueue &)=delete

MutablePriorityQueue &	operator= (const MutablePriorityQueue &)=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

bool	empty () const

T &	operator[] (std::size_t idx) noexcept

const T &	operator[] (std::size_t idx) const noexcept

iterator	begin ()

iterator	end ()

const_iterator	cbegin () const

const_iterator	cend () const

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)

Private Attributes
std::vector< T >	m_heap

IndexSetter	m_index_setter

LessPredicate	m_less_predicate

Detailed Description

template<typename T, typename IndexSetter, typename LessPredicate, const bool ResetIndexWhenRemoved = false>
class Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >

Member Typedef Documentation

◆ const_iterator

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

using Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::const_iterator = typename std::vector<T>::const_iterator

◆ iterator

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

using Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::iterator = typename std::vector<T>::iterator

Constructor & Destructor Documentation

◆ MutablePriorityQueue() [1/3]

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::MutablePriorityQueue	(	IndexSetter &&	index_setter,
		LessPredicate &&	less_predicate
	)

inline

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

◆ ~MutablePriorityQueue()

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

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

inline

25{ clear(); }

Slic3r::MutablePriorityQueue::clear

void clear()

Definition MutablePriorityQueue.hpp:75

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

Here is the call graph for this function:

◆ MutablePriorityQueue() [2/3]

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

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

default

◆ MutablePriorityQueue() [3/3]

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

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

delete

Member Function Documentation

◆ begin()

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

iterator Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::begin ( )

inline

52{ return m_heap.begin(); }

Slic3r::MutablePriorityQueue::m_heap

std::vector< T > m_heap

Definition MutablePriorityQueue.hpp:62

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

◆ cbegin()

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

const_iterator Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::cbegin ( ) const

inline

54{ return m_heap.cbegin(); }

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

◆ cend()

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

const_iterator Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::cend ( ) const

inline

55{ return m_heap.cend(); }

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

◆ clear()

template<class T , class LessPredicate , class IndexSetter , const bool ResetIndexWhenRemoved>

void Slic3r::MutablePriorityQueue< T, LessPredicate, IndexSetter, ResetIndexWhenRemoved >::clear

inline

{ 
  if constexpr (ResetIndexWhenRemoved) {
    for (size_t idx = 0; idx < m_heap.size(); ++ idx)
      // Mark as removed from the queue.
      m_index_setter(m_heap[idx], this->invalid_id());
  }
  m_heap.clear();
}

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

Here is the caller graph for this function:

◆ empty()

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

bool Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::empty ( ) const

inline

45{ return m_heap.empty(); }

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

◆ end()

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

iterator Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::end ( )

inline

53{ return m_heap.end(); }

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

◆ invalid_id()

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

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

inlinestaticconstexpr

48{ return InvalidQueueID; }

Slic3r::InvalidQueueID

constexpr auto InvalidQueueID

Definition MutablePriorityQueue.hpp:12

References Slic3r::InvalidQueueID.

◆ operator=() [1/2]

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

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

delete

◆ operator=() [2/2]

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

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

default

◆ operator[]() [1/2]

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

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

inlinenoexcept

47{ return m_heap[idx]; }

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

◆ operator[]() [2/2]

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

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

inlinenoexcept

46{ return m_heap[idx]; }

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

◆ pop()

template<class T , class LessPredicate , class IndexSetter , const bool ResetIndexWhenRemoved>

void Slic3r::MutablePriorityQueue< T, LessPredicate, IndexSetter, ResetIndexWhenRemoved >::pop

inline

{
  assert(! m_heap.empty());
  if constexpr (ResetIndexWhenRemoved) {
    // Mark as removed from the queue.
    m_index_setter(m_heap.front(), this->invalid_id());
  }
  if (m_heap.size() > 1) {
    m_heap.front() = m_heap.back();
    m_heap.pop_back();
    m_index_setter(m_heap.front(), 0);
    update_heap_down(0, m_heap.size() - 1);
  } else
    m_heap.clear();
}

◆ push() [1/2]

template<class T , class LessPredicate , class IndexSetter , const bool ResetIndexWhenRemoved>

void Slic3r::MutablePriorityQueue< T, LessPredicate, IndexSetter, ResetIndexWhenRemoved >::push ( const T & item )

inline

{
  size_t idx = m_heap.size();
  m_heap.emplace_back(item);
  m_index_setter(m_heap.back(), idx);
  update_heap_up(0, idx);
}

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

Here is the caller graph for this function:

◆ push() [2/2]

template<class T , class LessPredicate , class IndexSetter , const bool ResetIndexWhenRemoved>

void Slic3r::MutablePriorityQueue< T, LessPredicate, IndexSetter, ResetIndexWhenRemoved >::push ( T && item )

inline

{
  size_t idx = m_heap.size();
  m_heap.emplace_back(std::move(item));
  m_index_setter(m_heap.back(), idx);
  update_heap_up(0, idx);
}

◆ remove()

template<class T , class LessPredicate , class IndexSetter , const bool ResetIndexWhenRemoved>

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

inline

{
  assert(idx < m_heap.size());
  // Only mark as removed from the queue in release mode, if configured so.
  if constexpr (ResetIndexWhenRemoved) {
    // Mark as removed from the queue.
    m_index_setter(m_heap[idx], this->invalid_id());
  }
  if (idx + 1 == m_heap.size()) {
    m_heap.pop_back();
    return;
  }
  m_heap[idx] = m_heap.back();
  m_index_setter(m_heap[idx], idx);
  m_heap.pop_back();
  update_heap_down(idx, m_heap.size() - 1);
  update_heap_up(0, idx);
}

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

Here is the caller graph for this function:

◆ reserve()

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

void Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::reserve ( size_t cnt )

inline

36{ m_heap.reserve(cnt); }

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

◆ size()

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

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

inline

44{ return m_heap.size(); }

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

◆ top()

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

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

inline

40{ return m_heap.front(); }

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

◆ update()

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

void Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::update ( size_t idx )

inline

42{ T item = m_heap[idx]; remove(idx); push(item); }

Slic3r::MutablePriorityQueue::push

void push(const T &item)

Definition MutablePriorityQueue.hpp:86

Slic3r::MutablePriorityQueue::remove

void remove(size_t idx)

Definition MutablePriorityQueue.hpp:121

References Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::m_heap, Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::push(), and Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::remove().

Here is the call graph for this function:

◆ update_heap_down()

template<class T , class LessPredicate , class IndexSetter , const bool ResetIndexWhenRemoved>

void Slic3r::MutablePriorityQueue< T, LessPredicate, IndexSetter, ResetIndexWhenRemoved >::update_heap_down	(	size_t	top,
		size_t	bottom
	)

inlineprotected

{
  size_t parentIdx = top;
  T *parent = &m_heap[parentIdx];
  for (;;) {
    size_t childIdx = (parentIdx << 1) + 1;
    if (childIdx > bottom)
      break;
    T *child = &m_heap[childIdx];
    size_t child2Idx = childIdx + 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 , const bool ResetIndexWhenRemoved>

void Slic3r::MutablePriorityQueue< T, LessPredicate, IndexSetter, ResetIndexWhenRemoved >::update_heap_up	(	size_t	top,
		size_t	bottom
	)

inlineprotected

{
  size_t childIdx = bottom;
  T *child = &m_heap[childIdx];
  for (;;) {
    size_t parentIdx = (childIdx - 1) >> 1;
    if (childIdx == 0 || 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 , const bool ResetIndexWhenRemoved = false>

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

private

◆ m_index_setter

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

IndexSetter Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::m_index_setter

private

◆ m_less_predicate

template<typename T , typename IndexSetter , typename LessPredicate , const bool ResetIndexWhenRemoved = false>

LessPredicate Slic3r::MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::m_less_predicate

private

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

src/libslic3r/MutablePriorityQueue.hpp

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ iterator

Constructor & Destructor Documentation

◆ MutablePriorityQueue() [1/3]

◆ ~MutablePriorityQueue()

◆ MutablePriorityQueue() [2/3]

◆ MutablePriorityQueue() [3/3]

Member Function Documentation

◆ begin()

◆ cbegin()

◆ cend()

◆ clear()

◆ empty()

◆ end()

◆ invalid_id()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ pop()

◆ push() [1/2]

◆ push() [2/2]

◆ remove()

◆ reserve()

◆ size()

◆ top()

◆ update()

◆ update_heap_down()

◆ update_heap_up()

Member Data Documentation

◆ m_heap

◆ m_index_setter

◆ m_less_predicate