Struct algorithm::BitMap

source ·

pub struct BitMap { /* private fields */ }

Expand description

位图类，根据访问的位看是否被占用解决经典的是否被占用的问题，但是相对占用大小会较大

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add_many(&vec![1, 2, 3, 4, 10]);
    assert!(map.contains(&1));
    assert!(!map.contains(&5));
    assert!(map.contains(&10));
    map.add_range(7, 16);
    assert!(!map.contains(&6));
    assert!(map.contains(&7));
    assert!(map.contains(&16));
    assert!(!map.contains(&17));
}

Implementations§

source §

pub fn add(&mut self, val: usize) -> bool

添加新的元素

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add(1);
    assert!(map.contains(&1));
    assert!(map.len() == 1);
}

source

pub fn add_many(&mut self, val: &[usize])

添加许多新的元素

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add_many(&vec![1, 2, 3, 4, 10]);
    assert!(map.contains(&1));
    assert!(map.contains(&10));
    assert!(map.len() == 5);
}

source

pub fn add_range(&mut self, start: usize, end: usize)

添加范围内的元素(包含头与结果)，批量添加增加效率

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add_range(7, 16);
    assert!(!map.contains(&6));
    assert!(map.contains(&7));
    assert!(map.contains(&16));
    assert!(!map.contains(&17));
    assert!(map.len() == 10);
}

source

pub fn remove(&mut self, val: usize) -> bool

删除元素

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add_range(7, 16);
    assert!(map.len() == 10);
    assert!(map.contains(&7));
    assert!(map.remove(7));
    assert!(!map.contains(&7));
    assert!(map.len() == 9);
}

source

pub fn remove_many(&mut self, val: &[usize])

删除列表中元素

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add_range(7, 16);
    assert!(map.len() == 10);
    assert!(map.contains(&7));
    assert!(map.remove(7));
    assert!(!map.contains(&7));
    assert!(map.len() == 9);
}

source

pub fn remove_range(&mut self, start: usize, end: usize)

删除范围元素（包含头与尾）

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add_range(7, 16);
    assert!(map.len() == 10);
    map.remove_range(7, 15);
    assert!(map.len() == 1);
    assert!(map.contains(&16));
}

source

pub fn contains(&self, val: &usize) -> bool

醒看是否包含

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add(7);
    assert!(map.contains(&7));
}

source

pub fn iter(&self) -> Iter<'_>

迭代器，通过遍历进行循环，如果位图的容量非常大，可能效率相当低

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add(7);
    map.add_range(9, 12);
    map.add_many(&vec![20, 100, 300]);
    assert!(map.iter().collect::<Vec<_>>() == vec![7, 9, 10, 11, 12, 20, 100, 300]);
}

source

pub fn retain<F>(&mut self, f: F)
where F: FnMut(&usize) -> bool,

是否保留，通过遍历进行循环，如果位图的容量非常大，可能效率相当低

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add_range(9, 16);
    map.retain(|v| v % 2 == 0);
    assert!(map.iter().collect::<Vec<_>>() == vec![10, 12, 14, 16]);
}

source

pub fn contains_sub(&self, other: &BitMap) -> bool

是否为子位图

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add_range(9, 16);
    let mut sub_map = BitMap::new(10240);
    sub_map.add_range(9, 12);
    assert!(map.contains_sub(&sub_map));
}

source

pub fn intersect(&self, other: &BitMap) -> BitMap

取两个位图间的交集

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add_range(9, 16);
    let mut sub_map = BitMap::new(10240);
    sub_map.add_range(7, 12);
    let map = map.intersect(&sub_map);
    assert!(map.iter().collect::<Vec<_>>() == vec![9, 10, 11, 12]);
}

source

pub fn union(&self, other: &BitMap) -> BitMap

取两个位图间的并集

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add_range(9, 16);
    let mut sub_map = BitMap::new(10240);
    sub_map.add_range(7, 12);
    let map = map.union(&sub_map);
    assert!(map.iter().collect::<Vec<_>>() == vec![7, 8, 9, 10, 11, 12, 13, 14, 15, 16]);
}

source

pub fn union_xor(&self, other: &BitMap) -> BitMap

取两个位图间的异或并集

§Examples

use algorithm::BitMap;
fn main() {
    let mut map = BitMap::new(10240);
    map.add_range(9, 16);
    let mut sub_map = BitMap::new(10240);
    sub_map.add_range(7, 12);
    let map = map.union_xor(&sub_map);
    assert_eq!(map.iter().collect::<Vec<_>>(), vec![7, 8, 13, 14, 15, 16]);
}