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
|
// $Id: split.cpp 962 2006-11-07 15:13:34Z privmane $
#include "split.h"
#include <cassert>
#include <algorithm>
using namespace std;
// there are always two options. Either the active set is _set[0] or _set[1].
// this depends on the parameter _reverse.
// The "1" will always be in the active set.
// so, for example consider the leaves [0,1,2] (_max = 3).
// The split {}{0,1,2} can be represented by both the empty split {} or the
// {0,1,2} split. Because the {0,1,2} split contains the "0" - this will be the active split.
// so we set _set[0] to be empty, and in _set[1] which is the active one (_reverse = true)
// we insert the leaves.
split::split (const int max): _max(max), _reverse(true){
for(int j=0;j<max;++j) {
_set[1].insert(j);
}
}
// isMember searches for the key in the active set.
bool split::isMember(const int key) const {
return(_set[_reverse].find(key)!=_set[_reverse].end());
}
void split::reverseMembership(const int key){
assert(key<_max && key >= 0);
// where is the key now
// if the key is member, than in = _reverese;
// Otherwise in = !_reverse
bool in =(isMember(key))?_reverse:!_reverse;
_set[in].erase(key);
_set[!in].insert(key);
if (key==0) // if we add "0", we need to reverse the split
reverse();
};
int split::size() const {
int tmp = _set[_reverse].size();
return (tmp<_max-tmp?tmp:_max-tmp);
}
void split::print(ostream& sout) const{ // = cout
sout <<"size ="<<size()<<" ";
set<int>::const_iterator i;
for (i=_set[_reverse].begin();i != _set[_reverse].end();++i)
sout << *i << " ";
sout <<" | ";
for (i=_set[!_reverse].begin();i != _set[!_reverse].end();++i)
sout << *i << " ";
sout << endl;
}
bool split::lessThen(const split& other) const{
return(_set[_reverse]<other._set[other._reverse]);
}
bool split::compatible(const split& other) const {
set<int>::const_iterator i (_set[_reverse].begin());
set<int>::const_iterator i_end (_set[_reverse].end());
set<int>::const_iterator j (other._set[other._reverse].begin());
set<int>::const_iterator j_end (other._set[other._reverse].end());
return (includes(i,i_end,j,j_end) || includes(j,j_end,i,i_end));
}
void split::reverse(){ // actualy reverse membership in the set
_reverse=!_reverse;
}
bool operator<(const split& a, const split& b) {
return(a.lessThen(b));
}
ostream& operator<< (ostream &sout, const split& split) {
split.print(sout);
return sout;
}
|
