immutable_chunkmap/
chunk.rs

1use alloc::{sync::Arc, vec::Vec};
2use arrayvec::ArrayVec;
3use core::{
4    borrow::Borrow,
5    cmp::{min, Ord, Ordering},
6    fmt::{self, Debug, Formatter},
7    iter, mem,
8    ops::Deref,
9    slice,
10};
11
12#[cfg(feature = "pool")]
13use core::{mem::ManuallyDrop, ptr};
14#[cfg(feature = "pool")]
15use poolshark::{
16    local::{insert_raw, take},
17    location_id, Discriminant, IsoPoolable, Poolable,
18};
19
20#[derive(PartialEq)]
21pub(crate) enum Loc {
22    InRight,
23    InLeft,
24    NotPresent(usize),
25    Here(usize),
26}
27
28/*
29elts is a sorted array of pairs, increasing the SIZE has several effects;
30
31-- decreases the height of the tree for a given number of elements,
32   decreasing the amount of indirection necessary to get to any given
33   key.
34
35-- decreases the number of objects allocated on the heap each time a
36   key is added or removed
37
38-- increases the size of each allocation
39
40-- icreases the overall amount of memory allocated for each change to
41   the tree
42*/
43pub const DEFAULT_SIZE: usize = 512;
44
45pub(crate) enum UpdateChunk<
46    Q: Ord,
47    K: Ord + Clone + Borrow<Q>,
48    V: Clone,
49    D,
50    const SIZE: usize,
51> {
52    UpdateLeft(Vec<(Q, D)>),
53    UpdateRight(Vec<(Q, D)>),
54    Updated {
55        elts: Chunk<K, V, SIZE>,
56        update_left: Vec<(Q, D)>,
57        update_right: Vec<(Q, D)>,
58        overflow_right: Vec<(K, V)>,
59    },
60    Removed {
61        not_done: Vec<(Q, D)>,
62        update_left: Vec<(Q, D)>,
63        update_right: Vec<(Q, D)>,
64    },
65}
66
67pub(crate) enum Update<Q: Ord, K: Ord + Clone + Borrow<Q>, V: Clone, D, const SIZE: usize>
68{
69    UpdateLeft(Q, D),
70    UpdateRight(Q, D),
71    Updated {
72        elts: Chunk<K, V, SIZE>,
73        overflow: Option<(K, V)>,
74        previous: Option<V>,
75    },
76}
77
78pub(crate) enum MutUpdate<Q: Ord, K: Ord + Clone + Borrow<Q>, V: Clone, D> {
79    UpdateLeft(Q, D),
80    UpdateRight(Q, D),
81    Updated {
82        overflow: Option<(K, V)>,
83        previous: Option<V>,
84    },
85}
86
87#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
88pub(crate) struct ChunkInner<K, V, const SIZE: usize> {
89    keys: ArrayVec<K, SIZE>,
90    vals: ArrayVec<V, SIZE>,
91}
92
93#[cfg(feature = "pool")]
94impl<K, V, const SIZE: usize> ChunkInner<K, V, SIZE> {
95    fn new() -> Self {
96        Self {
97            keys: ArrayVec::new(),
98            vals: ArrayVec::new(),
99        }
100    }
101
102    fn reset(&mut self) {
103        self.keys.clear();
104        self.vals.clear();
105    }
106}
107
108#[cfg(feature = "pool")]
109#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
110pub(crate) struct Chunk<K: Ord + Clone, V: Clone, const SIZE: usize>(
111    ManuallyDrop<Arc<ChunkInner<K, V, SIZE>>>,
112);
113
114#[cfg(feature = "pool")]
115impl<K: Ord + Clone, V: Clone, const SIZE: usize> Poolable for Chunk<K, V, SIZE> {
116    fn capacity(&self) -> usize {
117        1
118    }
119
120    fn empty() -> Self {
121        Self(ManuallyDrop::new(Arc::new(ChunkInner::new())))
122    }
123
124    fn really_dropped(&mut self) -> bool {
125        Arc::get_mut(&mut self.0).is_some()
126    }
127
128    fn reset(&mut self) {
129        Arc::get_mut(&mut self.0).unwrap().reset()
130    }
131}
132
133#[cfg(feature = "pool")]
134unsafe impl<K: Ord + Clone, V: Clone, const SIZE: usize> IsoPoolable
135    for Chunk<K, V, SIZE>
136{
137    const DISCRIMINANT: Option<Discriminant> =
138        Discriminant::new_p2_size::<K, V, SIZE>(location_id!());
139}
140
141#[cfg(feature = "pool")]
142impl<K: Ord + Clone, V: Clone, const SIZE: usize> Drop for Chunk<K, V, SIZE> {
143    fn drop(&mut self) {
144        match Arc::get_mut(&mut self.0) {
145            None => unsafe {
146                ManuallyDrop::drop(&mut self.0);
147            },
148            Some(inner) => {
149                inner.reset();
150                if let Some(mut t) = unsafe { insert_raw::<Self>(ptr::read(self)) } {
151                    unsafe { ManuallyDrop::drop(&mut t.0) };
152                    mem::forget(t); // don't call ourselves recursively
153                }
154            }
155        }
156    }
157}
158
159#[cfg(not(feature = "pool"))]
160#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
161pub(crate) struct Chunk<K: Ord + Clone, V: Clone, const SIZE: usize>(
162    Arc<ChunkInner<K, V, SIZE>>,
163);
164
165impl<K: Ord + Clone, V: Clone, const SIZE: usize> Deref for Chunk<K, V, SIZE> {
166    type Target = ChunkInner<K, V, SIZE>;
167
168    fn deref(&self) -> &Self::Target {
169        &*self.0
170    }
171}
172
173impl<K: Ord + Clone, V: Clone, const SIZE: usize> Debug for Chunk<K, V, SIZE>
174where
175    K: Debug,
176    V: Debug,
177{
178    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
179        f.debug_map().entries(self.into_iter()).finish()
180    }
181}
182
183impl<K: Ord + Clone, V: Clone, const SIZE: usize> Chunk<K, V, SIZE>
184where
185    K: Ord + Clone,
186    V: Clone,
187{
188    pub(crate) fn singleton(k: K, v: V) -> Self {
189        let mut t = Self::empty();
190        let inner = Arc::get_mut(&mut t.0).unwrap();
191        inner.keys.push(k);
192        inner.vals.push(v);
193        t
194    }
195
196    fn make_mut<'a>(&'a mut self) -> &'a mut ChunkInner<K, V, SIZE> {
197        Arc::make_mut(&mut self.0)
198    }
199
200    #[cfg(feature = "pool")]
201    pub(crate) fn empty() -> Self {
202        take()
203    }
204
205    #[cfg(not(feature = "pool"))]
206    pub(crate) fn empty() -> Self {
207        Self(Arc::new(ChunkInner {
208            keys: ArrayVec::new(),
209            vals: ArrayVec::new(),
210        }))
211    }
212
213    pub(crate) fn create_with<Q, D, F>(chunk: Vec<(Q, D)>, f: &mut F) -> Self
214    where
215        Q: Ord,
216        K: Borrow<Q>,
217        F: FnMut(Q, D, Option<(&K, &V)>) -> Option<(K, V)>,
218    {
219        let mut t = Chunk::empty();
220        let inner = Arc::get_mut(&mut t.0).unwrap();
221        for (k, v) in chunk.into_iter().filter_map(|(q, d)| f(q, d, None)) {
222            inner.keys.push(k);
223            inner.vals.push(v);
224        }
225        t
226    }
227
228    pub(crate) fn get_local<Q: ?Sized + Ord>(&self, k: &Q) -> Option<usize>
229    where
230        K: Borrow<Q>,
231    {
232        match self.keys.binary_search_by_key(&k, |k| k.borrow()) {
233            Ok(i) => Some(i),
234            Err(_) => None,
235        }
236    }
237
238    pub(crate) fn get<Q: ?Sized + Ord>(&self, k: &Q) -> Loc
239    where
240        K: Borrow<Q>,
241    {
242        let len = self.len();
243        if len == 0 {
244            Loc::NotPresent(0)
245        } else {
246            let first = k.cmp(&self.keys[0].borrow());
247            let last = k.cmp(&self.keys[len - 1].borrow());
248            match (first, last) {
249                (Ordering::Equal, _) => Loc::Here(0),
250                (_, Ordering::Equal) => Loc::Here(len - 1),
251                (Ordering::Less, _) => Loc::InLeft,
252                (_, Ordering::Greater) => Loc::InRight,
253                (Ordering::Greater, Ordering::Less) => {
254                    match self.keys.binary_search_by_key(&k, |k| k.borrow()) {
255                        Result::Ok(i) => Loc::Here(i),
256                        Result::Err(i) => Loc::NotPresent(i),
257                    }
258                }
259            }
260        }
261    }
262
263    // invariant: chunk is sorted and deduped
264    pub(crate) fn update_chunk<Q, D, F>(
265        &self,
266        chunk: Vec<(Q, D)>,
267        leaf: bool,
268        f: &mut F,
269    ) -> UpdateChunk<Q, K, V, D, SIZE>
270    where
271        Q: Ord,
272        K: Borrow<Q>,
273        F: FnMut(Q, D, Option<(&K, &V)>) -> Option<(K, V)>,
274    {
275        assert!(chunk.len() <= SIZE && chunk.len() > 0 && self.len() > 0);
276        let full = !leaf || self.len() >= SIZE;
277        let in_left = self.get(&chunk[chunk.len() - 1].0) == Loc::InLeft;
278        let in_right = self.get(&chunk[0].0) == Loc::InRight;
279        if full && in_left {
280            UpdateChunk::UpdateLeft(chunk)
281        } else if full && in_right {
282            UpdateChunk::UpdateRight(chunk)
283        } else if leaf && (in_left || in_right) {
284            let iter = chunk.into_iter().filter_map(|(q, d)| f(q, d, None));
285            let mut overflow_right = Vec::new();
286            let mut elts = Chunk::empty();
287            let inner = Arc::get_mut(&mut elts.0).unwrap();
288            if in_right {
289                inner.clone_from(self);
290                for (k, v) in iter {
291                    if inner.keys.len() < SIZE {
292                        inner.keys.push(k);
293                        inner.vals.push(v);
294                    } else {
295                        overflow_right.push((k, v));
296                    }
297                }
298            } else {
299                for (k, v) in iter {
300                    if inner.keys.len() < SIZE {
301                        inner.keys.push(k);
302                        inner.vals.push(v);
303                    } else {
304                        overflow_right.push((k, v));
305                    }
306                }
307                for (k, v) in self.keys.iter().cloned().zip(self.vals.iter().cloned()) {
308                    if inner.keys.len() < SIZE {
309                        inner.keys.push(k);
310                        inner.vals.push(v);
311                    } else {
312                        overflow_right.push((k, v));
313                    }
314                }
315            }
316            UpdateChunk::Updated {
317                elts,
318                update_left: Vec::new(),
319                update_right: Vec::new(),
320                overflow_right,
321            }
322        } else {
323            #[inline(always)]
324            fn copy_up_to<K, V, const SIZE: usize>(
325                t: &Chunk<K, V, SIZE>,
326                elts: &mut ChunkInner<K, V, SIZE>,
327                overflow_right: &mut Vec<(K, V)>,
328                m: &mut usize,
329                i: usize,
330            ) where
331                K: Ord + Clone,
332                V: Clone,
333            {
334                let n = min(i.saturating_sub(*m), SIZE.saturating_sub(elts.keys.len()));
335                if n > 0 {
336                    elts.keys.extend(t.keys[*m..*m + n].iter().cloned());
337                    elts.vals.extend(t.vals[*m..*m + n].iter().cloned());
338                    *m += n;
339                }
340                if *m < i {
341                    overflow_right.extend(
342                        t.keys.as_slice()[*m..i]
343                            .iter()
344                            .cloned()
345                            .zip(t.vals.as_slice()[*m..i].iter().cloned()),
346                    );
347                    *m = i;
348                }
349            }
350            // invariant: don't cross the streams.
351            let mut not_done = Vec::new();
352            let mut update_left = Vec::new();
353            let mut update_right = Vec::new();
354            let mut overflow_right = Vec::new();
355            let mut m = 0;
356            let mut elts = Chunk::empty();
357            let inner = Arc::get_mut(&mut elts.0).unwrap();
358            let mut chunk = chunk.into_iter();
359            loop {
360                if m == self.len() && inner.keys.len() == 0 {
361                    not_done.extend(chunk);
362                    break;
363                }
364                match chunk.next() {
365                    None => {
366                        copy_up_to(self, inner, &mut overflow_right, &mut m, self.len());
367                        break;
368                    }
369                    Some((q, d)) => {
370                        match self.get(&q) {
371                            Loc::Here(i) => {
372                                copy_up_to(self, inner, &mut overflow_right, &mut m, i);
373                                let r = f(q, d, Some((&self.keys[i], &self.vals[i])));
374                                if let Some((k, v)) = r {
375                                    if inner.keys.len() < SIZE {
376                                        inner.keys.push(k);
377                                        inner.vals.push(v);
378                                    } else {
379                                        overflow_right.push((k, v))
380                                    }
381                                }
382                                // self[i] was replaced or deleted, skip it
383                                m += 1;
384                            }
385                            Loc::NotPresent(i) => {
386                                copy_up_to(self, inner, &mut overflow_right, &mut m, i);
387                                if let Some((k, v)) = f(q, d, None) {
388                                    if inner.keys.len() < SIZE {
389                                        inner.keys.push(k);
390                                        inner.vals.push(v);
391                                    } else {
392                                        overflow_right.push((k, v));
393                                    }
394                                }
395                            }
396                            Loc::InLeft => {
397                                if leaf && inner.keys.len() < SIZE {
398                                    if let Some((k, v)) = f(q, d, None) {
399                                        inner.keys.push(k);
400                                        inner.vals.push(v);
401                                    }
402                                } else {
403                                    update_left.push((q, d))
404                                }
405                            }
406                            Loc::InRight => {
407                                let len = self.len();
408                                copy_up_to(self, inner, &mut overflow_right, &mut m, len);
409                                if leaf && inner.keys.len() < SIZE {
410                                    let iter = iter::once((q, d))
411                                        .chain(chunk)
412                                        .filter_map(|(q, d)| f(q, d, None));
413                                    for (k, v) in iter {
414                                        if inner.keys.len() < SIZE {
415                                            inner.keys.push(k);
416                                            inner.vals.push(v);
417                                        } else {
418                                            overflow_right.push((k, v));
419                                        }
420                                    }
421                                } else {
422                                    update_right.push((q, d));
423                                    update_right.extend(chunk);
424                                }
425                                break;
426                            }
427                        }
428                    }
429                }
430            }
431            if elts.len() > 0 {
432                assert_eq!(not_done.len(), 0);
433                UpdateChunk::Updated {
434                    elts,
435                    update_left,
436                    update_right,
437                    overflow_right,
438                }
439            } else {
440                assert_eq!(overflow_right.len(), 0);
441                UpdateChunk::Removed {
442                    not_done,
443                    update_left,
444                    update_right,
445                }
446            }
447        }
448    }
449
450    pub(crate) fn update<Q, D, F>(
451        &self,
452        q: Q,
453        d: D,
454        leaf: bool,
455        f: &mut F,
456    ) -> Update<Q, K, V, D, SIZE>
457    where
458        Q: Ord,
459        K: Borrow<Q>,
460        F: FnMut(Q, D, Option<(&K, &V)>) -> Option<(K, V)>,
461    {
462        match self.get(&q) {
463            Loc::Here(i) => {
464                let mut elts = Chunk::empty();
465                let inner = Arc::get_mut(&mut elts.0).unwrap();
466                inner.keys.extend(self.keys[0..i].iter().cloned());
467                inner.vals.extend(self.vals[0..i].iter().cloned());
468                if let Some((k, v)) = f(q, d, Some((&self.keys[i], &self.vals[i]))) {
469                    inner.keys.push(k);
470                    inner.vals.push(v);
471                }
472                if i + 1 < self.len() {
473                    inner
474                        .keys
475                        .extend(self.keys[i + 1..self.len()].iter().cloned());
476                    inner
477                        .vals
478                        .extend(self.vals[i + 1..self.len()].iter().cloned());
479                }
480                Update::Updated {
481                    elts,
482                    overflow: None,
483                    previous: Some(self.vals[i].clone()),
484                }
485            }
486            Loc::NotPresent(i) => {
487                let mut elts = Chunk::empty();
488                let inner = Arc::get_mut(&mut elts.0).unwrap();
489                inner.keys.extend(self.keys[0..i].iter().cloned());
490                inner.vals.extend(self.vals[0..i].iter().cloned());
491                let overflow = match f(q, d, None) {
492                    None => None,
493                    Some((k, v)) => {
494                        if inner.keys.len() == SIZE {
495                            let (ok, ov) =
496                                (inner.keys.pop().unwrap(), inner.vals.pop().unwrap());
497                            inner.keys.push(k);
498                            inner.vals.push(v);
499                            Some((ok, ov))
500                        } else {
501                            inner.keys.push(k);
502                            inner.vals.push(v);
503                            let mut iter = self.keys[i..self.len()]
504                                .iter()
505                                .cloned()
506                                .zip(self.vals[i..self.len()].iter().cloned());
507                            loop {
508                                match iter.next() {
509                                    None => break None,
510                                    Some((k, v)) => {
511                                        if inner.keys.len() < SIZE {
512                                            inner.keys.push(k);
513                                            inner.vals.push(v);
514                                        } else {
515                                            break Some((k, v));
516                                        }
517                                    }
518                                }
519                            }
520                        }
521                    }
522                };
523                Update::Updated {
524                    elts,
525                    overflow,
526                    previous: None,
527                }
528            }
529            loc @ Loc::InLeft | loc @ Loc::InRight => {
530                if !leaf || self.len() == SIZE {
531                    match loc {
532                        Loc::InLeft => Update::UpdateLeft(q, d),
533                        Loc::InRight => Update::UpdateRight(q, d),
534                        Loc::Here(..) | Loc::NotPresent(..) => unreachable!(),
535                    }
536                } else {
537                    let mut elts = Chunk::empty();
538                    let inner = Arc::get_mut(&mut elts.0).unwrap();
539                    match loc {
540                        Loc::InLeft => {
541                            if let Some((k, v)) = f(q, d, None) {
542                                inner.keys.push(k);
543                                inner.vals.push(v);
544                            }
545                            inner.keys.extend(self.keys[0..self.len()].iter().cloned());
546                            inner.vals.extend(self.vals[0..self.len()].iter().cloned());
547                        }
548                        Loc::InRight => {
549                            inner.keys.extend(self.keys[0..self.len()].iter().cloned());
550                            inner.vals.extend(self.vals[0..self.len()].iter().cloned());
551                            if let Some((k, v)) = f(q, d, None) {
552                                inner.keys.push(k);
553                                inner.vals.push(v);
554                            }
555                        }
556                        _ => unreachable!("bug"),
557                    };
558                    Update::Updated {
559                        elts,
560                        overflow: None,
561                        previous: None,
562                    }
563                }
564            }
565        }
566    }
567
568    pub(crate) fn update_mut<Q, D, F>(
569        &mut self,
570        q: Q,
571        d: D,
572        leaf: bool,
573        f: &mut F,
574    ) -> MutUpdate<Q, K, V, D>
575    where
576        Q: Ord,
577        K: Borrow<Q>,
578        F: FnMut(Q, D, Option<(&K, &V)>) -> Option<(K, V)>,
579    {
580        match self.get(&q) {
581            Loc::Here(i) => match f(q, d, Some((&self.keys[i], &self.vals[i]))) {
582                Some((k, v)) => {
583                    let inner = self.make_mut();
584                    inner.keys[i] = k;
585                    MutUpdate::Updated {
586                        overflow: None,
587                        previous: Some(mem::replace(&mut inner.vals[i], v)),
588                    }
589                }
590                None => {
591                    let inner = self.make_mut();
592                    inner.keys.remove(i);
593                    MutUpdate::Updated {
594                        overflow: None,
595                        previous: Some(inner.vals.remove(i)),
596                    }
597                }
598            },
599            Loc::NotPresent(i) => match f(q, d, None) {
600                Some((k, v)) => {
601                    let inner = self.make_mut();
602                    let overflow = if inner.keys.len() == SIZE {
603                        let (ok, ov) =
604                            (inner.keys.pop().unwrap(), inner.vals.pop().unwrap());
605                        inner.keys.insert(i, k);
606                        inner.vals.insert(i, v);
607                        Some((ok, ov))
608                    } else {
609                        inner.keys.insert(i, k);
610                        inner.vals.insert(i, v);
611                        None
612                    };
613                    MutUpdate::Updated {
614                        overflow,
615                        previous: None,
616                    }
617                }
618                None => MutUpdate::Updated {
619                    overflow: None,
620                    previous: None,
621                },
622            },
623            loc @ Loc::InLeft | loc @ Loc::InRight => {
624                if !leaf || self.len() == SIZE {
625                    match loc {
626                        Loc::InLeft => MutUpdate::UpdateLeft(q, d),
627                        Loc::InRight => MutUpdate::UpdateRight(q, d),
628                        Loc::Here(..) | Loc::NotPresent(..) => unreachable!(),
629                    }
630                } else {
631                    let inner = self.make_mut();
632                    match loc {
633                        Loc::InLeft => {
634                            if let Some((k, v)) = f(q, d, None) {
635                                inner.keys.insert(0, k);
636                                inner.vals.insert(0, v);
637                            }
638                        }
639                        Loc::InRight => {
640                            if let Some((k, v)) = f(q, d, None) {
641                                inner.keys.push(k);
642                                inner.vals.push(v);
643                            }
644                        }
645                        _ => unreachable!("bug"),
646                    };
647                    MutUpdate::Updated {
648                        overflow: None,
649                        previous: None,
650                    }
651                }
652            }
653        }
654    }
655
656    pub(crate) fn intersect<F>(
657        c0: &Chunk<K, V, SIZE>,
658        c1: &Chunk<K, V, SIZE>,
659        r: &mut Vec<(K, V)>,
660        f: &mut F,
661    ) where
662        F: FnMut(&K, &V, &V) -> Option<V>,
663    {
664        if c0.len() > 0 && c1.len() > 0 {
665            let (c0, c1) = if c0.len() < c1.len() {
666                (c0, c1)
667            } else {
668                (c1, c0)
669            };
670            r.extend(c0.keys.iter().enumerate().filter_map(|(i, k)| {
671                match c1.keys.binary_search(&k) {
672                    Err(_) => None,
673                    Ok(j) => f(k, &c0.vals[i], &c1.vals[j]).map(|v| (k.clone(), v)),
674                }
675            }))
676        }
677    }
678
679    pub(crate) fn remove_elt_at(&self, i: usize) -> Self {
680        let mut elts = Chunk::empty();
681        let t = Arc::get_mut(&mut elts.0).unwrap();
682        if i >= self.keys.len() {
683            panic!("remove_elt_at: out of bounds")
684        } else if self.len() == 1 {
685            elts
686        } else if i == 0 {
687            t.keys.extend(self.keys[1..self.len()].iter().cloned());
688            t.vals.extend(self.vals[1..self.len()].iter().cloned());
689            elts
690        } else if i == self.keys.len() - 1 {
691            t.keys.extend(self.keys[0..self.len() - 1].iter().cloned());
692            t.vals.extend(self.vals[0..self.len() - 1].iter().cloned());
693            elts
694        } else {
695            t.keys.extend(self.keys[0..i].iter().cloned());
696            t.keys.extend(self.keys[i + 1..self.len()].iter().cloned());
697            t.vals.extend(self.vals[0..i].iter().cloned());
698            t.vals.extend(self.vals[i + 1..self.len()].iter().cloned());
699            elts
700        }
701    }
702
703    pub(crate) fn remove_elt_at_mut(&mut self, i: usize) -> (K, V) {
704        if i >= self.len() {
705            panic!("remove_elt_at_mut: out of bounds")
706        } else {
707            let inner = self.make_mut();
708            let k = inner.keys.remove(i);
709            let v = inner.vals.remove(i);
710            (k, v)
711        }
712    }
713
714    pub(crate) fn append<I: IntoIterator<Item = (K, V)>>(&self, other: I) -> Self {
715        let mut elts = self.clone();
716        let inner = elts.make_mut();
717        for (k, v) in other {
718            if inner.keys.len() < SIZE {
719                inner.keys.push(k);
720                inner.vals.push(v);
721            }
722        }
723        elts
724    }
725
726    pub(crate) fn min_max_key(&self) -> Option<(K, K)> {
727        if self.len() == 0 {
728            None
729        } else {
730            Some((self.keys[0].clone(), self.keys[self.len() - 1].clone()))
731        }
732    }
733
734    pub(crate) fn min_elt(&self) -> Option<(&K, &V)> {
735        if self.len() == 0 {
736            None
737        } else {
738            Some((&self.keys[0], &self.vals[0]))
739        }
740    }
741
742    pub(crate) fn max_elt(&self) -> Option<(&K, &V)> {
743        if self.len() == 0 {
744            None
745        } else {
746            let last = self.len() - 1;
747            Some((&self.keys[last], &self.vals[last]))
748        }
749    }
750
751    pub(crate) fn len(&self) -> usize {
752        self.keys.len()
753    }
754
755    pub(crate) fn key(&self, i: usize) -> &K {
756        &self.keys[i]
757    }
758
759    pub(crate) fn val(&self, i: usize) -> &V {
760        &self.vals[i]
761    }
762
763    pub(crate) fn val_mut(&mut self, i: usize) -> &mut V {
764        &mut self.make_mut().vals[i]
765    }
766
767    pub(crate) fn kv(&self, i: usize) -> (&K, &V) {
768        (&self.keys[i], &self.vals[i])
769    }
770
771    pub(crate) fn to_vec(&self) -> Vec<(K, V)> {
772        self.into_iter()
773            .map(|(k, v)| (k.clone(), v.clone()))
774            .collect()
775    }
776}
777
778impl<K: Ord + Clone, V: Clone, const SIZE: usize> IntoIterator for Chunk<K, V, SIZE> {
779    type Item = (K, V);
780    type IntoIter = iter::Zip<arrayvec::IntoIter<K, SIZE>, arrayvec::IntoIter<V, SIZE>>;
781    fn into_iter(mut self) -> Self::IntoIter {
782        let inner = mem::replace(
783            self.make_mut(),
784            ChunkInner {
785                keys: ArrayVec::new(),
786                vals: ArrayVec::new(),
787            },
788        );
789        inner.keys.into_iter().zip(inner.vals.into_iter())
790    }
791}
792
793impl<'a, K: Ord + Clone, V: Clone, const SIZE: usize> IntoIterator
794    for &'a Chunk<K, V, SIZE>
795{
796    type Item = (&'a K, &'a V);
797    type IntoIter = iter::Zip<slice::Iter<'a, K>, slice::Iter<'a, V>>;
798    fn into_iter(self) -> Self::IntoIter {
799        (&self.keys).into_iter().zip(&self.vals)
800    }
801}
802
803impl<'a, K: Ord + Clone, V: Clone, const SIZE: usize> IntoIterator
804    for &'a mut Chunk<K, V, SIZE>
805{
806    type Item = (&'a K, &'a mut V);
807    type IntoIter = iter::Zip<slice::Iter<'a, K>, slice::IterMut<'a, V>>;
808    fn into_iter(self) -> Self::IntoIter {
809        let inner = self.make_mut();
810        (&inner.keys).into_iter().zip(&mut inner.vals)
811    }
812}
immutable_chunkmap/chunk.rs

immutable_chunkmap/
chunk.rs
