Microsimulation API

heap.h
Go to the documentation of this file.
1 // -*-C++-*-
2 //
3 // This file is part of SSim, a simple discrete-event simulator.
4 // See http://www.inf.usi.ch/carzaniga/ssim/
5 //
6 // Copyright (C) 2004-2005 University of Colorado
7 // Copyright (C) 2012 Antonio Carzaniga
8 //
9 // Authors: Antonio Carzaniga <firstname.lastname@usi.ch>
10 // See AUTHORS for full details.
11 //
12 // SSim is free software: you can redistribute it and/or modify it under
13 // the terms of the GNU General Public License as published by the Free
14 // Software Foundation, either version 3 of the License, or (at your
15 // option) any later version.
16 //
17 // SSim is distributed in the hope that it will be useful,
18 // but WITHOUT ANY WARRANTY; without even the implied warranty of
19 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 // GNU General Public License for more details.
21 //
22 // You should have received a copy of the GNU General Public License
23 // along with SSim. If not, see <http://www.gnu.org/licenses/>.
24 //
25 #ifndef _heap_h
26 #define _heap_h
27
28 #include <vector>
29
30 namespace ssim {
31
32 //
33 // This is an implementation of a binary heap taken from R. Sedgewick,
34 // "Algorithms in C," 3rd Ed., Vol. 1, pp. 368--375. A few
35 // modifications to Sedgewick's implementation are noted below.
36 // Notice that this implementation is completely independent from the
37 // rest of SSim, and in fact can be used as is elsewhere.
38 //
39 template <typename T>
40 class heap {
41 public:
42 typedef typename std::vector<T>::size_type size_type;
43 typedef typename std::vector<T>::iterator iterator;
44 typedef typename std::vector<T>::const_iterator const_iterator;
45
46 private:
47 std::vector<T> a;
48 static void swap(T & first, T & second) throw() {
49 T tmp = first;
50 first = second;
51 second = tmp;
52 }
53 // contrary to Sedgewick's implementation, which counts elements
54 // starting from 1, we start from 0. So, in order to avoid
55 // confusion and mistakes, we abstract all the position stuff with
56 // the following member functions. The compiler should optimize
57 // everything out anyway.
58 //
59 static const size_type FIRST = 0;
60 size_type last() const throw() { return a.size() - 1; }
61 static size_type left(size_type pos) throw() { return pos*2 + 1; }
62 static size_type right(size_type pos) throw() { return (pos + 1)*2; }
63 static size_type parent(size_type pos) throw() { return (pos - 1)/2; }
64
65 public:
66 bool empty() throw() { return a.empty(); }
67 iterator begin() throw() { return a.begin(); }
68 iterator end() throw() { return a.end(); }
69 const_iterator begin() const throw() { return a.begin(); }
70 const_iterator end() const throw() { return a.end(); }
71 void clear() throw() { a.clear(); }
72 iterator erase(iterator first, iterator last) throw() {return a.erase(first, last); }
73
74 void insert(const T & x) throw() {
75 a.push_back(x);
76 size_type k = last();
77 size_type k_parent;
78 while(k > FIRST) {
79 k_parent = parent(k);
80 if (a[k] < a[k_parent]) {
81 swap(a[k], a[k_parent]);
82 k = k_parent;
83 } else {
84 return;
85 }
86 }
87 }
88
89 T pop_first() throw() {
90 // ASSERT( FIRST <= last() ). I.e., ! empty()
91 T res = a[FIRST];
92 if (FIRST == last()) {
93 a.pop_back();
94 return res;
95 }
96 a[FIRST] = a[last()];
97 a.pop_back();
98 size_type k = FIRST;
99 size_type k_next;
100 for(;;) {
101 k_next = left(k);
102 if (k_next > last()) {
103 break;
104 }
105 if (right(k) <= last() && a[right(k)] < a[k_next]) {
106 k_next = right(k);
107 }
108 if (a[k_next] < a[k]) {
109 swap(a[k], a[k_next]);
110 k = k_next;
111 } else {
112 break;
113 }
114 }
115 return res;
116 }
117 };
118
119 } // end namespace ssim
120
121 #endif /* _ssim_h */
122
ssim::heap::end
iterator end()
Definition: heap.h:68
ssim::heap::size_type
std::vector< T >::size_type size_type
Definition: heap.h:42
ssim::heap::insert
void insert(const T &x)
Definition: heap.h:74
ssim::heap::pop_first
T pop_first()
Definition: heap.h:89
ssim::heap::clear
void clear()
Definition: heap.h:71
ssim::heap::right
static size_type right(size_type pos)
Definition: heap.h:62
ssim::heap::begin
iterator begin()
Definition: heap.h:67
ssim::heap::parent
static size_type parent(size_type pos)
Definition: heap.h:63
ssim::heap::const_iterator
std::vector< T >::const_iterator const_iterator
Definition: heap.h:44
ssim::heap::empty
bool empty()
Definition: heap.h:66
ssim::heap
Definition: heap.h:40
ssim::heap::iterator
std::vector< T >::iterator iterator
Definition: heap.h:43
ssim::heap::a
std::vector< T > a
Definition: heap.h:47
ssim::heap::FIRST
static const size_type FIRST
Definition: heap.h:59
ssim::heap::erase
iterator erase(iterator first, iterator last)
Definition: heap.h:72
ssim::heap::swap
static void swap(T &first, T &second)
Definition: heap.h:48
ssim::heap::last
size_type last() const
Definition: heap.h:60
ssim::heap::left
static size_type left(size_type pos)
Definition: heap.h:61
ssim
name space for the Siena simulator.
Definition: microsimulation.cc:8
ssim::heap::end
const_iterator end() const
Definition: heap.h:70
ssim::heap::begin
const_iterator begin() const
Definition: heap.h:69