1 | #ifndef SASS_ORDERED_MAP_H |
2 | #define SASS_ORDERED_MAP_H |
3 | |
4 | namespace Sass { |
5 | |
6 | // ########################################################################## |
7 | // Very simple and limited container for insert ordered hash map. |
8 | // Piggy-back implementation on std::unordered_map and sass::vector |
9 | // ########################################################################## |
10 | template< |
11 | class Key, |
12 | class T, |
13 | class Hash = std::hash<Key>, |
14 | class KeyEqual = std::equal_to<Key>, |
15 | class Allocator = std::allocator<std::pair<const Key, T>> |
16 | > |
17 | class ordered_map { |
18 | |
19 | private: |
20 | |
21 | using map_type = typename std::unordered_map< Key, T, Hash, KeyEqual, Allocator>; |
22 | using map_iterator = typename std::unordered_map< Key, T, Hash, KeyEqual, Allocator>::iterator; |
23 | using map_const_iterator = typename std::unordered_map< Key, T, Hash, KeyEqual, Allocator>::const_iterator; |
24 | |
25 | // The main unordered map |
26 | map_type _map; |
27 | |
28 | // Keep insertion order |
29 | sass::vector<Key> _keys; |
30 | sass::vector<T> _values; |
31 | |
32 | const KeyEqual _keyEqual; |
33 | |
34 | public: |
35 | |
36 | ordered_map() : |
37 | _keyEqual(KeyEqual()) |
38 | { |
39 | } |
40 | |
41 | ordered_map& operator= (const ordered_map& other) { |
42 | _map = other._map; |
43 | _keys = other._keys; |
44 | _values = other._values; |
45 | return *this; |
46 | } |
47 | |
48 | std::pair<Key, T> front() { |
49 | return std::make_pair( |
50 | _keys.front(), |
51 | _values.front() |
52 | ); |
53 | } |
54 | |
55 | bool empty() const { |
56 | return _keys.empty(); |
57 | } |
58 | |
59 | void insert(const Key& key, const T& val) { |
60 | if (!hasKey(key)) { |
61 | _values.push_back(val); |
62 | _keys.push_back(key); |
63 | } |
64 | _map[key] = val; |
65 | } |
66 | |
67 | bool hasKey(const Key& key) const { |
68 | return _map.find(key) != _map.end(); |
69 | } |
70 | |
71 | bool erase(const Key& key) { |
72 | _map.erase(key); |
73 | // find the position in the array |
74 | for (size_t i = 0; i < _keys.size(); i += 1) { |
75 | if (_keyEqual(key, _keys[i])) { |
76 | _keys.erase(_keys.begin() + i); |
77 | _values.erase(_values.begin() + i); |
78 | return true; |
79 | } |
80 | } |
81 | return false; |
82 | } |
83 | |
84 | const sass::vector<Key>& keys() const { return _keys; } |
85 | const sass::vector<T>& values() const { return _values; } |
86 | |
87 | const T& get(const Key& key) { |
88 | if (hasKey(key)) { |
89 | return _map[key]; |
90 | } |
91 | throw std::runtime_error("Key does not exist" ); |
92 | } |
93 | |
94 | using iterator = typename sass::vector<Key>::iterator; |
95 | using const_iterator = typename sass::vector<Key>::const_iterator; |
96 | using reverse_iterator = typename sass::vector<Key>::reverse_iterator; |
97 | using const_reverse_iterator = typename sass::vector<Key>::const_reverse_iterator; |
98 | |
99 | typename sass::vector<Key>::iterator end() { return _keys.end(); } |
100 | typename sass::vector<Key>::iterator begin() { return _keys.begin(); } |
101 | typename sass::vector<Key>::reverse_iterator rend() { return _keys.rend(); } |
102 | typename sass::vector<Key>::reverse_iterator rbegin() { return _keys.rbegin(); } |
103 | typename sass::vector<Key>::const_iterator end() const { return _keys.end(); } |
104 | typename sass::vector<Key>::const_iterator begin() const { return _keys.begin(); } |
105 | typename sass::vector<Key>::const_reverse_iterator rend() const { return _keys.rend(); } |
106 | typename sass::vector<Key>::const_reverse_iterator rbegin() const { return _keys.rbegin(); } |
107 | |
108 | }; |
109 | |
110 | } |
111 | |
112 | #endif |
113 | |