Changeset 1931:6abf67b02ff5 in lemon-0.x
- Timestamp:
- 01/31/06 20:33:48 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2506
- Location:
- lemon
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/graph_utils.h
r1909 r1931 887 887 /// and if a key is set to a new value then store it 888 888 /// in the inverse map. 889 /// 890 /// The values of the map can be accessed 891 /// with stl compatible forward iterator. 892 /// 889 893 /// \param _Graph The graph type. 890 894 /// \param _Item The item type of the graph. 891 895 /// \param _Value The value type of the map. 896 /// 897 /// \see IterableValueMap 892 898 #ifndef DOXYGEN 893 899 /// \param _Map A ReadWriteMap mapping from the item type to integer. … … 900 906 #endif 901 907 class InvertableMap : protected _Map { 902 903 public: 904 905 typedef _Map Map; 906 typedef _Graph Graph; 908 public: 907 909 908 910 /// The key type of InvertableMap (Node, Edge, UEdge). … … 911 913 typedef typename _Map::Value Value; 912 914 915 private: 916 917 typedef _Map Map; 918 typedef _Graph Graph; 919 920 typedef std::map<Value, Key> Container; 921 Container invMap; 922 923 public: 924 925 926 913 927 /// \brief Constructor. 914 928 /// … … 916 930 /// 917 931 InvertableMap(const Graph& graph) : Map(graph) {} 932 933 /// \brief Forward iterator for values. 934 /// 935 /// This iterator is an stl compatible forward 936 /// iterator on the values of the map. The values can 937 /// be accessed in the [beginValue, endValue) range. 938 /// 939 class ValueIterator 940 : public std::iterator<std::forward_iterator_tag, Value> { 941 friend class InvertableMap; 942 private: 943 ValueIterator(typename Container::const_iterator _it) 944 : it(_it) {} 945 public: 946 947 ValueIterator() {} 948 949 ValueIterator& operator++() { ++it; return *this; } 950 ValueIterator operator++(int) { 951 ValueIterator tmp(*this); 952 operator++(); 953 return tmp; 954 } 955 956 const Value& operator*() const { return it->first; } 957 const Value* operator->() const { return &(it->first); } 958 959 bool operator==(ValueIterator jt) const { return it == jt.it; } 960 bool operator!=(ValueIterator jt) const { return it != jt.it; } 961 962 private: 963 typename Container::const_iterator it; 964 }; 965 966 /// \brief Returns an iterator to the first value. 967 /// 968 /// Returns an stl compatible iterator to the 969 /// first value of the map. The values of the 970 /// map can be accessed in the [beginValue, endValue) 971 /// range. 972 ValueIterator beginValue() const { 973 return ValueIterator(invMap.begin()); 974 } 975 976 /// \brief Returns an iterator after the last value. 977 /// 978 /// Returns an stl compatible iterator after the 979 /// last value of the map. The values of the 980 /// map can be accessed in the [beginValue, endValue) 981 /// range. 982 ValueIterator endValue() const { 983 return ValueIterator(invMap.end()); 984 } 918 985 919 986 /// \brief The setter function of the map. … … 933 1000 /// 934 1001 /// It gives back the value associated with the key. 935 Value operator[](const Key& key) const { 1002 typename MapTraits<Map>::ConstReturnValue 1003 operator[](const Key& key) const { 936 1004 return Map::operator[](key); 937 1005 } … … 975 1043 Map::clear(); 976 1044 } 977 978 private:979 980 typedef std::map<Value, Key> Container;981 Container invMap;982 1045 983 1046 public: … … 1141 1204 public: 1142 1205 1206 /// \brief Returns the maximal value plus one. 1207 /// 1208 /// Returns the maximal value plus one in the map. 1209 unsigned int size() const { 1210 return invMap.size(); 1211 } 1212 1143 1213 /// \brief Swaps the position of the two items in the map. 1144 1214 /// … … 1194 1264 /// 1195 1265 /// Returns the size of the map. 1196 int size() const {1266 unsigned int size() const { 1197 1267 return inverted.invMap.size(); 1198 1268 } … … 1448 1518 Parent::set(key, 0); 1449 1519 } 1520 1450 1521 virtual void add(const std::vector<Key>& keys) { 1451 1522 Parent::add(keys); … … 1488 1559 } 1489 1560 1561 virtual void add(const std::vector<Edge>& edges) { 1562 for (int i = 0; i < (int)edges.size(); ++i) { 1563 ++deg[graph.target(edges[i])]; 1564 } 1565 } 1566 1490 1567 virtual void erase(const Edge& edge) { 1491 1568 --deg[graph.target(edge)]; 1569 } 1570 1571 virtual void erase(const std::vector<Edge>& edges) { 1572 for (int i = 0; i < (int)edges.size(); ++i) { 1573 --deg[graph.target(edges[i])]; 1574 } 1492 1575 } 1493 1576 … … 1592 1675 } 1593 1676 1677 virtual void add(const std::vector<Edge>& edges) { 1678 for (int i = 0; i < (int)edges.size(); ++i) { 1679 ++deg[graph.source(edges[i])]; 1680 } 1681 } 1682 1594 1683 virtual void erase(const Edge& edge) { 1595 1684 --deg[graph.source(edge)]; 1685 } 1686 1687 virtual void erase(const std::vector<Edge>& edges) { 1688 for (int i = 0; i < (int)edges.size(); ++i) { 1689 --deg[graph.source(edges[i])]; 1690 } 1596 1691 } 1597 1692 -
lemon/iterable_maps.h
r1913 r1931 17 17 #include <lemon/traits.h> 18 18 #include <lemon/invalid.h> 19 19 20 #include <vector> 21 #include <map> 22 23 #include <iterator> 20 24 #include <limits> 21 25 … … 30 34 namespace lemon { 31 35 32 ///\ingroup maps36 ///\ingroup graph_maps 33 37 /// 34 38 /// \brief Dynamic iterable bool map. … … 46 50 private: 47 51 typedef _Graph Graph; 48 typedef _Item Item; 49 50 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; 51 typedef typename ItemSetTraits<Graph, Item> 52 53 typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt; 54 typedef typename ItemSetTraits<Graph, _Item> 52 55 ::template Map<int>::Parent Parent; 53 56 54 std::vector< Item> array;57 std::vector<_Item> array; 55 58 int sep; 56 59 57 60 const Graph& graph; 58 59 private:60 61 int position(const Item& item) const {62 return Parent::operator[](item);63 }64 61 65 62 public: … … 69 66 70 67 /// The key type 71 typedef Item Key;68 typedef _Item Key; 72 69 /// The value type 73 70 typedef bool Value; … … 75 72 typedef const Value& ConstReference; 76 73 74 private: 75 76 int position(const Key& key) const { 77 return Parent::operator[](key); 78 } 79 80 public: 77 81 78 82 /// \brief Refernce to the value of the map. … … 122 126 IterableBoolMap(const Graph& _graph, bool def = false) 123 127 : Parent(_graph), graph(_graph) { 124 for ( ItemIt it(graph); it != INVALID; ++it) {128 for (KeyIt it(graph); it != INVALID; ++it) { 125 129 Parent::set(it, array.size()); 126 130 array.push_back(it); … … 132 136 /// 133 137 /// Const subscript operator of the map. 134 bool operator[](const Item& item) const {135 return position( item) < sep;138 bool operator[](const Key& key) const { 139 return position(key) < sep; 136 140 } 137 141 … … 139 143 /// 140 144 /// Subscript operator of the map. 141 Reference operator[](const Item& item) {142 return Reference(*this, item);145 Reference operator[](const Key& key) { 146 return Reference(*this, key); 143 147 } 144 148 … … 146 150 /// 147 151 /// Set operation of the map. 148 void set(const Item& item, bool value) {149 int pos = position( item);152 void set(const Key& key, bool value) { 153 int pos = position(key); 150 154 if (value) { 151 155 if (pos < sep) return; 152 Itemtmp = array[sep];153 array[sep] = item;154 Parent::set( item, sep);156 Key tmp = array[sep]; 157 array[sep] = key; 158 Parent::set(key, sep); 155 159 array[pos] = tmp; 156 160 Parent::set(tmp, pos); … … 159 163 if (pos >= sep) return; 160 164 --sep; 161 Itemtmp = array[sep];162 array[sep] = item;163 Parent::set( item, sep);165 Key tmp = array[sep]; 166 array[sep] = key; 167 Parent::set(key, sep); 164 168 array[pos] = tmp; 165 169 Parent::set(tmp, pos); … … 167 171 } 168 172 169 /// \brief Returns the number of the items mapped to true.170 /// 171 /// Returns the number of the items mapped to true.173 /// \brief Returns the number of the keys mapped to true. 174 /// 175 /// Returns the number of the keys mapped to true. 172 176 int trueNum() const { 173 177 return sep; 174 178 } 175 179 176 /// \brief Returns the number of the items mapped to false.177 /// 178 /// Returns the number of the items mapped to false.180 /// \brief Returns the number of the keys mapped to false. 181 /// 182 /// Returns the number of the keys mapped to false. 179 183 int falseNum() const { 180 184 return array.size() - sep; … … 185 189 /// Iterator for the keys mapped to true. It works 186 190 /// like a graph item iterator in the map, it can be converted 187 /// the itemtype of the map, incremented with \c ++ operator, and188 /// if the iterator leave the last valid itemit will be equal to191 /// the key type of the map, incremented with \c ++ operator, and 192 /// if the iterator leave the last valid key it will be equal to 189 193 /// \c INVALID. 190 class TrueIt : public Item{194 class TrueIt : public Key { 191 195 public: 192 typedef ItemParent;196 typedef Key Parent; 193 197 194 198 /// \brief Creates an iterator. … … 203 207 /// \brief Invalid constructor \& conversion. 204 208 /// 205 /// This constructor initializes the itemto be invalid.209 /// This constructor initializes the key to be invalid. 206 210 /// \sa Invalid for more details. 207 211 TrueIt(Invalid) : Parent(INVALID), map(0) {} … … 225 229 /// Iterator for the keys mapped to false. It works 226 230 /// like a graph item iterator in the map, it can be converted 227 /// the itemtype of the map, incremented with \c ++ operator, and228 /// if the iterator leave the last valid itemit will be equal to231 /// the key type of the map, incremented with \c ++ operator, and 232 /// if the iterator leave the last valid key it will be equal to 229 233 /// \c INVALID. 230 class FalseIt : public Item{234 class FalseIt : public Key { 231 235 public: 232 typedef ItemParent;236 typedef Key Parent; 233 237 234 238 /// \brief Creates an iterator. … … 238 242 /// \param map The IterableIntMap 239 243 FalseIt(const IterableBoolMap& _map) 240 : Parent(_map.sep < _map.array.size() ? _map.array.back() : INVALID),241 map(&_map) {}244 : Parent(_map.sep < (int)_map.array.size() ? 245 _map.array.back() : INVALID), map(&_map) {} 242 246 243 247 /// \brief Invalid constructor \& conversion. 244 248 /// 245 /// This constructor initializes the itemto be invalid.249 /// This constructor initializes the key to be invalid. 246 250 /// \sa Invalid for more details. 247 251 FalseIt(Invalid) : Parent(INVALID), map(0) {} … … 260 264 }; 261 265 266 /// \brief Iterator for the keys mapped to a given value. 267 /// 268 /// Iterator for the keys mapped to a given value. It works 269 /// like a graph item iterator in the map, it can be converted 270 /// the key type of the map, incremented with \c ++ operator, and 271 /// if the iterator leave the last valid key it will be equal to 272 /// \c INVALID. 273 class ItemIt : public Key { 274 public: 275 typedef Key Parent; 276 277 /// \brief Creates an iterator. 278 /// 279 /// Creates an iterator. It iterates on the 280 /// keys which mapped to false. 281 /// \param map The IterableIntMap 282 /// \param value Which elements should be iterated. 283 ItemIt(const IterableBoolMap& _map, bool value) 284 : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) : 285 (_map.sep < (int)_map.array.size() ? 286 _map.array.back() : INVALID)), map(&_map) {} 287 288 /// \brief Invalid constructor \& conversion. 289 /// 290 /// This constructor initializes the key to be invalid. 291 /// \sa Invalid for more details. 292 ItemIt(Invalid) : Parent(INVALID), map(0) {} 293 294 /// \brief Increment operator. 295 /// 296 /// Increment Operator. 297 ItemIt& operator++() { 298 int pos = map->position(*this); 299 int sep = pos >= map->sep ? map->sep : 0; 300 Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID); 301 return *this; 302 } 303 304 private: 305 const IterableBoolMap* map; 306 }; 307 262 308 protected: 263 309 264 virtual void add(const Item& item) {265 Parent::add( item);266 Parent::set( item, array.size());267 array.push_back( item);268 } 269 270 virtual void add(const std::vector< Item>& items) {271 Parent::add( items);272 for (int i = 0; i < (int) items.size(); ++i) {273 Parent::set( items[i], array.size());274 array.push_back( items[i]);275 } 276 } 277 278 virtual void erase(const Item& item) {279 int pos = position( item);310 virtual void add(const Key& key) { 311 Parent::add(key); 312 Parent::set(key, array.size()); 313 array.push_back(key); 314 } 315 316 virtual void add(const std::vector<Key>& keys) { 317 Parent::add(keys); 318 for (int i = 0; i < (int)keys.size(); ++i) { 319 Parent::set(keys[i], array.size()); 320 array.push_back(keys[i]); 321 } 322 } 323 324 virtual void erase(const Key& key) { 325 int pos = position(key); 280 326 if (pos < sep) { 281 327 --sep; … … 290 336 array.pop_back(); 291 337 } 292 Parent::erase( item);293 } 294 295 virtual void erase(const std::vector< Item>& items) {296 for (int i = 0; i < (int) items.size(); ++i) {297 int pos = position( items[i]);338 Parent::erase(key); 339 } 340 341 virtual void erase(const std::vector<Key>& keys) { 342 for (int i = 0; i < (int)keys.size(); ++i) { 343 int pos = position(keys[i]); 298 344 if (pos < sep) { 299 345 --sep; … … 309 355 } 310 356 } 311 Parent::erase( items);357 Parent::erase(keys); 312 358 } 313 359 314 360 virtual void build() { 315 361 Parent::build(); 316 for ( ItemIt it(graph); it != INVALID; ++it) {362 for (KeyIt it(graph); it != INVALID; ++it) { 317 363 Parent::set(it, array.size()); 318 364 array.push_back(it); … … 340 386 } 341 387 342 ///\ingroup maps388 ///\ingroup graph_maps 343 389 /// 344 390 /// \brief Dynamic iterable integer map. … … 515 561 /// 516 562 /// Gives back the maximal value plus one. 517 int size() const {518 return (int)first.size();563 unsigned int size() const { 564 return first.size(); 519 565 } 520 566 … … 595 641 596 642 virtual void erase(const std::vector<Key>& keys) { 597 for (int i = 0; i < keys.size(); ++i) {643 for (int i = 0; i < (int)keys.size(); ++i) { 598 644 unlace(keys[i]); 599 645 } … … 610 656 }; 611 657 658 namespace _iterable_maps_bits { 659 template <typename Item, typename Value> 660 struct IterableValueMapNode { 661 IterableValueMapNode(Value _value = Value()) : value(_value) {} 662 Item prev, next; 663 Value value; 664 }; 665 } 666 667 ///\ingroup graph_maps 668 /// 669 /// \brief Dynamic iterable map for comparable values. 670 /// 671 /// This class provides a special graph map type which can store 672 /// for each graph item(node, edge, etc.) a value. For each 673 /// value it is possible to iterate on the keys which mapped to the 674 /// given value. The type stores for each value a linked list with 675 /// the items which mapped to the value, and the values are stored 676 /// in balanced binary tree. The values of the map can be accessed 677 /// with stl compatible forward iterator. 678 /// 679 /// This type is not reference map so it cannot be modified with 680 /// the subscription operator. 681 /// 682 /// \see InvertableMap 683 /// 684 /// \param _Graph The graph type. 685 /// \param _Item One of the graph's item type, the key of the map. 686 /// \param _Value Any comparable value type. 687 template <typename _Graph, typename _Item, typename _Value> 688 class IterableValueMap : protected ItemSetTraits<_Graph, _Item> 689 ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> > 690 ::Parent { 691 public: 692 typedef typename ItemSetTraits<_Graph, _Item> 693 ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> > 694 ::Parent Parent; 695 696 /// The key type 697 typedef _Item Key; 698 /// The value type 699 typedef _Value Value; 700 /// The graph type 701 typedef _Graph Graph; 702 703 /// \brief Constructor of the Map with a given value. 704 /// 705 /// Constructor of the Map with a given value. 706 explicit IterableValueMap(const Graph& graph, 707 const Value& value = Value()) 708 : Parent(graph, _iterable_maps_bits::IterableValueMapNode<_Item, 709 _Value>(value)) { 710 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { 711 lace(it); 712 } 713 } 714 715 private: 716 717 void unlace(const Key& key) { 718 typename Parent::Value& node = Parent::operator[](key); 719 if (node.prev != INVALID) { 720 Parent::operator[](node.prev).next = node.next; 721 } else { 722 if (node.next != INVALID) { 723 first[node.value] = node.next; 724 } else { 725 first.erase(node.value); 726 } 727 } 728 if (node.next != INVALID) { 729 Parent::operator[](node.next).prev = node.prev; 730 } 731 } 732 733 void lace(const Key& key) { 734 typename Parent::Value& node = Parent::operator[](key); 735 typename std::map<Value, Key>::iterator it = first.find(node.value); 736 if (it == first.end()) { 737 node.prev = node.next = INVALID; 738 if (node.next != INVALID) { 739 Parent::operator[](node.next).prev = key; 740 } 741 first.insert(make_pair(node.value, key)); 742 } else { 743 node.prev = INVALID; 744 node.next = it->second; 745 if (node.next != INVALID) { 746 Parent::operator[](node.next).prev = key; 747 } 748 it->second = key; 749 } 750 } 751 752 public: 753 754 /// \brief Forward iterator for values. 755 /// 756 /// This iterator is an stl compatible forward 757 /// iterator on the values of the map. The values can 758 /// be accessed in the [beginValue, endValue) range. 759 /// 760 class ValueIterator 761 : public std::iterator<std::forward_iterator_tag, Value> { 762 friend class IterableValueMap; 763 private: 764 ValueIterator(typename std::map<Value, Key>::const_iterator _it) 765 : it(_it) {} 766 public: 767 768 ValueIterator() {} 769 770 ValueIterator& operator++() { ++it; return *this; } 771 ValueIterator operator++(int) { 772 ValueIterator tmp(*this); 773 operator++(); 774 return tmp; 775 } 776 777 const Value& operator*() const { return it->first; } 778 const Value* operator->() const { return &(it->first); } 779 780 bool operator==(ValueIterator jt) const { return it == jt.it; } 781 bool operator!=(ValueIterator jt) const { return it != jt.it; } 782 783 private: 784 typename std::map<Value, Key>::const_iterator it; 785 }; 786 787 /// \brief Returns an iterator to the first value. 788 /// 789 /// Returns an stl compatible iterator to the 790 /// first value of the map. The values of the 791 /// map can be accessed in the [beginValue, endValue) 792 /// range. 793 ValueIterator beginValue() const { 794 return ValueIterator(first.begin()); 795 } 796 797 /// \brief Returns an iterator after the last value. 798 /// 799 /// Returns an stl compatible iterator after the 800 /// last value of the map. The values of the 801 /// map can be accessed in the [beginValue, endValue) 802 /// range. 803 ValueIterator endValue() const { 804 return ValueIterator(first.end()); 805 } 806 807 /// \brief Set operation of the map. 808 /// 809 /// Set operation of the map. 810 void set(const Key& key, const Value& value) { 811 unlace(key); 812 Parent::operator[](key).value = value; 813 lace(key); 814 } 815 816 /// \brief Const subscript operator of the map. 817 /// 818 /// Const subscript operator of the map. 819 const Value& operator[](const Key& key) const { 820 return Parent::operator[](key).value; 821 } 822 823 /// \brief Iterator for the keys with the same value. 824 /// 825 /// Iterator for the keys with the same value. It works 826 /// like a graph item iterator in the map, it can be converted 827 /// the item type of the map, incremented with \c ++ operator, and 828 /// if the iterator leave the last valid item it will be equal to 829 /// \c INVALID. 830 class ItemIt : public _Item { 831 public: 832 typedef _Item Parent; 833 834 /// \brief Invalid constructor \& conversion. 835 /// 836 /// This constructor initializes the item to be invalid. 837 /// \sa Invalid for more details. 838 ItemIt(Invalid) : Parent(INVALID), _map(0) {} 839 840 /// \brief Creates an iterator with a value. 841 /// 842 /// Creates an iterator with a value. It iterates on the 843 /// keys which have the given value. 844 /// \param map The IterableValueMap 845 /// \param value The value 846 ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) { 847 typename std::map<Value, Key>::const_iterator it = 848 map.first.find(value); 849 if (it == map.first.end()) { 850 Parent::operator=(INVALID); 851 } else { 852 Parent::operator=(it->second); 853 } 854 } 855 856 /// \brief Increment operator. 857 /// 858 /// Increment Operator. 859 ItemIt& operator++() { 860 Parent::operator=(_map->IterableValueMap::Parent:: 861 operator[](static_cast<Parent&>(*this)).next); 862 return *this; 863 } 864 865 866 private: 867 const IterableValueMap* _map; 868 }; 869 870 protected: 871 872 virtual void erase(const Key& key) { 873 unlace(key); 874 Parent::erase(key); 875 } 876 877 virtual void erase(const std::vector<Key>& keys) { 878 for (int i = 0; i < (int)keys.size(); ++i) { 879 unlace(keys[i]); 880 } 881 Parent::erase(keys); 882 } 883 884 virtual void clear() { 885 first.clear(); 886 Parent::clear(); 887 } 888 889 private: 890 std::map<Value, Key> first; 891 }; 892 612 893 /// @} 613 894 }
Note: See TracChangeset
for help on using the changeset viewer.