1 /*
2 * Frozen
3 * Copyright 2016 QuarksLab
4 *
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * with the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
20 * under the License.
21 */
22
23 #ifndef FROZEN_SET_H
24 #define FROZEN_SET_H
25
26 #include "frozen/bits/algorithms.h"
27 #include "frozen/bits/basic_types.h"
28 #include "frozen/bits/constexpr_assert.h"
29 #include "frozen/bits/version.h"
30
31 #include <utility>
32
33 namespace frozen {
34
35 template <class Key, std::size_t N, class Compare = std::less<Key>> class set {
36 using container_type = bits::carray<Key, N>;
37 Compare less_than_;
38 container_type keys_;
39
40 public:
41 /* container typedefs*/
42 using key_type = Key;
43 using value_type = Key;
44 using size_type = typename container_type::size_type;
45 using difference_type = typename container_type::size_type;
46 using key_compare = Compare;
47 using value_compare = Compare;
48 using reference = typename container_type::const_reference;
49 using const_reference = reference;
50 using pointer = typename container_type::const_pointer;
51 using const_pointer = pointer;
52 using iterator = typename container_type::const_iterator;
53 using reverse_iterator = typename container_type::const_reverse_iterator;
54 using const_iterator = iterator;
55 using const_reverse_iterator = reverse_iterator;
56
57 public:
58 /* constructors */
59 constexpr set(const set &other) = default;
60
set(container_type keys,Compare const & comp)61 constexpr set(container_type keys, Compare const & comp)
62 : less_than_{comp}
63 , keys_(bits::quicksort(keys, less_than_)) {
64 }
65
set(container_type keys)66 explicit constexpr set(container_type keys)
67 : set{keys, Compare{}} {}
68
set(std::initializer_list<Key> keys,Compare const & comp)69 constexpr set(std::initializer_list<Key> keys, Compare const & comp)
70 : set{container_type{keys}, comp} {
71 constexpr_assert(keys.size() == N, "Inconsistent initializer_list size and type size argument");
72 }
73
set(std::initializer_list<Key> keys)74 constexpr set(std::initializer_list<Key> keys)
75 : set{keys, Compare{}} {}
76
77 /* capacity */
empty()78 constexpr bool empty() const { return !N; }
size()79 constexpr size_type size() const { return N; }
max_size()80 constexpr size_type max_size() const { return N; }
81
82 /* lookup */
count(Key const & key)83 constexpr std::size_t count(Key const &key) const {
84 return bits::binary_search<N>(keys_.begin(), key, less_than_);
85 }
86
find(Key const & key)87 constexpr const_iterator find(Key const &key) const {
88 const_iterator where = lower_bound(key);
89 if ((where != end()) && !less_than_(key, *where))
90 return where;
91 else
92 return end();
93 }
94
equal_range(Key const & key)95 constexpr std::pair<const_iterator, const_iterator> equal_range(Key const &key) const {
96 auto const lower = lower_bound(key);
97 if (lower == end())
98 return {lower, lower};
99 else
100 return {lower, lower + 1};
101 }
102
lower_bound(Key const & key)103 constexpr const_iterator lower_bound(Key const &key) const {
104 auto const where = bits::lower_bound<N>(keys_.begin(), key, less_than_);
105 if ((where != end()) && !less_than_(key, *where))
106 return where;
107 else
108 return end();
109 }
110
upper_bound(Key const & key)111 constexpr const_iterator upper_bound(Key const &key) const {
112 auto const where = bits::lower_bound<N>(keys_.begin(), key, less_than_);
113 if ((where != end()) && !less_than_(key, *where))
114 return where + 1;
115 else
116 return end();
117 }
118
119 /* observers */
key_comp()120 constexpr key_compare key_comp() const { return less_than_; }
value_comp()121 constexpr key_compare value_comp() const { return less_than_; }
122
123 /* iterators */
begin()124 constexpr const_iterator begin() const { return keys_.begin(); }
cbegin()125 constexpr const_iterator cbegin() const { return keys_.cbegin(); }
end()126 constexpr const_iterator end() const { return keys_.end(); }
cend()127 constexpr const_iterator cend() const { return keys_.cend(); }
128
rbegin()129 constexpr const_reverse_iterator rbegin() const { return keys_.rbegin(); }
crbegin()130 constexpr const_reverse_iterator crbegin() const { return keys_.crbegin(); }
rend()131 constexpr const_reverse_iterator rend() const { return keys_.rend(); }
crend()132 constexpr const_reverse_iterator crend() const { return keys_.crend(); }
133
134 /* comparison */
135 constexpr bool operator==(set const& rhs) const { return bits::equal(begin(), end(), rhs.begin()); }
136 constexpr bool operator!=(set const& rhs) const { return !(*this == rhs); }
137 constexpr bool operator<(set const& rhs) const { return bits::lexicographical_compare(begin(), end(), rhs.begin(), rhs.end()); }
138 constexpr bool operator<=(set const& rhs) const { return (*this < rhs) || (*this == rhs); }
139 constexpr bool operator>(set const& rhs) const { return bits::lexicographical_compare(rhs.begin(), rhs.end(), begin(), end()); }
140 constexpr bool operator>=(set const& rhs) const { return (*this > rhs) || (*this == rhs); }
141 };
142
143 template <class Key, class Compare> class set<Key, 0, Compare> {
144 using container_type = bits::carray<Key, 0>; // just for the type definitions
145 Compare less_than_;
146
147 public:
148 /* container typedefs*/
149 using key_type = Key;
150 using value_type = Key;
151 using size_type = typename container_type::size_type;
152 using difference_type = typename container_type::size_type;
153 using key_compare = Compare;
154 using value_compare = Compare;
155 using reference = typename container_type::const_reference;
156 using const_reference = reference;
157 using pointer = typename container_type::const_pointer;
158 using const_pointer = pointer;
159 using iterator = pointer;
160 using reverse_iterator = pointer;
161 using const_iterator = const_pointer;
162 using const_reverse_iterator = const_pointer;
163
164 public:
165 /* constructors */
166 constexpr set(const set &other) = default;
set(bits::carray<Key,0>,Compare const &)167 constexpr set(bits::carray<Key, 0>, Compare const &) {}
set(bits::carray<Key,0>)168 explicit constexpr set(bits::carray<Key, 0>) {}
169
set(std::initializer_list<Key>,Compare const & comp)170 constexpr set(std::initializer_list<Key>, Compare const &comp)
171 : less_than_{comp} {}
set(std::initializer_list<Key> keys)172 constexpr set(std::initializer_list<Key> keys) : set{keys, Compare{}} {}
173
174 /* capacity */
empty()175 constexpr bool empty() const { return true; }
size()176 constexpr size_type size() const { return 0; }
max_size()177 constexpr size_type max_size() const { return 0; }
178
179 /* lookup */
count(Key const &)180 constexpr std::size_t count(Key const &) const { return 0; }
181
find(Key const &)182 constexpr const_iterator find(Key const &) const { return end(); }
183
184 constexpr std::pair<const_iterator, const_iterator>
equal_range(Key const &)185 equal_range(Key const &) const { return {end(), end()}; }
186
lower_bound(Key const &)187 constexpr const_iterator lower_bound(Key const &) const { return end(); }
188
upper_bound(Key const &)189 constexpr const_iterator upper_bound(Key const &) const { return end(); }
190
191 /* observers */
key_comp()192 constexpr key_compare key_comp() const { return less_than_; }
value_comp()193 constexpr key_compare value_comp() const { return less_than_; }
194
195 /* iterators */
begin()196 constexpr const_iterator begin() const { return nullptr; }
cbegin()197 constexpr const_iterator cbegin() const { return nullptr; }
end()198 constexpr const_iterator end() const { return nullptr; }
cend()199 constexpr const_iterator cend() const { return nullptr; }
200
rbegin()201 constexpr const_reverse_iterator rbegin() const { return nullptr; }
crbegin()202 constexpr const_reverse_iterator crbegin() const { return nullptr; }
rend()203 constexpr const_reverse_iterator rend() const { return nullptr; }
crend()204 constexpr const_reverse_iterator crend() const { return nullptr; }
205 };
206
207 template <typename T>
208 constexpr auto make_set(bits::ignored_arg = {}/* for consistency with the initializer below for N = 0*/) {
209 return set<T, 0>{};
210 }
211
212 template <typename T, std::size_t N>
make_set(const T (& args)[N])213 constexpr auto make_set(const T (&args)[N]) {
214 return set<T, N>(args);
215 }
216
217
218 } // namespace frozen
219
220 #endif
221