00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #include <lemon/traits.h>
00020 #include <lemon/invalid.h>
00021
00022 #include <vector>
00023 #include <map>
00024
00025 #include <iterator>
00026 #include <limits>
00027
00034
00035
00036 namespace lemon {
00037
00049 template <typename _Graph, typename _Item>
00050 class IterableBoolMap
00051 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent {
00052 private:
00053 typedef _Graph Graph;
00054
00055 typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
00056 typedef typename ItemSetTraits<Graph, _Item>
00057 ::template Map<int>::Parent Parent;
00058
00059 std::vector<_Item> array;
00060 int sep;
00061
00062 const Graph& graph;
00063
00064 public:
00065
00067 typedef True ReferenceMapTag;
00068
00070 typedef _Item Key;
00072 typedef bool Value;
00074 typedef const Value& ConstReference;
00075
00076 private:
00077
00078 int position(const Key& key) const {
00079 return Parent::operator[](key);
00080 }
00081
00082 public:
00083
00088 class Reference {
00089 friend class IterableBoolMap;
00090 private:
00091 Reference(IterableBoolMap& map, const Key& key)
00092 : _key(key), _map(map) {}
00093 public:
00094
00095 Reference& operator=(const Reference& value) {
00096 _map.set(_key, (bool)value);
00097 return *this;
00098 }
00099
00100 operator bool() const {
00101 return static_cast<const IterableBoolMap&>(_map)[_key];
00102 }
00103
00104 Reference& operator=(bool value) {
00105 _map.set(_key, value);
00106 return *this;
00107 }
00108 Reference& operator&=(bool value) {
00109 _map.set(_key, _map[_key] & value);
00110 return *this;
00111 }
00112 Reference& operator|=(bool value) {
00113 _map.set(_key, _map[_key] | value);
00114 return *this;
00115 }
00116 Reference& operator^=(bool value) {
00117 _map.set(_key, _map[_key] ^ value);
00118 return *this;
00119 }
00120 private:
00121 Key _key;
00122 IterableBoolMap& _map;
00123 };
00124
00128 IterableBoolMap(const Graph& _graph, bool def = false)
00129 : Parent(_graph), graph(_graph) {
00130 for (KeyIt it(graph); it != INVALID; ++it) {
00131 Parent::set(it, array.size());
00132 array.push_back(it);
00133 }
00134 sep = (def ? array.size() : 0);
00135 }
00136
00140 bool operator[](const Key& key) const {
00141 return position(key) < sep;
00142 }
00143
00147 Reference operator[](const Key& key) {
00148 return Reference(*this, key);
00149 }
00150
00154 void set(const Key& key, bool value) {
00155 int pos = position(key);
00156 if (value) {
00157 if (pos < sep) return;
00158 Key tmp = array[sep];
00159 array[sep] = key;
00160 Parent::set(key, sep);
00161 array[pos] = tmp;
00162 Parent::set(tmp, pos);
00163 ++sep;
00164 } else {
00165 if (pos >= sep) return;
00166 --sep;
00167 Key tmp = array[sep];
00168 array[sep] = key;
00169 Parent::set(key, sep);
00170 array[pos] = tmp;
00171 Parent::set(tmp, pos);
00172 }
00173 }
00174
00178 int trueNum() const {
00179 return sep;
00180 }
00181
00185 int falseNum() const {
00186 return array.size() - sep;
00187 }
00188
00196 class TrueIt : public Key {
00197 public:
00198 typedef Key Parent;
00199
00205 TrueIt(const IterableBoolMap& _map)
00206 : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID),
00207 map(&_map) {}
00208
00213 TrueIt(Invalid) : Parent(INVALID), map(0) {}
00214
00218 TrueIt& operator++() {
00219 int pos = map->position(*this);
00220 Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
00221 return *this;
00222 }
00223
00224
00225 private:
00226 const IterableBoolMap* map;
00227 };
00228
00236 class FalseIt : public Key {
00237 public:
00238 typedef Key Parent;
00239
00245 FalseIt(const IterableBoolMap& _map)
00246 : Parent(_map.sep < (int)_map.array.size() ?
00247 _map.array.back() : INVALID), map(&_map) {}
00248
00253 FalseIt(Invalid) : Parent(INVALID), map(0) {}
00254
00258 FalseIt& operator++() {
00259 int pos = map->position(*this);
00260 Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
00261 return *this;
00262 }
00263
00264 private:
00265 const IterableBoolMap* map;
00266 };
00267
00275 class ItemIt : public Key {
00276 public:
00277 typedef Key Parent;
00278
00285 ItemIt(const IterableBoolMap& _map, bool value)
00286 : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
00287 (_map.sep < (int)_map.array.size() ?
00288 _map.array.back() : INVALID)), map(&_map) {}
00289
00294 ItemIt(Invalid) : Parent(INVALID), map(0) {}
00295
00299 ItemIt& operator++() {
00300 int pos = map->position(*this);
00301 int sep = pos >= map->sep ? map->sep : 0;
00302 Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
00303 return *this;
00304 }
00305
00306 private:
00307 const IterableBoolMap* map;
00308 };
00309
00310 protected:
00311
00312 virtual void add(const Key& key) {
00313 Parent::add(key);
00314 Parent::set(key, array.size());
00315 array.push_back(key);
00316 }
00317
00318 virtual void add(const std::vector<Key>& keys) {
00319 Parent::add(keys);
00320 for (int i = 0; i < (int)keys.size(); ++i) {
00321 Parent::set(keys[i], array.size());
00322 array.push_back(keys[i]);
00323 }
00324 }
00325
00326 virtual void erase(const Key& key) {
00327 int pos = position(key);
00328 if (pos < sep) {
00329 --sep;
00330 Parent::set(array[sep], pos);
00331 array[pos] = array[sep];
00332 Parent::set(array.back(), sep);
00333 array[sep] = array.back();
00334 array.pop_back();
00335 } else {
00336 Parent::set(array.back(), pos);
00337 array[pos] = array.back();
00338 array.pop_back();
00339 }
00340 Parent::erase(key);
00341 }
00342
00343 virtual void erase(const std::vector<Key>& keys) {
00344 for (int i = 0; i < (int)keys.size(); ++i) {
00345 int pos = position(keys[i]);
00346 if (pos < sep) {
00347 --sep;
00348 Parent::set(array[sep], pos);
00349 array[pos] = array[sep];
00350 Parent::set(array.back(), sep);
00351 array[sep] = array.back();
00352 array.pop_back();
00353 } else {
00354 Parent::set(array.back(), pos);
00355 array[pos] = array.back();
00356 array.pop_back();
00357 }
00358 }
00359 Parent::erase(keys);
00360 }
00361
00362 virtual void build() {
00363 Parent::build();
00364 for (KeyIt it(graph); it != INVALID; ++it) {
00365 Parent::set(it, array.size());
00366 array.push_back(it);
00367 }
00368 sep = 0;
00369 }
00370
00371 virtual void clear() {
00372 array.clear();
00373 sep = 0;
00374 Parent::clear();
00375 }
00376
00377 };
00378
00379
00380 namespace _iterable_maps_bits {
00381 template <typename Item>
00382 struct IterableIntMapNode {
00383 IterableIntMapNode() : value(-1) {}
00384 IterableIntMapNode(int _value) : value(_value) {}
00385 Item prev, next;
00386 int value;
00387 };
00388 }
00389
00401 template <typename _Graph, typename _Item>
00402 class IterableIntMap : protected ItemSetTraits<_Graph, _Item>
00403 ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
00404 public:
00405 typedef typename ItemSetTraits<_Graph, _Item>
00406 ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
00407 ::Parent Parent;
00408
00410 typedef _Item Key;
00412 typedef int Value;
00414 typedef _Graph Graph;
00415
00419 explicit IterableIntMap(const Graph& graph)
00420 : Parent(graph) {}
00421
00425 explicit IterableIntMap(const Graph& graph, int value)
00426 : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
00427 if (value >= 0) {
00428 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
00429 lace(it);
00430 }
00431 }
00432 }
00433
00434 private:
00435
00436 void unlace(const Key& key) {
00437 typename Parent::Value& node = Parent::operator[](key);
00438 if (node.value < 0) return;
00439 if (node.prev != INVALID) {
00440 Parent::operator[](node.prev).next = node.next;
00441 } else {
00442 first[node.value] = node.next;
00443 }
00444 if (node.next != INVALID) {
00445 Parent::operator[](node.next).prev = node.prev;
00446 }
00447 while (!first.empty() && first.back() == INVALID) {
00448 first.pop_back();
00449 }
00450 }
00451
00452 void lace(const Key& key) {
00453 typename Parent::Value& node = Parent::operator[](key);
00454 if (node.value < 0) return;
00455 if (node.value >= (int)first.size()) {
00456 first.resize(node.value + 1, INVALID);
00457 }
00458 node.prev = INVALID;
00459 node.next = first[node.value];
00460 if (node.next != INVALID) {
00461 Parent::operator[](node.next).prev = key;
00462 }
00463 first[node.value] = key;
00464 }
00465
00466 public:
00467
00469 typedef True ReferenceMapTag;
00470
00475 class Reference {
00476 friend class IterableIntMap;
00477 private:
00478 Reference(IterableIntMap& map, const Key& key)
00479 : _key(key), _map(map) {}
00480 public:
00481
00482 Reference& operator=(const Reference& value) {
00483 _map.set(_key, (const int&)value);
00484 return *this;
00485 }
00486
00487 operator const int&() const {
00488 return static_cast<const IterableIntMap&>(_map)[_key];
00489 }
00490
00491 Reference& operator=(int value) {
00492 _map.set(_key, value);
00493 return *this;
00494 }
00495 Reference& operator++() {
00496 _map.set(_key, _map[_key] + 1);
00497 return *this;
00498 }
00499 int operator++(int) {
00500 int value = _map[_key];
00501 _map.set(_key, value + 1);
00502 return value;
00503 }
00504 Reference& operator--() {
00505 _map.set(_key, _map[_key] - 1);
00506 return *this;
00507 }
00508 int operator--(int) {
00509 int value = _map[_key];
00510 _map.set(_key, value - 1);
00511 return value;
00512 }
00513 Reference& operator+=(int value) {
00514 _map.set(_key, _map[_key] + value);
00515 return *this;
00516 }
00517 Reference& operator-=(int value) {
00518 _map.set(_key, _map[_key] - value);
00519 return *this;
00520 }
00521 Reference& operator*=(int value) {
00522 _map.set(_key, _map[_key] * value);
00523 return *this;
00524 }
00525 Reference& operator/=(int value) {
00526 _map.set(_key, _map[_key] / value);
00527 return *this;
00528 }
00529 Reference& operator%=(int value) {
00530 _map.set(_key, _map[_key] % value);
00531 return *this;
00532 }
00533 Reference& operator&=(int value) {
00534 _map.set(_key, _map[_key] & value);
00535 return *this;
00536 }
00537 Reference& operator|=(int value) {
00538 _map.set(_key, _map[_key] | value);
00539 return *this;
00540 }
00541 Reference& operator^=(int value) {
00542 _map.set(_key, _map[_key] ^ value);
00543 return *this;
00544 }
00545 Reference& operator<<=(int value) {
00546 _map.set(_key, _map[_key] << value);
00547 return *this;
00548 }
00549 Reference& operator>>=(int value) {
00550 _map.set(_key, _map[_key] >> value);
00551 return *this;
00552 }
00553
00554 private:
00555 Key _key;
00556 IterableIntMap& _map;
00557 };
00558
00560 typedef const Value& ConstReference;
00561
00565 unsigned int size() const {
00566 return first.size();
00567 }
00568
00572 void set(const Key& key, const Value& value) {
00573 unlace(key);
00574 Parent::operator[](key).value = value;
00575 lace(key);
00576 }
00577
00581 const Value& operator[](const Key& key) const {
00582 return Parent::operator[](key).value;
00583 }
00584
00588 Reference operator[](const Key& key) {
00589 return Reference(*this, key);
00590 }
00591
00599 class ItemIt : public _Item {
00600 public:
00601 typedef _Item Parent;
00602
00607 ItemIt(Invalid) : Parent(INVALID), _map(0) {}
00608
00615 ItemIt(const IterableIntMap& map, int value) : _map(&map) {
00616 if (value < 0 || value >= (int)_map->first.size()) {
00617 Parent::operator=(INVALID);
00618 } else {
00619 Parent::operator=(_map->first[value]);
00620 }
00621 }
00622
00626 ItemIt& operator++() {
00627 Parent::operator=(_map->IterableIntMap::Parent::
operator[](static_cast<Parent&>(*this)).next);
00628 return *this;
00629 }
00630
00631
00632 private:
00633 const IterableIntMap* _map;
00634 };
00635
00636 protected:
00637
00638 virtual void erase(const Key& key) {
00639 unlace(key);
00640 Parent::erase(key);
00641 }
00642
00643 virtual void erase(const std::vector<Key>& keys) {
00644 for (int i = 0; i < (int)keys.size(); ++i) {
00645 unlace(keys[i]);
00646 }
00647 Parent::erase(keys);
00648 }
00649
00650 virtual void clear() {
00651 first.clear();
00652 Parent::clear();
00653 }
00654
00655 private:
00656 std::vector<_Item> first;
00657 };
00658
00659 namespace _iterable_maps_bits {
00660 template <typename Item, typename Value>
00661 struct IterableValueMapNode {
00662 IterableValueMapNode(Value _value = Value()) : value(_value) {}
00663 Item prev, next;
00664 Value value;
00665 };
00666 }
00667
00688 template <typename _Graph, typename _Item, typename _Value>
00689 class IterableValueMap : protected ItemSetTraits<_Graph, _Item>
00690 ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
00691 ::Parent {
00692 public:
00693 typedef typename ItemSetTraits<_Graph, _Item>
00694 ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
00695 ::Parent Parent;
00696
00698 typedef _Item Key;
00700 typedef _Value Value;
00702 typedef _Graph Graph;
00703
00707 explicit IterableValueMap(const Graph& graph,
00708 const Value& value = Value())
00709 : Parent(graph, _iterable_maps_bits::IterableValueMapNode<_Item,
00710 _Value>(value)) {
00711 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
00712 lace(it);
00713 }
00714 }
00715
00716 private:
00717
00718 void unlace(const Key& key) {
00719 typename Parent::Value& node = Parent::operator[](key);
00720 if (node.prev != INVALID) {
00721 Parent::operator[](node.prev).next = node.next;
00722 } else {
00723 if (node.next != INVALID) {
00724 first[node.value] = node.next;
00725 } else {
00726 first.erase(node.value);
00727 }
00728 }
00729 if (node.next != INVALID) {
00730 Parent::operator[](node.next).prev = node.prev;
00731 }
00732 }
00733
00734 void lace(const Key& key) {
00735 typename Parent::Value& node = Parent::operator[](key);
00736 typename std::map<Value, Key>::iterator it = first.find(node.value);
00737 if (it == first.end()) {
00738 node.prev = node.next = INVALID;
00739 if (node.next != INVALID) {
00740 Parent::operator[](node.next).prev = key;
00741 }
00742 first.insert(make_pair(node.value, key));
00743 } else {
00744 node.prev = INVALID;
00745 node.next = it->second;
00746 if (node.next != INVALID) {
00747 Parent::operator[](node.next).prev = key;
00748 }
00749 it->second = key;
00750 }
00751 }
00752
00753 public:
00754
00761 class ValueIterator
00762 : public std::iterator<std::forward_iterator_tag, Value> {
00763 friend class IterableValueMap;
00764 private:
00765 ValueIterator(typename std::map<Value, Key>::const_iterator _it)
00766 : it(_it) {}
00767 public:
00768
00769 ValueIterator() {}
00770
00771 ValueIterator& operator++() { ++it; return *this; }
00772 ValueIterator operator++(int) {
00773 ValueIterator tmp(*this);
00774 operator++();
00775 return tmp;
00776 }
00777
00778 const Value& operator*() const { return it->first; }
00779 const Value* operator->() const { return &(it->first); }
00780
00781 bool operator==(ValueIterator jt) const { return it == jt.it; }
00782 bool operator!=(ValueIterator jt) const { return it != jt.it; }
00783
00784 private:
00785 typename std::map<Value, Key>::const_iterator it;
00786 };
00787
00794 ValueIterator beginValue() const {
00795 return ValueIterator(first.begin());
00796 }
00797
00804 ValueIterator endValue() const {
00805 return ValueIterator(first.end());
00806 }
00807
00811 void set(const Key& key, const Value& value) {
00812 unlace(key);
00813 Parent::operator[](key).value = value;
00814 lace(key);
00815 }
00816
00820 const Value& operator[](const Key& key) const {
00821 return Parent::operator[](key).value;
00822 }
00823
00831 class ItemIt : public _Item {
00832 public:
00833 typedef _Item Parent;
00834
00839 ItemIt(Invalid) : Parent(INVALID), _map(0) {}
00840
00847 ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
00848 typename std::map<Value, Key>::const_iterator it =
00849 map.first.find(value);
00850 if (it == map.first.end()) {
00851 Parent::operator=(INVALID);
00852 } else {
00853 Parent::operator=(it->second);
00854 }
00855 }
00856
00860 ItemIt& operator++() {
00861 Parent::operator=(_map->IterableValueMap::Parent::
operator[](static_cast<Parent&>(*this)).next);
00862 return *this;
00863 }
00864
00865
00866 private:
00867 const IterableValueMap* _map;
00868 };
00869
00870 protected:
00871
00872 virtual void erase(const Key& key) {
00873 unlace(key);
00874 Parent::erase(key);
00875 }
00876
00877 virtual void erase(const std::vector<Key>& keys) {
00878 for (int i = 0; i < (int)keys.size(); ++i) {
00879 unlace(keys[i]);
00880 }
00881 Parent::erase(keys);
00882 }
00883
00884 virtual void clear() {
00885 first.clear();
00886 Parent::clear();
00887 }
00888
00889 private:
00890 std::map<Value, Key> first;
00891 };
00892
00894 }
00895