+++ /dev/null
-// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
-// vim: ts=8 sw=2 smarttab
-/*
- * Ceph - scalable distributed file system
- *
- * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
- *
- * This is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License version 2.1, as published by the Free Software
- * Foundation. See file COPYING.
- *
- */
-
-
-#ifndef CEPH_RANGESET_H
-#define CEPH_RANGESET_H
-
-/*
- *
- * my first container with iterator! it's pretty ugly.
- *
- */
-
-#include <map>
-using namespace std;
-
-//typedef int T;
-
-template <class T>
-struct _rangeset_base {
- map<T,T> ranges; // pair(first,last) (inclusive, e.g. [first,last])
-
- typedef typename map<T,T>::iterator mapit;
-
- // get iterator for range including val. or ranges.end().
- mapit get_range_for(T val) {
- mapit it = ranges.lower_bound(val);
- if (it == ranges.end()) {
- // search backwards
- typename map<T,T>::reverse_iterator it = ranges.rbegin();
- if (it == ranges.rend()) return ranges.end();
- if (it->first <= val && it->second >= val)
- return ranges.find(it->first);
- return ranges.end();
- } else {
- if (it->first == val) return
- it--;
- if (it->first <= val && it->second >= val)
- return it;
- return ranges.end();
- }
- }
-
-};
-
-
-template <class T>
-class rangeset_iterator :
- public std::iterator<std::input_iterator_tag, T>
-{
- //typedef typename map<T,T>::iterator mapit;
-
- map<T,T> ranges;
- typename map<T,T>::iterator it;
- T current;
-
-public:
- // cons
- rangeset_iterator() {}
-
- rangeset_iterator(typename map<T,T>::iterator& it, map<T,T>& ranges) {
- this->ranges = ranges;
- this->it = it;
- if (this->it != ranges.end())
- current = it->first;
- }
-
- bool operator==(rangeset_iterator<T> rit) {
- return (it == rit.it && rit.current == current);
- }
- bool operator!=(rangeset_iterator<T> rit) {
- return (it != rit.it) || (rit.current != current);
- }
-
- T& operator*() {
- return current;
- }
-
- rangeset_iterator<T> operator++(int) {
- if (current < it->second)
- current++;
- else {
- it++;
- if (it != ranges.end())
- current = it->first;
- }
-
- return *this;
- }
-};
-
-
-template <class T>
-class rangeset
-{
- typedef typename map<T,T>::iterator map_iterator;
-
- _rangeset_base<T> theset;
- inodeno_t _size;
-
-public:
- rangeset() { _size = 0; }
- typedef rangeset_iterator<T> iterator;
-
- iterator begin() {
- map_iterator it = theset.ranges.begin();
- return iterator(it, theset.ranges);
- }
-
- iterator end() {
- map_iterator it = theset.ranges.end();
- return iterator(it, theset.ranges);
- }
-
- map_iterator map_begin() {
- return theset.ranges.begin();
- }
- map_iterator map_end() {
- return theset.ranges.end();
- }
- int map_size() {
- return theset.ranges.size();
- }
-
- void map_insert(T v1, T v2) {
- theset.ranges.insert(pair<T,T>(v1,v2));
- _size += v2 - v1+1;
- }
-
-
- // ...
- bool contains(T val) {
- if (theset.get_range_for(val) == theset.ranges.end()) return false;
- assert(!empty());
- return true;
- }
-
- void insert(T val) {
- assert(!contains(val));
-
- map_iterator left = theset.get_range_for(val-1);
- map_iterator right = theset.get_range_for(val+1);
-
- if (left != theset.ranges.end() &&
- right != theset.ranges.end()) {
- // join!
- left->second = right->second;
- theset.ranges.erase(right);
- _size++;
- return;
- }
-
- if (left != theset.ranges.end()) {
- // add to left range
- left->second = val;
- _size++;
- return;
- }
-
- if (right != theset.ranges.end()) {
- // add to right range
- theset.ranges.insert(pair<T,T>(val, right->second));
- theset.ranges.erase(val+1);
- _size++;
- return;
- }
-
- // new range
- theset.ranges.insert(pair<T,T>(val,val));
- _size++;
- return;
- }
-
- unsigned size() {
- return size();
- }
-
- bool empty() {
- if (theset.ranges.empty()) {
- assert(_size == 0);
- return true;
- }
- assert(_size>0);
- return false;
- }
-
-
- T first() {
- assert(!empty());
- map_iterator it = theset.ranges.begin();
- return it->first;
- }
-
- void erase(T val) {
- assert(contains(val));
- map_iterator it = theset.get_range_for(val);
- assert(it != theset.ranges.end());
-
- // entire range
- if (val == it->first && val == it->second) {
- theset.ranges.erase(it);
- _size--;
- return;
- }
-
- // beginning
- if (val == it->first) {
- theset.ranges.insert(pair<T,T>(val+1, it->second));
- theset.ranges.erase(it);
- _size--;
- return;
- }
-
- // end
- if (val == it->second) {
- it->second = val-1;
- _size--;
- return;
- }
-
- // middle split
- theset.ranges.insert(pair<T,T>(it->first, val-1));
- theset.ranges.insert(pair<T,T>(val+1, it->second));
- theset.ranges.erase(it);
- _size--;
- return;
- }
-
- void dump() {
- for (typename map<T,T>::iterator it = theset.ranges.begin();
- it != theset.ranges.end();
- it++) {
- cout << " " << it->first << "-" << it->second << endl;
- }
- }
-
-};
-
-
-#endif