A Discrete-Event Network Simulator
API
heap-scheduler.h
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2005 INRIA
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
19  */
20 
21 #ifndef HEAP_SCHEDULER_H
22 #define HEAP_SCHEDULER_H
23 
24 #include "scheduler.h"
25 #include <stdint.h>
26 #include <vector>
27 
34 namespace ns3 {
35 
53 class HeapScheduler : public Scheduler
54 {
55 public:
60  static TypeId GetTypeId (void);
61 
63  HeapScheduler ();
65  virtual ~HeapScheduler ();
66 
67  // Inherited
68  virtual void Insert (const Scheduler::Event &ev);
69  virtual bool IsEmpty (void) const;
70  virtual Scheduler::Event PeekNext (void) const;
71  virtual Scheduler::Event RemoveNext (void);
72  virtual void Remove (const Scheduler::Event &ev);
73 
74 private:
76  typedef std::vector<Scheduler::Event> BinaryHeap;
77 
84  inline uint32_t Parent (uint32_t id) const;
91  uint32_t Sibling (uint32_t id) const;
98  inline uint32_t LeftChild (uint32_t id) const;
105  inline uint32_t RightChild (uint32_t id) const;
111  inline uint32_t Root (void) const;
116  uint32_t Last (void) const;
123  inline bool IsRoot (uint32_t id) const;
130  inline bool IsBottom (uint32_t id) const;
138  inline bool IsLessStrictly (uint32_t a, uint32_t b) const;
146  inline uint32_t Smallest (uint32_t a, uint32_t b) const;
153  inline void Exch (uint32_t a, uint32_t b);
155  void BottomUp (void);
161  void TopDown (uint32_t start);
162 
164  BinaryHeap m_heap;
165 };
166 
167 } // namespace ns3
168 
169 #endif /* HEAP_SCHEDULER_H */
uint32_t Sibling(uint32_t id) const
Get the next sibling of a given entry.
virtual ~HeapScheduler()
Destructor.
void TopDown(uint32_t start)
Percolate a deletion bubble down the heap.
virtual Scheduler::Event RemoveNext(void)
Remove the earliest event from the event list.
def start()
Definition: core.py:1482
bool IsLessStrictly(uint32_t a, uint32_t b) const
Compare (less than) two items.
virtual Scheduler::Event PeekNext(void) const
Get a pointer to the next event.
static TypeId GetTypeId(void)
Register this type.
bool IsRoot(uint32_t id) const
Test if an index is the root.
void Exch(uint32_t a, uint32_t b)
Swap two items.
uint32_t RightChild(uint32_t id) const
Get the right child index of a given entry.
ns3::Scheduler abstract base class, ns3::Scheduler::Event and ns3::Scheduler::EventKey declarations...
a binary heap event scheduler
uint32_t Smallest(uint32_t a, uint32_t b) const
Minimum of two items.
Maintain the event list.
Definition: scheduler.h:66
virtual void Insert(const Scheduler::Event &ev)
Insert a new Event in the schedule.
BinaryHeap m_heap
The event list.
Scheduler event.
Definition: scheduler.h:92
Every class exported by the ns3 library is enclosed in the ns3 namespace.
HeapScheduler()
Constructor.
bool IsBottom(uint32_t id) const
Test if an index is at the bottom of the heap.
uint32_t Last(void) const
Return the index of the last element.
virtual void Remove(const Scheduler::Event &ev)
Remove a specific event from the event list.
void BottomUp(void)
Percolate a newly inserted Last item to its proper position.
virtual bool IsEmpty(void) const
Test if the schedule is empty.
uint32_t Parent(uint32_t id) const
Get the parent index of a given entry.
a unique identifier for an interface.
Definition: type-id.h:58
std::vector< Scheduler::Event > BinaryHeap
Event list type: vector of Events, managed as a heap.
uint32_t Root(void) const
Get the root index of the heap.
uint32_t LeftChild(uint32_t id) const
Get the left child of a given entry.