1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

//! Module for the trait to define a `Key`.

#[cfg(feature = "hashbrown")]
use crate::map::storage::HashbrownMapStorage;
use crate::map::storage::{BooleanMapStorage, MapStorage, OptionMapStorage, SingletonMapStorage};
#[cfg(feature = "hashbrown")]
use crate::set::storage::HashbrownSetStorage;
use crate::set::storage::{BooleanSetStorage, OptionSetStorage, SetStorage, SingletonSetStorage};

/// The trait for a key that can be used to store values in a
/// [`Map`][crate::Set] or [`Set`][crate::Set].
///
/// This can be derived automatically from enums. The following is a *simple*
/// key which has no nested keys:
///
/// ```
/// use fixed_map::Key;
///
/// #[derive(Clone, Copy, Key)]
/// enum MyKey {
///     First,
///     Second,
/// }
/// ```
///
/// *Composite keys* are when keys structurally includes other keys. They have
/// slightly worse performance than simple keys because they can't be simply
/// arranged as arrays internally. `bool` below here implements [`Key`] and
/// using it in one key constructs a composite key. It's a simple form of key
/// since it can only inhabit two values - `true` or `false`. `Option<K>` can
/// also be used as a composite key:
///
/// ```
/// use fixed_map::Key;
///
/// #[derive(Clone, Copy, Key)]
/// enum MyKey {
///     First(bool),
///     Second(Option<bool>),
/// }
/// ```
///
/// Some composite keys require dynamic storage since they can inhabit a large
/// number of values, and preferrably should be avoided in favor of using a
/// `HashMap` directly. But if you absolutely have to you can enable the `map`
/// feature:
///
/// ```
/// use fixed_map::Key;
///
/// #[derive(Clone, Copy, Key)]
/// enum MyKey {
///     # #[cfg(feature = "hashbrown")]
///     First(u32),
///     Second,
/// }
/// ```
///
/// ## Ordering
///
/// Keys provide their own ordering semantics instead of relying on the
/// [`PartialOrd`] and [`Ord`] traits.
///
/// Therefore keys when stored in a collection such as [`Map`] and [`Set`] are
/// always ordered in *declaration order*. This allows those containers
/// themselves to be ordered if the underlying key supports, it similarly to how
/// [`BTreeMap`] and [`BTreeSet`] works.
///
/// ```
/// use fixed_map::{Key, Set};
///
/// #[derive(Clone, Copy, Key)]
/// enum MyKey {
///     First,
///     Second,
///     Third,
/// }
///
/// let mut a = Set::new();
/// a.insert(MyKey::First);
///
/// let mut b = Set::new();
/// b.insert(MyKey::Third);
///
/// let mut c = Set::new();
/// c.insert(MyKey::First);
/// c.insert(MyKey::Third);
///
/// assert!(a < b);
/// assert!(c < b);
/// assert!(a < c);
/// ```
///
/// The same example with [`BTreeSet`]:
///
/// ```
/// use std::collections::BTreeSet;
///
/// #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
/// enum MyKey {
///     First,
///     Second,
///     Third,
/// }
///
/// let mut a = BTreeSet::new();
/// a.insert(MyKey::First);
///
/// let mut b = BTreeSet::new();
/// b.insert(MyKey::Third);
///
/// let mut c = BTreeSet::new();
/// c.insert(MyKey::First);
/// c.insert(MyKey::Third);
///
/// assert!(a < b);
/// assert!(c < b);
/// assert!(a < c);
/// ```
///
/// [`BTreeMap`]: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
/// [`BTreeSet`]: https://doc.rust-lang.org/std/collections/struct.BTreeSet.html
/// [`Map`]: crate::Map
/// [`Set`]: crate::Set
pub trait Key: Copy {
    /// The [`Map`][crate::Map] storage implementation to use for the key
    /// implementing this trait.
    type MapStorage<V>: MapStorage<Self, V>;

    /// The [`Set`][crate::Set] storage implementation to use for the key
    /// implementing this trait.
    type SetStorage: SetStorage<Self>;
}

impl Key for bool {
    type MapStorage<V> = BooleanMapStorage<V>;
    type SetStorage = BooleanSetStorage;
}

impl<K> Key for Option<K>
where
    K: Key,
{
    type MapStorage<V> = OptionMapStorage<K, V>;
    type SetStorage = OptionSetStorage<K>;
}

macro_rules! map_key {
    ($ty:ty) => {
        #[cfg(feature = "hashbrown")]
        impl Key for $ty {
            type MapStorage<V> = HashbrownMapStorage<$ty, V>;
            type SetStorage = HashbrownSetStorage<$ty>;
        }
    };
}

macro_rules! singleton_key {
    ($ty:ty) => {
        impl Key for $ty {
            type MapStorage<V> = SingletonMapStorage<V>;
            type SetStorage = SingletonSetStorage;
        }
    };
}

map_key!(char);
map_key!(u8);
map_key!(u32);
map_key!(u64);
map_key!(u128);
map_key!(usize);
map_key!(i8);
map_key!(i32);
map_key!(i64);
map_key!(i128);
map_key!(isize);
map_key!(&'static str);
map_key!(&'static [u8]);
singleton_key!(());