← Back to branch summary

~ubuntu-branches/debian/wheezy/libtorrent/wheezy

« back to all changes in this revision

Viewing changes to rak/priority_queue.h

  • Committer: Bazaar Package Importer
  • Author(s): Rogério Brito
  • Date: 2011-03-09 20:04:41 UTC
  • mfrom: (1.3.4 upstream) (7.1.5 sid)
  • Revision ID: james.westby@ubuntu.com-20110309200441-ffi9aaqdyd72d8xl
Tags: 0.12.7-4
* Steal patch from upstream's bug tracking system to enable IPv6.
* Refresh patches to apply cleanly.
* This should, hopefully, be a good step towards addressing #490277.

Show diffs side-by-side

added added

removed removed

Lines of Context:
rak/priority_queue.h
 
1
// rak - Rakshasa's toolbox
 
2
// Copyright (C) 2005-2007, Jari Sundell
 
3
//
 
4
// This program is free software; you can redistribute it and/or modify
 
5
// it under the terms of the GNU General Public License as published by
 
6
// the Free Software Foundation; either version 2 of the License, or
 
7
// (at your option) any later version.
 
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
// In addition, as a special exception, the copyright holders give
 
19
// permission to link the code of portions of this program with the
 
20
// OpenSSL library under certain conditions as described in each
 
21
// individual source file, and distribute linked combinations
 
22
// including the two.
 
23
//
 
24
// You must obey the GNU General Public License in all respects for
 
25
// all of the code used other than OpenSSL.  If you modify file(s)
 
26
// with this exception, you may extend this exception to your version
 
27
// of the file(s), but you are not obligated to do so.  If you do not
 
28
// wish to do so, delete this exception statement from your version.
 
29
// If you delete this exception statement from all source files in the
 
30
// program, then also delete it here.
 
31
//
 
32
// Contact:  Jari Sundell <jaris@ifi.uio.no>
 
33
//
 
34
//           Skomakerveien 33
 
35
//           3185 Skoppum, NORWAY
 
36
 
 
37
// priority_queue is a priority queue implemented using a binary
 
38
// heap. It can contain multiple instances of a value.
 
39
 
 
40
#ifndef RAK_PRIORITY_QUEUE_H
 
41
#define RAK_PRIORITY_QUEUE_H
 
42
 
 
43
#include <algorithm>
 
44
#include <functional>
 
45
#include <vector>
 
46
 
 
47
namespace rak {
 
48
 
 
49
template <typename Value, typename Compare, typename Equal, typename Alloc = std::allocator<Value> >
 
50
class priority_queue : public std::vector<Value, Alloc> {
 
51
public:
 
52
  typedef std::vector<Value, Alloc>           base_type;
 
53
  typedef typename base_type::reference       reference;
 
54
  typedef typename base_type::const_reference const_reference;
 
55
  typedef typename base_type::iterator        iterator;
 
56
  typedef typename base_type::const_iterator  const_iterator;
 
57
  typedef typename base_type::value_type      value_type;
 
58
 
 
59
  using base_type::begin;
 
60
  using base_type::end;
 
61
  using base_type::size;
 
62
  using base_type::empty;
 
63
 
 
64
  priority_queue(Compare l = Compare(), Equal e = Equal())
 
65
    : m_compare(l), m_equal(e) {}
 
66
 
 
67
  const_reference top() const {
 
68
    return base_type::front();
 
69
  }
 
70
 
 
71
  void pop() {
 
72
    std::pop_heap(begin(), end(), m_compare);
 
73
    base_type::pop_back();
 
74
  }
 
75
 
 
76
  void push(const value_type& value) {
 
77
    base_type::push_back(value);
 
78
    std::push_heap(begin(), end(), m_compare);
 
79
  }
 
80
 
 
81
  template <typename Key>
 
82
  iterator find(const Key& key) {
 
83
    return std::find_if(begin(), end(), std::bind2nd(m_equal, key));
 
84
  }
 
85
 
 
86
  template <typename Key>
 
87
  bool erase(const Key& key) {
 
88
    iterator itr = find(key);
 
89
 
 
90
    if (itr == end())
 
91
      return false;
 
92
 
 
93
    erase(itr);
 
94
    return true;
 
95
  }
 
96
 
 
97
  // Removes 'itr' from the queue. This assumes 'itr' has been
 
98
  // modified such that it has a higher priority than any other
 
99
  // element in the queue.
 
100
  void erase(iterator itr) {
 
101
//     std::push_heap(begin(), ++itr, m_compare);
 
102
//     pop();
 
103
    base_type::erase(itr);
 
104
    std::make_heap(begin(), end(), m_compare);
 
105
  }
 
106
 
 
107
private:
 
108
  Compare             m_compare;
 
109
  Equal               m_equal;
 
110
};
 
111
 
 
112
// Iterate while the top node has higher priority, as 'Compare'
 
113
// returns false.
 
114
template <typename Queue, typename Compare>
 
115
class queue_pop_iterator
 
116
  : public std::iterator<std::forward_iterator_tag, void, void, void, void> {
 
117
public:
 
118
  typedef Queue container_type;
 
119
 
 
120
  queue_pop_iterator() : m_queue(NULL) {}
 
121
  queue_pop_iterator(Queue* q, Compare c) : m_queue(q), m_compare(c) {}
 
122
 
 
123
  queue_pop_iterator& operator ++ ()                     { m_queue->pop(); return *this; }
 
124
  queue_pop_iterator& operator ++ (int)                  { m_queue->pop(); return *this; }
 
125
 
 
126
  typename container_type::const_reference operator * () { return m_queue->top(); }
 
127
 
 
128
  bool operator != (const queue_pop_iterator& itr)       { return !m_queue->empty() && !m_compare(m_queue->top()); }
 
129
  bool operator == (const queue_pop_iterator& itr)       { return m_queue->empty() || m_compare(m_queue->top()); }
 
130
 
 
131
private:
 
132
  Queue*  m_queue;
 
133
  Compare m_compare;
 
134
};
 
135
 
 
136
template <typename Queue, typename Compare>
 
137
inline queue_pop_iterator<Queue, Compare>
 
138
queue_popper(Queue& queue, Compare comp) {
 
139
  return queue_pop_iterator<Queue, Compare>(&queue, comp);
 
140
}
 
141
 
 
142
}
 
143
 
 
144
#endif