use crate::{XorName, XOR_NAME_LEN};
use core::{
borrow::Borrow,
cmp::{self, Ordering},
fmt::{Binary, Debug, Display, Formatter, Result as FmtResult},
hash::{Hash, Hasher},
ops::RangeInclusive,
str::FromStr,
};
use serde::{Deserialize, Serialize};
#[derive(Clone, Copy, Default, Eq, Deserialize, Serialize)]
pub struct Prefix {
bit_count: u16,
name: XorName,
}
impl Prefix {
pub fn new(bit_count: usize, name: XorName) -> Self {
Prefix {
bit_count: bit_count.min(8 * XOR_NAME_LEN) as u16,
name: name.set_remaining(bit_count as u8, false),
}
}
pub fn name(&self) -> XorName {
self.name
}
pub fn pushed(mut self, bit: bool) -> Self {
if self.bit_count < 8 * XOR_NAME_LEN as u16 {
self.name = self.name.with_bit(self.bit_count() as u8, bit);
self.bit_count += 1;
}
self
}
pub fn popped(mut self) -> Self {
if self.bit_count > 0 {
self.bit_count -= 1;
self.name = self.name.with_bit(self.bit_count() as u8, false);
}
self
}
pub fn bit_count(&self) -> usize {
self.bit_count as usize
}
pub fn is_empty(&self) -> bool {
self.bit_count == 0
}
pub fn is_compatible(&self, other: &Self) -> bool {
let i = self.name.common_prefix(&other.name);
i >= self.bit_count() || i >= other.bit_count()
}
pub fn is_extension_of(&self, other: &Self) -> bool {
let i = self.name.common_prefix(&other.name);
i >= other.bit_count() && self.bit_count() > other.bit_count()
}
pub fn is_neighbour(&self, other: &Self) -> bool {
let i = self.name.common_prefix(&other.name);
if i >= self.bit_count() || i >= other.bit_count() {
false
} else {
let j = self
.name
.with_flipped_bit(i as u8)
.common_prefix(&other.name);
j >= self.bit_count() || j >= other.bit_count()
}
}
pub fn common_prefix(&self, name: &XorName) -> usize {
cmp::min(self.bit_count(), self.name.common_prefix(name))
}
pub fn matches(&self, name: &XorName) -> bool {
self.name.common_prefix(name) >= self.bit_count()
}
pub fn cmp_distance(&self, other: &Self, target: &XorName) -> Ordering {
if self.is_compatible(other) {
Ord::cmp(&self.bit_count, &other.bit_count)
} else {
Ord::cmp(
&other.name.common_prefix(target),
&self.name.common_prefix(target),
)
}
}
pub fn cmp_breadth_first(&self, other: &Self) -> Ordering {
self.bit_count
.cmp(&other.bit_count)
.then_with(|| self.name.cmp(&other.name))
}
pub fn lower_bound(&self) -> XorName {
if self.bit_count() < 8 * XOR_NAME_LEN {
self.name.set_remaining(self.bit_count() as u8, false)
} else {
self.name
}
}
pub fn upper_bound(&self) -> XorName {
if self.bit_count() < 8 * XOR_NAME_LEN {
self.name.set_remaining(self.bit_count() as u8, true)
} else {
self.name
}
}
pub fn range_inclusive(&self) -> RangeInclusive<XorName> {
RangeInclusive::new(self.lower_bound(), self.upper_bound())
}
pub fn is_covered_by<'a, I>(&self, prefixes: I) -> bool
where
I: IntoIterator<Item = &'a Self> + Clone,
{
let max_prefix_len = prefixes
.clone()
.into_iter()
.map(Self::bit_count)
.max()
.unwrap_or(0);
self.is_covered_by_impl(prefixes, max_prefix_len)
}
fn is_covered_by_impl<'a, I>(&self, prefixes: I, max_prefix_len: usize) -> bool
where
I: IntoIterator<Item = &'a Self> + Clone,
{
prefixes
.clone()
.into_iter()
.any(|x| x.is_compatible(self) && x.bit_count() <= self.bit_count())
|| (self.bit_count() <= max_prefix_len
&& self
.pushed(false)
.is_covered_by_impl(prefixes.clone(), max_prefix_len)
&& self
.pushed(true)
.is_covered_by_impl(prefixes, max_prefix_len))
}
pub fn with_flipped_bit(&self, i: u8) -> Self {
if i as usize >= self.bit_count() {
*self
} else {
Self::new(self.bit_count(), self.name.with_flipped_bit(i))
}
}
pub fn substituted_in(&self, mut name: XorName) -> XorName {
for i in 0..self.bit_count() {
name = name.with_bit(i as u8, self.name.bit(i as u8));
}
name
}
pub fn sibling(&self) -> Self {
if self.bit_count() > 0 && self.bit_count() < 8 * XOR_NAME_LEN {
self.with_flipped_bit(self.bit_count() as u8 - 1)
} else {
*self
}
}
pub fn ancestor(&self, bit_count: u8) -> Self {
assert!((bit_count as usize) < self.bit_count());
Self::new(bit_count as usize, self.name)
}
pub fn ancestors(&self) -> Ancestors {
Ancestors {
target: *self,
current_len: 0,
}
}
}
impl PartialEq for Prefix {
fn eq(&self, other: &Self) -> bool {
self.is_compatible(other) && self.bit_count == other.bit_count
}
}
impl PartialOrd for Prefix {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Prefix {
fn cmp(&self, other: &Self) -> Ordering {
if self == other {
Ordering::Equal
} else if self.is_compatible(other) {
self.bit_count().cmp(&other.bit_count())
} else {
self.name.cmp(&other.name)
}
}
}
impl Hash for Prefix {
fn hash<H: Hasher>(&self, state: &mut H) {
for i in 0..self.bit_count() {
self.name.bit(i as u8).hash(state);
}
}
}
impl Binary for Prefix {
fn fmt(&self, formatter: &mut Formatter) -> FmtResult {
write!(formatter, "{0:1$b}", self.name, self.bit_count())
}
}
impl Debug for Prefix {
fn fmt(&self, formatter: &mut Formatter) -> FmtResult {
write!(formatter, "Prefix({:b})", self)
}
}
impl<T> Borrow<Prefix> for (Prefix, T) {
fn borrow(&self) -> &Prefix {
&self.0
}
}
#[derive(Debug)]
pub struct FromStrError {
pub invalid_char: char,
}
impl Display for FromStrError {
fn fmt(&self, formatter: &mut Formatter) -> FmtResult {
write!(
formatter,
"'{}' not allowed - the string must represent a binary number.",
self.invalid_char
)
}
}
impl FromStr for Prefix {
type Err = FromStrError;
fn from_str(bits: &str) -> Result<Self, Self::Err> {
let mut name = [0; XOR_NAME_LEN];
for (i, bit) in bits.chars().enumerate() {
if bit == '1' {
let byte = i / 8;
name[byte] |= 1 << (7 - i);
} else if bit != '0' {
return Err(FromStrError { invalid_char: bit });
}
}
Ok(Self::new(bits.len(), XorName(name)))
}
}
pub struct Ancestors {
target: Prefix,
current_len: usize,
}
impl Iterator for Ancestors {
type Item = Prefix;
fn next(&mut self) -> Option<Self::Item> {
if self.current_len < self.target.bit_count() {
let output = self.target.ancestor(self.current_len as u8);
self.current_len += 1;
Some(output)
} else {
None
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use rand::{rngs::SmallRng, seq::SliceRandom, SeedableRng};
#[test]
fn prefix() {
assert_eq!(parse("101").pushed(true), parse("1011"));
assert_eq!(parse("101").pushed(false), parse("1010"));
assert_eq!(parse("1011").popped(), parse("101"));
assert!(parse("101").is_compatible(&parse("1010")));
assert!(parse("1010").is_compatible(&parse("101")));
assert!(!parse("1010").is_compatible(&parse("1011")));
assert!(parse("101").is_neighbour(&parse("1111")));
assert!(!parse("1010").is_neighbour(&parse("1111")));
assert!(parse("1010").is_neighbour(&parse("10111")));
assert!(!parse("101").is_neighbour(&parse("10111")));
assert!(parse("101").matches(&xor_name!(0b10101100)));
assert!(!parse("1011").matches(&xor_name!(0b10101100)));
assert_eq!(parse("0101").lower_bound(), xor_name!(0b01010000));
assert_eq!(
parse("0101").upper_bound(),
xor_name!(
0b01011111, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255
)
);
assert_eq!(Prefix::new(256, xor_name!(0)).bit_count(), 256);
assert_eq!(Prefix::new(257, xor_name!(0)).bit_count(), 256);
}
#[test]
fn breadth_first_order() {
let expected = [
parse(""),
parse("0"),
parse("1"),
parse("00"),
parse("01"),
parse("10"),
parse("11"),
parse("000"),
parse("001"),
parse("010"),
parse("011"),
parse("100"),
parse("101"),
parse("110"),
parse("111"),
];
let mut rng = SmallRng::from_entropy();
for _ in 0..100 {
let mut actual = expected;
actual.shuffle(&mut rng);
actual.sort_by(|lhs, rhs| lhs.cmp_breadth_first(rhs));
assert_eq!(actual, expected);
}
}
#[test]
fn ancestors() {
let mut ancestors = parse("").ancestors();
assert_eq!(ancestors.next(), None);
let mut ancestors = parse("0").ancestors();
assert_eq!(ancestors.next(), Some(parse("")));
assert_eq!(ancestors.next(), None);
let mut ancestors = parse("01").ancestors();
assert_eq!(ancestors.next(), Some(parse("")));
assert_eq!(ancestors.next(), Some(parse("0")));
assert_eq!(ancestors.next(), None);
let mut ancestors = parse("011").ancestors();
assert_eq!(ancestors.next(), Some(parse("")));
assert_eq!(ancestors.next(), Some(parse("0")));
assert_eq!(ancestors.next(), Some(parse("01")));
assert_eq!(ancestors.next(), None);
}
#[test]
fn format_binary() {
assert_eq!(&format!(0, "{:b}", parse("")), "");
assert_eq!(&format!(1, "{:b}", parse("0")), "0");
assert_eq!(&format!(2, "{:b}", parse("00")), "00");
assert_eq!(&format!(2, "{:b}", parse("01")), "01");
assert_eq!(&format!(2, "{:b}", parse("10")), "10");
assert_eq!(&format!(2, "{:b}", parse("11")), "11");
assert_eq!(&format!(7, "{:b}", parse("1100101")), "1100101");
}
fn parse(input: &str) -> Prefix {
Prefix::from_str(input).unwrap()
}
}