1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
8 * This is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License version 2.1, as published by the Free Software
11 * Foundation. See file COPYING.
16 #ifndef CEPH_RANGESET_H
17 #define CEPH_RANGESET_H
21 * my first container with iterator! it's pretty ugly.
31 struct _rangeset_base {
32 map<T,T> ranges; // pair(first,last) (inclusive, e.g. [first,last])
34 typedef typename map<T,T>::iterator mapit;
36 // get iterator for range including val. or ranges.end().
37 mapit get_range_for(T val) {
38 mapit it = ranges.lower_bound(val);
39 if (it == ranges.end()) {
41 typename map<T,T>::reverse_iterator it = ranges.rbegin();
42 if (it == ranges.rend()) return ranges.end();
43 if (it->first <= val && it->second >= val)
44 return ranges.find(it->first);
47 if (it->first == val) return
49 if (it->first <= val && it->second >= val)
59 class rangeset_iterator :
60 public std::iterator<std::input_iterator_tag, T>
62 //typedef typename map<T,T>::iterator mapit;
65 typename map<T,T>::iterator it;
70 rangeset_iterator() {}
72 rangeset_iterator(typename map<T,T>::iterator& it, map<T,T>& ranges) {
73 this->ranges = ranges;
75 if (this->it != ranges.end())
79 bool operator==(rangeset_iterator<T> rit) {
80 return (it == rit.it && rit.current == current);
82 bool operator!=(rangeset_iterator<T> rit) {
83 return (it != rit.it) || (rit.current != current);
90 rangeset_iterator<T> operator++(int) {
91 if (current < it->second)
95 if (it != ranges.end())
107 typedef typename map<T,T>::iterator map_iterator;
109 _rangeset_base<T> theset;
113 rangeset() { _size = 0; }
114 typedef rangeset_iterator<T> iterator;
117 map_iterator it = theset.ranges.begin();
118 return iterator(it, theset.ranges);
122 map_iterator it = theset.ranges.end();
123 return iterator(it, theset.ranges);
126 map_iterator map_begin() {
127 return theset.ranges.begin();
129 map_iterator map_end() {
130 return theset.ranges.end();
133 return theset.ranges.size();
136 void map_insert(T v1, T v2) {
137 theset.ranges.insert(pair<T,T>(v1,v2));
143 bool contains(T val) {
144 if (theset.get_range_for(val) == theset.ranges.end()) return false;
150 assert(!contains(val));
152 map_iterator left = theset.get_range_for(val-1);
153 map_iterator right = theset.get_range_for(val+1);
155 if (left != theset.ranges.end() &&
156 right != theset.ranges.end()) {
158 left->second = right->second;
159 theset.ranges.erase(right);
164 if (left != theset.ranges.end()) {
171 if (right != theset.ranges.end()) {
172 // add to right range
173 theset.ranges.insert(pair<T,T>(val, right->second));
174 theset.ranges.erase(val+1);
180 theset.ranges.insert(pair<T,T>(val,val));
190 if (theset.ranges.empty()) {
201 map_iterator it = theset.ranges.begin();
206 assert(contains(val));
207 map_iterator it = theset.get_range_for(val);
208 assert(it != theset.ranges.end());
211 if (val == it->first && val == it->second) {
212 theset.ranges.erase(it);
218 if (val == it->first) {
219 theset.ranges.insert(pair<T,T>(val+1, it->second));
220 theset.ranges.erase(it);
226 if (val == it->second) {
233 theset.ranges.insert(pair<T,T>(it->first, val-1));
234 theset.ranges.insert(pair<T,T>(val+1, it->second));
235 theset.ranges.erase(it);
241 for (typename map<T,T>::iterator it = theset.ranges.begin();
242 it != theset.ranges.end();
244 cout << " " << it->first << "-" << it->second << endl;