A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
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 
28 namespace ns3 {
29 
47 class HeapScheduler : public Scheduler
48 {
49 public:
50  static TypeId GetTypeId (void);
51 
52  HeapScheduler ();
53  virtual ~HeapScheduler ();
54 
55  virtual void Insert (const Event &ev);
56  virtual bool IsEmpty (void) const;
57  virtual Event PeekNext (void) const;
58  virtual Event RemoveNext (void);
59  virtual void Remove (const Event &ev);
60 
61 private:
62  typedef std::vector<Event> BinaryHeap;
63 
64  inline uint32_t Parent (uint32_t id) const;
65  uint32_t Sibling (uint32_t id) const;
66  inline uint32_t LeftChild (uint32_t id) const;
67  inline uint32_t RightChild (uint32_t id) const;
68  inline uint32_t Root (void) const;
69  /* Return the position in the array of the last element included in it. */
70  uint32_t Last (void) const;
71  inline bool IsRoot (uint32_t id) const;
72  inline bool IsBottom (uint32_t id) const;
73  inline bool IsLessStrictly (uint32_t a, uint32_t b) const;
74  inline uint32_t Smallest (uint32_t a, uint32_t b) const;
75 
76  inline void Exch (uint32_t a, uint32_t b);
77  void BottomUp (void);
78  void TopDown (uint32_t start);
79 
80  BinaryHeap m_heap;
81 };
82 
83 } // namespace ns3
84 
85 #endif /* HEAP_SCHEDULER_H */