sid_vec/
lib.rs

1use std::marker::PhantomData;
2use std::ops::Add;
3use std::hash::{ Hash, Hasher };
4
5mod id_vector;
6mod id_list;
7//pub mod sparse_id_vector;
8
9pub use id_vector::{ IdSlice, MutIdSlice, IdVec };
10pub use id_list::{ IdFreeList, NullId, NoneAsNullId };
11
12// --------------------------------------------------------------------------------------------- Id
13
14pub struct Id<Tag, Handle = u32> {
15    pub handle: Handle,
16    pub _marker: PhantomData<Tag>
17}
18
19impl<T, H: std::fmt::Display> std::fmt::Debug for Id<T, H> {
20    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
21        write!(f, "Id#{}", self.handle)
22    }
23}
24
25impl<T, H:Copy> Copy for Id<T, H> {}
26
27impl<T, H:Copy> Clone for Id<T, H> { fn clone(&self) -> Id<T, H> { *self } }
28
29impl<T, H:PartialEq> PartialEq for Id<T, H> {
30    fn eq(&self, other: &Id<T,H>) -> bool { self.handle.eq(&other.handle) }
31}
32
33impl<T, H:Copy+Eq> Eq for Id<T, H> {}
34
35impl<T, H:Copy> Id<T, H> {
36    pub fn new(idx: H) -> Id<T, H> { Id { handle: idx, _marker: PhantomData } }
37}
38
39impl<T, H:IntegerHandle> Identifier for Id<T, H> {
40    type Handle = H;
41    type Unit = T;
42}
43
44impl<T, H:ToIndex> ToIndex for Id<T, H> {
45    fn to_index(&self) -> usize { self.handle.to_index() }
46}
47
48impl<T, H:Copy+FromIndex> FromIndex for Id<T, H> {
49    fn from_index(idx: usize) -> Id<T, H> { Id::new(FromIndex::from_index(idx)) }
50}
51
52impl<T, Handle: Hash> Hash for Id<T, Handle> {
53    fn hash<H: Hasher>(&self, state: &mut H) {
54        self.handle.hash(state);
55    }
56}
57
58
59// ---------------------------------------------------------------------------------------- IdRange
60
61pub struct IdRange<T, H> {
62    pub first: Id<T, H>,
63    pub count: H,
64}
65
66impl<T, H: std::fmt::Display> std::fmt::Debug for IdRange<T, H> {
67    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
68        write!(f, "Id#[{}..{}]", self.first.handle, self.count)
69    }
70}
71
72impl<T, H:Copy> Copy for IdRange<T, H> {}
73
74impl<T, H:Copy> Clone for IdRange<T, H> { fn clone(&self) -> IdRange<T, H> { *self } }
75
76impl<T, H:PartialEq> PartialEq for IdRange<T, H> {
77    fn eq(&self, other: &IdRange<T,H>) -> bool { self.first.eq(&other.first) && self.count.eq(&other.count) }
78}
79
80impl<T, H:Copy+Eq> Eq for IdRange<T, H> {}
81
82impl<T, H:IntegerHandle> IdRange<T, H> {
83    pub fn new(first: H, count: H) -> IdRange<T, H> {
84        IdRange { first: Id::new(first), count: count }
85    }
86
87    pub fn len(self) -> usize { self.count.to_index() }
88
89    pub fn is_empty(self) -> bool { self.len() == 0 }
90
91    pub fn get(self, i: H) -> Id<T, H> {
92        debug_assert!(i < self.count);
93        return Id { handle: self.first.handle + i, _marker: PhantomData };
94    }
95
96    /// Return a range with the front element popped, or None if the range is empty.
97    pub fn shrinked_left(self) -> Option<IdRange<T, H>> {
98        if self.is_empty() {
99            return None;
100        }
101        return Some(IdRange{
102            count: FromIndex::from_index(self.count.to_index() - 1),
103            first: FromIndex::from_index(self.first.to_index() + 1),
104        });
105    }
106
107    /// Return a range with the back element popped, or None if the range is empty.
108    pub fn shrinked_right(self) -> Option<IdRange<T, H>> {
109        if self.is_empty() {
110            return None;
111        }
112        return Some(IdRange{
113            first: self.first,
114            count: FromIndex::from_index(self.count.to_index() - 1),
115        });
116    }
117}
118
119impl<T, H:IntegerHandle> Iterator for IdRange<T, H> {
120    type Item = Id<T, H>;
121    fn next(&mut self) -> Option<Id<T, H>> {
122        if self.count.to_index() == 0 {
123            return None;
124        }
125        let res = self.first;
126        self.count = FromIndex::from_index(self.count.to_index() - 1);
127        self.first = FromIndex::from_index(self.first.to_index() + 1);
128        return Some(res);
129    }
130
131    fn size_hint(&self) -> (usize, Option<usize>) {
132        return (self.count.to_index(), Some(self.count.to_index()));
133    }
134
135    fn count(self) -> usize { self.count.to_index() }
136}
137
138pub struct ReverseIdRange<T, H> {
139    range: IdRange<T, H>,
140}
141
142impl<T, H: std::fmt::Display> std::fmt::Debug for ReverseIdRange<T, H> {
143    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
144        write!(f, "ReverseId#[{}..{}]", self.range.first.handle, self.range.count)
145    }
146}
147
148impl<T, H:Copy> Copy for ReverseIdRange<T, H> {}
149
150impl<T, H:Copy> Clone for ReverseIdRange<T, H> { fn clone(&self) -> ReverseIdRange<T, H> { *self } }
151
152impl<T, H:PartialEq> PartialEq for ReverseIdRange<T, H> {
153    fn eq(&self, other: &ReverseIdRange<T,H>) -> bool { self.range.eq(&other.range) }
154}
155
156impl<T, H:Copy+Eq> Eq for ReverseIdRange<T, H> {}
157
158impl<T, H:IntegerHandle> ReverseIdRange<T, H> {
159
160    pub fn new(range: IdRange<T, H>) -> ReverseIdRange<T, H> { ReverseIdRange { range: range } }
161
162    pub fn len(&self) -> usize { self.range.len() }
163
164    pub fn is_empty(self) -> bool { self.len() == 0 }
165
166    pub fn get(self, i: H) -> Id<T, H> { self.range.get(i) }
167}
168
169impl<T, H:IntegerHandle> Iterator for ReverseIdRange<T, H> {
170    type Item = Id<T, H>;
171    fn next(&mut self) -> Option<Id<T, H>> {
172        if self.range.count.to_index() == 0 {
173            return None;
174        }
175        self.range.count = FromIndex::from_index(self.range.count.to_index() - 1);
176        return Some(FromIndex::from_index(self.range.first.to_index() + self.range.count.to_index()));
177    }
178
179    fn size_hint(&self) -> (usize, Option<usize>) {
180        self.range.size_hint()
181    }
182
183    fn count(self) -> usize { self.range.count() }
184}
185
186
187
188// ------------------------------------------------------------------------------------------ GenId
189// TODO: remove it or implement traits manually
190
191#[derive(Copy, Clone)]
192pub struct GenId<T, H:Copy, G> {
193    pub id: Id<T, H>,
194    pub gen: G,
195}
196
197impl<T, H: Copy+std::fmt::Display, G: std::fmt::Display> std::fmt::Debug for GenId<T, H, G> {
198    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
199        write!(f, "GenId#{}({})", self.id.handle, self.gen)
200    }
201}
202
203impl<T, H:IntegerHandle, G: PartialEq> PartialEq for GenId<T, H, G> {
204    fn eq(&self, other: &GenId<T, H, G>) -> bool { self.id == other.id && self.gen == other.gen }
205}
206
207impl<T, H:IntegerHandle, G> ToIndex for GenId<T, H, G> {
208    fn to_index(&self) -> usize { self.id.to_index() }
209}
210
211
212// ----------------------------------------------------------------------------------------- traits
213
214pub trait FromIndex {  fn from_index(idx: usize) -> Self; }
215
216pub trait ToIndex { fn to_index(&self) -> usize; }
217
218pub trait Generation { fn get_gen(&self) -> u32; }
219
220pub trait IntegerHandle : Copy + Clone
221                        + Add<Output=Self>
222                        + PartialEq + PartialOrd
223                        + FromIndex + ToIndex {}
224
225pub trait Identifier: Copy + FromIndex + ToIndex + PartialEq {
226    type Handle: IntegerHandle;
227    type Unit;
228}
229
230impl Identifier for u8 { type Handle = u8; type Unit = (); }
231impl Identifier for u16 { type Handle = u16; type Unit = (); }
232impl Identifier for u32 { type Handle = u32; type Unit = (); }
233impl Identifier for u64 { type Handle = u64; type Unit = (); }
234impl Identifier for i8 { type Handle = i8; type Unit = (); }
235impl Identifier for i16 { type Handle = i16; type Unit = (); }
236impl Identifier for i32 { type Handle = i32; type Unit = (); }
237impl Identifier for i64 { type Handle = i64; type Unit = (); }
238
239impl ToIndex for u8 { fn to_index(&self) -> usize { *self as usize } }
240impl ToIndex for u16 { fn to_index(&self) -> usize { *self as usize } }
241impl ToIndex for u32 { fn to_index(&self) -> usize { *self as usize } }
242impl ToIndex for u64 { fn to_index(&self) -> usize { *self as usize } }
243impl ToIndex for usize { fn to_index(&self) -> usize { *self } }
244impl ToIndex for i8 { fn to_index(&self) -> usize { *self as usize } }
245impl ToIndex for i16 { fn to_index(&self) -> usize { *self as usize } }
246impl ToIndex for i32 { fn to_index(&self) -> usize { *self as usize } }
247impl ToIndex for i64 { fn to_index(&self) -> usize { *self as usize } }
248impl ToIndex for isize { fn to_index(&self) -> usize { *self as usize } }
249
250impl FromIndex for u8 { fn from_index(idx: usize) -> u8 { idx as u8 } }
251impl FromIndex for u16 { fn from_index(idx: usize) -> u16 { idx as u16 } }
252impl FromIndex for u32 { fn from_index(idx: usize) -> u32 { idx as u32 } }
253impl FromIndex for u64 { fn from_index(idx: usize) -> u64 { idx as u64 } }
254impl FromIndex for usize { fn from_index(idx: usize) -> usize { idx } }
255impl FromIndex for i8 { fn from_index(idx: usize) -> i8 { idx as i8 } }
256impl FromIndex for i16 { fn from_index(idx: usize) -> i16 { idx as i16 } }
257impl FromIndex for i32 { fn from_index(idx: usize) -> i32 { idx as i32 } }
258impl FromIndex for i64 { fn from_index(idx: usize) -> i64 { idx as i64 } }
259impl FromIndex for isize { fn from_index(idx: usize) -> isize { idx as isize } }
260
261impl Generation for u8  { fn get_gen(&self) -> u32 { *self as u32 } }
262impl Generation for u16 { fn get_gen(&self) -> u32 { *self as u32 } }
263impl Generation for u32 { fn get_gen(&self) -> u32 { *self as u32 } }
264impl Generation for u64 { fn get_gen(&self) -> u32 { *self as u32 } }
265
266impl<T, H:Copy, G:Generation> Generation for GenId<T, H, G>  {
267    fn get_gen(&self) -> u32 { self.gen.get_gen() }
268}
269
270impl IntegerHandle for u8 {}
271impl IntegerHandle for u16 {}
272impl IntegerHandle for u32 {}
273impl IntegerHandle for u64 {}
274impl IntegerHandle for usize {}
275impl IntegerHandle for i8 {}
276impl IntegerHandle for i16 {}
277impl IntegerHandle for i32 {}
278impl IntegerHandle for i64 {}
279impl IntegerHandle for isize {}
280
281
282// ------------------------------------------------------------------------------------------ tests
283
284#[test]
285fn test_copy_id() {
286    #[derive(Debug)]
287    struct Foo;
288
289    // check that Id is Copy
290    let a: Id<Foo, u32> = Id::new(0);
291    let b = a;
292    let c = a;
293    assert_eq!(b, c);
294
295    // check that IdRange is Copy
296    let r1 = IdRange {
297        first: a,
298        count: 10,
299    };
300
301    let r2 = r1;
302    let r3 = r1;
303    assert_eq!(r2, r3);
304}
305
306#[test]
307fn test_reverese_id_range() {
308    use std::iter::FromIterator;
309    fn range(first:u16, count:u16) -> IdRange<u16, u16> { IdRange::new(first, count) }
310    let v: Vec<Id<u16, u16>> = Vec::from_iter(ReverseIdRange::new(range(1, 5)));
311    assert_eq!(v, vec![Id::new(5), Id::new(4), Id::new(3), Id::new(2), Id::new(1)]);
312}
sid_vec/lib.rs

sid_vec/
lib.rs
