A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
ns3::HeapScheduler Class Reference

a binary heap event scheduler More...

#include <heap-scheduler.h>

+ Inheritance diagram for ns3::HeapScheduler:

Public Member Functions

virtual void Insert (const Event &ev)
 
virtual bool IsEmpty (void) const
 
virtual Event PeekNext (void) const
 
virtual void Remove (const Event &ev)
 
virtual Event RemoveNext (void)
 
- Public Member Functions inherited from ns3::Scheduler
virtual void Insert (const Event &ev)=0
 
virtual void Remove (const Event &ev)=0
 
- Public Member Functions inherited from ns3::Object
void AggregateObject (Ptr< Object > other)
 
void Dispose (void)
 
AggregateIterator GetAggregateIterator (void) const
 
virtual TypeId GetInstanceTypeId (void) const
 
template<typename T >
Ptr< T > GetObject (void) const
 
template<typename T >
Ptr< T > GetObject (TypeId tid) const
 
void Initialize (void)
 
- Public Member Functions inherited from ns3::SimpleRefCount< Object, ObjectBase, ObjectDeleter >
 SimpleRefCount (const SimpleRefCount &o)
 
uint32_t GetReferenceCount (void) const
 
SimpleRefCountoperator= (const SimpleRefCount &o)
 
void Ref (void) const
 
void Unref (void) const
 
- Public Member Functions inherited from ns3::ObjectBase
void GetAttribute (std::string name, AttributeValue &value) const
 
bool GetAttributeFailSafe (std::string name, AttributeValue &attribute) const
 
void SetAttribute (std::string name, const AttributeValue &value)
 
bool SetAttributeFailSafe (std::string name, const AttributeValue &value)
 
bool TraceConnect (std::string name, std::string context, const CallbackBase &cb)
 
bool TraceConnectWithoutContext (std::string name, const CallbackBase &cb)
 
bool TraceDisconnect (std::string name, std::string context, const CallbackBase &cb)
 
bool TraceDisconnectWithoutContext (std::string name, const CallbackBase &cb)
 

Static Public Member Functions

static TypeId GetTypeId (void)
 
- Static Public Member Functions inherited from ns3::Scheduler
static TypeId GetTypeId (void)
 
- Static Public Member Functions inherited from ns3::Object
static TypeId GetTypeId (void)
 
- Static Public Member Functions inherited from ns3::SimpleRefCount< Object, ObjectBase, ObjectDeleter >
static void Cleanup (void)
 
- Static Public Member Functions inherited from ns3::ObjectBase
static TypeId GetTypeId (void)
 

Private Types

typedef std::vector< Event > BinaryHeap
 

Private Member Functions

void BottomUp (void)
 
void Exch (uint32_t a, uint32_t b)
 
bool IsBottom (uint32_t id) const
 
bool IsLessStrictly (uint32_t a, uint32_t b) const
 
bool IsRoot (uint32_t id) const
 
uint32_t Last (void) const
 
uint32_t LeftChild (uint32_t id) const
 
uint32_t Parent (uint32_t id) const
 
uint32_t RightChild (uint32_t id) const
 
uint32_t Root (void) const
 
uint32_t Sibling (uint32_t id) const
 
uint32_t Smallest (uint32_t a, uint32_t b) const
 
void TopDown (uint32_t start)
 

Private Attributes

BinaryHeap m_heap
 

Additional Inherited Members

- Protected Member Functions inherited from ns3::Object
 Object (const Object &o)
 
virtual void DoDispose (void)
 
virtual void DoInitialize (void)
 
virtual void NotifyNewAggregate (void)
 
- Protected Member Functions inherited from ns3::ObjectBase
void ConstructSelf (const AttributeConstructionList &attributes)
 
virtual void NotifyConstructionCompleted (void)
 

Detailed Description

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. Not much to say about it.

What is smart about this code ?

  • it does not use the index 0 in the array to avoid having to convert C-style array indexes (which start at zero) and heap-style indexes (which start at 1). This is why all indexes start at 1, and that the index of the root is 1.
  • It uses a slightly non-standard while loop for top-down heapify to move one if statement out of the loop.

Doxygen introspection did not find any typical Config paths.
No Attributes are defined for this type.
No TraceSources are defined for this type.

Definition at line 47 of file heap-scheduler.h.

Member Function Documentation

bool ns3::HeapScheduler::IsEmpty ( void  ) const
virtual
Returns
true if the event list is empty and false otherwise.

Implements ns3::Scheduler.

Definition at line 139 of file heap-scheduler.cc.

References NS_LOG_FUNCTION.

Scheduler::Event ns3::HeapScheduler::PeekNext ( void  ) const
virtual
Returns
a pointer to the next earliest event. The caller takes ownership of the returned pointer.

This method cannot be invoked if the list is empty.

Implements ns3::Scheduler.

Definition at line 203 of file heap-scheduler.cc.

References NS_LOG_FUNCTION.

Scheduler::Event ns3::HeapScheduler::RemoveNext ( void  )
virtual

This method cannot be invoked if the list is empty. Remove the next earliest event from the event list.

Implements ns3::Scheduler.

Definition at line 209 of file heap-scheduler.cc.

References NS_LOG_FUNCTION.


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