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 }
93
94 ~OrderedMap() {
95 Clear();
96 }
97
98 void SetAllowDuplicates(bool Value) {
99 FAllowDuplicates = Value;
100 }
101
102 iterator begin() {
103 return FList.begin();
104 }
105
106 const_iterator begin() const {
107 return FList.begin();
108 }
109
110 iterator end() {
111 return FList.end();
112 }
113
114 const_iterator end() const {
115 return FList.end();
116 }
117
118 void Clear() {
119 for (typename list_type::iterator iterator =
120 FList.begin(); iterator != FList.end(); iterator++) {
121 container_type *item = *iterator;
122
123 if (item != NULL) {
124 delete item;
125 item = NULL;
126 }
127 }
128
129 FMap.clear();
130 FList.clear();
131 }
132
133 bool ContainsKey(key_type Key) {
134 bool result = false;
135
136 if (FMap.find(Key) != FMap.end()) {
137 result = true;
138 }
139
140 return result;
141 }
142
143 std::vector<key_type> GetKeys() {
144 std::vector<key_type> result;
145
146 for (typename list_type::const_iterator iterator = FList.begin();
147 iterator != FList.end(); iterator++) {
148 container_type *item = *iterator;
149 result.push_back(item->first);
150 }
151
152 return result;
153 }
154
155 void Assign(const OrderedMap<key_type, mapped_type> &Value) {
156 Clear();
157 Append(Value);
158 }
159
160 void Append(const OrderedMap<key_type, mapped_type> &Value) {
161 for (size_t index = 0; index < Value.FList.size(); index++) {
162 container_type *item = Value.FList[index];
163 Append(item->first, item->second);
164 }
165 }
166
167 void Append(key_type Key, mapped_type Value) {
168 container_type *item = new container_type(Key, Value);
169 FMap.insert(std::pair<key_type, container_type*>(Key, item));
170 FList.push_back(item);
171 }
172
173 bool RemoveByKey(key_type Key) {
174 bool result = false;
175 typename list_type::iterator iterator = FindListItem(Key);
176
177 if (iterator != FList.end()) {
178 FMap.erase(Key);
179 FList.erase(iterator);
180 result = true;
181 }
182
183 return result;
184 }
185
186 bool GetValue(key_type Key, mapped_type &Value) {
187 bool result = false;
188 container_type* item = FMap[Key];
189
190 if (item != NULL) {
191 Value = item->second;
192 result = true;
193 }
194
195 return result;
196 }
197
198 bool SetValue(key_type Key, mapped_type &Value) {
199 bool result = false;
200
201 if ((FAllowDuplicates == false) && (ContainsKey(Key) == true)) {
202 container_type *item = FMap[Key];
203
204 if (item != NULL) {
205 item->second = Value;
206 result = true;
207 }
208 }
209 else {
210 Append(Key, Value);
211 result = true;
212 }
213
214 return result;
215 }
216
217 mapped_type &operator[](key_type Key) {
218 container_type* item = FMap[Key];
219 assert(item != NULL);
220
221 if (item != NULL) {
222 return item->second;
223 }
224
225 throw std::invalid_argument("Key not found");
226 }
227
228 OrderedMap& operator= (OrderedMap &Value) {
229 Clear();
230 Append(Value);
231 return *this;
232 }
233
234 size_t Count() {
235 return FList.size();
236 }
237 };
238
239 #endif // ORDEREDMAP_H