use std::cmp::{max, Ordering};
use std::convert::{TryFrom, TryInto};
use std::fmt::{
self, Binary, Debug, Display, Formatter, LowerHex, Octal, UpperHex,
};
use std::hash::{Hash, Hasher};
use std::io;
use std::ops::{BitAnd, BitOr, BitXor};
use std::str::FromStr;
use strict_encoding::{StrictDecode, StrictEncode};
pub type FlagNo = u16;
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct FlagRef<'a> {
byte: &'a u8,
bit: u8,
}
#[derive(Clone)]
pub struct FlagVec(Vec<u8>);
impl BitOr for FlagVec {
type Output = Self;
fn bitor(self, mut rhs: Self) -> Self::Output {
let mut lhs = self.shrunk();
rhs.shrink();
let size = max(lhs.capacity(), rhs.capacity());
lhs.enlarge(size);
rhs.enlarge(size);
for i in 0..rhs.0.len() {
rhs.0[i] = lhs.0[i] | rhs.0[i];
}
rhs
}
}
impl BitAnd for FlagVec {
type Output = Self;
fn bitand(self, mut rhs: Self) -> Self::Output {
let mut lhs = self.shrunk();
rhs.shrink();
let size = max(lhs.capacity(), rhs.capacity());
lhs.enlarge(size);
rhs.enlarge(size);
for i in 0..rhs.0.len() {
rhs.0[i] = lhs.0[i] & rhs.0[i];
}
rhs
}
}
impl BitXor for FlagVec {
type Output = Self;
fn bitxor(self, mut rhs: Self) -> Self::Output {
let mut lhs = self.shrunk();
rhs.shrink();
let size = max(lhs.capacity(), rhs.capacity());
lhs.enlarge(size);
rhs.enlarge(size);
for i in 0..rhs.0.len() {
rhs.0[i] = lhs.0[i] ^ rhs.0[i];
}
rhs
}
}
impl Default for FlagVec {
fn default() -> Self {
FlagVec::new()
}
}
impl PartialEq for FlagVec {
fn eq(&self, other: &Self) -> bool {
self.shrunk().0 == other.shrunk().0
}
}
impl Eq for FlagVec {}
impl PartialOrd for FlagVec {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for FlagVec {
fn cmp(&self, other: &Self) -> Ordering {
self.shrunk().0.cmp(&other.shrunk().0)
}
}
impl Hash for FlagVec {
fn hash<H: Hasher>(&self, state: &mut H) {
self.shrunk().0.hash(state)
}
}
impl Debug for FlagVec {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
let mut shrunk = self.clone();
if f.alternate() {
f.write_str("flags:")?;
shrunk.shrink();
}
for b in 0..shrunk.capacity() {
write!(f, "{}", if self.is_set(b) { '1' } else { '0' })?;
}
Ok(())
}
}
impl Display for FlagVec {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
let mut shrunk = self.clone();
let (p, n) = if f.alternate() {
shrunk.shrink();
('#', '_')
} else {
('+', '-')
};
for b in 0..shrunk.capacity() {
write!(f, "{}", if shrunk.is_set(b) { p } else { n })?;
}
Ok(())
}
}
impl LowerHex for FlagVec {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
let mut shrunk = self.clone();
if f.alternate() {
f.write_str("0x")?;
shrunk.shrink();
}
for b in shrunk.0 {
write!(f, "{:02x}", b)?;
}
Ok(())
}
}
impl UpperHex for FlagVec {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
let mut shrunk = self.clone();
if f.alternate() {
f.write_str("0x")?;
shrunk.shrink();
}
for b in shrunk.0 {
write!(f, "{:02X}", b)?;
}
Ok(())
}
}
impl Binary for FlagVec {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
let mut shrunk = self.clone();
if f.alternate() {
f.write_str("0b")?;
shrunk.shrink();
}
for b in shrunk.0 {
write!(f, "{:08b}", b)?;
}
Ok(())
}
}
impl Octal for FlagVec {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
let mut shrunk = self.clone();
if f.alternate() {
f.write_str("0o")?;
shrunk.shrink();
}
for b in shrunk.0 {
write!(f, "{:03o}", b)?;
}
Ok(())
}
}
#[derive(
Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Display, Error,
)]
#[display(doc_comments)]
pub struct ParseError;
impl FromStr for FlagVec {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut vec = Vec::with_capacity(s.len());
for c in s.chars() {
vec.push(match c {
'1' | '+' | '*' | '#' => 1,
'0' | '-' | '!' | '_' => 0,
' ' | '\n' | '\t' | '\r' => continue,
_ => return Err(ParseError),
})
}
vec.try_into()
}
}
impl TryFrom<Vec<u8>> for FlagVec {
type Error = ParseError;
fn try_from(value: Vec<u8>) -> Result<Self, Self::Error> {
Self::try_from(&value[..])
}
}
impl TryFrom<&[u8]> for FlagVec {
type Error = ParseError;
fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
let mut vec = FlagVec::with_capacity(value.len() as FlagNo);
for (i, v) in value.iter().enumerate() {
match v {
1 => vec.set(i as FlagNo),
0 => false,
_ => return Err(ParseError),
};
}
Ok(vec)
}
}
impl StrictEncode for FlagVec {
#[inline]
fn strict_encode<E: io::Write>(
&self,
e: E,
) -> Result<usize, strict_encoding::Error> {
self.shrunk().0.strict_encode(e)
}
}
impl StrictDecode for FlagVec {
#[inline]
fn strict_decode<D: io::Read>(
d: D,
) -> Result<Self, strict_encoding::Error> {
Ok(Self(StrictDecode::strict_decode(d)?))
}
}
impl FlagVec {
fn bits_to_bytes(bits: FlagNo) -> usize {
if bits == 0 {
0
} else {
((bits - 1) / 8 + 1) as usize
}
}
pub fn new() -> FlagVec {
FlagVec(vec![])
}
pub fn with_capacity(upto: FlagNo) -> Self {
if upto == 0 {
FlagVec::default()
} else {
FlagVec(vec![0u8; Self::bits_to_bytes(upto)])
}
}
pub fn shrunk(&self) -> Self {
let mut shrinked = self.clone();
shrinked.shrink();
shrinked
}
#[inline]
pub fn iter(&self) -> AllSet {
AllSet::new(&self)
}
#[inline]
pub fn known_iter(&self, mut known: FlagVec) -> FilteredIter {
known.enlarge(self.capacity());
FilteredIter::new(&self, known)
}
#[inline]
pub fn unknown_iter(&self, mut known: FlagVec) -> FilteredIter {
known.enlarge(self.capacity());
for byte in 0..self.0.len() {
known.0[byte as usize] = !known.0[byte as usize];
}
FilteredIter::new(&self, known)
}
#[inline]
pub(self) fn capacity(&self) -> FlagNo {
(self.0.len() * 8) as FlagNo
}
#[inline]
fn enlarge(&mut self, upto: FlagNo) -> bool {
if upto <= self.capacity() {
return false;
}
let old = self.0.clone();
self.0 = vec![0u8; Self::bits_to_bytes(upto)];
self.0[..old.len()].copy_from_slice(&old);
return true;
}
#[inline]
pub fn shrink(&mut self) -> bool {
let capacity = self.capacity();
if capacity == 0 {
return false;
}
let mut top = 1;
while top < capacity && !self.is_set(capacity - top) {
top += 1;
}
let top = capacity - top;
let used = Self::bits_to_bytes(top);
if used < self.0.len() {
let old = self.0.clone();
self.0 = vec![0u8; used as usize];
self.0.copy_from_slice(&old[..used]);
return true;
}
return false;
}
#[inline]
fn byte_at(&self, flag_no: FlagNo) -> Option<&u8> {
if flag_no >= self.capacity() {
return None;
}
Some(&self.0[flag_no as usize / 8])
}
#[inline]
fn mut_byte_at(&mut self, flag_no: FlagNo) -> &mut u8 {
self.enlarge(flag_no);
&mut self.0[flag_no as usize / 8]
}
#[inline]
pub fn is_set(&self, flag_no: FlagNo) -> bool {
self.byte_at(flag_no)
.map(|byte| (byte & (1 << (flag_no % 8))) > 0)
.unwrap_or(false)
}
#[inline]
pub fn set(&mut self, flag_no: FlagNo) -> bool {
let byte = self.mut_byte_at(flag_no);
let mask = 1u8 << (flag_no % 8);
let was = *byte & mask;
*byte = *byte | mask;
was > 0
}
#[inline]
pub fn unset(&mut self, flag_no: FlagNo) -> bool {
let byte = self.mut_byte_at(flag_no);
let mask = 1u8 << (flag_no % 8);
let was = *byte & mask;
*byte = *byte & (!mask);
was > 0
}
#[inline]
pub fn invert(&mut self, flag_no: FlagNo) {
let byte = self.mut_byte_at(flag_no);
let mask = 1u8 << (flag_no % 8);
let was = *byte & mask;
*byte = (*byte ^ was) | (mask ^ was);
}
}
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct AllSet<'a> {
features: &'a FlagVec,
offset: FlagNo,
}
impl<'a> AllSet<'a> {
#[inline]
pub fn new(features: &'a FlagVec) -> Self {
Self {
features,
offset: 0,
}
}
}
impl Iterator for AllSet<'_> {
type Item = FlagNo;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
while self.offset < self.features.capacity() {
self.offset += 1;
if self.features.is_set(self.offset - 1) {
return Some(self.offset - 1);
}
}
None
}
}
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct FilteredIter<'a> {
features: &'a FlagVec,
filter: FlagVec,
offset: FlagNo,
}
impl<'a> FilteredIter<'a> {
#[inline]
pub fn new(features: &'a FlagVec, filter: FlagVec) -> Self {
Self {
features,
filter,
offset: 0,
}
}
}
impl Iterator for FilteredIter<'_> {
type Item = FlagNo;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
while self.offset < self.features.capacity() {
self.offset += 1;
if self.features.is_set(self.offset - 1)
&& self.filter.is_set(self.offset - 1)
{
return Some(self.offset - 1);
}
}
None
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_flag_init() {
let empty_vec = Vec::<FlagNo>::new();
let f1 = FlagVec::default();
let f2 = FlagVec::new();
let f3 = FlagVec::with_capacity(0);
assert_eq!(f1, f2);
assert_eq!(f1, f3);
assert_eq!(f2, f3);
assert_eq!(f1.capacity(), 0);
assert_eq!(f1.iter().collect::<Vec<_>>(), empty_vec);
assert_eq!(f2.capacity(), 0);
assert_eq!(f2.iter().collect::<Vec<_>>(), empty_vec);
assert_eq!(f3.capacity(), 0);
assert_eq!(f3.iter().collect::<Vec<_>>(), empty_vec);
let f4 = FlagVec::with_capacity(10);
assert_eq!(f1, f4);
assert_eq!(f4.capacity(), 16);
assert_eq!(f4.iter().collect::<Vec<_>>(), empty_vec);
}
#[test]
fn test_flag_capacity() {
let mut f1 = FlagVec::with_capacity(10);
assert_eq!(f1.capacity(), 16);
let mut f2 = f1.clone();
assert_eq!(f2.capacity(), 16);
f2 = f1.shrunk();
f1.shrink();
assert_eq!(f1.capacity(), 0);
assert_eq!(f1, f2);
f1.enlarge(20);
assert_eq!(f1.capacity(), 24);
}
#[test]
fn test_flag_ops() {
let mut f1 = FlagVec::with_capacity(10);
assert_eq!(f1.is_set(33), false);
assert_eq!(f1.capacity(), 16);
assert_eq!(f1.set(2), false);
assert_eq!(f1.is_set(2), true);
assert_eq!(f1.unset(2), true);
assert_eq!(f1.is_set(2), false);
assert_eq!(f1.set(7), false);
f1.shrink();
assert_eq!(f1.capacity(), 8);
assert_eq!(f1.set(22), false);
assert_eq!(f1.is_set(22), true);
assert_eq!(f1.capacity(), 24);
assert_eq!(f1.invert(22), ());
assert_eq!(f1.is_set(22), false);
assert_eq!(f1.capacity(), 24);
f1.shrink();
assert_eq!(f1.capacity(), 8);
}
#[test]
fn test_fmt() {
let mut f1 = FlagVec::from_str("-0-\t#__1 \n--\r+* +!").unwrap();
assert_eq!(f1.is_set(0), false);
assert_eq!(f1.is_set(1), false);
assert_eq!(f1.is_set(2), false);
assert_eq!(f1.is_set(3), true);
assert_eq!(f1.is_set(4), false);
assert_eq!(f1.is_set(5), false);
assert_eq!(f1.is_set(6), true);
assert_eq!(f1.is_set(7), false);
assert_eq!(f1.is_set(8), false);
assert_eq!(f1.is_set(9), true);
assert_eq!(f1.is_set(10), true);
assert_eq!(f1.is_set(11), true);
assert_eq!(f1.is_set(12), false);
assert_eq!(f1.capacity(), 16);
assert_eq!(format!("{}", f1), "---+--+--+++----");
assert_eq!(format!("{:#}", f1), "___#__#__###____");
assert_eq!(format!("{:?}", f1), "0001001001110000");
assert_eq!(format!("{:x}", f1), "480e");
assert_eq!(format!("{:X}", f1), "480E");
assert_eq!(format!("{:b}", f1), "0100100000001110");
assert_eq!(format!("{:o}", f1), "110016");
f1.enlarge(22);
assert_eq!(format!("{}", f1), "---+--+--+++------------");
assert_eq!(format!("{:#}", f1), "___#__#__###____");
assert_eq!(format!("{:?}", f1), "000100100111000000000000");
assert_eq!(format!("{:#?}", f1), "flags:0001001001110000");
assert_eq!(format!("{:#x}", f1), "0x480e");
assert_eq!(format!("{:#X}", f1), "0x480E");
assert_eq!(format!("{:#b}", f1), "0b0100100000001110");
assert_eq!(format!("{:#o}", f1), "0o110016");
}
#[test]
fn test_filtered() {
let f1 = FlagVec::from_str("---+--+--+++-").unwrap();
let f2 = FlagVec::from_str("-+++-+---+-++--+").unwrap();
assert_eq!(
f2.iter().collect::<Vec<_>>(),
vec![1u16, 2, 3, 5, 9, 11, 12, 15]
);
assert_eq!(
f2.known_iter(f1.clone()).collect::<Vec<_>>(),
vec![3u16, 9, 11]
);
assert_eq!(
f2.unknown_iter(f1).collect::<Vec<_>>(),
vec![1u16, 2, 5, 12, 15]
);
}
#[test]
fn test_binary_and() {
let f1 = FlagVec::from_str("---+--+--+++-").unwrap();
let f2 = FlagVec::from_str("-+++-+---+-++--+").unwrap();
assert_eq!(
f1.clone() & f2.clone(),
FlagVec::from_str("---+-----+-+----").unwrap()
);
}
#[test]
fn test_binary_or() {
let f1 = FlagVec::from_str("---+--+--+++-").unwrap();
let f2 = FlagVec::from_str("-+++-+---+-++--+").unwrap();
assert_eq!(
f1.clone() | f2.clone(),
FlagVec::from_str("-+++-++--++++--+").unwrap()
);
}
#[test]
fn test_binary_xor() {
let f1 = FlagVec::from_str("---+--+--+++-").unwrap();
let f2 = FlagVec::from_str("-+++-+---+-++--+").unwrap();
assert_eq!(
f1.clone() ^ f2.clone(),
FlagVec::from_str("-++--++---+-+--+").unwrap()
);
}
}