1 /*
2 * Copyright (c) 2015, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 #ifndef ORDEREDMAP_H
27 #define ORDEREDMAP_H
28
29 #ifdef WINDOWS
30 #pragma warning(disable:4522)
31 #endif
32
33 #include <map>
34 #include <vector>
35 #include <assert.h>
36 #include <stdexcept>
37
38 #include <iostream>
39
40
41 template <typename _T1, typename _T2>
42 struct pair
43 {
44 typedef _T1 first_type;
45 typedef _T2 second_type;
46
47 first_type first;
48 second_type second;
49
50 pair(first_type Value1, second_type Value2) {
51 first = Value1;
52 second = Value2;
53 }
54 };
55
56
57 template <typename TKey, typename TValue>
58 class OrderedMap {
59 public:
60 typedef TKey key_type;
61 typedef TValue mapped_type;
62 typedef pair<key_type, mapped_type> container_type;
63 typedef typename std::vector<container_type*>::iterator iterator;
64 typedef typename std::vector<container_type*>::const_iterator const_iterator;
65
66 private:
67 typedef std::map<key_type, container_type*> map_type;
68 typedef std::vector<container_type*> list_type;
69
70 map_type FMap;
71 list_type FList;
72 bool FAllowDuplicates;
73
74 typename list_type::iterator FindListItem(const key_type Key) {
75 typename list_type::iterator result = FList.end();
76
77 for (typename list_type::iterator iterator =
78 FList.begin(); iterator != FList.end(); iterator++) {
79 container_type *item = *iterator;
80
81 if (item->first == Key) {
82 result = iterator;
83 break;
84 }
85 }
86
87 return result;
88 }
89
90 public:
91 OrderedMap() {
92 FAllowDuplicates = false;
93 }
94
95 OrderedMap(const OrderedMap<key_type, mapped_type> &Value) {
96 Append(Value);
97 }
98
99 ~OrderedMap() {
100 Clear();
101 }
102
103 void SetAllowDuplicates(bool Value) {
104 FAllowDuplicates = Value;
105 }
106
107 iterator begin() {
108 return FList.begin();
109 }
110
111 const_iterator begin() const {
112 return FList.begin();
113 }
114
115 iterator end() {
116 return FList.end();
117 }
118
119 const_iterator end() const {
120 return FList.end();
121 }
122
123 void Clear() {
124 for (typename list_type::iterator iterator =
125 FList.begin(); iterator != FList.end(); iterator++) {
126 container_type *item = *iterator;
127
128 if (item != NULL) {
129 delete item;
130 item = NULL;
131 }
132 }
133
134 FMap.clear();
135 FList.clear();
136 }
137
138 bool ContainsKey(key_type Key) {
139 bool result = false;
140
141 if (FMap.find(Key) != FMap.end()) {
142 result = true;
143 }
144
145 return result;
146 }
147
148 std::vector<key_type> GetKeys() {
149 std::vector<key_type> result;
150
151 for (typename list_type::const_iterator iterator = FList.begin();
152 iterator != FList.end(); iterator++) {
153 container_type *item = *iterator;
154 result.push_back(item->first);
155 }
156
157 return result;
158 }
159
160 void Assign(const OrderedMap<key_type, mapped_type> &Value) {
161 Clear();
162 Append(Value);
163 }
164
165 void Append(const OrderedMap<key_type, mapped_type> &Value) {
166 for (size_t index = 0; index < Value.FList.size(); index++) {
167 container_type *item = Value.FList[index];
168 Append(item->first, item->second);
169 }
170 }
171
172 void Append(key_type Key, mapped_type Value) {
173 container_type *item = new container_type(Key, Value);
174 FMap.insert(std::pair<key_type, container_type*>(Key, item));
175 FList.push_back(item);
176 }
177
178 bool RemoveByKey(key_type Key) {
179 bool result = false;
180 typename list_type::iterator iterator = FindListItem(Key);
181
182 if (iterator != FList.end()) {
183 FMap.erase(Key);
184 FList.erase(iterator);
185 result = true;
186 }
187
188 return result;
189 }
190
191 bool GetValue(key_type Key, mapped_type &Value) {
192 bool result = false;
193 container_type* item = FMap[Key];
194
195 if (item != NULL) {
196 Value = item->second;
197 result = true;
198 }
199
200 return result;
201 }
202
203 bool SetValue(key_type Key, mapped_type &Value) {
204 bool result = false;
205
206 if ((FAllowDuplicates == false) && (ContainsKey(Key) == true)) {
207 container_type *item = FMap[Key];
208
209 if (item != NULL) {
210 item->second = Value;
211 result = true;
212 }
213 }
214 else {
215 Append(Key, Value);
216 result = true;
217 }
218
219 return result;
220 }
221
222 mapped_type &operator[](key_type Key) {
223 container_type* item = FMap[Key];
224 assert(item != NULL);
225
226 if (item != NULL) {
227 return item->second;
228 }
229
230 throw std::invalid_argument("Key not found");
231 }
232
233 OrderedMap& operator= (OrderedMap &Value) {
234 Clear();
235 Append(Value);
236 return *this;
237 }
238
239 OrderedMap& operator= (const OrderedMap &Value) {
240 Clear();
241 Append(Value);
242 return *this;
243 }
244
245 size_t Count() {
246 return FList.size();
247 }
248 };
249
250 #endif // ORDEREDMAP_H