Iterator for Binary Indexed Tree

bit_iter.rs

struct BITIter {
  start: i64,
  end: i64
}

impl BITIter {
  fn new(start: usize, end: usize) -> Self {
    BITIter { start: start as i64, end: end as i64 }
  }
}

impl std::iter::Iterator for BITIter {
  type Item = usize;

  fn next(&mut self) -> Option<Self::Item> {
    let ret = self.start;
    if ret <= 0 || self.end <= ret {
      return None;
    }
    self.start += least_significant_bit(self.start);
    Some(ret as usize)
  }
}

impl std::iter::DoubleEndedIterator for BITIter {
  fn next_back(&mut self) -> Option<Self::Item> {
    let ret = self.end;
    if ret <= self.start {
      return None;
    }
    self.end -= least_significant_bit(self.end);
    Some(ret as usize)
  }
}