dart::PriorityQueue< P, V > Class Template Reference

#include <priority_queue.h>

Classes
struct	Entry

Public Member Functions
	PriorityQueue ()
	~PriorityQueue ()
bool	IsEmpty () const
void	Insert (const P &priority, const V &value)
const Entry &	Minimum () const
void	RemoveMinimum ()
bool	RemoveByValue (const V &value)
bool	ContainsValue (const V &value)
bool	InsertOrChangePriority (const P &priority, const V &value)

Static Public Attributes
static constexpr intptr_t	kMinimumSize = 16

Detailed Description

template<typename P, typename V>
class dart::PriorityQueue< P, V >

Definition at line 25 of file priority_queue.h.

Constructor & Destructor Documentation

PriorityQueue()

template<typename P , typename V >

dart::PriorityQueue< P, V >::PriorityQueue ( )

inline

Definition at line 34 of file priority_queue.h.

                  : hashmap_(&MatchFun, kMinimumSize) {
    min_heap_size_ = kMinimumSize;
    min_heap_ =
        reinterpret_cast<Entry*>(malloc(sizeof(Entry) * min_heap_size_));
    if (min_heap_ == nullptr) FATAL("Cannot allocate memory.");
    size_ = 0;
  }

~PriorityQueue()

template<typename P , typename V >

dart::PriorityQueue< P, V >::~PriorityQueue ( )

inline

Definition at line 42 of file priority_queue.h.

{ free(min_heap_); }

Member Function Documentation

ContainsValue()

template<typename P , typename V >

bool dart::PriorityQueue< P, V >::ContainsValue ( const V &  value )

inline

Definition at line 92 of file priority_queue.h.

{ return FindMapEntry(value) != nullptr; }

Insert()

template<typename P , typename V >

void dart::PriorityQueue< P, V >::Insert ( const P &  priority, const V &  value  )

inline

Definition at line 49 of file priority_queue.h.

                                                 {
    ASSERT(!ContainsValue(value));
 
    if (size_ == min_heap_size_) {
      Resize(min_heap_size_ << 1);
    }
 
    Set(size_, {priority, value});
    BubbleUp(size_);
 
    size_++;
  }

InsertOrChangePriority()

template<typename P , typename V >

bool dart::PriorityQueue< P, V >::InsertOrChangePriority ( const P &  priority, const V &  value  )

inline

Definition at line 96 of file priority_queue.h.

                                                                 {
    auto map_entry = FindMapEntry(value);
    if (map_entry == nullptr) {
      Insert(priority, value);
      return true;
    }
 
    const intptr_t offset = ValueOfMapEntry(map_entry);
    ASSERT(offset < size_);
 
    Entry& entry = min_heap_[offset];
    entry.priority = priority;
    if (offset == 0) {
      BubbleDown(offset);
    } else {
      intptr_t parent = (offset - 1) / 2;
      intptr_t diff = entry.priority - min_heap_[parent].priority;
      if (diff < 0) {
        BubbleUp(offset);
      } else if (diff > 0) {
        BubbleDown(offset);
      }
    }
    return false;
  }

IsEmpty()

template<typename P , typename V >

bool dart::PriorityQueue< P, V >::IsEmpty ( ) const

inline

Definition at line 45 of file priority_queue.h.

{ return size_ == 0; }

Minimum()

template<typename P , typename V >

const Entry & dart::PriorityQueue< P, V >::Minimum ( ) const

inline

Definition at line 65 of file priority_queue.h.

                               {
    ASSERT(!IsEmpty());
    return min_heap_[0];
  }

RemoveByValue()

template<typename P , typename V >

bool dart::PriorityQueue< P, V >::RemoveByValue ( const V &  value )

inline

Definition at line 79 of file priority_queue.h.

                                     {
    auto entry = FindMapEntry(value);
    if (entry != nullptr) {
      const intptr_t offset = ValueOfMapEntry(entry);
      RemoveAt(offset);
 
      ASSERT(hashmap_.size() == size_);
      return true;
    }
    return false;
  }

RemoveMinimum()

template<typename P , typename V >

void dart::PriorityQueue< P, V >::RemoveMinimum ( )

inline

Definition at line 71 of file priority_queue.h.

                       {
    ASSERT(!IsEmpty());
    RemoveAt(0);
  }

Member Data Documentation

kMinimumSize

template<typename P , typename V >

constexpr intptr_t dart::PriorityQueue< P, V >::kMinimumSize = 16

staticconstexpr

Definition at line 27 of file priority_queue.h.

---

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

• third_party/dart-lang/sdk/runtime/platform/priority_queue.h