sid/
id_vector.rs

1use {Identifier, FromUsize, ToUsize, IdRange};
2use core::default::Default;
3use core::slice;
4use alloc::{vec, vec::Vec};
5use core::marker::PhantomData;
6use core::ops;
7use core::iter::IntoIterator;
8use num_traits::Zero;
9
10/// Similar to Vec except that it is indexed using an Id rather than an usize index.
11/// if the stored type implements Default, IdVec can also use the set(...) method which can
12/// grow the vector to accomodate for the requested id.
13pub struct IdVec<ID: Identifier, T> {
14    data: Vec<T>,
15    _idtype: PhantomData<ID>,
16}
17
18impl<ID: Identifier, T> IdVec<ID, T> {
19    /// Create an empty IdVec
20    #[inline]
21    pub fn new() -> Self {
22        IdVec {
23            data: Vec::new(),
24            _idtype: PhantomData,
25        }
26    }
27
28    /// Create an IdVec with preallocated storage
29    #[inline]
30    pub fn with_capacity(size: ID::Handle) -> Self {
31        IdVec {
32            data: Vec::with_capacity(size.to_usize()),
33            _idtype: PhantomData,
34        }
35    }
36
37    /// Create an IdVec by recycling a Vec and its content.
38    #[inline]
39    pub fn from_vec(vec: Vec<T>) -> Self {
40        IdVec {
41            data: vec,
42            _idtype: PhantomData,
43        }
44    }
45
46    /// Consume the IdVec and create a Vec.
47    #[inline]
48    pub fn into_vec(self) -> Vec<T> {
49        self.data
50    }
51
52    /// Exposes the internal Vec.
53    #[inline]
54    pub fn as_vec(&self) -> &Vec<T> {
55        &self.data
56    }
57
58    /// Number of elements in the IdVec
59    #[inline]
60    pub fn len(&self) -> ID::Handle {
61        FromUsize::from_usize(self.data.len())
62    }
63
64    /// Returns true if the vector contains no elements.
65    #[inline]
66    pub fn is_empty(&self) -> bool {
67        self.data.is_empty()
68    }
69
70    /// Extracts a slice containing the entire vector.
71    #[inline]
72    pub fn as_slice(&self) -> IdSlice<ID, T> {
73        IdSlice::new(self.data.as_slice())
74    }
75
76    /// Extracts a mutable slice containing the entire vector.
77    #[inline]
78    pub fn as_mut_slice(&mut self) -> MutIdSlice<ID, T> {
79        MutIdSlice::new(self.data.as_mut_slice())
80    }
81
82    #[inline]
83    pub fn range(&self, ids: IdRange<ID::Tag, ID::Handle>) -> IdSlice<ID, T> {
84        IdSlice::new(&self.data[ids.start.to_usize()..ids.end.to_usize()])
85    }
86
87    #[inline]
88    pub fn mut_range(&mut self, ids: IdRange<ID::Tag, ID::Handle>) -> MutIdSlice<ID, T> {
89        MutIdSlice::new(&mut self.data[ids.start.to_usize()..ids.end.to_usize()])
90    }
91
92    #[inline]
93    pub fn range_from(&self, id: ID) -> IdSlice<ID, T> {
94        IdSlice::new(&self.data[id.to_usize()..])
95    }
96
97    #[inline]
98    pub fn mut_range_from(&mut self, id: ID) -> MutIdSlice<ID, T> {
99        MutIdSlice::new(&mut self.data[id.to_usize()..])
100    }
101
102    #[inline]
103    pub fn range_to(&self, id: ID) -> IdSlice<ID, T> {
104        IdSlice::new(&self.data[..id.to_usize()])
105    }
106
107    #[inline]
108    pub fn mut_range_to(&mut self, id: ID) -> MutIdSlice<ID, T> {
109        MutIdSlice::new(&mut self.data[..id.to_usize()])
110    }
111
112    #[inline]
113    pub fn range_to_inclusive(&self, id: ID) -> IdSlice<ID, T> {
114        IdSlice::new(&self.data[..(id.to_usize()+1)])
115    }
116
117    #[inline]
118    pub fn mut_range_to_inclusive(&mut self, id: ID) -> MutIdSlice<ID, T> {
119        MutIdSlice::new(&mut self.data[..(id.to_usize()+1)])
120    }
121
122    /// Return the nth element of the IdVec using an usize index rather than an Id (à la Vec).
123    #[inline]
124    pub fn nth(&self, idx: ID::Handle) -> &T {
125        &self.data[idx.to_usize()]
126    }
127
128    /// Return the nth element of the IdVec using an usize index rather than an Id (à la Vec).
129    #[inline]
130    pub fn nth_mut(&mut self, idx: ID::Handle) -> &mut T {
131        &mut self.data[idx.to_usize()]
132    }
133
134    /// Iterate over the elements of the IdVec
135    #[inline]
136    pub fn iter<'l>(&'l self) -> slice::Iter<'l, T> {
137        self.data.iter()
138    }
139
140    /// Iterate over the elements of the IdVec
141    #[inline]
142    pub fn iter_mut<'l>(&'l mut self) -> slice::IterMut<'l, T> {
143        self.data.iter_mut()
144    }
145
146    /// Add an element to the IdVec and return its Id.
147    /// This method can cause the storage to be reallocated.
148    #[inline]
149    pub fn push(&mut self, elt: T) -> ID {
150        let index = self.data.len();
151        self.data.push(elt);
152        return FromUsize::from_usize(index);
153    }
154
155
156    /// Inserts an element at position `id` within the vector, shifting all elements
157    /// after it to the right.
158    #[inline]
159    pub fn insert(&mut self, id: ID, elt: T) {
160        self.data.insert(id.to_usize(), elt);
161    }
162
163    /// Insert several elements by cloning them starting at position 'id` and shifting
164    /// all elements after them to the right.
165    pub fn insert_slice(&mut self, id: ID, elts: &[T]) where T: Clone {
166        self.data.reserve(elts.len());
167        let offset = id.to_usize();
168        for (i, elt) in elts.iter().enumerate() {
169            self.data.insert(offset + i, elt.clone());
170        }
171    }
172    /// Insert several elements by cloning them starting at position 'id` and shifting
173    /// all elements after them to the right.
174    pub fn insert_id_slice(&mut self, id: ID, elts: IdSlice<ID, T>) where T: Clone {
175        self.insert_slice(id, elts.untyped());
176    }
177
178    /// Clones and appends all elements in a slice to the vector.
179    pub fn extend_from_slice(&mut self, elts: &[T]) where T: Clone {
180        self.data.extend_from_slice(elts);
181    }
182
183    /// Clones and appends all elements in a slice to the vector.
184    pub fn extend_from_id_slice(&mut self, elts: IdSlice<ID, T>) where T: Clone {
185        self.data.extend_from_slice(elts.untyped());
186    }
187
188    /// Reserves capacity for at least additional more elements to be inserted in the given vector.
189    #[inline]
190    pub fn reserve(&mut self, additional: ID::Handle) {
191        self.data.reserve(additional.to_usize());
192    }
193
194    /// Shrinks the capacity of the vector as much as possible.
195    #[inline]
196    pub fn shrink_to_fit(&mut self) {
197        self.data.shrink_to_fit();
198    }
199
200    /// Drop all of the contained elements and clear the IdVec's storage.
201    #[inline]
202    pub fn clear(&mut self) {
203        self.data.clear();
204    }
205
206    /// Removes and returns the element at position index within the vector,
207    /// shifting all elements after it to the left.
208    #[inline]
209    pub fn remove(&mut self, index: ID) -> T {
210        self.data.remove(index.to_usize())
211    }
212
213    /// Removes an element from the vector and returns it.
214    /// The removed element is replaced by the last element of the vector.
215    #[inline]
216    pub fn swap_remove(&mut self, index: ID) -> T {
217        self.data.swap_remove(index.to_usize())
218    }
219
220    #[inline]
221    pub fn has_id(&self, id: ID) -> bool {
222        id.to_usize() < self.data.len()
223    }
224
225    #[inline]
226    pub fn first_id(&self) -> Option<ID> {
227        return if self.data.len() > 0 {
228            Some(ID::from_usize(0))
229        } else {
230            None
231        };
232    }
233
234    #[inline]
235    pub fn last_id(&self) -> Option<ID> {
236        return if self.data.len() > 0 {
237            Some(ID::from_usize(self.data.len() - 1))
238        } else {
239            None
240        };
241    }
242
243    #[inline]
244    pub fn ids(&self) -> IdRange<ID::Tag, ID::Handle> {
245        IdRange::new(Zero::zero()..self.len())
246    }
247}
248
249impl<ID: Identifier, T: Default> IdVec<ID, T> {
250    /// Set the value for a certain Id, possibly adding default values if the Id's index is Greater
251    /// than the size of the underlying vector.
252    pub fn set(&mut self, id: ID, val: T) {
253        while self.len().to_usize() < id.to_usize() {
254            self.push(T::default());
255        }
256        if self.len().to_usize() == id.to_usize() {
257            self.push(val);
258        } else {
259            self[id] = val;
260        }
261    }
262}
263
264impl<T: Default, ID: Identifier> IdVec<ID, T> {
265    pub fn resize(&mut self, size: ID::Handle) {
266        if size.to_usize() > self.data.len() {
267            let d = size.to_usize() - self.data.len();
268            self.data.reserve(d as usize);
269            for _ in 0..d {
270                self.data.push(Default::default());
271            }
272        } else {
273            let d = self.data.len() - size.to_usize();
274            for _ in 0..d {
275                self.data.pop();
276            }
277        }
278    }
279
280    /// Creates an IdVec with an n elements initialized to `Default::default`.
281    pub fn with_len(n: ID::Handle) -> Self {
282        let mut result: IdVec<ID, T> = IdVec::with_capacity(n);
283        result.resize(n);
284        return result;
285    }
286}
287
288impl<ID: Identifier, T> ops::Index<ID> for IdVec<ID, T> {
289    type Output = T;
290    fn index<'l>(&'l self, id: ID) -> &'l T {
291        &self.data[id.to_usize()]
292    }
293}
294
295impl<ID: Identifier, T> ops::IndexMut<ID> for IdVec<ID, T> {
296    fn index_mut<'l>(&'l mut self, id: ID) -> &'l mut T {
297        &mut self.data[id.to_usize()]
298    }
299}
300
301impl<ID: Identifier, T> IntoIterator for IdVec<ID, T> {
302    type Item = T;
303    type IntoIter = vec::IntoIter<T>;
304    #[inline]
305    fn into_iter(self) -> vec::IntoIter<T> {
306        self.data.into_iter()
307    }
308}
309
310impl<'l, ID: Identifier, T> IntoIterator for &'l IdVec<ID, T> {
311    type Item = &'l T;
312    type IntoIter = slice::Iter<'l, T>;
313    #[inline]
314    fn into_iter(self) -> slice::Iter<'l, T> {
315        (&self.data).into_iter()
316    }
317}
318
319impl<'l, ID: Identifier, T> IntoIterator for &'l mut IdVec<ID, T> {
320    type Item = &'l mut T;
321    type IntoIter = slice::IterMut<'l, T>;
322    #[inline]
323    fn into_iter(self) -> slice::IterMut<'l, T> {
324        (&mut self.data).into_iter()
325    }
326}
327
328
329impl<ID: Identifier, T: Clone> Clone for IdVec<ID, T> {
330    fn clone(&self) -> Self {
331        IdVec {
332            data: self.data.clone(),
333            _idtype: PhantomData,
334        }
335    }
336}
337
338pub struct IdSlice<'l, ID: Identifier, T>
339where
340    T: 'l,
341{
342    slice: &'l [T],
343    _idtype: PhantomData<ID>,
344}
345
346impl<'l, T, ID: Identifier> Copy for IdSlice<'l, ID, T>
347where
348    T: 'l,
349{
350}
351
352impl<'l, T, ID: Identifier> Clone for IdSlice<'l, ID, T>
353where
354    T: 'l,
355{
356    #[inline]
357    fn clone(&self) -> IdSlice<'l, ID, T> {
358        IdSlice {
359            slice: self.slice,
360            _idtype: PhantomData,
361        }
362    }
363}
364
365impl<'l, T, ID: Identifier> IdSlice<'l, ID, T>
366where
367    T: 'l,
368{
369    #[inline]
370    pub fn new(slice: &'l [T]) -> IdSlice<'l, ID, T> {
371        IdSlice {
372            slice: slice,
373            _idtype: PhantomData,
374        }
375    }
376
377    #[inline]
378    pub fn len(&self) -> ID::Handle {
379        FromUsize::from_usize(self.slice.len())
380    }
381
382    #[inline]
383    pub fn untyped<'a>(&'a self) -> &'a [T] {
384        self.slice
385    }
386
387    #[inline]
388    pub fn iter<'a>(&'a self) -> slice::Iter<'a, T> {
389        self.slice.iter()
390    }
391
392    #[inline]
393    pub fn ids(&self) -> IdRange<ID::Tag, ID::Handle> {
394        IdRange::new(Zero::zero()..self.len())
395    }
396
397    #[inline]
398    pub fn nth(&self, idx: ID::Handle) -> &T {
399        &self.slice[idx.to_usize()]
400    }
401
402    #[inline]
403    pub fn first(&self) -> Option<&T> {
404        self.slice.first()
405    }
406
407    #[inline]
408    pub fn last(&self) -> Option<&T> {
409        self.slice.last()
410    }
411
412    #[inline]
413    pub fn first_id(&self) -> Option<ID> {
414        return if self.slice.len() > 0 {
415            Some(ID::from_usize(0))
416        } else {
417            None
418        };
419    }
420
421    #[inline]
422    pub fn last_id(&self) -> Option<ID> {
423        return if self.slice.len() > 0 {
424            Some(ID::from_usize(self.slice.len() - 1))
425        } else {
426            None
427        };
428    }
429
430    #[inline]
431    pub fn split_at(&self, id: ID) -> (Self, Self) {
432        let (s1, s2) = self.slice.split_at(id.to_usize());
433        (Self::new(s1), Self::new(s2))
434    }
435
436    #[inline]
437    pub fn range(&self, ids: IdRange<ID::Tag, ID::Handle>) -> IdSlice<ID, T> {
438        IdSlice::new(&self.slice[ids.start.to_usize()..ids.end.to_usize()])
439    }
440
441    #[inline]
442    pub fn range_from(&self, id: ID) -> IdSlice<ID, T> {
443        IdSlice::new(&self.slice[id.to_usize()..])
444    }
445
446    #[inline]
447    pub fn range_to(&self, id: ID) -> IdSlice<ID, T> {
448        IdSlice::new(&self.slice[..id.to_usize()])
449    }
450
451    #[inline]
452    pub fn range_to_inclusive(&self, id: ID) -> IdSlice<ID, T> {
453        IdSlice::new(&self.slice[..(id.to_usize()+1)])
454    }
455}
456
457impl<'l, ID: Identifier, T> ops::Index<ID> for IdSlice<'l, ID, T>
458where
459    T: 'l,
460{
461    type Output = T;
462    #[inline]
463    fn index<'a>(&'a self, id: ID) -> &'a T {
464        &self.slice[id.to_usize()]
465    }
466}
467
468
469
470pub struct MutIdSlice<'l, ID: Identifier, T: 'l> {
471    slice: &'l mut [T],
472    _idtype: PhantomData<ID>,
473}
474
475impl<'l, ID: Identifier, T: 'l> MutIdSlice<'l, ID, T> {
476    #[inline]
477    pub fn new(slice: &'l mut [T]) -> MutIdSlice<'l, ID, T> {
478        MutIdSlice {
479            slice: slice,
480            _idtype: PhantomData,
481        }
482    }
483
484    #[inline]
485    pub fn len(&self) -> ID::Handle {
486        FromUsize::from_usize(self.slice.len())
487    }
488
489    #[inline]
490    pub fn untyped(&mut self) -> &mut [T] {
491        self.slice
492    }
493
494    #[inline]
495    pub fn iter<'a>(&'a self) -> slice::Iter<'a, T> {
496        self.slice.iter()
497    }
498
499    #[inline]
500    pub fn iter_mut<'a>(&'a mut self) -> slice::IterMut<'a, T> {
501        self.slice.iter_mut()
502    }
503
504    #[inline]
505    pub fn ids(&self) -> IdRange<ID::Tag, ID::Handle> {
506        IdRange::new(Zero::zero()..self.len())
507    }
508
509    #[inline]
510    pub fn nth(&mut self, idx: ID::Handle) -> &mut T {
511        &mut self.slice[idx.to_usize()]
512    }
513
514    #[inline]
515    pub fn first(&mut self) -> Option<&mut T> {
516        self.slice.first_mut()
517    }
518
519    #[inline]
520    pub fn last(&mut self) -> Option<&mut T> {
521        self.slice.last_mut()
522    }
523
524    #[inline]
525    pub fn range(&mut self, ids: IdRange<ID::Tag, ID::Handle>) -> MutIdSlice<ID, T> {
526        MutIdSlice::new(&mut self.slice[ids.start.to_usize()..ids.end.to_usize()])
527    }
528
529    #[inline]
530    pub fn range_from(&mut self, id: ID) -> MutIdSlice<ID, T> {
531        MutIdSlice::new(&mut self.slice[id.to_usize()..])
532    }
533
534    #[inline]
535    pub fn range_to(&mut self, id: ID) -> MutIdSlice<ID, T> {
536        MutIdSlice::new(&mut self.slice[..id.to_usize()])
537    }
538
539    #[inline]
540    pub fn range_to_inclusive(&mut self, id: ID) -> MutIdSlice<ID, T> {
541        MutIdSlice::new(&mut self.slice[..(id.to_usize()+1)])
542    }
543}
544
545impl<'l, ID: Identifier, T: 'l> IntoIterator for IdSlice<'l, ID, T> {
546    type Item = &'l T;
547    type IntoIter = slice::Iter<'l, T>;
548    #[inline]
549    fn into_iter(self) -> slice::Iter<'l, T> {
550        self.slice.iter()
551    }
552}
553
554impl<'l, ID: Identifier, T: 'l> IntoIterator for MutIdSlice<'l, ID, T> {
555    type Item = &'l mut T;
556    type IntoIter = slice::IterMut<'l, T>;
557    #[inline]
558    fn into_iter(self) -> slice::IterMut<'l, T> {
559        self.slice.iter_mut()
560    }
561}
562
563impl<'l, ID: Identifier, T: 'l> ops::Index<ID> for MutIdSlice<'l, ID, T> {
564    type Output = T;
565    #[inline]
566    fn index<'a>(&'a self, id: ID) -> &'a T {
567        &self.slice[id.to_usize()]
568    }
569}
570
571impl<'l, ID: Identifier, T: 'l> ops::IndexMut<ID> for MutIdSlice<'l, ID, T> {
572    #[inline]
573    fn index_mut<'a>(&'a mut self, id: ID) -> &'a mut T {
574        &mut self.slice[id.to_usize()]
575    }
576}
577
578#[test]
579fn test_id_vector() {
580    use super::*;
581
582    #[derive(Debug)]
583    struct T;
584
585    fn id(i: u16) -> Id<T, u16> {
586        Id::new(i)
587    }
588
589    let mut v = IdVec::new();
590    let a = v.push(42 as u32);
591    assert_eq!(v[a], 42);
592    v.set(a, 0);
593    assert_eq!(v[a], 0);
594
595    v.set(id(10), 100);
596    assert_eq!(v[id(10)], 100);
597
598    v.set(id(5), 50);
599    assert_eq!(v[id(5)], 50);
600
601    v.set(id(20), 200);
602    assert_eq!(v[id(20)], 200);
603    assert_eq!(v.len(), 21);
604}
605
606#[test]
607fn test_id_vector_u32() {
608    let _: IdVec<u32, u32> = IdVec::new();
609    let _: IdVec<i32, i32> = IdVec::new();
610}
611
612#[test]
613fn test_into_iter() {
614    use super::*;
615
616    let mut v: IdVec<u16, u16> = IdVec::from_vec(vec![
617        0, 1, 2, 3, 4, 5
618    ]);
619
620    let mut idx = 0;
621    for elt in &v {
622        assert_eq!(*elt, idx);
623        idx += 1;
624    }
625
626    for elt in &mut v {
627        *elt += 1;
628    }
629
630    let mut idx = 0;
631    for elt in &v {
632        assert_eq!(*elt, idx + 1);
633        idx += 1;
634    }
635}
sid/id_vector.rs

sid/
id_vector.rs
