brepkit_sketch/gcs/
entity.rs

1//! Generational arena and geometric entity types for the GCS.
2
3use std::marker::PhantomData;
4
5// ── Generational Arena ──────────────────────────────────────────────
6
7/// A typed handle into a [`GenArena`].
8///
9/// Stores an index and a generation counter. If the generation doesn't
10/// match the slot's current generation, the handle is stale (the entity
11/// was removed and the slot may have been reused).
12pub struct Handle<T> {
13    pub(crate) index: u32,
14    pub(crate) generation: u32,
15    pub(crate) _marker: PhantomData<fn() -> T>,
16}
17
18// Manual impls to avoid requiring T: Debug/Clone/etc.
19impl<T> std::fmt::Debug for Handle<T> {
20    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
21        f.debug_struct("Handle")
22            .field("index", &self.index)
23            .field("gen", &self.generation)
24            .finish()
25    }
26}
27
28impl<T> Clone for Handle<T> {
29    fn clone(&self) -> Self {
30        *self
31    }
32}
33impl<T> Copy for Handle<T> {}
34
35impl<T> PartialEq for Handle<T> {
36    fn eq(&self, other: &Self) -> bool {
37        self.index == other.index && self.generation == other.generation
38    }
39}
40impl<T> Eq for Handle<T> {}
41
42impl<T> std::hash::Hash for Handle<T> {
43    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
44        self.index.hash(state);
45        self.generation.hash(state);
46    }
47}
48
49impl<T> Handle<T> {
50    /// Raw index into the arena's slot vector.
51    #[must_use]
52    pub const fn index(self) -> u32 {
53        self.index
54    }
55
56    /// Generation counter for stale-handle detection.
57    #[must_use]
58    pub const fn generation(self) -> u32 {
59        self.generation
60    }
61}
62
63/// Slot in the generational arena — either occupied or free.
64enum Entry<T> {
65    Occupied {
66        value: T,
67        generation: u32,
68    },
69    Free {
70        next_free: Option<u32>,
71        generation: u32,
72    },
73}
74
75/// A generational arena that supports O(1) insert, get, and remove.
76///
77/// Removed slots are recycled via a free list. Each slot has a generation
78/// counter that is bumped on removal, so stale handles are detected.
79pub struct GenArena<T> {
80    entries: Vec<Entry<T>>,
81    free_head: Option<u32>,
82    len: usize,
83}
84
85impl<T: Clone> Clone for GenArena<T> {
86    fn clone(&self) -> Self {
87        let entries = self
88            .entries
89            .iter()
90            .map(|e| match e {
91                Entry::Occupied { value, generation } => Entry::Occupied {
92                    value: value.clone(),
93                    generation: *generation,
94                },
95                Entry::Free {
96                    next_free,
97                    generation,
98                } => Entry::Free {
99                    next_free: *next_free,
100                    generation: *generation,
101                },
102            })
103            .collect();
104        Self {
105            entries,
106            free_head: self.free_head,
107            len: self.len,
108        }
109    }
110}
111
112impl<T> Default for GenArena<T> {
113    fn default() -> Self {
114        Self::new()
115    }
116}
117
118impl<T> GenArena<T> {
119    /// Creates an empty arena.
120    #[must_use]
121    pub const fn new() -> Self {
122        Self {
123            entries: Vec::new(),
124            free_head: None,
125            len: 0,
126        }
127    }
128
129    /// Number of live entries.
130    #[must_use]
131    pub const fn len(&self) -> usize {
132        self.len
133    }
134
135    /// Whether the arena is empty.
136    #[must_use]
137    #[allow(dead_code)]
138    pub const fn is_empty(&self) -> bool {
139        self.len == 0
140    }
141
142    /// Insert a value and return its handle.
143    pub fn insert(&mut self, value: T) -> Handle<T> {
144        self.len += 1;
145        if let Some(free_idx) = self.free_head {
146            let idx = free_idx as usize;
147            let generation = match &self.entries[idx] {
148                Entry::Free {
149                    next_free,
150                    generation,
151                } => {
152                    self.free_head = *next_free;
153                    *generation
154                }
155                Entry::Occupied { .. } => {
156                    // Should never happen — free_head pointed to an occupied slot.
157                    // Defensive: just append instead.
158                    self.free_head = None;
159                    return self.push_new(value);
160                }
161            };
162            self.entries[idx] = Entry::Occupied { value, generation };
163            Handle {
164                index: free_idx,
165                generation,
166                _marker: PhantomData,
167            }
168        } else {
169            self.push_new(value)
170        }
171    }
172
173    /// Append a new entry at the end (no free slot available).
174    fn push_new(&mut self, value: T) -> Handle<T> {
175        let index = self.entries.len() as u32;
176        self.entries.push(Entry::Occupied {
177            value,
178            generation: 0,
179        });
180        Handle {
181            index,
182            generation: 0,
183            _marker: PhantomData,
184        }
185    }
186
187    /// Get a reference to the value at `handle`, or `None` if stale/invalid.
188    #[must_use]
189    pub fn get(&self, handle: Handle<T>) -> Option<&T> {
190        let entry = self.entries.get(handle.index as usize)?;
191        match entry {
192            Entry::Occupied { value, generation } if *generation == handle.generation => {
193                Some(value)
194            }
195            _ => None,
196        }
197    }
198
199    /// Get a mutable reference to the value at `handle`.
200    pub fn get_mut(&mut self, handle: Handle<T>) -> Option<&mut T> {
201        let entry = self.entries.get_mut(handle.index as usize)?;
202        match entry {
203            Entry::Occupied { value, generation } if *generation == handle.generation => {
204                Some(value)
205            }
206            _ => None,
207        }
208    }
209
210    /// Remove the value at `handle`. Returns the removed value, or `None` if stale.
211    pub fn remove(&mut self, handle: Handle<T>) -> Option<T> {
212        let idx = handle.index as usize;
213        let entry = self.entries.get(idx)?;
214        let cur_gen = match entry {
215            Entry::Occupied { generation, .. } if *generation == handle.generation => *generation,
216            _ => return None,
217        };
218        // Replace with a free entry, bumping the generation.
219        let old = std::mem::replace(
220            &mut self.entries[idx],
221            Entry::Free {
222                next_free: self.free_head,
223                generation: cur_gen + 1,
224            },
225        );
226        self.free_head = Some(handle.index);
227        self.len -= 1;
228        match old {
229            Entry::Occupied { value, .. } => Some(value),
230            Entry::Free { .. } => None, // unreachable
231        }
232    }
233
234    /// Iterate over all live `(Handle<T>, &T)` pairs.
235    pub fn iter(&self) -> impl Iterator<Item = (Handle<T>, &T)> {
236        self.entries
237            .iter()
238            .enumerate()
239            .filter_map(|(i, entry)| match entry {
240                Entry::Occupied { value, generation } => Some((
241                    Handle {
242                        index: i as u32,
243                        generation: *generation,
244                        _marker: PhantomData,
245                    },
246                    value,
247                )),
248                Entry::Free { .. } => None,
249            })
250    }
251
252    /// Iterate over all live `(Handle<T>, &mut T)` pairs.
253    #[allow(dead_code)]
254    pub fn iter_mut(&mut self) -> impl Iterator<Item = (Handle<T>, &mut T)> {
255        self.entries
256            .iter_mut()
257            .enumerate()
258            .filter_map(|(i, entry)| match entry {
259                Entry::Occupied { value, generation } => Some((
260                    Handle {
261                        index: i as u32,
262                        generation: *generation,
263                        _marker: PhantomData,
264                    },
265                    value,
266                )),
267                Entry::Free { .. } => None,
268            })
269    }
270
271    /// Check if a handle is still valid (points to a live entry).
272    #[must_use]
273    pub fn contains(&self, handle: Handle<T>) -> bool {
274        self.get(handle).is_some()
275    }
276}
277
278// ── Entity Types ────────────────────────────────────────────────────
279
280/// A handle to a point in the GCS.
281pub type PointId = Handle<PointData>;
282/// A handle to a line in the GCS.
283pub type LineId = Handle<LineData>;
284/// A handle to a circle in the GCS.
285pub type CircleId = Handle<CircleData>;
286/// A handle to an arc in the GCS.
287pub type ArcId = Handle<ArcData>;
288
289/// A 2D point in the constraint system.
290#[derive(Debug, Clone, Copy)]
291pub struct PointData {
292    /// X coordinate.
293    pub x: f64,
294    /// Y coordinate.
295    pub y: f64,
296    /// Whether this point is fixed (not adjusted by the solver).
297    pub fixed: bool,
298}
299
300/// A line defined by two points.
301#[derive(Debug, Clone, Copy)]
302pub struct LineData {
303    /// First endpoint.
304    pub p1: PointId,
305    /// Second endpoint.
306    pub p2: PointId,
307}
308
309/// A circle defined by a center point and radius.
310#[derive(Debug, Clone, Copy)]
311pub struct CircleData {
312    /// Center point.
313    pub center: PointId,
314    /// Radius (a solver parameter if not fixed).
315    pub radius: f64,
316}
317
318/// An arc defined by a center point and two boundary points.
319///
320/// The radius is implicit: `dist(center, start)`. An internal
321/// constraint enforces `dist(center, start) == dist(center, end)`.
322#[derive(Debug, Clone, Copy)]
323pub struct ArcData {
324    /// Center point of the arc's underlying circle.
325    pub center: PointId,
326    /// Start endpoint on the arc.
327    pub start: PointId,
328    /// End endpoint on the arc.
329    pub end: PointId,
330}
331
332/// A reference to a solver parameter.
333#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
334pub enum ParamRef {
335    /// X coordinate of a point.
336    PointX(PointId),
337    /// Y coordinate of a point.
338    PointY(PointId),
339    /// Radius of a circle.
340    CircleRadius(CircleId),
341}
342
343#[cfg(test)]
344#[allow(clippy::unwrap_used, clippy::expect_used)]
345mod tests {
346    use super::*;
347
348    #[test]
349    fn insert_get_remove() {
350        let mut arena = GenArena::<i32>::new();
351        let h1 = arena.insert(10);
352        let h2 = arena.insert(20);
353
354        assert_eq!(*arena.get(h1).unwrap(), 10);
355        assert_eq!(*arena.get(h2).unwrap(), 20);
356        assert_eq!(arena.len(), 2);
357
358        let removed = arena.remove(h1).unwrap();
359        assert_eq!(removed, 10);
360        assert!(arena.get(h1).is_none()); // stale
361        assert_eq!(arena.len(), 1);
362    }
363
364    #[test]
365    fn stale_handle_after_remove() {
366        let mut arena = GenArena::<i32>::new();
367        let h = arena.insert(42);
368        arena.remove(h);
369
370        // Reuse the slot
371        let h2 = arena.insert(99);
372        assert_eq!(h2.index(), h.index()); // same slot
373        assert_ne!(h2.generation(), h.generation()); // different gen
374
375        // Old handle is stale
376        assert!(arena.get(h).is_none());
377        assert_eq!(*arena.get(h2).unwrap(), 99);
378    }
379
380    #[test]
381    fn free_list_reuse() {
382        let mut arena = GenArena::<i32>::new();
383        let h0 = arena.insert(0);
384        let h1 = arena.insert(1);
385        let h2 = arena.insert(2);
386
387        arena.remove(h1);
388        arena.remove(h0);
389
390        // Next inserts should reuse freed slots (LIFO)
391        let h3 = arena.insert(30);
392        assert_eq!(h3.index(), h0.index());
393        let h4 = arena.insert(40);
394        assert_eq!(h4.index(), h1.index());
395
396        assert_eq!(*arena.get(h3).unwrap(), 30);
397        assert_eq!(*arena.get(h4).unwrap(), 40);
398        assert_eq!(*arena.get(h2).unwrap(), 2);
399    }
400
401    #[test]
402    fn iteration() {
403        let mut arena = GenArena::<i32>::new();
404        let _h0 = arena.insert(10);
405        let h1 = arena.insert(20);
406        let _h2 = arena.insert(30);
407
408        arena.remove(h1);
409
410        let values: Vec<i32> = arena.iter().map(|(_, v)| *v).collect();
411        assert_eq!(values.len(), 2);
412        assert!(values.contains(&10));
413        assert!(values.contains(&30));
414    }
415
416    #[test]
417    fn empty_arena() {
418        let arena = GenArena::<i32>::new();
419        assert!(arena.is_empty());
420        assert_eq!(arena.len(), 0);
421        assert_eq!(arena.iter().count(), 0);
422    }
423
424    #[test]
425    fn double_remove() {
426        let mut arena = GenArena::<i32>::new();
427        let h = arena.insert(42);
428        assert!(arena.remove(h).is_some());
429        assert!(arena.remove(h).is_none()); // already removed
430    }
431
432    #[test]
433    fn get_mut_works() {
434        let mut arena = GenArena::<i32>::new();
435        let h = arena.insert(10);
436        *arena.get_mut(h).unwrap() = 20;
437        assert_eq!(*arena.get(h).unwrap(), 20);
438    }
439}
brepkit_sketch/gcs/entity.rs

brepkit_sketch/gcs/
entity.rs
