use crate::encode::Encoder;
use crate::error::Error;
pub struct MapBuilder<'e, 'b, const N: usize> {
enc: &'e mut Encoder<'b>,
spans: [(u32, u32, u32); N],
count: usize,
}
impl<'e, 'b, const N: usize> MapBuilder<'e, 'b, N> {
#[must_use]
pub fn new(enc: &'e mut Encoder<'b>) -> Self {
Self { enc, spans: [(0, 0, 0); N], count: 0 }
}
pub fn add<K, V>(&mut self, key: K, value: V) -> Result<&mut Self, Error>
where
for<'x> K: FnOnce(&'x mut Encoder<'b>) -> Result<&'x mut Encoder<'b>, Error>,
for<'x> V: FnOnce(&'x mut Encoder<'b>) -> Result<&'x mut Encoder<'b>, Error>,
{
match self.count < N {
true => {}
false => return Err(Error::DEPTH_EXCEEDED),
}
let start = self.enc.written();
let enc: &'_ mut Encoder<'b> = &mut *self.enc;
key(enc)?;
let key_end = self.enc.written();
let enc: &'_ mut Encoder<'b> = &mut *self.enc;
value(enc)?;
self.spans[self.count] = (start as u32, key_end as u32, self.enc.written() as u32);
self.count += 1;
Ok(self)
}
pub fn finish(self, scratch: &mut [u8]) -> Result<&'e mut Encoder<'b>, Error> {
let order: [usize; N] = {
let buf: &[u8] = self.enc.buf;
let keys: [&[u8]; N] =
core::array::from_fn(|i| &buf[self.spans[i].0 as usize..self.spans[i].1 as usize]);
let mut order = [0usize; N];
for (i, slot) in order.iter_mut().enumerate() {
*slot = i;
}
for i in 1..self.count {
let mut j = i;
while j > 0 && keys[order[j - 1]] > keys[order[j]] {
order.swap(j - 1, j);
j -= 1;
}
}
order
};
if self.count == 0 {
return Ok(self.enc);
}
let region_start = self.spans[0].0 as usize;
let region_end = self.enc.written();
let sorted = order[..self.count].windows(2).all(|w| w[0] < w[1]);
if sorted {
return Ok(self.enc);
}
let region_len = region_end - region_start;
match region_len <= scratch.len() {
true => {}
false => return Err(Error::OUT_OF_SPACE),
}
scratch[..region_len].copy_from_slice(&self.enc.buf[region_start..region_end]);
let mut dst = region_start;
for &idx in &order[..self.count] {
let (ks, _, ve) = self.spans[idx];
let (ks, ve) = (ks as usize, ve as usize);
let len = ve - ks;
self.enc.buf[dst..dst + len]
.copy_from_slice(&scratch[ks - region_start..ve - region_start]);
dst += len;
}
debug_assert_eq!(dst, region_end);
Ok(self.enc)
}
}
#[cfg(test)]
mod tests {
use super::MapBuilder;
use crate::Encoder;
#[test]
fn canonical_reorder_produces_sorted_keys() {
let mut buf = [0u8; 64];
let mut enc = Encoder::new(&mut buf);
enc.map_len(2).unwrap();
let mut m = MapBuilder::<2>::new(&mut enc);
m.add(|k| k.str("bb"), |v| v.u8(1)).unwrap();
m.add(|k| k.str("aa"), |v| v.u8(2)).unwrap();
let enc = m.finish(&mut [0u8; 8]).unwrap();
let n = enc.written();
assert_eq!(&enc.buf[..n], &[0xa2, 0x62, b'a', b'a', 2, 0x62, b'b', b'b', 1]);
}
}