rectangle_pack/
grouped_rects_to_place.rs

1use crate::RectToInsert;
2
3#[cfg(not(std))]
4use alloc::collections::BTreeMap as KeyValMap;
5#[cfg(std)]
6use std::collections::HashMap as KeyValMap;
7
8use alloc::{
9    collections::{btree_map::Entry, BTreeMap},
10    vec::Vec,
11};
12use core::{fmt::Debug, hash::Hash};
13
14/// Groups of rectangles that need to be placed into bins.
15///
16/// When placing groups a heuristic is used to determine which groups are the largest.
17/// Larger groups are placed first.
18///
19/// A group's heuristic is computed by calculating the heuristic of all of the rectangles inside
20/// the group and then summing them.
21#[derive(Debug)]
22pub struct GroupedRectsToPlace<RectToPlaceId, GroupId = ()>
23where
24    RectToPlaceId: Debug + Hash + Eq + Ord + PartialOrd,
25    GroupId: Debug + Hash + Eq + Ord + PartialOrd,
26{
27    // FIXME: inbound_id_to_group_id appears to be unused. If so, remove it. Also remove the
28    //  Hash and Eq constraints on RectToPlaceId if we remove this map
29    pub(crate) inbound_id_to_group_ids:
30        KeyValMap<RectToPlaceId, Vec<Group<GroupId, RectToPlaceId>>>,
31    pub(crate) group_id_to_inbound_ids: BTreeMap<Group<GroupId, RectToPlaceId>, Vec<RectToPlaceId>>,
32    pub(crate) rects: KeyValMap<RectToPlaceId, RectToInsert>,
33}
34
35/// A group of rectangles that need to be placed together
36#[derive(Debug, Hash, Eq, PartialEq, Ord, PartialOrd)]
37pub enum Group<GroupId, RectToPlaceId>
38where
39    GroupId: Debug + Hash + Eq + PartialEq + Ord + PartialOrd,
40    RectToPlaceId: Debug + Ord + PartialOrd,
41{
42    /// An automatically generated (auto incrementing) group identifier for rectangles that were
43    /// passed in without any associated group ids.
44    ///
45    /// We still want to treat these lone rectangles as their own "groups" so that we can more
46    /// easily compare their heuristics against those of other groups.
47    ///
48    /// If everything is a "group" - comparing groups becomes simpler.
49    Ungrouped(RectToPlaceId),
50    /// Wraps a user provided group identifier.
51    Grouped(GroupId),
52}
53
54impl<RectToPlaceId, GroupId> GroupedRectsToPlace<RectToPlaceId, GroupId>
55where
56    RectToPlaceId: Debug + Hash + Clone + Eq + Ord + PartialOrd,
57    GroupId: Debug + Hash + Clone + Eq + Ord + PartialOrd,
58{
59    /// Create a new `LayeredRectGroups`
60    pub fn new() -> Self {
61        Self {
62            inbound_id_to_group_ids: Default::default(),
63            group_id_to_inbound_ids: Default::default(),
64            rects: Default::default(),
65        }
66    }
67
68    /// Push one or more rectangles
69    ///
70    /// # Panics
71    ///
72    /// Panics if a `Some(Vec<GroupId>)` passed in but the length is 0, as this is likely a
73    /// mistake and `None` should be used instead.
74    pub fn push_rect(
75        &mut self,
76        inbound_id: RectToPlaceId,
77        group_ids: Option<Vec<GroupId>>,
78        inbound: RectToInsert,
79    ) {
80        self.rects.insert(inbound_id.clone(), inbound);
81
82        match group_ids {
83            None => {
84                self.group_id_to_inbound_ids.insert(
85                    Group::Ungrouped(inbound_id.clone()),
86                    vec![inbound_id.clone()],
87                );
88
89                self.inbound_id_to_group_ids
90                    .insert(inbound_id.clone(), vec![Group::Ungrouped(inbound_id)]);
91            }
92            Some(group_ids) => {
93                self.inbound_id_to_group_ids.insert(
94                    inbound_id.clone(),
95                    group_ids
96                        .clone()
97                        .into_iter()
98                        .map(|gid| Group::Grouped(gid))
99                        .collect(),
100                );
101
102                for group_id in group_ids {
103                    match self.group_id_to_inbound_ids.entry(Group::Grouped(group_id)) {
104                        Entry::Occupied(mut o) => {
105                            o.get_mut().push(inbound_id.clone());
106                        }
107                        Entry::Vacant(v) => {
108                            v.insert(vec![inbound_id.clone()]);
109                        }
110                    };
111                }
112            }
113        };
114    }
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120    use crate::RectToInsert;
121
122    /// Verify that if we insert a rectangle that doesn't have a group it is given a group ID based
123    /// on its RectToPlaceId.
124    #[test]
125    fn ungrouped_rectangles_use_their_inbound_id_as_their_group_id() {
126        let mut lrg: GroupedRectsToPlace<_, ()> = GroupedRectsToPlace::new();
127
128        lrg.push_rect(RectToPlaceId::One, None, RectToInsert::new(10, 10, 1));
129
130        assert_eq!(
131            lrg.group_id_to_inbound_ids[&Group::Ungrouped(RectToPlaceId::One)],
132            vec![RectToPlaceId::One]
133        );
134    }
135
136    /// When multiple different rects from the same group are pushed they should be present in the
137    /// map of group id -> inbound rect id
138    #[test]
139    fn group_id_to_inbound_ids() {
140        let mut lrg = GroupedRectsToPlace::new();
141
142        lrg.push_rect(
143            RectToPlaceId::One,
144            Some(vec![0]),
145            RectToInsert::new(10, 10, 1),
146        );
147        lrg.push_rect(
148            RectToPlaceId::Two,
149            Some(vec![0]),
150            RectToInsert::new(10, 10, 1),
151        );
152
153        assert_eq!(
154            lrg.group_id_to_inbound_ids.get(&Group::Grouped(0)).unwrap(),
155            &vec![RectToPlaceId::One, RectToPlaceId::Two]
156        );
157    }
158
159    /// Verify that we store the map of inbound id -> group ids
160    #[test]
161    fn inbound_id_to_group_ids() {
162        let mut lrg = GroupedRectsToPlace::new();
163
164        lrg.push_rect(
165            RectToPlaceId::One,
166            Some(vec![0, 1]),
167            RectToInsert::new(10, 10, 1),
168        );
169
170        lrg.push_rect(RectToPlaceId::Two, None, RectToInsert::new(10, 10, 1));
171
172        assert_eq!(
173            lrg.inbound_id_to_group_ids[&RectToPlaceId::One],
174            vec![Group::Grouped(0), Group::Grouped(1)]
175        );
176
177        assert_eq!(
178            lrg.inbound_id_to_group_ids[&RectToPlaceId::Two],
179            vec![Group::Ungrouped(RectToPlaceId::Two)]
180        );
181    }
182
183    /// Verify that we store in rectangle associated with its inbound ID
184    #[test]
185    fn store_the_inbound_rectangle() {
186        let mut lrg = GroupedRectsToPlace::new();
187
188        lrg.push_rect(
189            RectToPlaceId::One,
190            Some(vec![0, 1]),
191            RectToInsert::new(10, 10, 1),
192        );
193
194        assert_eq!(lrg.rects[&RectToPlaceId::One], RectToInsert::new(10, 10, 1));
195    }
196
197    #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
198    enum RectToPlaceId {
199        One,
200        Two,
201    }
202}
rectangle_pack/grouped_rects_to_place.rs

rectangle_pack/
grouped_rects_to_place.rs
