#104

Committed 01 Oct 2025 07:35AM UTC coverage: 93.085% (+0.03%) from 93.053%

Build # #104

Build Type

push

Committed by Mr Martian

Commit Message

add line and poly tools; box_index; flat_queue

Coverage Stats

955 of 994 new or added lines in 11 files covered. (96.08%)

94792 of 101834 relevant lines covered (93.08%)

459229.68 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

91.78

/rust/data_structures/flat_queue.rs

use alloc::vec::Vec;

/// # FlatQueue
///
/// ## Description
/// A priority queue implemented using a binary heap.
///
/// A port from the [flatqueue](https://github.com/mourner/flatqueue) code.
///
/// ## Usage
///
/// ```rust
/// use gistools::data_structures::FlatQueue;
///
/// let mut q = FlatQueue::new();
/// q.push(1, 1.0);
/// q.push(3, 3.0);
/// q.push(2, 2.0);
/// assert_eq!(q.pop(), Some(1));
/// assert_eq!(q.pop(), Some(2));
/// assert_eq!(q.pop(), Some(3));
/// assert_eq!(q.pop(), None);
/// ```
pub struct FlatQueue<T> {
    ids: Vec<T>,
    values: Vec<f64>, // priority
    len: usize,
}
impl<T: Clone> Default for FlatQueue<T> {
    fn default() -> Self {
        Self::new()
    }
}
impl<T: Clone> FlatQueue<T> {
    /// Creates a new empty queue.
    pub fn new() -> Self {
        Self { ids: Vec::new(), values: Vec::new(), len: 0 }
    }

    /// Returns the number of items.
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns whether the queue is empty.
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Clears all items from the queue.
    pub fn clear(&mut self) {
        self.len = 0;
    }

    /// Adds `item` to the queue with the specified `priority`.
    ///
    /// `priority` must be a number. Items are sorted and returned from low to high priority. Multiple items
    /// with the same priority value can be added to the queue, but there is no guaranteed order between these items.
    ///
    /// ## Parameters
    /// - `item`: the item to add
    /// - `priority`: the priority of the item
    pub fn push(&mut self, item: T, priority: f64) {
        let mut pos = self.len;
        self.len += 1;

        if self.ids.len() < self.len {
            self.ids.resize(self.len, item.clone());
            self.values.resize(self.len, priority);
        }

        while pos > 0 {
            let parent = (pos - 1) >> 1;
            let parent_value = self.values[parent];
            if priority >= parent_value {
                break;
            }
            self.ids[pos] = self.ids[parent].clone();
            self.values[pos] = parent_value;
            pos = parent;
        }

        self.ids[pos] = item;
        self.values[pos] = priority;
    }

    /// Removes and returns the item from the head of this queue, which is one of
    /// the items with the lowest priority. If this queue is empty, returns `undefined`.
    ///
    /// ## Returns
    /// the item from the head of this queue
    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            return None;
        }

        let top = self.ids[0].clone();
        self.len -= 1;

        if self.len > 0 {
            let id = self.ids[self.len].clone();
            let value = self.values[self.len];
            let mut pos = 0;
            let half_len = self.len >> 1;

            while pos < half_len {
                let left = (pos << 1) + 1;
                let right = left + 1;
                let mut child = left;
                if right < self.len && self.values[right] < self.values[left] {
                    child = right;
                }
                if self.values[child] >= value {
                    break;
                }
                self.ids[pos] = self.ids[child].clone();
                self.values[pos] = self.values[child];
                pos = child;
            }

            self.ids[pos] = id;
            self.values[pos] = value;
        }

        Some(top)
    }

    /// Returns the item with the lowest priority without removing it.
    pub fn peek(&self) -> Option<&T> {
        if self.len > 0 { Some(&self.ids[0]) } else { None }
    }

    /// Returns the priority of the lowest-priority item.
    pub fn peek_value(&self) -> Option<f64> {
        if self.len > 0 { Some(self.values[0]) } else { None }
    }

    /// Shrinks underlying arrays to current length.
    pub fn shrink(&mut self) {
        self.ids.truncate(self.len);
        self.values.truncate(self.len);
    }
}

1	use alloc::vec::Vec;
2
3	/// # FlatQueue
4	///
5	/// ## Description
6	/// A priority queue implemented using a binary heap.
7	///
8	/// A port from the [flatqueue](https://github.com/mourner/flatqueue) code.
9	///
10	/// ## Usage
11	///
12	/// ```rust
13	/// use gistools::data_structures::FlatQueue;
14	///
15	/// let mut q = FlatQueue::new();
16	/// q.push(1, 1.0);
17	/// q.push(3, 3.0);
18	/// q.push(2, 2.0);
19	/// assert_eq!(q.pop(), Some(1));
20	/// assert_eq!(q.pop(), Some(2));
21	/// assert_eq!(q.pop(), Some(3));
22	/// assert_eq!(q.pop(), None);
23	/// ```
24	pub struct FlatQueue<T> {
25	ids: Vec<T>,
26	values: Vec<f64>, // priority
27	len: usize,
28	}
29	impl<T: Clone> Default for FlatQueue<T> {
NEW 30	fn default() -> Self {	×
NEW 31	Self::new()	×
NEW 32	}	×
33	}
34	impl<T: Clone> FlatQueue<T> {
35	/// Creates a new empty queue.
36	pub fn new() -> Self {	6✔
37	Self { ids: Vec::new(), values: Vec::new(), len: 0 }	6✔
38	}	6✔
39
40	/// Returns the number of items.
41	pub fn len(&self) -> usize {	113✔
42	self.len	113✔
43	}	113✔
44
45	/// Returns whether the queue is empty.
46	pub fn is_empty(&self) -> bool {	60✔
47	self.len == 0	60✔
48	}	60✔
49
50	/// Clears all items from the queue.
NEW 51	pub fn clear(&mut self) {	×
NEW 52	self.len = 0;	×
NEW 53	}	×
54
55	/// Adds `item` to the queue with the specified `priority`.
56	///
57	/// `priority` must be a number. Items are sorted and returned from low to high priority. Multiple items
58	/// with the same priority value can be added to the queue, but there is no guaranteed order between these items.
59	///
60	/// ## Parameters
61	/// - `item`: the item to add
62	/// - `priority`: the priority of the item
63	pub fn push(&mut self, item: T, priority: f64) {	284✔
64	let mut pos = self.len;	284✔
65	self.len += 1;	284✔
66
67	if self.ids.len() < self.len {	284✔
68	self.ids.resize(self.len, item.clone());	258✔
69	self.values.resize(self.len, priority);	258✔
70	}	258✔
71
72	while pos > 0 {	504✔
73	let parent = (pos - 1) >> 1;	484✔
74	let parent_value = self.values[parent];	484✔
75	if priority >= parent_value {	484✔
76	break;	264✔
77	}	220✔
78	self.ids[pos] = self.ids[parent].clone();	220✔
79	self.values[pos] = parent_value;	220✔
80	pos = parent;	220✔
81	}
82
83	self.ids[pos] = item;	284✔
84	self.values[pos] = priority;	284✔
85	}	284✔
86
87	/// Removes and returns the item from the head of this queue, which is one of
88	/// the items with the lowest priority. If this queue is empty, returns `undefined`.
89	///
90	/// ## Returns
91	/// the item from the head of this queue
92	pub fn pop(&mut self) -> Option<T> {	158✔
93	if self.len == 0 {	158✔
94	return None;	2✔
95	}	156✔
96
97	let top = self.ids[0].clone();	156✔
98	self.len -= 1;	156✔
99
100	if self.len > 0 {	156✔
101	let id = self.ids[self.len].clone();	148✔
102	let value = self.values[self.len];	148✔
103	let mut pos = 0;	148✔
104	let half_len = self.len >> 1;	148✔
105
106	while pos < half_len {	702✔
107	let left = (pos << 1) + 1;	589✔
108	let right = left + 1;	589✔
109	let mut child = left;	589✔
110	if right < self.len && self.values[right] < self.values[left] {	589✔
111	child = right;	278✔
112	}	311✔
113	if self.values[child] >= value {	589✔
114	break;	35✔
115	}	554✔
116	self.ids[pos] = self.ids[child].clone();	554✔
117	self.values[pos] = self.values[child];	554✔
118	pos = child;	554✔
119	}
120
121	self.ids[pos] = id;	148✔
122	self.values[pos] = value;	148✔
123	}	8✔
124
125	Some(top)	156✔
126	}	158✔
127
128	/// Returns the item with the lowest priority without removing it.
129	pub fn peek(&self) -> Option<&T> {	44✔
130	if self.len > 0 { Some(&self.ids[0]) } else { None }	44✔
131	}	44✔
132
133	/// Returns the priority of the lowest-priority item.
134	pub fn peek_value(&self) -> Option<f64> {	28✔
135	if self.len > 0 { Some(self.values[0]) } else { None }	28✔
136	}	28✔
137
138	/// Shrinks underlying arrays to current length.
139	pub fn shrink(&mut self) {	1✔
140	self.ids.truncate(self.len);	1✔
141	self.values.truncate(self.len);	1✔
142	}	1✔
143	}

Open-S2 / gis-tools / #104

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous