Struct Static2DTree

Source

pub struct Static2DTree<T, U, V>where
    T: Ord,
    U: Ord,{
    data: Vec<(T, U, V)>,
}

Fields§

§data: Vec<(T, U, V)>

Implementations§

Source §

impl<T, U, V> Static2DTree<T, U, V>
where T: Ord, U: Ord,

Source

pub fn new(data: I) -> Self
where I: IntoIterator<Item = (T, U, V)>,

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_2_c.rs (line 10)

6pub fn dsl_2_c(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, xy: [(i64, i64)]);
10    let tree = Static2DTree::new(xy.take(n).enumerate().map(|(i, (x, y))| (x, y, i)));
11    scan!(scanner, q, query: [(i64, i64, i64, i64)]);
12    for (sx, tx, sy, ty) in query.take(q) {
13        let mut v = tree.range(sx..tx + 1, sy..ty + 1);
14        v.sort();
15        for v in v {
16            writeln!(writer, "{}", v).ok();
17        }
18        writeln!(writer).ok();
19    }
20}

Source

fn build(data: &mut [(T, U, V)], l: usize, r: usize, depth: usize)

Examples found in repository ?

crates/competitive/src/data_structure/kdtree.rs (line 21)

15    pub fn new<I>(data: I) -> Self
16    where
17        I: IntoIterator<Item = (T, U, V)>,
18    {
19        let mut data: Vec<_> = data.into_iter().collect();
20        let n = data.len();
21        Self::build(&mut data, 0, n, 0);
22        Self { data }
23    }
24    fn build(data: &mut [(T, U, V)], l: usize, r: usize, depth: usize) {
25        if l < r {
26            let m = l.midpoint(r);
27            if depth.is_multiple_of(2) {
28                data[l..r].sort_by(|p, q| p.0.cmp(&q.0));
29            } else {
30                data[l..r].sort_by(|p, q| p.1.cmp(&q.1));
31            }
32            Self::build(data, l, m, depth + 1);
33            Self::build(data, m + 1, r, depth + 1);
34        }
35    }

Source

pub fn range(&self, range1: Range<T>, range2: Range) -> Vec<&V>

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_2_c.rs (line 13)

6pub fn dsl_2_c(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, xy: [(i64, i64)]);
10    let tree = Static2DTree::new(xy.take(n).enumerate().map(|(i, (x, y))| (x, y, i)));
11    scan!(scanner, q, query: [(i64, i64, i64, i64)]);
12    for (sx, tx, sy, ty) in query.take(q) {
13        let mut v = tree.range(sx..tx + 1, sy..ty + 1);
14        v.sort();
15        for v in v {
16            writeln!(writer, "{}", v).ok();
17        }
18        writeln!(writer).ok();
19    }
20}

Source

fn range_inner<'a>( &'a self, range1: &Range<T>, range2: &Range, l: usize, r: usize, depth: usize, res: &mut Vec<&'a V>, )

Examples found in repository ?

crates/competitive/src/data_structure/kdtree.rs (line 38)

36    pub fn range(&self, range1: Range<T>, range2: Range<U>) -> Vec<&V> {
37        let mut res = vec![];
38        self.range_inner(&range1, &range2, 0, self.data.len(), 0, &mut res);
39        res
40    }
41    fn range_inner<'a>(
42        &'a self,
43        range1: &Range<T>,
44        range2: &Range<U>,
45        l: usize,
46        r: usize,
47        depth: usize,
48        res: &mut Vec<&'a V>,
49    ) {
50        if l < r {
51            let m = l.midpoint(r);
52            let (t, u, v) = &self.data[m];
53            if range1.contains(t) && range2.contains(u) {
54                res.push(v);
55            }
56            if if depth.is_multiple_of(2) {
57                &range1.start <= t
58            } else {
59                &range2.start <= u
60            } {
61                self.range_inner(range1, range2, l, m, depth + 1, res);
62            }
63            if if depth.is_multiple_of(2) {
64                t < &range1.end
65            } else {
66                u < &range2.end
67            } {
68                self.range_inner(range1, range2, m + 1, r, depth + 1, res);
69            }
70        }
71    }