23 #include "heap-scheduler.h"
24 #include "event-impl.h"
32 NS_OBJECT_ENSURE_REGISTERED (HeapScheduler);
35 HeapScheduler::GetTypeId (
void)
37 static TypeId tid = TypeId (
"ns3::HeapScheduler")
38 .SetParent<Scheduler> ()
39 .AddConstructor<HeapScheduler> ()
44 HeapScheduler::HeapScheduler ()
50 Scheduler::Event empty = { 0,{ 0,0}};
51 m_heap.push_back (empty);
54 HeapScheduler::~HeapScheduler ()
60 HeapScheduler::Parent (uint32_t
id)
const
66 HeapScheduler::Sibling (uint32_t
id)
const
72 HeapScheduler::LeftChild (uint32_t
id)
const
78 HeapScheduler::RightChild (uint32_t
id)
const
85 HeapScheduler::Root (
void)
const
92 HeapScheduler::IsRoot (uint32_t
id)
const
95 return (
id == Root ()) ?
true :
false;
99 HeapScheduler::Last (
void)
const
102 return m_heap.size () - 1;
107 HeapScheduler::IsBottom (uint32_t
id)
const
110 return (
id >= m_heap.size ()) ?
true :
false;
114 HeapScheduler::Exch (uint32_t a, uint32_t b)
117 NS_ASSERT (b < m_heap.size () && a < m_heap.size ());
119 Event tmp (m_heap[a]);
120 m_heap[a] = m_heap[b];
125 HeapScheduler::IsLessStrictly (uint32_t a, uint32_t b)
const
128 return m_heap[a] < m_heap[b];
132 HeapScheduler::Smallest (uint32_t a, uint32_t b)
const
135 return IsLessStrictly (a,b) ? a : b;
142 return (m_heap.size () == 1) ?
true :
false;
146 HeapScheduler::BottomUp (
void)
149 uint32_t index = Last ();
150 while (!IsRoot (index)
151 && IsLessStrictly (index, Parent (index)))
153 Exch (index, Parent (index));
154 index = Parent (index);
159 HeapScheduler::TopDown (uint32_t start)
162 uint32_t index = start;
163 uint32_t right = RightChild (index);
164 while (!IsBottom (right))
166 uint32_t left = LeftChild (index);
167 uint32_t tmp = Smallest (left, right);
168 if (IsLessStrictly (index, tmp))
174 right = RightChild (index);
176 if (IsBottom (index))
181 uint32_t left = LeftChild (index);
186 if (IsLessStrictly (index, left))
195 HeapScheduler::Insert (
const Event &ev)
198 m_heap.push_back (ev);
206 return m_heap[Root ()];
212 Event next = m_heap[Root ()];
213 Exch (Root (), Last ());
221 HeapScheduler::Remove (
const Event &ev)
224 uint32_t uid = ev.key.m_uid;
225 for (uint32_t i = 1; i < m_heap.size (); i++)
227 if (uid == m_heap[i].key.m_uid)
#define NS_LOG_FUNCTION(parameters)
virtual Event RemoveNext(void)
#define NS_ASSERT(condition)
#define NS_LOG_COMPONENT_DEFINE(name)
virtual Event PeekNext(void) const
#define NS_LOG_DEBUG(msg)
virtual bool IsEmpty(void) const