1 | // |
2 | // ListMap.h |
3 | // |
4 | // Library: Foundation |
5 | // Package: Hashing |
6 | // Module: ListMap |
7 | // |
8 | // Definition of the ListMap class. |
9 | // |
10 | // Copyright (c) 2006, Applied Informatics Software Engineering GmbH. |
11 | // and Contributors. |
12 | // |
13 | // SPDX-License-Identifier: BSL-1.0 |
14 | // |
15 | |
16 | |
17 | #ifndef Foundation_ListMap_INCLUDED |
18 | #define Foundation_ListMap_INCLUDED |
19 | |
20 | |
21 | #include "Poco/Foundation.h" |
22 | #include "Poco/String.h" |
23 | #include "Poco/Exception.h" |
24 | #include <list> |
25 | #include <utility> |
26 | |
27 | |
28 | namespace Poco { |
29 | |
30 | |
31 | template <class Key, class Mapped, class Container = std::list<std::pair<Key, Mapped> >, bool CaseSensitive = false > |
32 | class ListMap |
33 | /// This class implements a multimap in terms of a sequential container. |
34 | /// The use for this type of associative container is wherever automatic |
35 | /// ordering of elements is not desirable. Naturally, this container will |
36 | /// have inferior data retrieval performance and it is not recommended for |
37 | /// use with large datasets. The main purpose within POCO is for Internet |
38 | /// messages (email message, http headers etc), to prevent automatic |
39 | /// header entry reordering. |
40 | { |
41 | public: |
42 | typedef Key KeyType; |
43 | typedef Mapped MappedType; |
44 | typedef Mapped& Reference; |
45 | typedef const Mapped& ConstReference; |
46 | typedef Mapped* Pointer; |
47 | typedef const Mapped* ConstPointer; |
48 | |
49 | typedef typename Container::value_type ValueType; |
50 | typedef typename Container::size_type SizeType; |
51 | typedef typename Container::iterator Iterator; |
52 | typedef typename Container::const_iterator ConstIterator; |
53 | |
54 | ListMap() |
55 | /// Creates an empty ListMap. |
56 | { |
57 | } |
58 | |
59 | ListMap(std::size_t initialReserve): |
60 | _list(initialReserve) |
61 | /// Creates the ListMap with room for initialReserve entries. |
62 | { |
63 | } |
64 | |
65 | ListMap& operator = (const ListMap& map) |
66 | /// Assigns another ListMap. |
67 | { |
68 | ListMap tmp(map); |
69 | swap(tmp); |
70 | return *this; |
71 | } |
72 | |
73 | void swap(ListMap& map) |
74 | /// Swaps the ListMap with another one. |
75 | { |
76 | _list.swap(map._list); |
77 | } |
78 | |
79 | ConstIterator begin() const |
80 | /// Returns the beginning of the map. |
81 | { |
82 | return _list.begin(); |
83 | } |
84 | |
85 | ConstIterator end() const |
86 | /// Returns the end of the map. |
87 | { |
88 | return _list.end(); |
89 | } |
90 | |
91 | Iterator begin() |
92 | /// Returns the beginning of the map. |
93 | { |
94 | return _list.begin(); |
95 | } |
96 | |
97 | Iterator end() |
98 | /// Returns the end of the map. |
99 | { |
100 | return _list.end(); |
101 | } |
102 | |
103 | ConstIterator find(const KeyType& key) const |
104 | /// Finds the first occurrence of the key and |
105 | /// returns iterator pointing to the found entry |
106 | /// or iterator pointing to the end if entry is |
107 | /// not found. |
108 | { |
109 | typename Container::const_iterator it = _list.begin(); |
110 | typename Container::const_iterator end = _list.end(); |
111 | for(; it != end; ++it) |
112 | { |
113 | if (isEqual(it->first, key)) return it; |
114 | } |
115 | return end; |
116 | } |
117 | |
118 | Iterator find(const KeyType& key) |
119 | /// Finds the first occurrence of the key and |
120 | /// returns iterator pointing to the found entry |
121 | /// or iterator pointing to the end if entry is |
122 | /// not found. |
123 | { |
124 | typename Container::iterator it = _list.begin(); |
125 | typename Container::iterator end = _list.end(); |
126 | for(; it != end; ++it) |
127 | { |
128 | if (isEqual(it->first, key)) return it; |
129 | } |
130 | return end; |
131 | } |
132 | |
133 | Iterator insert(const ValueType& val) |
134 | /// Inserts the value into the map. If one or more values |
135 | /// already exist, new value is inserted at the end of the |
136 | /// block. Thus, all the equal value entries are located |
137 | /// sequentially at all times. |
138 | /// Returns iterator pointing to the newly inserted value |
139 | { |
140 | Iterator it = find(val.first); |
141 | while (it != _list.end() && isEqual(it->first, val.first)) ++it; |
142 | return _list.insert(it, val); |
143 | } |
144 | |
145 | void erase(Iterator it) |
146 | { |
147 | _list.erase(it); |
148 | } |
149 | |
150 | SizeType erase(const KeyType& key) |
151 | { |
152 | SizeType count = 0; |
153 | Iterator it = find(key); |
154 | bool removed = false; |
155 | while (it != _list.end()) |
156 | { |
157 | if (isEqual(it->first, key)) |
158 | { |
159 | ++count; |
160 | it = _list.erase(it); |
161 | removed = true; |
162 | } |
163 | else |
164 | { |
165 | if (removed) return count; |
166 | ++it; |
167 | } |
168 | } |
169 | return count; |
170 | } |
171 | |
172 | void clear() |
173 | { |
174 | _list.clear(); |
175 | } |
176 | |
177 | std::size_t size() const |
178 | { |
179 | return _list.size(); |
180 | } |
181 | |
182 | bool empty() const |
183 | { |
184 | return _list.empty(); |
185 | } |
186 | |
187 | ConstReference operator [] (const KeyType& key) const |
188 | { |
189 | ConstIterator it = find(key); |
190 | if (it != _list.end()) |
191 | return it->second; |
192 | else |
193 | throw NotFoundException(); |
194 | } |
195 | |
196 | Reference operator [] (const KeyType& key) |
197 | { |
198 | Iterator it = find(key); |
199 | if (it != _list.end()) |
200 | return it->second; |
201 | else |
202 | { |
203 | ValueType value(key, Mapped()); |
204 | Iterator it = insert(value); |
205 | return it->second; |
206 | } |
207 | } |
208 | |
209 | private: |
210 | template <typename T1, typename T2> |
211 | bool isEqual(T1 val1, T2 val2) const |
212 | { |
213 | return val1 == val2; |
214 | } |
215 | |
216 | bool isEqual(const std::string& s1, const std::string& s2) const |
217 | { |
218 | if (!CaseSensitive) |
219 | return Poco::icompare(s1, s2) == 0; |
220 | else |
221 | return s1 == s2; |
222 | } |
223 | |
224 | bool isEqual(const std::string& s1, const char* s2) const |
225 | { |
226 | return isEqual(s1, std::string(s2)); |
227 | } |
228 | |
229 | bool isEqual(const char* s1, const std::string& s2) const |
230 | { |
231 | return isEqual(std::string(s1), s2); |
232 | } |
233 | |
234 | bool isEqual(const char* s1, const char* s2) const |
235 | { |
236 | return isEqual(std::string(s1), std::string(s2)); |
237 | } |
238 | |
239 | Container _list; |
240 | }; |
241 | |
242 | |
243 | } // namespace Poco |
244 | |
245 | |
246 | #endif // Foundation_ListMap_INCLUDED |
247 | |