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 #include <map>
30 #include <vector>
31 #include <assert.h>
32 #include <stdexcept>
33
34 #include <iostream>
35
36 template <typename _T1, typename _T2>
37 struct JPPair
38 {
39 typedef _T1 first_type;
40 typedef _T2 second_type;
41
42 first_type first;
43 second_type second;
44
45 JPPair(first_type Value1, second_type Value2) {
46 first = Value1;
47 second = Value2;
48 }
49 };
50
51
52 template <typename TKey, typename TValue>
53 class OrderedMap {
54 public:
55 typedef TKey key_type;
56 typedef TValue mapped_type;
57 typedef JPPair<key_type, mapped_type> container_type;
58 typedef typename std::vector<container_type*>::iterator iterator;
59 typedef typename std::vector<container_type*>::const_iterator const_iterator;
60
61 private:
62 typedef std::map<key_type, container_type*> map_type;
63 typedef std::vector<container_type*> list_type;
64
65 map_type FMap;
66 list_type FList;
67 bool FAllowDuplicates;
68
69 typename list_type::iterator FindListItem(const key_type Key) {
70 typename list_type::iterator result = FList.end();
71
72 for (typename list_type::iterator iterator =
73 FList.begin(); iterator != FList.end(); iterator++) {
74 container_type *item = *iterator;
75
76 if (item->first == Key) {
77 result = iterator;
78 break;
79 }
80 }
81
82 return result;
83 }
84
85 public:
86 OrderedMap() {
87 FAllowDuplicates = false;
88 }
89
90 OrderedMap(const OrderedMap<key_type, mapped_type> &Value) {
91 Append(Value);
92 FAllowDuplicates = Value.GetAllowDuplicates();
93 }
94
95 ~OrderedMap() {
96 Clear();
97 }
98
99 void SetAllowDuplicates(bool Value) {
100 FAllowDuplicates = Value;
101 }
102
103 bool GetAllowDuplicates() const {
104 return FAllowDuplicates;
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 bool GetKey(int index, key_type &Value) {
223 if (index < 0 || index >= (int)FList.size()) {
224 return false;
225 }
226 container_type *item = FList.at(index);
227 if (item != NULL) {
228 Value = item->first;
229 return true;
230 }
231
232 return false;
233 }
234
235 bool GetValue(int index, mapped_type &Value) {
236 if (index < 0 || index >= (int)FList.size()) {
237 return false;
238 }
239 container_type *item = FList.at(index);
240 if (item != NULL) {
241 Value = item->second;
242 return true;
243 }
244
245 return false;
246 }
247
248 mapped_type &operator[](key_type Key) {
249 container_type* item = FMap[Key];
250 assert(item != NULL);
251
252 if (item != NULL) {
253 return item->second;
254 }
255
256 throw std::invalid_argument("Key not found");
257 }
258
259 OrderedMap& operator= (OrderedMap &Value) {
260 Clear();
261 FAllowDuplicates = Value.GetAllowDuplicates();
262 Append(Value);
263 return *this;
264 }
265
266 size_t Count() {
267 return FList.size();
268 }
269 };
270
271 #endif // ORDEREDMAP_H