interval_tree/
pointsegment.rs

1extern crate num;
2
3use self::num::traits::{Num};
4use self::num::traits::{One};
5use common::{mid};
6
7pub struct PointSegmentTree<N, P>{
8    root: Node<N, P>,
9    lower_bound: N, 
10    upper_bound: N, 
11    default: P,
12    combine: Box<F<P>>
13}
14
15#[derive(PartialEq, Eq, Debug)]
16struct Node<N, P> {
17    start: N,
18    end: N,
19    value: P, 
20    left: Option<Box<Node<N, P>>>,
21    right: Option<Box<Node<N, P>>>,
22}
23
24pub type F<P> = Fn(&P, &P) -> P;
25
26impl<N: Num+Clone+Ord, P: Clone> PointSegmentTree<N, P> {
27    pub fn new(lower_bound: N, upper_bound: N, default_value: P,
28               combine: Box<F<P>>) -> Self 
29    {
30        if lower_bound > upper_bound {
31            panic!("Invalid bounds (lower_bound must not be greater than upper_bound)");
32        }
33        let node = Node::new(lower_bound.clone(),
34                             upper_bound.clone(),
35                             &default_value);
36            
37        PointSegmentTree {
38            default:  default_value,
39            lower_bound: lower_bound,
40            upper_bound: upper_bound,
41            combine: combine,
42            root: node
43        }
44    }
45
46    pub fn insert(&mut self, point_n: N, point_data: P) {
47        if point_n < self.lower_bound || point_n > self.upper_bound {
48           panic!("Attempted insert out of tree bounds"); 
49        }
50        self.root.insert(point_n, point_data, &self.default, 
51                         &*self.combine);
52    }
53
54    pub fn query(&self, start_q: N, end_q: N) -> Option<P> {
55        if end_q < start_q || start_q < self.lower_bound || end_q > self.upper_bound {
56            None
57        } else {
58            Some(self.root.query(start_q, end_q, &*self.combine, self.default.clone()))
59        }
60    }
61
62    pub fn bounds(&self) -> (N, N) {
63        (self.lower_bound.clone(), self.upper_bound.clone())
64    }
65
66}
67
68impl<N: Num+Clone+Ord, P: Clone> Node<N, P> {
69    fn new(start: N, end: N, default_value: &P) -> Self { 
70        Node {
71            start: start,
72            end: end,
73            value: default_value.clone(),
74            left: None,
75            right: None,
76        }
77    }
78
79    fn new_son(start: N, end: N, default_value: &P) -> Option<Box<Self>> {
80        Some(Box::new(Node::new(start, end, default_value)))
81    }
82
83    fn query(&self, start_q: N, end_q: N, combine: &F<P>, acc: P) -> P {
84        if self.start == start_q && self.end == end_q {
85            return combine(&self.value, &acc);
86        }
87        let mid = mid(self.start.clone(), self.end.clone());
88
89        if end_q <= mid {
90            match self.left {
91                None => acc,
92                Some(ref n) => n.query(start_q, end_q, combine, acc)
93            }
94        } else if start_q > mid {
95            match self.right {
96                None => acc,
97                Some(ref n) => n.query(start_q, end_q, combine, acc)
98            }
99        } else {
100            // split
101            let acc_l = match self.left {
102                None => acc,
103                Some(ref n) => n.query(start_q, mid.clone(), combine, acc)
104            };
105            let acc_r = match self.right {
106                None => acc_l,
107                Some(ref n) => n.query(mid + One::one(), end_q, combine, acc_l)
108            };
109            acc_r
110        }
111    }
112
113    fn insert(&mut self, point_n: N, point_data: P,
114              default: &P, combine: &F<P>) {
115        let mid = mid(self.start.clone(), self.end.clone());
116        if self.start == self.end {
117            self.value = point_data;
118            return;
119        } else if point_n <= mid {
120            if self.left.is_none() {
121                self.left = Node::new_son(self.start.clone(), mid, default);
122            }
123            self.left.as_mut().map(|n| n.insert(point_n, point_data, default, combine));
124        } else { // point_n > mid
125            if self.right.is_none() {
126                self.right = Node::new_son(mid + One::one(), self.end.clone(), default);
127            }
128            self.right.as_mut().map(|n| n.insert(point_n, point_data, default, combine));
129        }
130        self.value = match (self.left.as_ref(), self.right.as_ref()) {
131            (Some(ref l), Some(ref r)) => combine(&l.value, &r.value),
132            (Some(ref l), _) => l.value.clone(),
133            (_, Some(ref r)) => r.value.clone(),
134            _ => unreachable!()
135        };
136    }
137}
interval_tree/pointsegment.rs

interval_tree/
pointsegment.rs
