A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
heap-scheduler.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2005 INRIA
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
7 */
8
9#ifndef HEAP_SCHEDULER_H
10#define HEAP_SCHEDULER_H
11
12#include "scheduler.h"
13
14#include <stdint.h>
15#include <vector>
16
17/**
18 * \file
19 * \ingroup scheduler
20 * ns3::HeapScheduler declaration.
21 */
22
23namespace ns3
24{
25
26/**
27 * \ingroup scheduler
28 * \brief a binary heap event scheduler
29 *
30 * This code started as a c++ translation of a Java-based code written in 2005
31 * to implement a heap sort. So, this binary heap is really a pretty
32 * straightforward implementation of the classic data structure,
33 * implemented on a `std::vector`. This implementation does not make use
34 * of any of the heap functions from the STL. Not much to say
35 * about it.
36 *
37 * What is smart about this code ?
38 * - it does not use the index 0 in the array to avoid having to convert
39 * C-style array indexes (which start at zero) and heap-style indexes
40 * (which start at 1). This is why _all_ indexes start at 1, and that
41 * the index of the root is 1.
42 * - It uses a slightly non-standard while loop for top-down heapify
43 * to move one if statement out of the loop.
44 *
45 * \par Time Complexity
46 *
47 * Operation | Amortized %Time | Reason
48 * :----------- | :-------------- | :-----
49 * Insert() | Logarithmic | Heapify
50 * IsEmpty() | Constant | Explicit queue size
51 * PeekNext() | Constant | Heap kept sorted
52 * Remove() | Logarithmic | Search, heapify
53 * RemoveNext() | Logarithmic | Heapify
54 *
55 * \par Memory Complexity
56 *
57 * Category | Memory | Reason
58 * :-------- | :------------------------------- | :-----
59 * Overhead | 3 x `sizeof (*)`<br/>(24 bytes) | `std::vector`
60 * Per Event | 0 | Events stored in `std::vector` directly
61 */
63{
64 public:
65 /**
66 * Register this type.
67 * \return The object TypeId.
68 */
69 static TypeId GetTypeId();
70
71 /** Constructor. */
73 /** Destructor. */
74 ~HeapScheduler() override;
75
76 // Inherited
77 void Insert(const Scheduler::Event& ev) override;
78 bool IsEmpty() const override;
79 Scheduler::Event PeekNext() const override;
81 void Remove(const Scheduler::Event& ev) override;
82
83 private:
84 /** Event list type: vector of Events, managed as a heap. */
85 typedef std::vector<Scheduler::Event> BinaryHeap;
86
87 /**
88 * Get the parent index of a given entry.
89 *
90 * \param [in] id The child index.
91 * \return The index of the parent of \pname{id}.
92 */
93 inline std::size_t Parent(std::size_t id) const;
94 /**
95 * Get the next sibling of a given entry.
96 *
97 * \param [in] id The starting index.
98 * \returns The next sibling of \pname{id}.
99 */
100 std::size_t Sibling(std::size_t id) const;
101 /**
102 * Get the left child of a given entry.
103 *
104 * \param [in] id The parent index.
105 * \returns The index of the left (first) child.
106 */
107 inline std::size_t LeftChild(std::size_t id) const;
108 /**
109 * Get the right child index of a given entry.
110 *
111 * \param [in] id The parent index.
112 * \returns The index of the right (second) child.
113 */
114 inline std::size_t RightChild(std::size_t id) const;
115 /**
116 * Get the root index of the heap.
117 *
118 * \returns The root index.
119 */
120 inline std::size_t Root() const;
121 /**
122 * Return the index of the last element.
123 * \returns The last index.
124 */
125 std::size_t Last() const;
126 /**
127 * Test if an index is the root.
128 *
129 * \param [in] id The index to test.
130 * \returns \c true if the \pname{id} is the root.
131 */
132 inline bool IsRoot(std::size_t id) const;
133 /**
134 * Test if an index is at the bottom of the heap.
135 *
136 * \param [in] id The index to test.
137 * \returns \c true if the index is at the bottom.
138 */
139 inline bool IsBottom(std::size_t id) const;
140 /**
141 * Compare (less than) two items.
142 *
143 * \param [in] a The first item.
144 * \param [in] b The second item.
145 * \returns \c true if \c a < \c b
146 */
147 inline bool IsLessStrictly(std::size_t a, std::size_t b) const;
148 /**
149 * Minimum of two items.
150 *
151 * \param [in] a The first item.
152 * \param [in] b The second item.
153 * \returns The smaller of the two items.
154 */
155 inline std::size_t Smallest(std::size_t a, std::size_t b) const;
156 /**
157 * Swap two items.
158 *
159 * \param [in] a The first item.
160 * \param [in] b The second item.
161 */
162 inline void Exch(std::size_t a, std::size_t b);
163 /** Percolate a newly inserted Last item to its proper position. */
164 void BottomUp();
165 /**
166 * Percolate a deletion bubble down the heap.
167 *
168 * \param [in] start Starting entry.
169 */
170 void TopDown(std::size_t start);
171
172 /** The event list. */
174};
175
176} // namespace ns3
177
178#endif /* HEAP_SCHEDULER_H */
a binary heap event scheduler
std::size_t Root() const
Get the root index of the heap.
void TopDown(std::size_t start)
Percolate a deletion bubble down the heap.
void Insert(const Scheduler::Event &ev) override
Insert a new Event in the schedule.
~HeapScheduler() override
Destructor.
static TypeId GetTypeId()
Register this type.
Scheduler::Event RemoveNext() override
Remove the earliest event from the event list.
bool IsLessStrictly(std::size_t a, std::size_t b) const
Compare (less than) two items.
HeapScheduler()
Constructor.
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.
Scheduler::Event PeekNext() const override
Get a pointer to the next event.
void Remove(const Scheduler::Event &ev) override
Remove a specific event from the event list.
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.
bool IsBottom(std::size_t id) const
Test if an index is at the bottom of the heap.
std::size_t LeftChild(std::size_t id) const
Get the left child of a given entry.
void BottomUp()
Percolate a newly inserted Last item to its proper position.
std::size_t Last() const
Return the index of the last element.
bool IsEmpty() const override
Test if the schedule is empty.
Maintain the event list.
Definition scheduler.h:146
a unique identifier for an interface.
Definition type-id.h:48
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::Scheduler abstract base class, ns3::Scheduler::Event and ns3::Scheduler::EventKey declarations.
Scheduler event.
Definition scheduler.h:173