#![deny(missing_docs, trivial_numeric_casts, unused_extern_crates)]
#![warn(unused_import_braces)]
#![cfg_attr(feature = "clippy", plugin(clippy(conf_file = "../../clippy.toml")))]
#![cfg_attr(feature = "cargo-clippy", allow(clippy::new_without_default))]
#![cfg_attr(
feature = "cargo-clippy",
warn(
clippy::float_arithmetic,
clippy::mut_mut,
clippy::nonminimal_bool,
clippy::option_map_unwrap_or,
clippy::option_map_unwrap_or_else,
clippy::print_stdout,
clippy::unicode_not_nfc,
clippy::use_self
)
)]
#![no_std]
#[cfg(test)]
extern crate alloc;
#[macro_use]
extern crate cranelift_entity as entity;
use crate::entity::packed_option;
use core::borrow::BorrowMut;
use core::cmp::Ordering;
mod map;
mod node;
mod path;
mod pool;
mod set;
pub use self::map::{Map, MapCursor, MapForest, MapIter};
pub use self::set::{Set, SetCursor, SetForest, SetIter};
use self::node::NodeData;
use self::path::Path;
use self::pool::NodePool;
const INNER_SIZE: usize = 8;
const MAX_PATH: usize = 16;
pub trait Comparator<K>
where
K: Copy,
{
fn cmp(&self, a: K, b: K) -> Ordering;
fn search(&self, k: K, s: &[K]) -> Result<usize, usize> {
s.binary_search_by(|x| self.cmp(*x, k))
}
}
impl<K> Comparator<K> for ()
where
K: Copy + Ord,
{
fn cmp(&self, a: K, b: K) -> Ordering {
a.cmp(&b)
}
}
trait Forest {
type Key: Copy;
type Value: Copy;
type LeafKeys: Copy + BorrowMut<[Self::Key]>;
type LeafValues: Copy + BorrowMut<[Self::Value]>;
fn splat_key(key: Self::Key) -> Self::LeafKeys;
fn splat_value(value: Self::Value) -> Self::LeafValues;
}
#[derive(Clone, Copy, PartialEq, Eq)]
struct Node(u32);
entity_impl!(Node, "node");
#[derive(Clone, Copy)]
struct SetValue();
fn slice_insert<T: Copy>(s: &mut [T], i: usize, x: T) {
for j in (i + 1..s.len()).rev() {
s[j] = s[j - 1];
}
s[i] = x;
}
fn slice_shift<T: Copy>(s: &mut [T], n: usize) {
for j in 0..s.len() - n {
s[j] = s[j + n];
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::entity::EntityRef;
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Block(u32);
entity_impl!(Block, "block");
#[test]
fn comparator() {
let block1 = Block::new(1);
let block2 = Block::new(2);
let block3 = Block::new(3);
let block4 = Block::new(4);
let vals = [block1, block2, block4];
let comp = ();
assert_eq!(comp.search(block1, &vals), Ok(0));
assert_eq!(comp.search(block3, &vals), Err(2));
assert_eq!(comp.search(block4, &vals), Ok(2));
}
#[test]
fn slice_insertion() {
let mut a = ['a', 'b', 'c', 'd'];
slice_insert(&mut a[0..1], 0, 'e');
assert_eq!(a, ['e', 'b', 'c', 'd']);
slice_insert(&mut a, 0, 'a');
assert_eq!(a, ['a', 'e', 'b', 'c']);
slice_insert(&mut a, 3, 'g');
assert_eq!(a, ['a', 'e', 'b', 'g']);
slice_insert(&mut a, 1, 'h');
assert_eq!(a, ['a', 'h', 'e', 'b']);
}
#[test]
fn slice_shifting() {
let mut a = ['a', 'b', 'c', 'd'];
slice_shift(&mut a[0..1], 1);
assert_eq!(a, ['a', 'b', 'c', 'd']);
slice_shift(&mut a[1..], 1);
assert_eq!(a, ['a', 'c', 'd', 'd']);
slice_shift(&mut a, 2);
assert_eq!(a, ['d', 'd', 'd', 'd']);
}
}