OLD | NEW |
1 // Copyright 2017 The Chromium Authors. All rights reserved. | 1 // Copyright 2017 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef BASE_CONTAINERS_FLAT_TREE_H_ | 5 #ifndef BASE_CONTAINERS_FLAT_TREE_H_ |
6 #define BASE_CONTAINERS_FLAT_TREE_H_ | 6 #define BASE_CONTAINERS_FLAT_TREE_H_ |
7 | 7 |
8 #include <algorithm> | 8 #include <algorithm> |
9 #include <iterator> | 9 #include <iterator> |
| 10 #include <type_traits> |
10 #include <vector> | 11 #include <vector> |
11 | 12 |
| 13 #include "base/template_util.h" |
| 14 |
12 namespace base { | 15 namespace base { |
13 | 16 |
14 enum FlatContainerDupes { | 17 enum FlatContainerDupes { |
15 KEEP_FIRST_OF_DUPES, | 18 KEEP_FIRST_OF_DUPES, |
16 KEEP_LAST_OF_DUPES, | 19 KEEP_LAST_OF_DUPES, |
17 }; | 20 }; |
18 | 21 |
19 namespace internal { | 22 namespace internal { |
20 | 23 |
21 // This is a convenience method returning true if Iterator is at least a | 24 // This is a convenience method returning true if Iterator is at least a |
(...skipping 26 matching lines...) Expand all Loading... |
48 for (Iterator next = std::next(first); next != last; ++next, ++first) { | 51 for (Iterator next = std::next(first); next != last; ++next, ++first) { |
49 if (!compare(*first, *next)) | 52 if (!compare(*first, *next)) |
50 *replacable++ = std::move(*first); | 53 *replacable++ = std::move(*first); |
51 } | 54 } |
52 | 55 |
53 // Last element should be copied unconditionally. | 56 // Last element should be copied unconditionally. |
54 *replacable++ = std::move(*first); | 57 *replacable++ = std::move(*first); |
55 return replacable; | 58 return replacable; |
56 } | 59 } |
57 | 60 |
| 61 // Uses SFINAE to detect whether type has is_transparent member. |
| 62 template <typename T, typename = void> |
| 63 struct IsTransparentCompare : std::false_type {}; |
| 64 template <typename T> |
| 65 struct IsTransparentCompare<T, void_t<typename T::is_transparent>> |
| 66 : std::true_type {}; |
| 67 |
| 68 // Implementation ------------------------------------------------------------- |
| 69 |
58 // Implementation of a sorted vector for backing flat_set and flat_map. Do not | 70 // Implementation of a sorted vector for backing flat_set and flat_map. Do not |
59 // use directly. | 71 // use directly. |
60 // | 72 // |
61 // The use of "value" in this is like std::map uses, meaning it's the thing | 73 // The use of "value" in this is like std::map uses, meaning it's the thing |
62 // contained (in the case of map it's a <Kay, Mapped> pair). The Key is how | 74 // contained (in the case of map it's a <Kay, Mapped> pair). The Key is how |
63 // things are looked up. In the case of a set, Key == Value. In the case of | 75 // things are looked up. In the case of a set, Key == Value. In the case of |
64 // a map, the Key is a component of a Value. | 76 // a map, the Key is a component of a Value. |
65 // | 77 // |
66 // The helper class GetKeyFromValue provides the means to extract a key from a | 78 // The helper class GetKeyFromValue provides the means to extract a key from a |
67 // value for comparison purposes. It should implement: | 79 // value for comparison purposes. It should implement: |
(...skipping 159 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
227 // Erase operations. | 239 // Erase operations. |
228 // | 240 // |
229 // Assume that every operation invalidates iterators and references. | 241 // Assume that every operation invalidates iterators and references. |
230 // | 242 // |
231 // erase(position), erase(first, last) can take O(size). | 243 // erase(position), erase(first, last) can take O(size). |
232 // erase(key) may take O(size) + O(log(size)). | 244 // erase(key) may take O(size) + O(log(size)). |
233 // | 245 // |
234 // Prefer base::EraseIf() or some other variation on erase(remove(), end()) | 246 // Prefer base::EraseIf() or some other variation on erase(remove(), end()) |
235 // idiom when deleting multiple non-consecutive elements. | 247 // idiom when deleting multiple non-consecutive elements. |
236 | 248 |
| 249 iterator erase(iterator position); |
237 iterator erase(const_iterator position); | 250 iterator erase(const_iterator position); |
238 iterator erase(const_iterator first, const_iterator last); | 251 iterator erase(const_iterator first, const_iterator last); |
239 size_type erase(const key_type& key); | 252 template <typename K> |
| 253 size_type erase(const K& key); |
240 | 254 |
241 // -------------------------------------------------------------------------- | 255 // -------------------------------------------------------------------------- |
242 // Comparators. | 256 // Comparators. |
243 | 257 |
244 key_compare key_comp() const; | 258 key_compare key_comp() const; |
245 value_compare value_comp() const; | 259 value_compare value_comp() const; |
246 | 260 |
247 // -------------------------------------------------------------------------- | 261 // -------------------------------------------------------------------------- |
248 // Search operations. | 262 // Search operations. |
249 // | 263 // |
250 // Search operations have O(log(size)) complexity. | 264 // Search operations have O(log(size)) complexity. |
251 | 265 |
252 size_type count(const key_type& key) const; | 266 template <typename K> |
| 267 size_type count(const K& key) const; |
253 | 268 |
254 iterator find(const key_type& key); | 269 template <typename K> |
255 const_iterator find(const key_type& key) const; | 270 iterator find(const K& key); |
256 | 271 |
257 std::pair<iterator, iterator> equal_range(const key_type& ket); | 272 template <typename K> |
258 std::pair<const_iterator, const_iterator> equal_range( | 273 const_iterator find(const K& key) const; |
259 const key_type& key) const; | |
260 | 274 |
261 iterator lower_bound(const key_type& key); | 275 template <typename K> |
262 const_iterator lower_bound(const key_type& key) const; | 276 std::pair<iterator, iterator> equal_range(const K& key); |
263 | 277 |
264 iterator upper_bound(const key_type& key); | 278 template <typename K> |
265 const_iterator upper_bound(const key_type& key) const; | 279 std::pair<const_iterator, const_iterator> equal_range(const K& key) const; |
| 280 |
| 281 template <typename K> |
| 282 iterator lower_bound(const K& key); |
| 283 |
| 284 template <typename K> |
| 285 const_iterator lower_bound(const K& key) const; |
| 286 |
| 287 template <typename K> |
| 288 iterator upper_bound(const K& key); |
| 289 |
| 290 template <typename K> |
| 291 const_iterator upper_bound(const K& key) const; |
266 | 292 |
267 // -------------------------------------------------------------------------- | 293 // -------------------------------------------------------------------------- |
268 // General operations. | 294 // General operations. |
269 // | 295 // |
270 // Assume that swap invalidates iterators and references. | 296 // Assume that swap invalidates iterators and references. |
271 // | 297 // |
272 // Implementation note: currently we use operator==() and operator<() on | 298 // Implementation note: currently we use operator==() and operator<() on |
273 // std::vector, because they have the same contract we need, so we use them | 299 // std::vector, because they have the same contract we need, so we use them |
274 // directly for brevity and in case it is more optimal than calling equal() | 300 // directly for brevity and in case it is more optimal than calling equal() |
275 // and lexicograhpical_compare(). If the underlying container type is changed, | 301 // and lexicograhpical_compare(). If the underlying container type is changed, |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
310 iterator unsafe_emplace(const_iterator position, Args&&... args); | 336 iterator unsafe_emplace(const_iterator position, Args&&... args); |
311 | 337 |
312 private: | 338 private: |
313 // Helper class for e.g. lower_bound that can compare a value on the left | 339 // Helper class for e.g. lower_bound that can compare a value on the left |
314 // to a key on the right. | 340 // to a key on the right. |
315 struct KeyValueCompare { | 341 struct KeyValueCompare { |
316 // The key comparison object must outlive this class. | 342 // The key comparison object must outlive this class. |
317 explicit KeyValueCompare(const key_compare& key_comp) | 343 explicit KeyValueCompare(const key_compare& key_comp) |
318 : key_comp_(key_comp) {} | 344 : key_comp_(key_comp) {} |
319 | 345 |
320 bool operator()(const value_type& left, const key_type& right) const { | 346 template <typename T, typename U> |
321 GetKeyFromValue extractor; | 347 bool operator()(const T& lhs, const U& rhs) const { |
322 return key_comp_(extractor(left), right); | 348 return key_comp_(extract_if_value_type(lhs), extract_if_value_type(rhs)); |
323 } | 349 } |
324 | 350 |
325 private: | 351 private: |
| 352 const key_type& extract_if_value_type(const value_type& v) const { |
| 353 GetKeyFromValue extractor; |
| 354 return extractor(v); |
| 355 } |
| 356 |
| 357 template <typename K> |
| 358 const K& extract_if_value_type(const K& k) const { |
| 359 return k; |
| 360 } |
| 361 |
326 const key_compare& key_comp_; | 362 const key_compare& key_comp_; |
327 }; | 363 }; |
328 | 364 |
329 const flat_tree& as_const() { return *this; } | 365 const flat_tree& as_const() { return *this; } |
330 | 366 |
331 iterator const_cast_it(const_iterator c_it) { | 367 iterator const_cast_it(const_iterator c_it) { |
332 auto distance = std::distance(cbegin(), c_it); | 368 auto distance = std::distance(cbegin(), c_it); |
333 return std::next(begin(), distance); | 369 return std::next(begin(), distance); |
334 } | 370 } |
335 | 371 |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
429 template <class Cmp, class... Body> | 465 template <class Cmp, class... Body> |
430 explicit Impl(Cmp&& compare_arg, Body&&... underlying_type_args) | 466 explicit Impl(Cmp&& compare_arg, Body&&... underlying_type_args) |
431 : value_compare(std::forward<Cmp>(compare_arg)), | 467 : value_compare(std::forward<Cmp>(compare_arg)), |
432 body_(std::forward<Body>(underlying_type_args)...) {} | 468 body_(std::forward<Body>(underlying_type_args)...) {} |
433 | 469 |
434 const value_compare& get_value_comp() const { return *this; } | 470 const value_compare& get_value_comp() const { return *this; } |
435 const key_compare& get_key_comp() const { return *this; } | 471 const key_compare& get_key_comp() const { return *this; } |
436 | 472 |
437 underlying_type body_; | 473 underlying_type body_; |
438 } impl_; | 474 } impl_; |
| 475 |
| 476 // If the compare is not transparent we want to construct key_type once. |
| 477 template <typename K> |
| 478 using KeyTypeOrK = typename std:: |
| 479 conditional<IsTransparentCompare<key_compare>::value, K, key_type>::type; |
439 }; | 480 }; |
440 | 481 |
441 // ---------------------------------------------------------------------------- | 482 // ---------------------------------------------------------------------------- |
442 // Lifetime. | 483 // Lifetime. |
443 | 484 |
444 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 485 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
445 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree() = default; | 486 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree() = default; |
446 | 487 |
447 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 488 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
448 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( | 489 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( |
(...skipping 311 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
760 const_iterator position_hint, | 801 const_iterator position_hint, |
761 Args&&... args) -> iterator { | 802 Args&&... args) -> iterator { |
762 return insert(position_hint, value_type(std::forward<Args>(args)...)); | 803 return insert(position_hint, value_type(std::forward<Args>(args)...)); |
763 } | 804 } |
764 | 805 |
765 // ---------------------------------------------------------------------------- | 806 // ---------------------------------------------------------------------------- |
766 // Erase operations. | 807 // Erase operations. |
767 | 808 |
768 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 809 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
769 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( | 810 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( |
| 811 iterator position) -> iterator { |
| 812 return impl_.body_.erase(position); |
| 813 } |
| 814 |
| 815 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| 816 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( |
770 const_iterator position) -> iterator { | 817 const_iterator position) -> iterator { |
771 // We have to cast away const because of crbug.com/677044. | 818 // We have to cast away const because of crbug.com/677044. |
772 return impl_.body_.erase(const_cast_it(position)); | 819 return erase(const_cast_it(position)); |
773 } | 820 } |
774 | 821 |
775 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 822 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
776 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( | 823 template <typename K> |
777 const key_type& val) -> size_type { | 824 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase(const K& val) |
| 825 -> size_type { |
778 auto eq_range = equal_range(val); | 826 auto eq_range = equal_range(val); |
779 auto res = std::distance(eq_range.first, eq_range.second); | 827 auto res = std::distance(eq_range.first, eq_range.second); |
780 // We have to cast away const because of crbug.com/677044. | 828 // We have to cast away const because of crbug.com/677044. |
781 erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second)); | 829 erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second)); |
782 return res; | 830 return res; |
783 } | 831 } |
784 | 832 |
785 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 833 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
786 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( | 834 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase( |
787 const_iterator first, | 835 const_iterator first, |
(...skipping 14 matching lines...) Expand all Loading... |
802 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 850 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
803 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::value_comp() const | 851 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::value_comp() const |
804 -> value_compare { | 852 -> value_compare { |
805 return impl_.get_value_comp(); | 853 return impl_.get_value_comp(); |
806 } | 854 } |
807 | 855 |
808 // ---------------------------------------------------------------------------- | 856 // ---------------------------------------------------------------------------- |
809 // Search operations. | 857 // Search operations. |
810 | 858 |
811 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 859 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| 860 template <typename K> |
812 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::count( | 861 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::count( |
813 const key_type& key) const -> size_type { | 862 const K& key) const -> size_type { |
814 auto eq_range = equal_range(key); | 863 auto eq_range = equal_range(key); |
815 return std::distance(eq_range.first, eq_range.second); | 864 return std::distance(eq_range.first, eq_range.second); |
816 } | 865 } |
817 | 866 |
818 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 867 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
819 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find( | 868 template <typename K> |
820 const key_type& key) -> iterator { | 869 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find(const K& key) |
| 870 -> iterator { |
821 return const_cast_it(as_const().find(key)); | 871 return const_cast_it(as_const().find(key)); |
822 } | 872 } |
823 | 873 |
824 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 874 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| 875 template <typename K> |
825 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find( | 876 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find( |
826 const key_type& key) const -> const_iterator { | 877 const K& key) const -> const_iterator { |
827 auto eq_range = equal_range(key); | 878 auto eq_range = equal_range(key); |
828 return (eq_range.first == eq_range.second) ? end() : eq_range.first; | 879 return (eq_range.first == eq_range.second) ? end() : eq_range.first; |
829 } | 880 } |
830 | 881 |
831 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 882 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| 883 template <typename K> |
832 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( | 884 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( |
833 const key_type& key) -> std::pair<iterator, iterator> { | 885 const K& key) -> std::pair<iterator, iterator> { |
834 auto res = as_const().equal_range(key); | 886 auto res = as_const().equal_range(key); |
835 return {const_cast_it(res.first), const_cast_it(res.second)}; | 887 return {const_cast_it(res.first), const_cast_it(res.second)}; |
836 } | 888 } |
837 | 889 |
838 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 890 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| 891 template <typename K> |
839 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( | 892 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range( |
840 const key_type& key) const -> std::pair<const_iterator, const_iterator> { | 893 const K& key) const -> std::pair<const_iterator, const_iterator> { |
841 auto lower = lower_bound(key); | 894 auto lower = lower_bound(key); |
842 | 895 |
843 GetKeyFromValue extractor; | 896 GetKeyFromValue extractor; |
844 if (lower == end() || impl_.get_key_comp()(key, extractor(*lower))) | 897 if (lower == end() || impl_.get_key_comp()(key, extractor(*lower))) |
845 return {lower, lower}; | 898 return {lower, lower}; |
846 | 899 |
847 return {lower, std::next(lower)}; | 900 return {lower, std::next(lower)}; |
848 } | 901 } |
849 | 902 |
850 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 903 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| 904 template <typename K> |
851 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( | 905 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( |
852 const key_type& key) -> iterator { | 906 const K& key) -> iterator { |
853 return const_cast_it(as_const().lower_bound(key)); | 907 return const_cast_it(as_const().lower_bound(key)); |
854 } | 908 } |
855 | 909 |
856 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 910 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| 911 template <typename K> |
857 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( | 912 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound( |
858 const key_type& key) const -> const_iterator { | 913 const K& key) const -> const_iterator { |
| 914 static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value, |
| 915 "Requested type cannot be bound to the container's key_type " |
| 916 "which is required for a non-transparent compare."); |
| 917 |
| 918 const KeyTypeOrK<K>& key_ref = key; |
| 919 |
859 KeyValueCompare key_value(impl_.get_key_comp()); | 920 KeyValueCompare key_value(impl_.get_key_comp()); |
860 return std::lower_bound(begin(), end(), key, key_value); | 921 return std::lower_bound(begin(), end(), key_ref, key_value); |
861 } | 922 } |
862 | 923 |
863 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 924 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| 925 template <typename K> |
864 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( | 926 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( |
865 const key_type& key) -> iterator { | 927 const K& key) -> iterator { |
866 return const_cast_it(as_const().upper_bound(key)); | 928 return const_cast_it(as_const().upper_bound(key)); |
867 } | 929 } |
868 | 930 |
869 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 931 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
| 932 template <typename K> |
870 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( | 933 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound( |
871 const key_type& key) const -> const_iterator { | 934 const K& key) const -> const_iterator { |
| 935 static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value, |
| 936 "Requested type cannot be bound to the container's key_type " |
| 937 "which is required for a non-transparent compare."); |
| 938 |
| 939 const KeyTypeOrK<K>& key_ref = key; |
| 940 |
872 KeyValueCompare key_value(impl_.get_key_comp()); | 941 KeyValueCompare key_value(impl_.get_key_comp()); |
873 return std::upper_bound(begin(), end(), key, key_value); | 942 return std::upper_bound(begin(), end(), key_ref, key_value); |
874 } | 943 } |
875 | 944 |
876 // ---------------------------------------------------------------------------- | 945 // ---------------------------------------------------------------------------- |
877 // General operations. | 946 // General operations. |
878 | 947 |
879 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> | 948 template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
880 void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::swap( | 949 void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::swap( |
881 flat_tree& other) { | 950 flat_tree& other) { |
882 std::swap(impl_, other.impl_); | 951 std::swap(impl_, other.impl_); |
883 } | 952 } |
(...skipping 29 matching lines...) Expand all Loading... |
913 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>& | 982 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>& |
914 container, | 983 container, |
915 Predicate pred) { | 984 Predicate pred) { |
916 container.erase(std::remove_if(container.begin(), container.end(), pred), | 985 container.erase(std::remove_if(container.begin(), container.end(), pred), |
917 container.end()); | 986 container.end()); |
918 } | 987 } |
919 | 988 |
920 } // namespace base | 989 } // namespace base |
921 | 990 |
922 #endif // BASE_CONTAINERS_FLAT_TREE_H_ | 991 #endif // BASE_CONTAINERS_FLAT_TREE_H_ |
OLD | NEW |