1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

use std::cmp;

use Coords;

#[derive(Debug)]
pub struct Pack {
    pub children: Option<Box<(Pack, Pack)>>,
    pub top: u16,
    pub left: u16,
    pub bottom: u16,
    pub right: u16,
    pub elem: Option<Coords>,
}

impl Pack {
    // for best results, sort elements by height before insertion
    pub fn insert(&mut self, dim: Coords) -> Option<Coords> {
        if !self.is_leaf() {
            let (mut right, mut below) = *self.children.take().unwrap();
            // must start with right, because we have "infinite" height
            // due to paging
            let res = right.insert(dim).or_else(|| below.insert(dim));
            self.children = Some(Box::new((right, below)));
            res
        } else {
            if self.elem.is_some() {
                return None;
            }
            if !self.can_accomodate(dim) {
                return None;
            }

            // we will accomodate
            self.elem = Some(dim);

            let cap = self.dim();
            if cap == dim {
                // no need for splitting remainder
                return Some((self.left, self.top));
            }

            // we need to split so that future inserts can
            // use the slack left from this insert
            let dx = cap.0 - dim.0;
            let dy = cap.1 - dim.1;

            // resize self
            self.right -= dx;
            self.bottom -= dy;

            let right = Pack {
                children: None,
                top: self.top,
                left: self.right,
                bottom: self.bottom,
                right: self.right + dx,
                elem: None,
            };

            let below = Pack {
                children: None,
                top: self.bottom,
                left: self.left,
                bottom: self.bottom + dy,
                right: self.right + dx,
                elem: None,
            };

            self.children = Some(Box::new((right, below)));

            Some((self.left, self.top))
        }
    }

    fn dim(&self) -> Coords {
        trace!("dim({:?})", self);
        (cmp::max(self.right, self.left) - self.left, cmp::max(self.bottom, self.top) - self.top)
    }

    fn is_leaf(&self) -> bool {
        self.children.is_none()
    }

    fn can_accomodate(&self, dim: Coords) -> bool {
        let capacity = self.dim();
        capacity.0 >= dim.0 && capacity.1 >= dim.1
    }
}