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
28namespace Poco {
29
30
31template <class Key, class Mapped, class Container = std::list<std::pair<Key, Mapped> >, bool CaseSensitive = false >
32class 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{
41public:
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
209private:
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