MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved > Class Template Reference

#include </home/runner/work/OrcaSlicer/OrcaSlicer/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 ()
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

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 MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >

Member Typedef Documentation

const_iterator

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

using 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 MutablePriorityQueue< T, IndexSetter, LessPredicate, ResetIndexWhenRemoved >::iterator = typename std::vector<T>::iterator

Constructor & Destructor Documentation

MutablePriorityQueue()

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

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

References m_index_setter, and m_less_predicate.

~MutablePriorityQueue()

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

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

inline

{ clear(); }

References clear().

Here is the call graph for this function:

Member Function Documentation

begin()

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

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

inline

{ return m_heap.begin(); }

References m_heap.

cbegin()

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

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

inline

{ return m_heap.cbegin(); }

References m_heap.

cend()

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

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

inline

{ return m_heap.cend(); }

References m_heap.

clear()

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

void MutablePriorityQueue< T, LessPredicate, IndexSetter, 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.
      m_index_setter(m_heap[idx], std::numeric_limits<size_t>::max());
  }
  m_heap.clear();
}

References m_heap, and m_index_setter.

Referenced by ~MutablePriorityQueue().

Here is the caller graph for this function:

empty()

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

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

inline

{ return m_heap.empty(); }

References m_heap.

end()

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

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

inline

{ return m_heap.end(); }

References m_heap.

operator[]() [1/2]

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

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

inlinenoexcept

{ return m_heap[idx]; }

References m_heap.

operator[]() [2/2]

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

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

inlinenoexcept

{ return m_heap[idx]; }

References m_heap.

pop()

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

void MutablePriorityQueue< T, LessPredicate, IndexSetter, 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.front(), std::numeric_limits<size_t>::max());
  }
  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();
}

References m_heap, m_index_setter, and update_heap_down().

Here is the call graph for this function:

push() [1/2]

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

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

References 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, const bool ResetIndexWhenRemoved>

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

References 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, const bool ResetIndexWhenRemoved>

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

inline

{
  assert(idx < m_heap.size());
#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()) {
    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);
}

References m_heap, m_index_setter, 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, const bool ResetIndexWhenRemoved = false>

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

inline

{ m_heap.reserve(cnt); }

References m_heap.

size()

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

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

inline

{ return m_heap.size(); }

References m_heap.

top()

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

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

inline

{ return m_heap.front(); }

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, const bool ResetIndexWhenRemoved = false>

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

inline

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

References m_heap, push(), and remove().

Here is the call graph for this function:

update_heap_down()

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

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

References 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, const bool ResetIndexWhenRemoved>

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

References m_heap, m_index_setter, m_less_predicate, 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, const bool ResetIndexWhenRemoved = false>

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

private

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

m_index_setter

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

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

private

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

m_less_predicate

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

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

private

Referenced by MutablePriorityQueue(), 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