File: range_list.h

package info (click to toggle)
btanks 0.9.8083-8
  • links: PTS, VCS
  • area: main
  • in suites: buster, sid
  • size: 43,584 kB
  • sloc: cpp: 46,425; ansic: 12,005; xml: 4,262; python: 313; sh: 13; makefile: 13
file content (86 lines) | stat: -rw-r--r-- 1,758 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#ifndef BTANKS_MATH_RANGE_LIST_H__
#define BTANKS_MATH_RANGE_LIST_H__

#include <map>

template<typename T>
class range_list : public std::map<const T, T> {
public: 
	typedef std::map<const T, T> parent_type;

private: 
	typename parent_type::iterator pack_left(typename parent_type::iterator i) {
		if (i == parent_type::begin())
			return i;

		typename parent_type::iterator prev = i;
		--prev;

		if (prev->second + 1 < i->first)
			return i;
		
		T e = i->second;
		
		parent_type::erase(i);
		prev->second = e;

		return pack_left(prev);
	}

	typename parent_type::iterator pack_right(typename parent_type::iterator i) {
		if (i == parent_type::end())
			return i;

		typename parent_type::iterator next = i;
		++next;
		if (next == parent_type::end())
			return i;
		
		if (i->second + 1 < next->first)
			return i;

		T e = next->second;
		parent_type::erase(next);
		i->second = e;

		return pack_right(i);
	}

public: 
	void insert(const T& value) {
		if (parent_type::empty()) {
			parent_type::insert(typename parent_type::value_type(value, value));
			return;
		}
	
		typename parent_type::iterator i = this->lower_bound(value);
		if (i != parent_type::end()) {
			if (i->first == value)
				return;

			if (value + 1 == i->first) {
				T e = i->second;
				this->erase(i);
				i = parent_type::insert(typename parent_type::value_type(value, e)).first; //expand beginning
				i = pack_left(i);
			}
		}
		
		if (i != parent_type::begin())
			--i; //look for the previous interval

		if (i->first <= value && value <= i->second) //included in interval
			return;
		
		if (i->second + 1 == value) {
			i->second = value;
			i = pack_right(i);
			return;
		}
		
		parent_type::insert(typename parent_type::value_type(value, value));
	}
};

#endif