1//
2// immer: immutable data structures for C++
3// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
4//
5// This software is distributed under the Boost Software License, Version 1.0.
6// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
7//
8
9#pragma once
10
11#include <immer/memory_policy.hpp>
12#include <immer/detail/hamts/champ.hpp>
13#include <immer/detail/hamts/champ_iterator.hpp>
14
15#include <functional>
16
17namespace immer {
18
19template <typename T,
20 typename Hash,
21 typename Equal,
22 typename MemoryPolicy,
23 detail::hamts::bits_t B>
24class set_transient;
25
26/*!
27 * Immutable set representing an unordered bag of values.
28 *
29 * @tparam T The type of the values to be stored in the container.
30 * @tparam Hash The type of a function object capable of hashing
31 * values of type `T`.
32 * @tparam Equal The type of a function object capable of comparing
33 * values of type `T`.
34 * @tparam MemoryPolicy Memory management policy. See @ref
35 * memory_policy.
36 *
37 * @rst
38 *
39 * This container provides a good trade-off between cache locality,
40 * membership checks, update performance and structural sharing. It
41 * does so by storing the data in contiguous chunks of :math:`2^{B}`
42 * elements. When storing big objects, the size of these contiguous
43 * chunks can become too big, damaging performance. If this is
44 * measured to be problematic for a specific use-case, it can be
45 * solved by using a `immer::box` to wrap the type `T`.
46 *
47 * **Example**
48 * .. literalinclude:: ../example/set/intro.cpp
49 * :language: c++
50 * :start-after: intro/start
51 * :end-before: intro/end
52 *
53 * @endrst
54 *
55 */
56template <typename T,
57 typename Hash = std::hash<T>,
58 typename Equal = std::equal_to<T>,
59 typename MemoryPolicy = default_memory_policy,
60 detail::hamts::bits_t B = default_bits>
61class set
62{
63 using impl_t = detail::hamts::champ<T, Hash, Equal, MemoryPolicy, B>;
64
65public:
66 using key_type = T;
67 using value_type = T;
68 using size_type = detail::hamts::size_t;
69 using diference_type = std::ptrdiff_t;
70 using hasher = Hash;
71 using key_equal = Equal;
72 using reference = const T&;
73 using const_reference = const T&;
74
75 using iterator = detail::hamts::champ_iterator<T, Hash, Equal,
76 MemoryPolicy, B>;
77 using const_iterator = iterator;
78
79 using transient_type = set_transient<T, Hash, Equal, MemoryPolicy, B>;
80
81 /*!
82 * Default constructor. It creates a set of `size() == 0`. It
83 * does not allocate memory and its complexity is @f$ O(1) @f$.
84 */
85 set() = default;
86
87 /*!
88 * Returns an iterator pointing at the first element of the
89 * collection. It does not allocate memory and its complexity is
90 * @f$ O(1) @f$.
91 */
92 IMMER_NODISCARD iterator begin() const { return {impl_}; }
93
94 /*!
95 * Returns an iterator pointing just after the last element of the
96 * collection. It does not allocate and its complexity is @f$ O(1) @f$.
97 */
98 IMMER_NODISCARD iterator end() const { return {impl_, typename iterator::end_t{}}; }
99
100 /*!
101 * Returns the number of elements in the container. It does
102 * not allocate memory and its complexity is @f$ O(1) @f$.
103 */
104 IMMER_NODISCARD size_type size() const { return impl_.size; }
105
106 /*!
107 * Returns `true` if there are no elements in the container. It
108 * does not allocate memory and its complexity is @f$ O(1) @f$.
109 */
110 IMMER_NODISCARD bool empty() const { return impl_.size == 0; }
111
112 /*!
113 * Returns `1` when `value` is contained in the set or `0`
114 * otherwise. It won't allocate memory and its complexity is
115 * *effectively* @f$ O(1) @f$.
116 */
117 IMMER_NODISCARD size_type count(const T& value) const
118 { return impl_.template get<detail::constantly<size_type, 1>,
119 detail::constantly<size_type, 0>>(value); }
120
121 /*!
122 * Returns whether the sets are equal.
123 */
124 IMMER_NODISCARD bool operator==(const set& other) const
125 { return impl_.equals(other.impl_); }
126 IMMER_NODISCARD bool operator!=(const set& other) const
127 { return !(*this == other); }
128
129 /*!
130 * Returns a set containing `value`. If the `value` is already in
131 * the set, it returns the same set. It may allocate memory and
132 * its complexity is *effectively* @f$ O(1) @f$.
133 */
134 IMMER_NODISCARD set insert(T value) const
135 { return impl_.add(std::move(value)); }
136
137 /*!
138 * Returns a set without `value`. If the `value` is not in the
139 * set it returns the same set. It may allocate memory and its
140 * complexity is *effectively* @f$ O(1) @f$.
141 */
142 IMMER_NODISCARD set erase(const T& value) const
143 { return impl_.sub(value); }
144
145 /*!
146 * Returns an @a transient form of this container, a
147 * `immer::set_transient`.
148 */
149 IMMER_NODISCARD transient_type transient() const&
150 { return transient_type{ impl_ }; }
151 IMMER_NODISCARD transient_type transient() &&
152 { return transient_type{ std::move(impl_) }; }
153
154 // Semi-private
155 const impl_t& impl() const { return impl_; }
156
157private:
158 friend transient_type;
159
160 set(impl_t impl)
161 : impl_(std::move(impl))
162 {}
163
164 impl_t impl_ = impl_t::empty();
165};
166
167} // namespace immer
168