1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54

mod fenwickfast;
use fenwick::_module::fenwick;
use std::time::Instant;

fn main() {
    const N: usize = 1 << 17;
    let a: Vec<_> = rand::random_iter::<i32>()
        .take(N)
        .map(|x| x % 1000)
        .collect();
    let seq = a
        .iter()
        .map(|x| dafny_runtime::DafnyInt::from_i32(*x))
        .collect();
    let obj = fenwick::_allocate_object();
    fenwick::_ctor(&obj, &seq);
    let ft = dafny_runtime::rd!(obj);

    const T: usize = 1 << 20;

    let test: Vec<_> = rand::random_iter::<i32>()
        .zip(rand::random_iter::<i32>())
        .take(T)
        .map(|x| (x.0 as usize % N + 1, x.1 as usize % N + 1))
        .map(|x| if x.0 > x.1 { (x.1, x.0) } else { x })
        .collect();
    let test_dafny: Vec<_> = test
        .iter()
        .map(|x| {
            (
                dafny_runtime::DafnyInt::from_usize(x.0),
                dafny_runtime::DafnyInt::from_usize(x.1),
            )
        })
        .collect();

    println!("starting benchmark");
    let now = Instant::now();
    for (i, j) in &test_dafny {
        ft.range_query(i, j);
    }
    let elapsed = now.elapsed().as_micros();
    println!("dafny range query took {} µs", elapsed);

    let mut f = vec![0];
    f.extend(a);
    fenwickfast::build(&mut f);
    let now = Instant::now();
    for (i, j) in test {
        fenwickfast::range_query(&f, i, j);
    }
    let elapsed = now.elapsed().as_micros();
    println!("rust range query took {} µs", elapsed);
}