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 
72 class HeapScheduler : public Scheduler
73 {
74 public:
79  static TypeId GetTypeId (void);
80 
82  HeapScheduler ();
84  virtual ~HeapScheduler ();
85 
86  // Inherited
87  virtual void Insert (const Scheduler::Event &ev);
88  virtual bool IsEmpty (void) const;
89  virtual Scheduler::Event PeekNext (void) const;
90  virtual Scheduler::Event RemoveNext (void);
91  virtual void Remove (const Scheduler::Event &ev);
92 
93 private:
95  typedef std::vector<Scheduler::Event> BinaryHeap;
96 
103  inline std::size_t Parent (std::size_t id) const;
110  std::size_t Sibling (std::size_t id) const;
117  inline std::size_t LeftChild (std::size_t id) const;
124  inline std::size_t RightChild (std::size_t id) const;
130  inline std::size_t Root (void) const;
135  std::size_t Last (void) const;
142  inline bool IsRoot (std::size_t id) const;
149  inline bool IsBottom (std::size_t id) const;
157  inline bool IsLessStrictly (std::size_t a, std::size_t b) const;
165  inline std::size_t Smallest (std::size_t a, std::size_t b) const;
172  inline void Exch (std::size_t a, std::size_t b);
174  void BottomUp (void);
180  void TopDown (std::size_t start);
181 
184 };
185 
186 } // namespace ns3
187 
188 #endif /* HEAP_SCHEDULER_H */
a binary heap event scheduler
void TopDown(std::size_t start)
Percolate a deletion bubble down the heap.
bool IsLessStrictly(std::size_t a, std::size_t b) const
Compare (less than) two items.
HeapScheduler()
Constructor.
static TypeId GetTypeId(void)
Register this type.
std::size_t RightChild(std::size_t id) const
Get the right child index of a given entry.
BinaryHeap m_heap
The event list.
bool IsRoot(std::size_t id) const
Test if an index is the root.
std::vector< Scheduler::Event > BinaryHeap
Event list type: vector of Events, managed as a heap.
void Exch(std::size_t a, std::size_t b)
Swap two items.
std::size_t Smallest(std::size_t a, std::size_t b) const
Minimum of two items.
std::size_t Sibling(std::size_t id) const
Get the next sibling of a given entry.
std::size_t Parent(std::size_t id) const
Get the parent index of a given entry.
virtual ~HeapScheduler()
Destructor.
virtual void Remove(const Scheduler::Event &ev)
Remove a specific event from the event list.
bool IsBottom(std::size_t id) const
Test if an index is at the bottom of the heap.
std::size_t Root(void) const
Get the root index of the heap.
virtual Scheduler::Event RemoveNext(void)
Remove the earliest event from the event list.
std::size_t LeftChild(std::size_t id) const
Get the left child of a given entry.
virtual bool IsEmpty(void) const
Test if the schedule is empty.
virtual void Insert(const Scheduler::Event &ev)
Insert a new Event in the schedule.
virtual Scheduler::Event PeekNext(void) const
Get a pointer to the next event.
void BottomUp(void)
Percolate a newly inserted Last item to its proper position.
std::size_t Last(void) const
Return the index of the last element.
Maintain the event list.
Definition: scheduler.h:156
a unique identifier for an interface.
Definition: type-id.h:59
Every class exported by the ns3 library is enclosed in the ns3 namespace.
def start()
Definition: core.py:1853
ns3::Scheduler abstract base class, ns3::Scheduler::Event and ns3::Scheduler::EventKey declarations.
Scheduler event.
Definition: scheduler.h:182