1use std::{
2 borrow::Borrow,
3 fmt,
4 mem,
5 ops::{Add, Bound, Sub},
6};
7
8use crate::{
9 CoordPair,
10 coords::CoordRange,
11 orientation::{Axis, Direction, DirectionFlags},
12};
13
14use super::{CoordMap, map};
15
16#[cfg(test)]
17mod test;
18
19#[derive(Debug)]
20pub enum ConnectError<C> {
21 UnknownNode(CoordPair<C>),
22 NoStraightDirection(CoordPair<C>, CoordPair<C>),
23}
24
25impl<C> fmt::Display for ConnectError<C>
26where
27 C: fmt::Display,
28{
29 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
30 match self {
31 Self::UnknownNode(location) => {
32 write!(f, "node location {location} is unknown")
33 },
34 Self::NoStraightDirection(a, b) => write!(
35 f,
36 "nodes with locations {a} and {b} do not have a straight \
37 direction"
38 ),
39 }
40 }
41}
42
43impl<C> std::error::Error for ConnectError<C> where C: fmt::Display + fmt::Debug {}
44
45#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
46pub struct Node {
47 edges: DirectionFlags,
48}
49
50impl Node {
51 pub fn new() -> Self {
52 Self::default()
53 }
54
55 pub fn connected(self, direction: Direction) -> bool {
56 self.edges.map()[direction]
57 }
58
59 pub fn connect(&mut self, direction: Direction) -> bool {
60 !self.edges.modify(|map| mem::replace(&mut map[direction], true))
61 }
62
63 pub fn with_connection(mut self, direction: Direction) -> Self {
64 self.connect(direction);
65 self
66 }
67
68 pub fn disconnect(&mut self, direction: Direction) -> bool {
69 self.edges.modify(|map| mem::replace(&mut map[direction], false))
70 }
71}
72
73#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
74pub struct CoordGraph<C> {
75 inner: CoordDiGraph<C>,
76}
77
78impl<C> Default for CoordGraph<C> {
79 fn default() -> Self {
80 Self::new()
81 }
82}
83
84impl<C> CoordGraph<C> {
85 pub fn new() -> Self {
86 Self { inner: CoordDiGraph::new() }
87 }
88}
89
90impl<C> CoordGraph<C>
91where
92 C: Ord,
93{
94 pub fn contains_node<C0>(&self, location: CoordPair<&C0>) -> bool
95 where
96 C: Borrow<C0>,
97 C0: Ord,
98 {
99 self.inner.contains_node(location)
100 }
101
102 pub fn node<C0>(&self, location: CoordPair<&C0>) -> Option<Node>
103 where
104 C: Borrow<C0>,
105 C0: Ord,
106 {
107 self.inner.node(location)
108 }
109
110 pub fn node_with_location<C0>(
111 &self,
112 location: CoordPair<&C0>,
113 ) -> Option<(CoordPair<&C>, Node)>
114 where
115 C: Borrow<C0>,
116 C0: Ord,
117 {
118 self.inner.node_with_location(location)
119 }
120}
121
122impl<C> CoordGraph<C>
123where
124 C: Ord + Clone,
125{
126 pub fn insert_node(&mut self, node: CoordPair<C>) -> bool {
127 self.inner.insert_node(node)
128 }
129}
130
131impl<C> CoordGraph<C>
132where
133 C: Ord + Clone + Add<Output = C> + Sub<Output = C>,
134{
135 pub fn remove_node(
136 &mut self,
137 location: CoordPair<C>,
138 ) -> Result<bool, ConnectError<C>> {
139 self.inner.remove_node_undirected(location)
140 }
141
142 pub fn connected(
143 &self,
144 origin: CoordPair<C>,
145 destiny: CoordPair<C>,
146 ) -> Result<bool, ConnectError<C>> {
147 self.inner.connected(origin, destiny)
148 }
149
150 pub fn connect(
151 &mut self,
152 origin: CoordPair<C>,
153 destiny: CoordPair<C>,
154 ) -> Result<bool, ConnectError<C>> {
155 self.inner.connect_undirected(origin, destiny).map(|(a, b)| a || b)
156 }
157
158 pub fn disconnect(
159 &mut self,
160 origin: CoordPair<C>,
161 destiny: CoordPair<C>,
162 ) -> Result<bool, ConnectError<C>> {
163 self.inner.disconnect_undirected(origin, destiny).map(|(a, b)| a || b)
164 }
165}
166
167impl<C> CoordGraph<C> {
168 pub fn iter(&self, higher_axis: Axis) -> Iter<C> {
169 self.inner.iter(higher_axis)
170 }
171
172 pub fn rows(&self) -> Iter<C> {
173 self.iter(Axis::Y)
174 }
175
176 pub fn columns(&self) -> Iter<C> {
177 self.iter(Axis::X)
178 }
179
180 pub fn locations(&self, higher_axis: Axis) -> Locations<C> {
181 self.inner.locations(higher_axis)
182 }
183
184 pub fn location_rows(&self) -> Locations<C> {
185 self.locations(Axis::Y)
186 }
187
188 pub fn location_columns(&self) -> Locations<C> {
189 self.locations(Axis::X)
190 }
191
192 pub fn nodes(&self, higher_axis: Axis) -> Nodes<C> {
193 self.inner.nodes(higher_axis)
194 }
195
196 pub fn node_rows(&self) -> Nodes<C> {
197 self.nodes(Axis::Y)
198 }
199
200 pub fn node_columns(&self) -> Nodes<C> {
201 self.nodes(Axis::X)
202 }
203}
204
205impl<C> CoordGraph<C>
206where
207 C: Clone,
208{
209 pub fn into_iter_with(self, higher_axis: Axis) -> IntoIter<C> {
210 self.inner.into_iter_with(higher_axis)
211 }
212
213 pub fn into_rows(self) -> IntoIter<C> {
214 self.into_iter_with(Axis::Y)
215 }
216
217 pub fn into_columns(self) -> IntoIter<C> {
218 self.into_iter_with(Axis::X)
219 }
220
221 pub fn into_locations(self, higher_axis: Axis) -> IntoLocations<C> {
222 self.inner.into_locations(higher_axis)
223 }
224
225 pub fn into_location_rows(self) -> IntoLocations<C> {
226 self.into_locations(Axis::Y)
227 }
228
229 pub fn into_location_columns(self) -> IntoLocations<C> {
230 self.into_locations(Axis::X)
231 }
232}
233
234impl<C> CoordGraph<C> {
235 pub fn into_nodes(self, higher_axis: Axis) -> IntoNodes<C> {
236 self.inner.into_nodes(higher_axis)
237 }
238
239 pub fn into_node_rows(self) -> IntoNodes<C> {
240 self.into_nodes(Axis::Y)
241 }
242
243 pub fn into_node_columns(self) -> IntoNodes<C> {
244 self.into_nodes(Axis::X)
245 }
246}
247
248impl<C> CoordGraph<C>
249where
250 C: Ord,
251{
252 pub fn neighbors<'q, 'a, C0>(
253 &'a self,
254 location: CoordPair<&'q C0>,
255 direction: Direction,
256 ) -> Neighbors<'q, 'a, C0, C>
257 where
258 C: Borrow<C0>,
259 C0: Ord,
260 {
261 self.inner.neighbors(location, direction)
262 }
263
264 pub fn neighbors_inclusive<'q, 'a, C0>(
265 &'a self,
266 location: CoordPair<&'q C0>,
267 direction: Direction,
268 ) -> Neighbors<'q, 'a, C0, C>
269 where
270 C: Borrow<C0>,
271 C0: Ord,
272 {
273 self.inner.neighbors_inclusive(location, direction)
274 }
275}
276
277impl<C> IntoIterator for CoordGraph<C>
278where
279 C: Clone,
280{
281 type IntoIter = IntoIter<C>;
282 type Item = (CoordPair<C>, Node);
283
284 fn into_iter(self) -> Self::IntoIter {
285 self.into_rows()
286 }
287}
288
289impl<'a, C> IntoIterator for &'a CoordGraph<C>
290where
291 C: Clone,
292{
293 type IntoIter = Iter<'a, C>;
294 type Item = (CoordPair<&'a C>, Node);
295
296 fn into_iter(self) -> Self::IntoIter {
297 self.rows()
298 }
299}
300
301#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
302pub struct CoordDiGraph<C> {
303 nodes: CoordMap<C, Node>,
304}
305
306impl<C> Default for CoordDiGraph<C> {
307 fn default() -> Self {
308 Self::new()
309 }
310}
311
312impl<C> CoordDiGraph<C> {
313 pub fn new() -> Self {
314 Self { nodes: CoordMap::default() }
315 }
316}
317
318impl<C> CoordDiGraph<C>
319where
320 C: Ord,
321{
322 pub fn contains_node<C0>(&self, location: CoordPair<&C0>) -> bool
323 where
324 C: Borrow<C0>,
325 C0: Ord,
326 {
327 self.node(location).is_some()
328 }
329
330 pub fn node<C0>(&self, location: CoordPair<&C0>) -> Option<Node>
331 where
332 C: Borrow<C0>,
333 C0: Ord,
334 {
335 let (_, node) = self.node_with_location(location)?;
336 Some(node)
337 }
338
339 pub fn node_with_location<C0>(
340 &self,
341 location: CoordPair<&C0>,
342 ) -> Option<(CoordPair<&C>, Node)>
343 where
344 C: Borrow<C0>,
345 C0: Ord,
346 {
347 let (found_location, node) = self.nodes.get_key_value(location)?;
348 Some((found_location, *node))
349 }
350}
351
352impl<C> CoordDiGraph<C>
353where
354 C: Ord + Clone,
355{
356 pub fn insert_node(&mut self, node: CoordPair<C>) -> bool {
357 match self.nodes.entry(node) {
358 map::Entry::Occupied(_) => false,
359 map::Entry::Vacant(entry) => {
360 entry.insert(Node::default());
361 true
362 },
363 }
364 }
365}
366
367impl<C> CoordDiGraph<C>
368where
369 C: Ord + Clone + Add<Output = C> + Sub<Output = C>,
370{
371 pub fn remove_node(
372 &mut self,
373 location: CoordPair<C>,
374 ) -> Result<bool, ConnectError<C>> {
375 for direction in Direction::ALL {
376 let Some(_) = self
377 .nodes
378 .with_mut(location.as_ref(), |node| node.disconnect(direction))
379 else {
380 return Ok(false);
381 };
382 if self.neighbors(location.as_ref(), direction).next().is_none() {
383 if let Some(neighbor) = self
384 .neighbors(location.as_ref(), -direction)
385 .next()
386 .map(|(coords, _)| coords.cloned())
387 {
388 self.nodes.with_mut(neighbor.as_ref(), |node| {
389 node.disconnect(direction)
390 });
391 }
392 }
393 }
394 self.nodes.remove(location.as_ref());
395 Ok(true)
396 }
397
398 pub fn remove_node_undirected(
399 &mut self,
400 location: CoordPair<C>,
401 ) -> Result<bool, ConnectError<C>> {
402 for direction in Direction::ALL {
416 let Some(disconnected) = self
417 .nodes
418 .with_mut(location.as_ref(), |node| node.disconnect(direction))
419 else {
420 return Ok(false);
421 };
422 if self.neighbors(location.as_ref(), direction).next().is_none()
423 || !disconnected
424 {
425 if let Some(neighbor) = self
426 .neighbors(location.as_ref(), -direction)
427 .next()
428 .map(|(coords, _)| coords.cloned())
429 {
430 self.nodes.with_mut(neighbor.as_ref(), |node| {
431 node.disconnect(direction)
432 });
433 }
434 }
435 }
436 self.nodes.remove(location.as_ref());
437 Ok(true)
438 }
439
440 pub fn connected(
441 &self,
442 origin: CoordPair<C>,
443 destiny: CoordPair<C>,
444 ) -> Result<bool, ConnectError<C>> {
445 if !self.contains_node(origin.as_ref()) {
446 return Err(ConnectError::UnknownNode(origin));
447 }
448 if !self.contains_node(destiny.as_ref()) {
449 return Err(ConnectError::UnknownNode(destiny));
450 }
451 let Some(vector) = origin.clone().direction_to(destiny.clone()) else {
452 return Err(ConnectError::NoStraightDirection(origin, destiny));
453 };
454 let mut neighbors =
455 self.neighbors_inclusive(origin.as_ref(), vector.direction);
456 loop {
457 let Some((neighbor, node)) = neighbors.next() else {
458 break Ok(true);
459 };
460 if neighbor == destiny.as_ref() {
461 break Ok(true);
462 }
463 if !node.connected(vector.direction) {
464 break Ok(false);
465 }
466 }
467 }
468
469 pub fn undirected_connected(
470 &self,
471 origin: CoordPair<C>,
472 destiny: CoordPair<C>,
473 ) -> Result<bool, ConnectError<C>> {
474 if !self.contains_node(origin.as_ref()) {
475 return Err(ConnectError::UnknownNode(origin));
476 }
477 if !self.contains_node(destiny.as_ref()) {
478 return Err(ConnectError::UnknownNode(destiny));
479 }
480 let Some(vector) = origin.clone().direction_to(destiny.clone()) else {
481 return Err(ConnectError::NoStraightDirection(origin, destiny));
482 };
483 let mut neighbors =
484 self.neighbors_inclusive(origin.as_ref(), vector.direction);
485 loop {
486 let Some((neighbor, node)) = neighbors.next() else {
487 break Ok(true);
488 };
489 if neighbor != origin.as_ref() && !node.connected(-vector.direction)
490 {
491 break Ok(false);
492 }
493 if neighbor == destiny.as_ref() {
494 break Ok(true);
495 }
496 if !node.connected(vector.direction) {
497 break Ok(false);
498 }
499 }
500 }
501
502 pub fn connect(
503 &mut self,
504 origin: CoordPair<C>,
505 destiny: CoordPair<C>,
506 ) -> Result<bool, ConnectError<C>> {
507 if !self.contains_node(origin.as_ref()) {
508 return Err(ConnectError::UnknownNode(origin));
509 }
510 if !self.contains_node(destiny.as_ref()) {
511 return Err(ConnectError::UnknownNode(destiny));
512 }
513 let Some(vector) = origin.clone().direction_to(destiny.clone()) else {
514 return Err(ConnectError::NoStraightDirection(origin, destiny));
515 };
516 let mut current = origin;
517 let mut new = false;
518 while let Some((neighbor, _)) = self
519 .neighbors(current.as_ref(), vector.direction)
520 .next()
521 .filter(|_| current != destiny)
522 {
523 let next = neighbor.cloned();
524 self.nodes.with_mut(current.as_ref(), |node| {
525 new |= node.connect(vector.direction);
526 });
527 current = next;
528 }
529 Ok(new)
530 }
531
532 pub fn connect_undirected(
533 &mut self,
534 origin: CoordPair<C>,
535 destiny: CoordPair<C>,
536 ) -> Result<(bool, bool), ConnectError<C>> {
537 if !self.contains_node(origin.as_ref()) {
538 return Err(ConnectError::UnknownNode(origin));
539 }
540 if !self.contains_node(destiny.as_ref()) {
541 return Err(ConnectError::UnknownNode(destiny));
542 }
543 let Some(vector) = origin.clone().direction_to(destiny.clone()) else {
544 return Err(ConnectError::NoStraightDirection(origin, destiny));
545 };
546 let mut current = origin;
547 let mut new = false;
548 let mut new_rev = false;
549 while let Some((neighbor, _)) = self
550 .neighbors(current.as_ref(), vector.direction)
551 .next()
552 .filter(|_| current != destiny)
553 {
554 let next = neighbor.cloned();
555 self.nodes.with_mut(current.as_ref(), |node| {
556 new |= node.connect(vector.direction);
557 });
558 self.nodes.with_mut(next.as_ref(), |node| {
559 new_rev |= node.connect(-vector.direction);
560 });
561 current = next;
562 }
563 Ok((new, new_rev))
564 }
565
566 pub fn disconnect(
567 &mut self,
568 origin: CoordPair<C>,
569 destiny: CoordPair<C>,
570 ) -> Result<bool, ConnectError<C>> {
571 if !self.connected(origin.clone(), destiny.clone())? {
572 return Ok(false);
573 }
574 let Some(vector) = origin.clone().direction_to(destiny.clone()) else {
575 return Err(ConnectError::NoStraightDirection(origin, destiny));
576 };
577 let mut current = origin;
578 while let Some((neighbor, _)) = self
579 .neighbors(current.as_ref(), vector.direction)
580 .next()
581 .filter(|_| current != destiny)
582 {
583 let next = neighbor.cloned();
584 self.nodes.with_mut(current.as_ref(), |node| {
585 node.disconnect(vector.direction);
586 });
587 current = next;
588 }
589 Ok(true)
590 }
591
592 pub fn disconnect_undirected(
593 &mut self,
594 origin: CoordPair<C>,
595 destiny: CoordPair<C>,
596 ) -> Result<(bool, bool), ConnectError<C>> {
597 if !self.connected(origin.clone(), destiny.clone())?
598 && !self.connected(destiny.clone(), origin.clone())?
599 {
600 return Ok((false, false));
601 }
602 let Some(vector) = origin.clone().direction_to(destiny.clone()) else {
603 return Err(ConnectError::NoStraightDirection(origin, destiny));
604 };
605 let mut current = origin;
606 let mut new = false;
607 let mut new_rev = false;
608 while let Some((neighbor, _)) = self
609 .neighbors(current.as_ref(), vector.direction)
610 .next()
611 .filter(|_| current != destiny)
612 {
613 let next = neighbor.cloned();
614 self.nodes.with_mut(current.as_ref(), |node| {
615 new |= node.disconnect(vector.direction);
616 });
617 self.nodes.with_mut(next.as_ref(), |node| {
618 new_rev |= node.disconnect(-vector.direction);
619 });
620 current = next;
621 }
622 Ok((new, new_rev))
623 }
624}
625
626impl<C> CoordDiGraph<C> {
627 pub fn iter(&self, higher_axis: Axis) -> Iter<C> {
628 Iter { inner: self.nodes.iter(higher_axis) }
629 }
630
631 pub fn rows(&self) -> Iter<C> {
632 self.iter(Axis::Y)
633 }
634
635 pub fn columns(&self) -> Iter<C> {
636 self.iter(Axis::X)
637 }
638
639 pub fn locations(&self, higher_axis: Axis) -> Locations<C> {
640 Locations { inner: self.nodes.keys(higher_axis) }
641 }
642
643 pub fn location_rows(&self) -> Locations<C> {
644 self.locations(Axis::Y)
645 }
646
647 pub fn location_columns(&self) -> Locations<C> {
648 self.locations(Axis::X)
649 }
650
651 pub fn nodes(&self, higher_axis: Axis) -> Nodes<C> {
652 Nodes { inner: self.nodes.values(higher_axis) }
653 }
654
655 pub fn node_rows(&self) -> Nodes<C> {
656 self.nodes(Axis::Y)
657 }
658
659 pub fn node_columns(&self) -> Nodes<C> {
660 self.nodes(Axis::X)
661 }
662}
663
664impl<C> CoordDiGraph<C>
665where
666 C: Clone,
667{
668 pub fn into_iter_with(self, higher_axis: Axis) -> IntoIter<C> {
669 IntoIter { inner: self.nodes.into_iter_with(higher_axis) }
670 }
671
672 pub fn into_rows(self) -> IntoIter<C> {
673 self.into_iter_with(Axis::Y)
674 }
675
676 pub fn into_columns(self) -> IntoIter<C> {
677 self.into_iter_with(Axis::X)
678 }
679
680 pub fn into_locations(self, higher_axis: Axis) -> IntoLocations<C> {
681 IntoLocations { inner: self.nodes.into_keys(higher_axis) }
682 }
683
684 pub fn into_location_rows(self) -> IntoLocations<C> {
685 self.into_locations(Axis::Y)
686 }
687
688 pub fn into_location_columns(self) -> IntoLocations<C> {
689 self.into_locations(Axis::X)
690 }
691}
692
693impl<C> CoordDiGraph<C> {
694 pub fn into_nodes(self, higher_axis: Axis) -> IntoNodes<C> {
695 IntoNodes { inner: self.nodes.into_values(higher_axis) }
696 }
697
698 pub fn into_node_rows(self) -> IntoNodes<C> {
699 self.into_nodes(Axis::Y)
700 }
701
702 pub fn into_node_columns(self) -> IntoNodes<C> {
703 self.into_nodes(Axis::X)
704 }
705}
706
707impl<C> CoordDiGraph<C>
708where
709 C: Ord,
710{
711 pub fn neighbors<'q, 'a, C0>(
712 &'a self,
713 location: CoordPair<&'q C0>,
714 direction: Direction,
715 ) -> Neighbors<'q, 'a, C0, C>
716 where
717 C: Borrow<C0>,
718 C0: Ord,
719 {
720 match direction {
721 Direction::Up => Neighbors {
722 rev: true,
723 inner: self.nodes.range(
724 Axis::Y,
725 CoordRange {
726 y: .. location.y,
727 x: location.x ..= location.x,
728 }
729 .to_bounds(),
730 ),
731 },
732 Direction::Left => Neighbors {
733 rev: true,
734 inner: self.nodes.range(
735 Axis::X,
736 CoordRange {
737 y: location.y ..= location.y,
738 x: .. location.x,
739 }
740 .to_bounds(),
741 ),
742 },
743 Direction::Down => Neighbors {
744 rev: false,
745 inner: self.nodes.range(
746 Axis::Y,
747 CoordRange {
748 y: (Bound::Excluded(location.y), Bound::Unbounded),
749 x: location.x ..= location.x,
750 }
751 .to_bounds(),
752 ),
753 },
754 Direction::Right => Neighbors {
755 rev: false,
756 inner: self.nodes.range(
757 Axis::X,
758 CoordRange {
759 y: location.y ..= location.y,
760 x: (Bound::Excluded(location.x), Bound::Unbounded),
761 }
762 .to_bounds(),
763 ),
764 },
765 }
766 }
767
768 pub fn neighbors_inclusive<'q, 'a, C0>(
769 &'a self,
770 location: CoordPair<&'q C0>,
771 direction: Direction,
772 ) -> Neighbors<'q, 'a, C0, C>
773 where
774 C: Borrow<C0>,
775 C0: Ord,
776 {
777 match direction {
778 Direction::Up => Neighbors {
779 rev: true,
780 inner: self.nodes.range(
781 Axis::Y,
782 CoordRange {
783 y: ..= location.y,
784 x: location.x ..= location.x,
785 }
786 .to_bounds(),
787 ),
788 },
789 Direction::Left => Neighbors {
790 rev: true,
791 inner: self.nodes.range(
792 Axis::X,
793 CoordRange {
794 y: location.y ..= location.y,
795 x: ..= location.x,
796 }
797 .to_bounds(),
798 ),
799 },
800 Direction::Down => Neighbors {
801 rev: false,
802 inner: self.nodes.range(
803 Axis::Y,
804 CoordRange {
805 y: location.y ..,
806 x: location.x ..= location.x,
807 }
808 .to_bounds(),
809 ),
810 },
811 Direction::Right => Neighbors {
812 rev: false,
813 inner: self.nodes.range(
814 Axis::X,
815 CoordRange {
816 y: location.y ..= location.y,
817 x: location.x ..,
818 }
819 .to_bounds(),
820 ),
821 },
822 }
823 }
824}
825
826impl<C> IntoIterator for CoordDiGraph<C>
827where
828 C: Clone,
829{
830 type IntoIter = IntoIter<C>;
831 type Item = (CoordPair<C>, Node);
832
833 fn into_iter(self) -> Self::IntoIter {
834 self.into_rows()
835 }
836}
837
838impl<'a, C> IntoIterator for &'a CoordDiGraph<C>
839where
840 C: Clone,
841{
842 type IntoIter = Iter<'a, C>;
843 type Item = (CoordPair<&'a C>, Node);
844
845 fn into_iter(self) -> Self::IntoIter {
846 self.rows()
847 }
848}
849
850#[derive(Debug, Clone)]
851pub struct Neighbors<'q, 'a, C0, C> {
852 inner: map::Range<'q, 'a, C0, C, Node>,
853 rev: bool,
854}
855
856impl<'q, 'a, C0, C> Iterator for Neighbors<'q, 'a, C0, C>
857where
858 C: Ord + Borrow<C0>,
859 C0: Ord,
860{
861 type Item = (CoordPair<&'a C>, Node);
862
863 fn next(&mut self) -> Option<Self::Item> {
864 let (location, node) = if self.rev {
865 self.inner.next_back()?
866 } else {
867 self.inner.next()?
868 };
869 Some((location, *node))
870 }
871
872 fn size_hint(&self) -> (usize, Option<usize>) {
873 self.inner.size_hint()
874 }
875}
876
877impl<'q, 'a, C0, C> DoubleEndedIterator for Neighbors<'q, 'a, C0, C>
878where
879 C: Ord + Borrow<C0>,
880 C0: Ord,
881{
882 fn next_back(&mut self) -> Option<Self::Item> {
883 let (location, node) = if self.rev {
884 self.inner.next()?
885 } else {
886 self.inner.next_back()?
887 };
888 Some((location, *node))
889 }
890}
891
892#[derive(Debug, Clone)]
893pub struct Iter<'a, C> {
894 inner: map::Iter<'a, C, Node>,
895}
896
897impl<'a, C> Iterator for Iter<'a, C> {
898 type Item = (CoordPair<&'a C>, Node);
899
900 fn next(&mut self) -> Option<Self::Item> {
901 self.inner.next().map(|(location, node)| (location, *node))
902 }
903
904 fn size_hint(&self) -> (usize, Option<usize>) {
905 self.inner.size_hint()
906 }
907}
908
909impl<'a, C> DoubleEndedIterator for Iter<'a, C> {
910 fn next_back(&mut self) -> Option<Self::Item> {
911 self.inner.next_back().map(|(location, node)| (location, *node))
912 }
913}
914
915#[derive(Debug, Clone)]
916pub struct Locations<'a, C> {
917 inner: map::Keys<'a, C, Node>,
918}
919
920impl<'a, C> Iterator for Locations<'a, C> {
921 type Item = CoordPair<&'a C>;
922
923 fn next(&mut self) -> Option<Self::Item> {
924 self.inner.next()
925 }
926
927 fn size_hint(&self) -> (usize, Option<usize>) {
928 self.inner.size_hint()
929 }
930}
931
932impl<'a, C> DoubleEndedIterator for Locations<'a, C> {
933 fn next_back(&mut self) -> Option<Self::Item> {
934 self.inner.next_back()
935 }
936}
937
938#[derive(Debug, Clone)]
939pub struct Nodes<'a, C> {
940 inner: map::Values<'a, C, Node>,
941}
942
943impl<'a, C> Iterator for Nodes<'a, C> {
944 type Item = Node;
945
946 fn next(&mut self) -> Option<Self::Item> {
947 self.inner.next().copied()
948 }
949
950 fn size_hint(&self) -> (usize, Option<usize>) {
951 self.inner.size_hint()
952 }
953}
954
955impl<'a, C> DoubleEndedIterator for Nodes<'a, C> {
956 fn next_back(&mut self) -> Option<Self::Item> {
957 self.inner.next_back().copied()
958 }
959}
960
961#[derive(Debug)]
962pub struct IntoIter<C> {
963 inner: map::IntoIter<C, Node>,
964}
965
966impl<C> Iterator for IntoIter<C>
967where
968 C: Clone,
969{
970 type Item = (CoordPair<C>, Node);
971
972 fn next(&mut self) -> Option<Self::Item> {
973 self.inner.next()
974 }
975
976 fn size_hint(&self) -> (usize, Option<usize>) {
977 self.inner.size_hint()
978 }
979}
980
981impl<C> DoubleEndedIterator for IntoIter<C>
982where
983 C: Clone,
984{
985 fn next_back(&mut self) -> Option<Self::Item> {
986 self.inner.next_back()
987 }
988}
989
990#[derive(Debug)]
991pub struct IntoLocations<C> {
992 inner: map::IntoKeys<C, Node>,
993}
994
995impl<C> Iterator for IntoLocations<C>
996where
997 C: Clone,
998{
999 type Item = CoordPair<C>;
1000
1001 fn next(&mut self) -> Option<Self::Item> {
1002 self.inner.next()
1003 }
1004
1005 fn size_hint(&self) -> (usize, Option<usize>) {
1006 self.inner.size_hint()
1007 }
1008}
1009
1010impl<C> DoubleEndedIterator for IntoLocations<C>
1011where
1012 C: Clone,
1013{
1014 fn next_back(&mut self) -> Option<Self::Item> {
1015 self.inner.next_back()
1016 }
1017}
1018
1019#[derive(Debug)]
1020pub struct IntoNodes<C> {
1021 inner: map::IntoValues<C, Node>,
1022}
1023
1024impl<C> Iterator for IntoNodes<C> {
1025 type Item = Node;
1026
1027 fn next(&mut self) -> Option<Self::Item> {
1028 self.inner.next()
1029 }
1030
1031 fn size_hint(&self) -> (usize, Option<usize>) {
1032 self.inner.size_hint()
1033 }
1034}
1035
1036impl<C> DoubleEndedIterator for IntoNodes<C> {
1037 fn next_back(&mut self) -> Option<Self::Item> {
1038 self.inner.next_back()
1039 }
1040}