orphanage 0.5.6

use std::fmt::Write;

use paste::paste;


pub trait UnsignedExt {
  type Type;

  /// Round down integer to its closes power-of-two.
  fn round_down_to_pow2(self) -> Self::Type;

  /// Convert integer to a string of bit blocks.
  fn to_str_ranges(self) -> String;

  /// Return an integer from a bit flags string.
  ///
  /// # Errors
  fn from_str_ranges(s: &str) -> Result<Self::Type, String>;

  /// Generate a vector of all bit indexes containing a `1`.
  fn bitidx_vec(self) -> Vec<usize>;
}


/// Given an array of (sorted) indexes, generate a vector of contiguous blocks.
///
/// Each block is inclusive-inclusive.
#[must_use]
pub fn usize_list_to_ranges(numbers: &[usize]) -> Vec<(usize, usize)> {
  let mut result = Vec::with_capacity(numbers.len());

  if numbers.is_empty() {
    return result;
  }

  let mut numbers_iter = numbers.iter().peekable();

  while let Some(&num) = numbers_iter.next() {
    let start = num;
    let mut end = num;

    while let Some(&&next_num) = numbers_iter.peek() {
      if next_num == end + 1 {
        end = next_num;
        numbers_iter.next();
      } else {
        break;
      }
    }

    if start == end {
      result.push((start, start));
    } else {
      result.push((start, end));
    }
  }

  result
}

#[must_use]
pub fn ranges_to_str(blocks: &[(usize, usize)]) -> String {
  let mut res = String::new();
  if blocks.is_empty() {
    return res;
  }

  let mut it = blocks.iter().peekable();

  while let Some((start, end)) = it.next() {
    if start == end {
      res.push_str(&start.to_string());
    } else {
      let _ = write!(res, "{start}-{end}");
    }

    if it.peek().is_some() {
      res.push(',');
    }
  }

  res
}

/// # Errors
pub fn str_to_ranges(s: &str) -> Result<Vec<(usize, usize)>, String> {
  if s.is_empty() {
    return Ok(Vec::new());
  }

  let mut ret = Vec::new();

  for blk in s.split(',') {
    // blk can either be "N" or "N-M"
    if let Some((first, last)) = blk.split_once('-') {
      let n = first.parse::<usize>().map_err(|e| e.to_string())?;
      let m = last.parse::<usize>().map_err(|e| e.to_string())?;
      if m < n {
        return Err("Range end before start".into());
      }
      ret.push((n, m));
    } else {
      let n = blk.parse::<usize>().map_err(|e| e.to_string())?;
      ret.push((n, n));
    }
  }

  if !verify_blocks_order(&ret) {
    return Err("Overlapping ranges".into());
  }

  Ok(ret)
}

fn verify_blocks_order(blocks: &[(usize, usize)]) -> bool {
  if blocks.is_empty() {
    return true;
  }

  let mut it = blocks.iter().peekable();

  loop {
    let Some(blk) = it.next() else {
      break true;
    };
    if let Some(next) = it.peek() {
      if blk.1 > next.0 {
        return false;
      }
    }
  }
}

#[must_use]
pub fn ranges_to_usize_list(numbers: &[(usize, usize)]) -> Vec<usize> {
  let mut ret = Vec::new();
  for blk in numbers {
    for idx in blk.0..=blk.1 {
      ret.push(idx);
    }
  }
  ret
}


macro_rules! impl_unsigned_ext {
  ($int_type:ident) => {
    paste! {
      #[must_use]
      pub const fn [<$int_type _round_down_to_pow2>](val: $int_type)
            -> $int_type {
        if val == 0 {
          return 0;
        }
        let n = val.leading_zeros();
        let nshift = $int_type::BITS - n - 1;
        1 << nshift
      }
    }

    paste! {
      #[must_use]
      pub fn [<$int_type _bitidx_vec>](bits: $int_type) -> Vec<usize> {
        let nbits = $int_type::BITS as usize;
        let mut ret = Vec::with_capacity(nbits);
        for idx in 0..nbits {
          if bits & (1 << idx) != 0 {
            ret.push(idx);
          }
        }
        ret
      }
    }

    paste! {
      #[must_use]
      pub fn [<$int_type _from_bits_list>](bits: &[usize]) -> $int_type {
        bits.iter().fold(0, |acc, x| acc | 1 << x)
      }
    }

    paste! {
      /// # Errors
      pub fn [<$int_type _from_str_ranges>](
          s: &str
      ) -> Result<$int_type, String> {
        let blocks = str_to_ranges(s)?;
        let bitlist = ranges_to_usize_list(&blocks);
        Ok([<$int_type _from_bits_list>](&bitlist))
      }
    }

    paste! {
      impl UnsignedExt for $int_type {
        type Type = $int_type;

        #[inline]
        fn round_down_to_pow2(self) -> Self::Type {
          [<$int_type _round_down_to_pow2>](self)
        }

        #[inline]
        fn to_str_ranges(self) -> String {
          let bv = self.bitidx_vec();
          let blocks = usize_list_to_ranges(&bv);
          ranges_to_str(&blocks)
        }

        #[inline]
        fn from_str_ranges(s: &str) -> Result<Self::Type, String> {
          [<$int_type _from_str_ranges>](s)
        }

        #[inline]
        fn bitidx_vec(self) -> Vec<usize> {
          [<$int_type _bitidx_vec>](self)
        }
      }
    }
  };
}

impl_unsigned_ext! { u8 }
impl_unsigned_ext! { u16 }
impl_unsigned_ext! { u32 }
impl_unsigned_ext! { u64 }
impl_unsigned_ext! { usize }


#[cfg(test)]
mod tests {
  use super::*;
  use rand::RngExt;

  #[test]
  fn bitidxvec() {
    let v = u32_bitidx_vec(0);
    assert_eq!(v.len(), 0);

    let v = u32_bitidx_vec(1);
    assert_eq!(&v, &[0]);

    let v = u32_bitidx_vec(2);
    assert_eq!(&v, &[1]);

    let v = u32_bitidx_vec(3);
    assert_eq!(&v, &[0, 1]);

    let v = u32_bitidx_vec(4);
    assert_eq!(&v, &[2]);
  }

  #[test]
  fn to_range_blocks() {
    let v = u32_bitidx_vec(0);
    let v2 = usize_list_to_ranges(&v);
    assert_eq!(v2.len(), 0);

    let v = u32_bitidx_vec(1);
    let v2 = usize_list_to_ranges(&v);
    assert_eq!(&v2, &[(0, 0)]);

    let v = u32_bitidx_vec(2);
    let v2 = usize_list_to_ranges(&v);
    assert_eq!(&v2, &[(1, 1)]);

    let v = u32_bitidx_vec(3);
    let v2 = usize_list_to_ranges(&v);
    assert_eq!(&v2, &[(0, 1)]);
  }

  #[test]
  fn to_ranges_str() {
    let v = u32_bitidx_vec(0);
    let v2 = usize_list_to_ranges(&v);
    let s = ranges_to_str(&v2);
    assert!(s.is_empty());

    let v = u32_bitidx_vec(1);
    let v2 = usize_list_to_ranges(&v);
    let s = ranges_to_str(&v2);
    assert_eq!(&s, "0");

    let v = u32_bitidx_vec(2);
    let v2 = usize_list_to_ranges(&v);
    let s = ranges_to_str(&v2);
    assert_eq!(&s, "1");

    let v = u32_bitidx_vec(3);
    let v2 = usize_list_to_ranges(&v);
    let s = ranges_to_str(&v2);
    assert_eq!(&s, "0-1");

    let v = u32_bitidx_vec(4);
    let v2 = usize_list_to_ranges(&v);
    let s = ranges_to_str(&v2);
    assert_eq!(&s, "2");

    let v = u32_bitidx_vec(5);
    let v2 = usize_list_to_ranges(&v);
    let s = ranges_to_str(&v2);
    assert_eq!(&s, "0,2");

    let v = u32_bitidx_vec(1 + 2 + 8 + 16);
    let v2 = usize_list_to_ranges(&v);
    let s = ranges_to_str(&v2);
    assert_eq!(&s, "0-1,3-4");
  }

  #[test]
  fn round_down_to_pow2() {
    assert_eq!(u8::round_down_to_pow2(0), 0);
    assert_eq!(u8::round_down_to_pow2(1), 1);
    assert_eq!(u8::round_down_to_pow2(2), 2);
    assert_eq!(u8::round_down_to_pow2(3), 2);

    assert_eq!(u16::round_down_to_pow2(0), 0);
    assert_eq!(u16::round_down_to_pow2(1), 1);
    assert_eq!(u16::round_down_to_pow2(2), 2);
    assert_eq!(u16::round_down_to_pow2(3), 2);

    assert_eq!(u32::round_down_to_pow2(0), 0);
    assert_eq!(u32::round_down_to_pow2(1), 1);
    assert_eq!(u32::round_down_to_pow2(2), 2);
    assert_eq!(u32::round_down_to_pow2(3), 2);

    assert_eq!(u64::round_down_to_pow2(0), 0);
    assert_eq!(u64::round_down_to_pow2(1), 1);
    assert_eq!(u64::round_down_to_pow2(2), 2);
    assert_eq!(u64::round_down_to_pow2(3), 2);
  }

  #[test]
  fn u8_str_ranges() {
    let s = "";
    let val = u8::from_str_ranges(s).unwrap();
    assert_eq!(val, 0);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "0-7";
    let val = u8::from_str_ranges(s).unwrap();
    assert_eq!(val, u8::MAX);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "0";
    let val = u8::from_str_ranges(s).unwrap();
    assert_eq!(val, 1);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "1";
    let val = u8::from_str_ranges(s).unwrap();
    assert_eq!(val, 2);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);
  }

  #[test]
  fn u16_str_ranges() {
    let s = "";
    let val = u16::from_str_ranges(s).unwrap();
    assert_eq!(val, 0);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "0-15";
    let val = u16::from_str_ranges(s).unwrap();
    assert_eq!(val, u16::MAX);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "0";
    let val = u16::from_str_ranges(s).unwrap();
    assert_eq!(val, 1);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "1";
    let val = u16::from_str_ranges(s).unwrap();
    assert_eq!(val, 2);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);
  }

  #[test]
  fn u32_str_ranges() {
    let s = "";
    let val = u32::from_str_ranges(s).unwrap();
    assert_eq!(val, 0);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "0-31";
    let val = u32::from_str_ranges(s).unwrap();
    assert_eq!(val, u32::MAX);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "0";
    let val = u32::from_str_ranges(s).unwrap();
    assert_eq!(val, 1);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "1";
    let val = u32::from_str_ranges(s).unwrap();
    assert_eq!(val, 2);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "0-3,5,7-10";
    let val = u32::from_str_ranges(s).unwrap();
    assert_eq!(val, 0b1111 | 0b1 << 5 | 0b1111 << 7);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);
  }

  #[test]
  fn u64_str_ranges() {
    let s = "";
    let val = u64::from_str_ranges(s).unwrap();
    assert_eq!(val, 0);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "0-63";
    let val = u64::from_str_ranges(s).unwrap();
    assert_eq!(val, u64::MAX);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "0";
    let val = u64::from_str_ranges(s).unwrap();
    assert_eq!(val, 1);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "1";
    let val = u64::from_str_ranges(s).unwrap();
    assert_eq!(val, 2);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);
  }

  #[test]
  fn usize_str_ranges() {
    let s = "";
    let val = usize::from_str_ranges(s).unwrap();
    assert_eq!(val, 0);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = format!("0-{}", usize::BITS - 1);
    let val = usize::from_str_ranges(&s).unwrap();
    assert_eq!(val, usize::MAX);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "0";
    let val = usize::from_str_ranges(s).unwrap();
    assert_eq!(val, 1);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);

    let s = "1";
    let val = usize::from_str_ranges(s).unwrap();
    assert_eq!(val, 2);
    let s2 = val.to_str_ranges();
    assert_eq!(s, s2);
  }

  #[test]
  fn rndbits() {
    let mut rng = rand::rng();
    for _ in 0..65546 {
      let val = rng.random::<u8>();
      let s = val.to_str_ranges();
      let val2 = u8::from_str_ranges(&s).unwrap();
      assert_eq!(val, val2);

      let val = rng.random::<u16>();
      let s = val.to_str_ranges();
      let val2 = u16::from_str_ranges(&s).unwrap();
      assert_eq!(val, val2);

      let val = rng.random::<u32>();
      let s = val.to_str_ranges();
      let val2 = u32::from_str_ranges(&s).unwrap();
      assert_eq!(val, val2);

      let val = rng.random::<u64>();
      let s = val.to_str_ranges();
      let val2 = u64::from_str_ranges(&s).unwrap();
      assert_eq!(val, val2);
    }
  }
}

// vim: set ft=rust et sw=2 ts=2 sts=2 cinoptions=2 tw=79 :