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 {
pub fn insert(&mut self, dim: Coords) -> Option<Coords> {
if !self.is_leaf() {
let (mut right, mut below) = *self.children.take().unwrap();
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;
}
self.elem = Some(dim);
let cap = self.dim();
if cap == dim {
return Some((self.left, self.top));
}
let dx = cap.0 - dim.0;
let dy = cap.1 - dim.1;
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
}
}