43 typedef std::set<KEY> Set;
45 typedef std::pair<KEY, KEY> KeyLabel;
53 DSF(
const Tree& tree) :
58 DSF(
const std::list<KEY>& keys) :
60 for(
const KEY& key: keys)
61 *
this = this->
add(key, key);
65 DSF(
const std::set<KEY>& keys) :
67 for(
const KEY& key: keys)
68 *
this = this->
add(key, key);
72 Self makeSet(
const KEY& key)
const {
76 return this->
add(key, key);
80 void makeSetInPlace(
const KEY& key) {
82 *
this = this->
add(key, key);
86 KEY findSet(
const KEY& key)
const {
87 KEY parent = this->
find(key);
88 return parent == key ? key : findSet(parent);
92 Self makeUnion(
const KEY& key1,
const KEY& key2)
const {
94 copy.makeUnionInPlace(key1,key2);
99 void makeUnionInPlace(
const KEY& key1,
const KEY& key2) {
104 Self makePair(
const KEY& key1,
const KEY& key2)
const {
105 return makeSet(key1).makeSet(key2).makeUnion(key1, key2);
109 Self makeList(
const std::list<KEY>& keys)
const {
111 for(
const KEY& key: keys)
112 t = t.makePair(key, keys.front());
117 DSF flatten()
const {
119 for(
const KeyLabel& pair: (Tree)t)
120 t.findSet_(pair.first);
125 DSF map(std::function<KEY(
const KEY&)> func)
const {
127 for(
const KeyLabel& pair: (Tree)*
this)
128 t = t.
add(func(pair.first), func(pair.second));
133 size_t numSets()
const {
135 for(
const KeyLabel& pair: (Tree)*
this)
136 if (pair.first == pair.second)
142 size_t size()
const {
147 std::map<KEY, Set> sets()
const {
148 std::map<KEY, Set> sets;
149 for(
const KeyLabel& pair: (Tree)*
this)
150 sets[findSet(pair.second)].insert(pair.first);
155 std::map<KEY, Set> partition(
const std::list<KEY>& keys)
const {
156 std::map<KEY, Set> partitions;
157 for(
const KEY& key: keys)
158 partitions[findSet(key)].insert(key);
163 Set
set(
const KEY& label)
const {
165 for(
const KeyLabel& pair: (Tree)*
this) {
166 if (pair.second == label || findSet(pair.second) == label)
167 set.insert(pair.first);
174 return (Tree) *
this == (Tree) t;
179 return (Tree) *
this != (Tree) t;
183 void print(
const std::string& name =
"DSF")
const {
184 std::cout << name << std::endl;
185 for(
const KeyLabel& pair: (Tree)*
this)
186 std::cout << (std::string) pair.first <<
" " << (std::string) pair.second
197 KEY parent = this->
find(key);
202 *
this = this->
add(key, label);
bool mem(const KEY &x) const
Definition: BTree.h:162
Binary tree.
Definition: BTree.h:34
size_t size() const
Definition: BTree.h:232
purely functional binary tree
KEY findSet_(const KEY &key)
Definition: DSF.h:196
bool operator==(const Self &t) const
Definition: DSF.h:173
Definition: chartTesting.h:28
bool operator!=(const Self &t) const
Definition: DSF.h:178
BTree add(const value_type &xd) const
Definition: BTree.h:145
const KEY & find(const KEY &k) const
Definition: BTree.h:241