#data-structures #utility

treez

A collection of useful data structures

28 releases (8 stable)

Uses old Rust 2015

1.6.0 Jul 21, 2020
1.4.1 May 22, 2020
1.1.0 Jul 6, 2019
0.12.0 Sep 16, 2018
0.7.0 Dec 31, 2017

#5 in #segment

Download history 4/week @ 2023-06-12 31/week @ 2023-06-19 9/week @ 2023-06-26 53/week @ 2023-07-03 2/week @ 2023-07-24 1/week @ 2023-07-31 1/week @ 2023-08-07 30/week @ 2023-08-14 29/week @ 2023-08-28 3/week @ 2023-09-04 32/week @ 2023-09-11 74/week @ 2023-09-18

138 downloads per month

BSD-2-Clause

205KB
6K SLoC

treez

A collection of useful data structures and algorithms

implementations:

monotone queue

segment tree

rb tree

prefix sum

treap/cartesian tree

disjoint set

strongly connected components

backtracking

monotone queue

    using treez::queue_monotone::QueueMonotone;
    
    let mut q : QueueMonotone<i32> = QueueMonotone::new();
    
    const window : usize = 20;

    q.set_auto_len(window);
    
    let mut rng = rand::thread_rng();

    let arr : Vec<i32> = (0..100).map(|x| rng.gen_range(-1000,1000)).collect();
    
    for (i,v) in arr.iter().enumerate() {
        
        q.push(*v);
       
        let bound_left = std::cmp::max((i+1).saturating_sub(window),0);

        let m = *q.max().expect("max");
        
        assert_eq!(m, *arr[bound_left..=i].iter().max().unwrap());
    }

segment tree

    //summation segment tree
    let mut seg = SegSum::new(0, m); //range: [0,m), subsequent operations have to be within this range
	let delta : T = ... //T: Add<Output=T> + Mul<i64, Output<T>> + Clone + Default + Debug
    seg.add(a, b, &delta); //add delta to range [a,b)
    seg.update(a, b, &val); //set range [a,b) to val
    ...
    let v : T = seg.query_range(i, j); //query sum in range [i,j)
	
	//max segment tree
    let mut seg = SegMax::new(0, m); //range: [0,m), subsequent operations have to be within this range
	
	let delta : T = ... //T: Add<Output=T> + Ord + Debug + Clone + Min
	//eg: 
	impl Min for i64 {
        fn min() -> i64 {
		    i64::MIN
		}
	}
    seg.add(a, b, &delta); //add delta to range [a,b)
    seg.update(a, b, &val); //set range [a,b) to max(val,element[i]) for i in [a,b)
    ...
    let v : T = seg.query_range(i, j); //query max in range [i,j)

red black tree

    let mut t : treez::rb::TreeRb< isize, isize > = treez::rb::TreeRb::new();
    for i in 0..nums.len() {
        let r = nums[i];
        t.insert( r, i as isize );
    }

    for i in 0..nums.len() {
        let r = nums[i];
        let v = t.remove( &r ).expect( "remove unsuccessful" );
    }

prefix sum

    let mut t = treez::prefix::TreePrefix< isize >::init(16);
    t.set(0, 5);
    t.set(1, 7);
    t.set(10, 4);
    assert_eq!( t.get_interval(0, 16), 16isize );
    assert_eq!( t.get_interval(10, 11), 4isize );
    assert_eq!( t.get_interval(1, 11), 11isize );

    t.set(1, 9);
    assert_eq!( t.get_interval(1, 2), 9isize );
    assert_eq!( t.get_interval(1, 11), 13isize );
    assert_eq!( t.get_interval_start( 2 ), 14isize );
    assert_eq!( t.get_interval_start( 11 ), 18isize );

    t.add( 0, 1);
    assert_eq!( t.get_interval_start( 2 ), 15isize );
    assert_eq!( t.get_interval_start( 11 ), 19isize );

treap

implementation: insert, search, query_key_range( [low,high) ), split_by_key, merge_contiguous( a.keys < b.keys ), union, intersect, remove_by_key, remove_by_key_range( [low,high) )

    let mut t = treap::NodePtr::new();
    
    {
        let v = t.query_key_range( -100., 100. ).iter().
            map(|x| x.key()).collect::<Vec<_>>();
        
        assert_eq!( v.len(), 0 );
    }

    let items = vec![ 56, -45, 1, 6, 9, -30, 7, -9, 12, 77, -25 ];
    for i in items.iter() {
        t = t.insert( *i as f32, *i ).0;
    }
    
    t = t.remove_by_key_range( 5., 10. );
    
    let mut expected = items.iter().cloned().filter(|x| *x < 5 || *x >= 10 ).collect::<Vec<_>>();
    expected.sort();

    {
        let v = t.query_key_range( -100., 100. ).iter().
            map(|x| x.key()).collect::<Vec<_>>();
        
        assert_eq!( v.len(), expected.len() );

        expected.iter().zip( v.iter() )
            .for_each(|(a,b)| assert!(equal_f32( (*a as f32), *b ) ) );
    }

    let ((t1, t2), node_with_key_0 ) = t.split_by_key(0.);
    
    assert!( node_with_key_0.is_some() );
    
    let t3 = t1.merge_contiguous( t2 );

    {
        let v = t3.query_key_range( -100., 100. ).iter().
            map(|x| x.key()).collect::<Vec<_>>();
        
        assert_eq!( v.len(), expected.len() );

        expected.iter().zip( v.iter() )
            .for_each(|(a,b)| assert!(equal_f32( (*a as f32), *b ) ) );
    }
    
    let va = (100..200).map(|x| (x*2) ).collect::<Vec<i32>>();
    
    let mut t4 = treap::NodePtr::new();

    for i in va.iter() {
        t4 = t4.insert( (*i as f32), *i ).0;
    }

    let t5 = t3.union(t4);
    
    let vc = (50..70).map(|x| (x*2) ).collect::<Vec<i32>>();

    let mut t6 = treap::NodePtr::new();

    for i in vc.iter() {
        t6 = t6.insert( (*i as f32), *i ).0;
    }
    
    let t7 = t5.intersect( t6 );    

disjoint set

    let mut v = Dsu::init(10);

    //1, 3, 5, 7 ,9
    for i in 0..5 {
        let j = i*2+1;
        v.merge( j, j-1 );
    }

    let ret = v.get_sets_repr();
    assert_eq!( ret.len(), 5 );

    v.merge(5,9);

    assert_eq!( v.get_sets_repr().len(), 4 );

lower_bound, upper_bound

same logic as C++ lower/upper_bound; requires item type to have cmp::Ord trait

    let mut arr = ...
    arr.sort();
    let val = ...
    let idx = bound::upper_bound(&arr[..], &val);
    //idx in [0, arr.size]
    
    let mut arr = ...
    arr.sort();
    let val = ...
    let idx = bound::lower_bound(&arr[..], &val);

Dependencies

~3.5MB
~55K SLoC