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