a binary heap event scheduler More...

#include <heap-scheduler.h>

Inheritance diagram for ns3::HeapScheduler:

Collaboration diagram for ns3::HeapScheduler:

Public Member Functions
	HeapScheduler ()
virtual	~HeapScheduler ()
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	~Scheduler ()=0
virtual void	Insert (const Event &ev)=0
virtual void	Remove (const Event &ev)=0
Public Member Functions inherited from ns3::Object
	Object ()
virtual	~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	Start (void)
Public Member Functions inherited from ns3::SimpleRefCount< Object, ObjectBase, ObjectDeleter >
	SimpleRefCount ()
	SimpleRefCount (const SimpleRefCount &o)
uint32_t	GetReferenceCount (void) const
SimpleRefCount &	operator= (const SimpleRefCount &o)
void	Ref (void) const
void	Unref (void) const
Public Member Functions inherited from ns3::ObjectBase
virtual	~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)
	This method returns the TypeId associated to ns3::HeapScheduler.

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	DoStart (void)
virtual void	NotifyNewAggregate (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.

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

Member Typedef Documentation

typedef std::vector<Event> ns3::HeapScheduler::BinaryHeap

private

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

Constructor & Destructor Documentation

ns3::HeapScheduler::HeapScheduler ( )

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

References m_heap.

ns3::HeapScheduler::~HeapScheduler ( )

virtual

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

Member Function Documentation

void ns3::HeapScheduler::BottomUp ( void )

private

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

References Exch(), IsLessStrictly(), IsRoot(), Last(), and Parent().

Referenced by Insert().

Here is the call graph for this function:

Here is the caller graph for this function:

void ns3::HeapScheduler::Exch	(	uint32_t	a,
		uint32_t	b
	)

inlineprivate

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

References m_heap, NS_ASSERT, and NS_LOG_DEBUG.

Referenced by BottomUp(), Remove(), RemoveNext(), and TopDown().

Here is the caller graph for this function:

TypeId ns3::HeapScheduler::GetTypeId ( void )

static

This method returns the TypeId associated to ns3::HeapScheduler.

No Attributes defined for this type.
No TraceSources defined for this type.

Reimplemented from ns3::Scheduler.

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

References ns3::TypeId::SetParent().

Referenced by ns3::SimulatorTestSuite::SimulatorTestSuite().

Here is the call graph for this function:

Here is the caller graph for this function:

void ns3::HeapScheduler::Insert ( const Event & ev )

virtual

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

References BottomUp(), and m_heap.

Here is the call graph for this function:

bool ns3::HeapScheduler::IsBottom ( uint32_t id ) const

inlineprivate

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

References m_heap.

Referenced by TopDown().

Here is the caller graph for this function:

bool ns3::HeapScheduler::IsEmpty ( void ) const

virtual

Returns: true if the event list is empty and false otherwise.

Implements ns3::Scheduler.

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

References m_heap.

bool ns3::HeapScheduler::IsLessStrictly	(	uint32_t	a,
		uint32_t	b
	)		const

inlineprivate

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

References m_heap.

Referenced by BottomUp(), Smallest(), and TopDown().

Here is the caller graph for this function:

bool ns3::HeapScheduler::IsRoot ( uint32_t id ) const

inlineprivate

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

References Root().

Referenced by BottomUp().

Here is the call graph for this function:

Here is the caller graph for this function:

uint32_t ns3::HeapScheduler::Last ( void ) const

private

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

References m_heap.

Referenced by BottomUp(), Remove(), and RemoveNext().

Here is the caller graph for this function:

uint32_t ns3::HeapScheduler::LeftChild ( uint32_t id ) const

inlineprivate

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

Referenced by TopDown().

Here is the caller graph for this function:

uint32_t ns3::HeapScheduler::Parent ( uint32_t id ) const

inlineprivate

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

Referenced by BottomUp().

Here is the caller graph for this 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 186 of file heap-scheduler.cc.

References m_heap, and Root().

Here is the call graph for this function:

void ns3::HeapScheduler::Remove ( const Event & ev )

virtual

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

References Exch(), Last(), m_heap, NS_ASSERT, and TopDown().

Here is the call graph for this 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 191 of file heap-scheduler.cc.

References Exch(), Last(), m_heap, Root(), and TopDown().

Here is the call graph for this function:

uint32_t ns3::HeapScheduler::RightChild ( uint32_t id ) const

inlineprivate

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

Referenced by TopDown().

Here is the caller graph for this function:

uint32_t ns3::HeapScheduler::Root ( void ) const

inlineprivate

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

Referenced by IsRoot(), PeekNext(), and RemoveNext().

Here is the caller graph for this function:

uint32_t ns3::HeapScheduler::Sibling ( uint32_t id ) const

private

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

uint32_t ns3::HeapScheduler::Smallest	(	uint32_t	a,
		uint32_t	b
	)		const

inlineprivate

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

References IsLessStrictly().

Referenced by TopDown().

Here is the call graph for this function:

Here is the caller graph for this function:

void ns3::HeapScheduler::TopDown ( uint32_t start )

private

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

References Exch(), IsBottom(), IsLessStrictly(), LeftChild(), NS_ASSERT, RightChild(), Smallest(), and visualizer.core::start().

Referenced by Remove(), and RemoveNext().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

BinaryHeap ns3::HeapScheduler::m_heap

private

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

Referenced by Exch(), HeapScheduler(), Insert(), IsBottom(), IsEmpty(), IsLessStrictly(), Last(), PeekNext(), Remove(), and RemoveNext().

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

src/core/model/heap-scheduler.h
doc/introspected-doxygen.h
src/core/model/heap-scheduler.cc

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation