a binary heap event scheduler More...
#include "heap-scheduler.h"
Public Member Functions | |
HeapScheduler () | |
Constructor. | |
~HeapScheduler () override | |
Destructor. | |
void | Insert (const Scheduler::Event &ev) override |
Insert a new Event in the schedule. | |
bool | IsEmpty () const override |
Test if the schedule is empty. | |
Scheduler::Event | PeekNext () const override |
Get a pointer to the next event. | |
void | Remove (const Scheduler::Event &ev) override |
Remove a specific event from the event list. | |
Scheduler::Event | RemoveNext () override |
Remove the earliest event from the event list. | |
Public Member Functions inherited from ns3::Scheduler | |
~Scheduler () override=0 | |
Destructor. | |
Public Member Functions inherited from ns3::Object | |
Object () | |
Constructor. | |
~Object () override | |
Destructor. | |
void | AggregateObject (Ptr< Object > other) |
Aggregate two Objects together. | |
void | Dispose () |
Dispose of this Object. | |
AggregateIterator | GetAggregateIterator () const |
Get an iterator to the Objects aggregated to this one. | |
TypeId | GetInstanceTypeId () const override |
Get the most derived TypeId for this Object. | |
template<typename T > | |
Ptr< T > | GetObject () const |
Get a pointer to the requested aggregated Object. | |
template<> | |
Ptr< Object > | GetObject () const |
Specialization of () for objects of type ns3::Object. | |
template<typename T > | |
Ptr< T > | GetObject (TypeId tid) const |
Get a pointer to the requested aggregated Object by TypeId. | |
template<> | |
Ptr< Object > | GetObject (TypeId tid) const |
Specialization of (TypeId tid) for objects of type ns3::Object. | |
void | Initialize () |
Invoke DoInitialize on all Objects aggregated to this one. | |
bool | IsInitialized () const |
Check if the object has been initialized. | |
void | UnidirectionalAggregateObject (Ptr< Object > other) |
Aggregate an Object to another Object. | |
Public Member Functions inherited from ns3::SimpleRefCount< Object, ObjectBase, ObjectDeleter > | |
SimpleRefCount () | |
Default constructor. | |
SimpleRefCount (const SimpleRefCount &o) | |
Copy constructor. | |
uint32_t | GetReferenceCount () const |
Get the reference count of the object. | |
SimpleRefCount & | operator= (const SimpleRefCount &o) |
Assignment operator. | |
void | Ref () const |
Increment the reference count. | |
void | Unref () const |
Decrement the reference count. | |
Public Member Functions inherited from ns3::ObjectBase | |
virtual | ~ObjectBase () |
Virtual destructor. | |
void | GetAttribute (std::string name, AttributeValue &value, bool permissive=false) const |
Get the value of an attribute, raising fatal errors if unsuccessful. | |
bool | GetAttributeFailSafe (std::string name, AttributeValue &value) const |
Get the value of an attribute without raising errors. | |
void | SetAttribute (std::string name, const AttributeValue &value) |
Set a single attribute, raising fatal errors if unsuccessful. | |
bool | SetAttributeFailSafe (std::string name, const AttributeValue &value) |
Set a single attribute without raising errors. | |
bool | TraceConnect (std::string name, std::string context, const CallbackBase &cb) |
Connect a TraceSource to a Callback with a context. | |
bool | TraceConnectWithoutContext (std::string name, const CallbackBase &cb) |
Connect a TraceSource to a Callback without a context. | |
bool | TraceDisconnect (std::string name, std::string context, const CallbackBase &cb) |
Disconnect from a TraceSource a Callback previously connected with a context. | |
bool | TraceDisconnectWithoutContext (std::string name, const CallbackBase &cb) |
Disconnect from a TraceSource a Callback previously connected without a context. | |
Static Public Member Functions | |
static TypeId | GetTypeId () |
Register this type. | |
Static Public Member Functions inherited from ns3::Scheduler | |
static TypeId | GetTypeId () |
Register this type. | |
Static Public Member Functions inherited from ns3::Object | |
static TypeId | GetTypeId () |
Register this type. | |
Static Public Member Functions inherited from ns3::ObjectBase | |
static TypeId | GetTypeId () |
Get the type ID. | |
Private Types | |
typedef std::vector< Scheduler::Event > | BinaryHeap |
Event list type: vector of Events, managed as a heap. | |
Private Member Functions | |
void | BottomUp () |
Percolate a newly inserted Last item to its proper position. | |
void | Exch (std::size_t a, std::size_t b) |
Swap two items. | |
bool | IsBottom (std::size_t id) const |
Test if an index is at the bottom of the heap. | |
bool | IsLessStrictly (std::size_t a, std::size_t b) const |
Compare (less than) two items. | |
bool | IsRoot (std::size_t id) const |
Test if an index is the root. | |
std::size_t | Last () const |
Return the index of the last element. | |
std::size_t | LeftChild (std::size_t id) const |
Get the left child of a given entry. | |
std::size_t | Parent (std::size_t id) const |
Get the parent index of a given entry. | |
std::size_t | RightChild (std::size_t id) const |
Get the right child index of a given entry. | |
std::size_t | Root () const |
Get the root index of the heap. | |
std::size_t | Sibling (std::size_t id) const |
Get the next sibling of a given entry. | |
std::size_t | Smallest (std::size_t a, std::size_t b) const |
Minimum of two items. | |
void | TopDown (std::size_t start) |
Percolate a deletion bubble down the heap. | |
Private Attributes | |
BinaryHeap | m_heap |
The event list. | |
Additional Inherited Members | |
Protected Member Functions inherited from ns3::Object | |
Object (const Object &o) | |
Copy an Object. | |
virtual void | DoDispose () |
Destructor implementation. | |
virtual void | DoInitialize () |
Initialize() implementation. | |
virtual void | NotifyNewAggregate () |
Notify all Objects aggregated to this one of a new Object being aggregated. | |
Protected Member Functions inherited from ns3::ObjectBase | |
void | ConstructSelf (const AttributeConstructionList &attributes) |
Complete construction of ObjectBase; invoked by derived classes. | |
virtual void | NotifyConstructionCompleted () |
Notifier called once the ObjectBase is fully constructed. | |
Related Symbols inherited from ns3::ObjectBase | |
static TypeId | GetObjectIid () |
Ensure the TypeId for ObjectBase gets fully configured to anchor the inheritance tree properly. | |
a binary heap event scheduler
This code started as a c++ translation of a Java-based code written in 2005 to implement a heap sort. So, this binary heap is really a pretty straightforward implementation of the classic data structure, implemented on a std::vector
. This implementation does not make use of any of the heap functions from the STL. Not much to say about it.
What is smart about this code ?
Operation | Amortized Time | Reason |
---|---|---|
Insert() | Logarithmic | Heapify |
IsEmpty() | Constant | Explicit queue size |
PeekNext() | Constant | Heap kept sorted |
Remove() | Logarithmic | Search, heapify |
RemoveNext() | Logarithmic | Heapify |
Category | Memory | Reason |
---|---|---|
Overhead | 3 x sizeof (*) (24 bytes) | std::vector |
Per Event | 0 | Events stored in std::vector directly |
Definition at line 62 of file heap-scheduler.h.
|
private |
Event list type: vector of Events, managed as a heap.
Definition at line 85 of file heap-scheduler.h.
ns3::HeapScheduler::HeapScheduler | ( | ) |
Constructor.
Definition at line 40 of file heap-scheduler.cc.
References m_heap, and NS_LOG_FUNCTION.
|
override |
|
private |
Percolate a newly inserted Last item to its proper position.
Definition at line 144 of file heap-scheduler.cc.
References Exch(), IsLessStrictly(), IsRoot(), Last(), NS_LOG_FUNCTION, and Parent().
Referenced by Insert().
|
inlineprivate |
Swap two items.
[in] | a | The first item. |
[in] | b | The second item. |
Definition at line 112 of file heap-scheduler.cc.
References m_heap, NS_ASSERT, NS_LOG_DEBUG, and NS_LOG_FUNCTION.
Referenced by BottomUp(), Remove(), RemoveNext(), and TopDown().
|
static |
Register this type.
Definition at line 31 of file heap-scheduler.cc.
References ns3::TypeId::SetParent().
Referenced by SimulatorTestSuite::SimulatorTestSuite().
|
overridevirtual |
Insert a new Event in the schedule.
[in] | ev | Event to store in the event list |
Implements ns3::Scheduler.
Definition at line 191 of file heap-scheduler.cc.
References BottomUp(), m_heap, and NS_LOG_FUNCTION.
|
inlineprivate |
Test if an index is at the bottom of the heap.
[in] | id | The index to test. |
true
if the index is at the bottom. Definition at line 105 of file heap-scheduler.cc.
References m_heap, and NS_LOG_FUNCTION.
Referenced by TopDown().
|
overridevirtual |
Test if the schedule is empty.
true
if the event list is empty and false
otherwise. Implements ns3::Scheduler.
Definition at line 137 of file heap-scheduler.cc.
References m_heap, and NS_LOG_FUNCTION.
|
inlineprivate |
Compare (less than) two items.
[in] | a | The first item. |
[in] | b | The second item. |
true
if a
< b
Definition at line 123 of file heap-scheduler.cc.
References m_heap, and NS_LOG_FUNCTION.
Referenced by BottomUp(), Smallest(), and TopDown().
|
inlineprivate |
Test if an index is the root.
[in] | id | The index to test. |
true
if the id is the root. Definition at line 91 of file heap-scheduler.cc.
References NS_LOG_FUNCTION, and Root().
Referenced by BottomUp().
|
private |
Return the index of the last element.
Definition at line 98 of file heap-scheduler.cc.
References m_heap, and NS_LOG_FUNCTION.
Referenced by BottomUp(), Remove(), and RemoveNext().
|
inlineprivate |
Get the left child of a given entry.
[in] | id | The parent index. |
Definition at line 70 of file heap-scheduler.cc.
References NS_LOG_FUNCTION.
Referenced by TopDown().
|
inlineprivate |
Get the parent index of a given entry.
[in] | id | The child index. |
Definition at line 56 of file heap-scheduler.cc.
References NS_LOG_FUNCTION.
Referenced by BottomUp().
|
overridevirtual |
Get a pointer to the next event.
This method cannot be invoked if the list is empty.
Implements ns3::Scheduler.
Definition at line 199 of file heap-scheduler.cc.
References m_heap, NS_LOG_FUNCTION, and Root().
|
overridevirtual |
Remove a specific event from the event list.
This method cannot be invoked if the list is empty.
[in] | ev | The event to remove |
Implements ns3::Scheduler.
Definition at line 217 of file heap-scheduler.cc.
References Exch(), ns3::Scheduler::Event::impl, ns3::Scheduler::Event::key, Last(), m_heap, ns3::Scheduler::EventKey::m_uid, NS_ASSERT, NS_LOG_FUNCTION, and TopDown().
|
overridevirtual |
Remove the earliest event from the event list.
This method cannot be invoked if the list is empty.
Implements ns3::Scheduler.
Definition at line 206 of file heap-scheduler.cc.
References Exch(), Last(), m_heap, NS_LOG_FUNCTION, Root(), and TopDown().
|
inlineprivate |
Get the right child index of a given entry.
[in] | id | The parent index. |
Definition at line 77 of file heap-scheduler.cc.
References NS_LOG_FUNCTION.
Referenced by TopDown().
|
inlineprivate |
Get the root index of the heap.
Definition at line 84 of file heap-scheduler.cc.
References NS_LOG_FUNCTION.
Referenced by IsRoot(), PeekNext(), and RemoveNext().
|
private |
Get the next sibling of a given entry.
[in] | id | The starting index. |
Definition at line 63 of file heap-scheduler.cc.
References NS_LOG_FUNCTION.
|
inlineprivate |
Minimum of two items.
[in] | a | The first item. |
[in] | b | The second item. |
Definition at line 130 of file heap-scheduler.cc.
References IsLessStrictly(), and NS_LOG_FUNCTION.
Referenced by TopDown().
|
private |
Percolate a deletion bubble down the heap.
[in] | start | Starting entry. |
Definition at line 156 of file heap-scheduler.cc.
References Exch(), IsBottom(), IsLessStrictly(), LeftChild(), NS_ASSERT, NS_LOG_FUNCTION, RightChild(), and Smallest().
Referenced by Remove(), and RemoveNext().
|
private |
The event list.
Definition at line 173 of file heap-scheduler.h.
Referenced by HeapScheduler(), Exch(), Insert(), IsBottom(), IsEmpty(), IsLessStrictly(), Last(), PeekNext(), Remove(), and RemoveNext().