]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2005, 2006, 2007, 2009 Free Software Foundation, Inc. |
4569a895 AT |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the terms | |
7 | // of the GNU General Public License as published by the Free Software | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
9 | // version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License | |
748086b7 JJ |
17 | // along with this library; see the file COPYING3. If not see |
18 | // <http://www.gnu.org/licenses/>. | |
4569a895 | 19 | |
4569a895 AT |
20 | |
21 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
22 | ||
23 | // Permission to use, copy, modify, sell, and distribute this software | |
24 | // is hereby granted without fee, provided that the above copyright | |
25 | // notice appears in all copies, and that both that copyright notice | |
26 | // and this permission notice appear in supporting documentation. None | |
27 | // of the above authors, nor IBM Haifa Research Laboratories, make any | |
28 | // representation about the suitability of this software for any | |
29 | // purpose. It is provided "as is" without express or implied | |
30 | // warranty. | |
31 | ||
32 | /** | |
33 | * @file native_hash_multimap.hpp | |
0c3de900 | 34 | * Contains an adapter to TR1 unordered containers. |
4569a895 AT |
35 | */ |
36 | ||
37 | #ifndef PB_DS_NATIVE_HASH_MULTIMAP_HPP | |
38 | #define PB_DS_NATIVE_HASH_MULTIMAP_HPP | |
39 | ||
d7f245b1 | 40 | #include <string> |
0c3de900 | 41 | #include <tr1/unordered_map> |
d7f245b1 | 42 | #include <ext/pb_ds/detail/type_utils.hpp> |
4569a895 | 43 | #include <ext/pb_ds/detail/standard_policies.hpp> |
2e3f9c21 | 44 | #include <native_type/native_hash_tag.hpp> |
4569a895 | 45 | #include <io/xml.hpp> |
4569a895 | 46 | |
5e11f978 | 47 | namespace __gnu_pbds |
4569a895 | 48 | { |
4569a895 AT |
49 | namespace test |
50 | { | |
d7f245b1 | 51 | #define PB_DS_BASE_C_DEC \ |
a345e45d | 52 | std::tr1::unordered_multimap<Key, Data, Hash_Fn, Eq_Fn, _Alloc> |
4569a895 AT |
53 | |
54 | template<typename Key, | |
55 | typename Data, | |
56 | size_t Init_Size = 8, | |
0c3de900 | 57 | class Hash_Fn = typename __gnu_pbds::detail::default_hash_fn<Key>::type, |
d7f245b1 BK |
58 | class Eq_Fn = std::equal_to<Key>, |
59 | class Less_Fn = std::less<Key>, | |
a345e45d | 60 | typename _Alloc = std::allocator<char> > |
4569a895 AT |
61 | class native_hash_multimap : public PB_DS_BASE_C_DEC |
62 | { | |
63 | private: | |
0c3de900 BK |
64 | typedef PB_DS_BASE_C_DEC base_type; |
65 | typedef std::pair<Key, Data> pair_type; | |
4569a895 AT |
66 | |
67 | public: | |
0c3de900 | 68 | typedef native_hash_tag container_category; |
a345e45d | 69 | typedef _Alloc allocator; |
0c3de900 | 70 | typedef typename base_type::iterator iterator; |
4569a895 AT |
71 | typedef typename base_type::const_iterator const_iterator; |
72 | ||
73 | typedef | |
2e3f9c21 | 74 | typename allocator::template rebind<pair_type>::other::const_reference |
4569a895 AT |
75 | const_reference; |
76 | ||
d7f245b1 BK |
77 | native_hash_multimap() : base_type(Init_Size) |
78 | { } | |
79 | ||
80 | template<typename It> | |
81 | native_hash_multimap(It f, It l) : base_type(f, l) | |
82 | { } | |
4569a895 AT |
83 | |
84 | inline void | |
0c3de900 | 85 | insert(const_reference r_val) |
4569a895 | 86 | { |
d7f245b1 | 87 | typedef std::pair<iterator, iterator> eq_range_t; |
4569a895 AT |
88 | eq_range_t f = base_type::equal_range(r_val.first); |
89 | ||
d7f245b1 | 90 | iterator it = f.first; |
4569a895 AT |
91 | while (it != f.second) |
92 | { | |
93 | if (it->second == r_val.second) | |
94 | return; | |
4569a895 AT |
95 | ++it; |
96 | } | |
4569a895 AT |
97 | base_type::insert(r_val); |
98 | } | |
99 | ||
100 | inline iterator | |
101 | find(const_reference r_val) | |
102 | { | |
d7f245b1 | 103 | typedef std::pair<iterator, iterator> eq_range_t; |
4569a895 AT |
104 | eq_range_t f = base_type::equal_range(r_val.first); |
105 | ||
d7f245b1 | 106 | iterator it = f.first; |
4569a895 AT |
107 | while (it != f.second) |
108 | { | |
109 | if (it->second == r_val.second) | |
110 | return it; | |
4569a895 AT |
111 | ++it; |
112 | } | |
4569a895 AT |
113 | return base_type::end(); |
114 | } | |
115 | ||
116 | inline const_iterator | |
117 | find(const_reference r_val) const | |
118 | { | |
d7f245b1 | 119 | typedef std::pair<const_iterator, const_iterator> eq_range_t; |
4569a895 AT |
120 | eq_range_t f = base_type::equal_range(r_val.first); |
121 | ||
d7f245b1 | 122 | const_iterator it = f.first; |
4569a895 AT |
123 | while (it != f.second) |
124 | { | |
125 | if (it->second == r_val.second) | |
126 | return it; | |
4569a895 AT |
127 | ++it; |
128 | } | |
4569a895 AT |
129 | return base_type::end(); |
130 | } | |
131 | ||
4569a895 AT |
132 | static std::string |
133 | name() | |
d7f245b1 | 134 | { return std::string("n_hash_mmap"); } |
4569a895 AT |
135 | |
136 | static std::string | |
137 | desc() | |
0c3de900 | 138 | { return make_xml_tag("type", "value", "__gnucxx_hash_multimap"); } |
4569a895 AT |
139 | }; |
140 | ||
4569a895 AT |
141 | #undef PB_DS_BASE_C_DEC |
142 | ||
4569a895 | 143 | } // namespace test |
5e11f978 | 144 | } // namespace __gnu_pbds |
4569a895 | 145 | |
d7f245b1 | 146 | #endif |