-
Notifications
You must be signed in to change notification settings - Fork 78
Expand file tree
/
Copy pathstep_vector.h
More file actions
180 lines (153 loc) · 4.79 KB
/
step_vector.h
File metadata and controls
180 lines (153 loc) · 4.79 KB
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#ifndef _STEP_VECTOR_H_
#define _STEP_VECTOR_H_
#include <map>
#include <stdexcept>
#include <climits>
#include <iostream> //for now only
template< class T >
class step_vector {
protected:
std::map< long int, T > m;
public:
static const long int min_index;
static const long int max_index;
typedef typename std::map< long int, T >::const_iterator const_iterator;
step_vector( );
const T operator[]( long int i ) const;
void set_value( long int from, long int to, T value );
void add_value( long int from, long int to, T value );
void apply_to_values( long int from, long int to, void (*func)( T & val ) );
const_iterator get_values( long int from ) const;
const_iterator begin( ) const;
const_iterator end( ) const;
};
template< class T >
const long int step_vector<T>::min_index = LONG_MIN;
template< class T >
const long int step_vector<T>::max_index = LONG_MAX;
template< class T >
step_vector<T>::step_vector( )
{
m[ min_index ] = T();
}
template< class T >
const T step_vector<T>::operator[]( long int i ) const
{
const_iterator it = m.upper_bound( i );
it--;
return it->second;
}
template< class T >
void step_vector<T>::set_value( long int from, long int to, T value )
{
if( from > to )
throw std::out_of_range( "Indices reversed in step_vector." );
// Unless the new step extends to the end, we need to insert a new
// value afterwards unless the step to the right has the same value
if( to < max_index ) {
T next_value = (*this)[to+1];
if( !( next_value == value ) )
m[ to + 1 ] = next_value;
}
// Find the left step, i.e., the step whose start is smaller or equal
// to 'from':
typename std::map< long int, T>::iterator left = m.upper_bound( from );
left--;
assert( left->first <= from );
// Get rid of the steps present between from and to
typename std::map< long int, T>::iterator it = m.lower_bound( from );
if( it->first == from )
it++;
assert( it->first > from );
if( it->first <= to ) {
m.erase( it, m.upper_bound( to ) );
}
if( ! (left->second == value ) ) {
if( left->first != from )
// Insert a new step
m[ from ] = value;
else {
// We have from == left->first, so the step is already present.
// Would changing m[from] to value make it equal to its left
// neighbor?
if( left == m.begin() )
// no, there is no left neighbor
m[ from ] = value;
else {
typename std::map< long int, T>::iterator leftleft = left;
leftleft--;
if( ! ( leftleft->second == value ) )
// ok, change the value
m[ from ] = value;
else
// no, rather delete the step
m.erase( left );
}
}
}
}
template< class T >
void step_vector<T>::add_value( long int from, long int to, T value )
{
if( from > to )
throw std::out_of_range( "Indices reversed in step_vector." );
if( to < max_index ) {
T next_value = (*this)[to+1];
m[ to + 1 ] = next_value;
}
typename std::map< long int, T>::iterator it = m.upper_bound( from );
it--;
bool need_to_insert_step_at_from = it->first < from;
T old_val_at_from;
if( need_to_insert_step_at_from ) {
old_val_at_from = it->second;
it++;
}
// Now, it points to the first element with it->first >= from
for( ; it != m.end() && it->first <= to; it++ )
it->second += value;
if( need_to_insert_step_at_from )
m[ from ] = old_val_at_from + value;
}
template< class T >
void step_vector<T>::apply_to_values( long int from, long int to,
void (*func)( T & val ) )
{
if( from > to )
throw std::out_of_range( "Indices reversed in step_vector." );
if( to < max_index ) {
T next_value = (*this)[to+1];
m[ to + 1 ] = next_value;
}
typename std::map< long int, T>::iterator it = m.upper_bound( from );
it--;
bool need_to_insert_step_at_from = it->first < from;
T old_val_at_from;
if( need_to_insert_step_at_from ) {
old_val_at_from = it->second;
it++;
}
// Now, it points to the first element with it->first >= from
for( ; it != m.end() && it->first <= to; it++ )
func( it->second );
if( need_to_insert_step_at_from ) {
func( old_val_at_from );
m[ from ] = old_val_at_from;
}
}
template< class T >
typename step_vector<T>::const_iterator step_vector<T>::get_values( long int from ) const
{
return --m.upper_bound( from );
}
template< class T >
typename step_vector<T>::const_iterator step_vector<T>::begin( ) const
{
return m.begin();
}
template< class T >
typename step_vector<T>::const_iterator step_vector<T>::end( ) const
{
return m.end();
}
#endif //_STEP_VECTOR_H_