← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/libtorrent/oneiric

« back to all changes in this revision

Viewing changes to rak/ranges.h

  • Committer: Bazaar Package Importer
  • Author(s): Rogério Brito
  • Date: 2011-03-20 01:06:18 UTC
  • mfrom: (1.1.13 upstream) (4.1.9 sid)
  • Revision ID: james.westby@ubuntu.com-20110320010618-g3wyylccqzqko73c
Tags: 0.12.7-5
http://bugs.debian.org/617791
* Use Steinar's "real" patch for IPv6. Addresses #490277, #618275,
  and Closes: #617791.
* Adapt libtorrent-0.12.6-ipv6-07.patch. It FTBFS otherwise.
* Add proper attibution to the IPv6 patch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
rak/ranges.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
#ifndef RAK_RANGES_H
 
38
#define RAK_RANGES_H
 
39
 
 
40
#include <algorithm>
 
41
#include <vector>
 
42
#include <rak/functional.h>
 
43
 
 
44
namespace rak {
 
45
 
 
46
template <typename Type>
 
47
class ranges : private std::vector<std::pair<Type, Type> > {
 
48
public:
 
49
  typedef std::vector<std::pair<Type, Type> >  base_type;
 
50
  typedef typename base_type::value_type       value_type;
 
51
  typedef typename base_type::reference        reference;
 
52
  typedef typename base_type::iterator         iterator;
 
53
  typedef typename base_type::const_iterator   const_iterator;
 
54
  typedef typename base_type::reverse_iterator reverse_iterator;
 
55
 
 
56
  using base_type::clear;
 
57
  using base_type::size;
 
58
  using base_type::begin;
 
59
  using base_type::end;
 
60
  using base_type::rbegin;
 
61
  using base_type::rend;
 
62
 
 
63
  using base_type::front;
 
64
  using base_type::back;
 
65
 
 
66
  void                insert(Type first, Type last) { insert(std::make_pair(first, last)); }
 
67
  void                erase(Type first, Type last)  { erase(std::make_pair(first, last)); }
 
68
 
 
69
  void                insert(value_type r);
 
70
  void                erase(value_type r);
 
71
 
 
72
  // Find the first ranges that has an end greater than index.
 
73
  iterator            find(Type index);
 
74
  const_iterator      find(Type index) const;
 
75
 
 
76
  // Use find with no closest match.
 
77
  bool                has(Type index) const;
 
78
};
 
79
 
 
80
template <typename Type>
 
81
void
 
82
ranges<Type>::insert(value_type r) {
 
83
  if (r.first >= r.second)
 
84
    return;
 
85
 
 
86
  iterator first = std::find_if(begin(), end(), rak::less_equal(r.first, rak::const_mem_ref(&value_type::second)));
 
87
 
 
88
  if (first == end() || r.second < first->first) {
 
89
    // The new range is before the first, after the last or between
 
90
    // two ranges.
 
91
    base_type::insert(first, r);
 
92
 
 
93
  } else {
 
94
    first->first = std::min(r.first, first->first);
 
95
    first->second = std::max(r.second, first->second);
 
96
 
 
97
    iterator last = std::find_if(first, end(), rak::less(first->second, rak::const_mem_ref(&value_type::second)));
 
98
 
 
99
    if (last != end() && first->second >= last->first)
 
100
      first->second = (last++)->second;
 
101
 
 
102
    base_type::erase(first + 1, last);
 
103
  }
 
104
}
 
105
 
 
106
template <typename Type>
 
107
void
 
108
ranges<Type>::erase(value_type r) {
 
109
  if (r.first >= r.second)
 
110
    return;
 
111
 
 
112
  iterator first = std::find_if(begin(), end(), rak::less(r.first, rak::const_mem_ref(&value_type::second)));
 
113
  iterator last  = std::find_if(first, end(), rak::less(r.second, rak::const_mem_ref(&value_type::second)));
 
114
 
 
115
  if (first == end())
 
116
    return;
 
117
 
 
118
  if (first == last) {
 
119
 
 
120
    if (r.first > first->first) {
 
121
      std::swap(first->first, r.second);
 
122
      base_type::insert(first, value_type(r.second, r.first));
 
123
 
 
124
    } else if (r.second > first->first) {
 
125
      first->first = r.second;
 
126
    }
 
127
 
 
128
  } else {
 
129
 
 
130
    if (r.first > first->first)
 
131
      (first++)->second = r.first;
 
132
    
 
133
    if (last != end() && r.second > last->first)
 
134
      last->first = r.second;
 
135
 
 
136
    base_type::erase(first, last);
 
137
  }
 
138
}
 
139
 
 
140
// Find the first ranges that has an end greater than index.
 
141
template <typename Type>
 
142
inline typename ranges<Type>::iterator
 
143
ranges<Type>::find(Type index) {
 
144
  return std::find_if(begin(), end(), rak::less(index, rak::const_mem_ref(&value_type::second)));
 
145
}
 
146
 
 
147
template <typename Type>
 
148
inline typename ranges<Type>::const_iterator
 
149
ranges<Type>::find(Type index) const {
 
150
  return std::find_if(begin(), end(), rak::less(index, rak::const_mem_ref(&value_type::second)));
 
151
}
 
152
 
 
153
// Use find with no closest match.
 
154
template <typename Type>
 
155
bool
 
156
ranges<Type>::has(Type index) const {
 
157
  const_iterator itr = find(index);
 
158
 
 
159
  return itr != end() && index >= itr->first;
 
160
}
 
161
 
 
162
}
 
163
 
 
164
#endif