Mercurial > repos > alg_tools / file comparison

comparison: src/sets.rs

src/sets.rs

changeset 198
3868555d135c
parent 171
fa8df5a14486
equal deleted inserted replaced
94:1f19c6bbf07b 198:3868555d135c
1 /*! 1 /*!
2 This module provides various sets and traits for them. 2 This module provides various sets and traits for them.
3 */ 3 */
4 4
5 use std::ops::{RangeFull,RangeFrom,Range,RangeInclusive,RangeTo,RangeToInclusive}; 5 use crate::euclidean::Euclidean;
6 use crate::instance::{BasicDecomposition, Instance, Space};
7 use crate::loc::Loc;
6 use crate::types::*; 8 use crate::types::*;
7 use crate::loc::Loc;
8 use crate::euclidean::Euclidean;
9 use crate::instance::{Space, Instance};
10 use serde::Serialize; 9 use serde::Serialize;
10 use std::ops::{Range, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive};
11 11
12 pub mod cube; 12 pub mod cube;
13 pub use cube::Cube; 13 pub use cube::Cube;
14 14
15 /// Trait for arbitrary sets. The parameter `U` is the element type. 15 /// Trait for arbitrary sets. The parameter `U` is the element type.
16 pub trait Set<U> where U : Space { 16 pub trait Set<U>
17 where
18 U: Space,
19 {
17 /// Check for element containment 20 /// Check for element containment
18 fn contains<I : Instance<U>>(&self, item : I) -> bool; 21 fn contains<I: Instance<U>>(&self, item: I) -> bool;
19 } 22 }
20 23
21 /// Additional ordering (besides [`PartialOrd`]) of a subfamily of sets: 24 /// Additional ordering (besides [`PartialOrd`]) of a subfamily of sets:
22 /// greatest lower bound and least upper bound. 25 /// greatest lower bound and least upper bound.
23 pub trait SetOrd : Sized { 26 pub trait SetOrd: Sized {
24 /// Returns the smallest set of same class contain both parameters. 27 /// Returns the smallest set of same class contain both parameters.
25 fn common(&self, other : &Self) -> Self; 28 fn common(&self, other: &Self) -> Self;
26 29
27 /// Returns the greatest set of same class contaied by n both parameter sets. 30 /// Returns the greatest set of same class contaied by n both parameter sets.
28 fn intersect(&self, other : &Self) -> Option<Self>; 31 fn intersect(&self, other: &Self) -> Option<Self>;
29 } 32 }
30 33
31 impl<U, const N : usize> Set<Loc<U, N>> 34 impl<U, const N: usize> Set<Loc<N, U>> for Cube<N, U>
32 for Cube<U,N> 35 where
33 where U : Num + PartialOrd + Sized { 36 U: Num + PartialOrd + Sized,
34 fn contains<I : Instance<Loc<U, N>>>(&self, item : I) -> bool { 37 {
35 self.0.iter().zip(item.ref_instance().iter()).all(|(s, x)| s.contains(x)) 38 fn contains<I: Instance<Loc<N, U>>>(&self, item: I) -> bool {
39 item.eval_ref(|r| self.0.iter().zip(r.iter()).all(|(s, x)| s.contains(x)))
36 } 40 }
37 } 41 }
38 42
39 impl<U : Space> Set<U> for RangeFull { 43 impl<U: Space> Set<U> for RangeFull {
40 fn contains<I : Instance<U>>(&self, _item : I) -> bool { true } 44 fn contains<I: Instance<U>>(&self, _item: I) -> bool {
45 true
46 }
41 } 47 }
42 48
43 macro_rules! impl_ranges { 49 macro_rules! impl_ranges {
44 ($($range:ident),*) => { $( 50 ($($range:ident),*) => { $(
45 impl<U,Idx> Set<U> for $range<Idx> 51 impl<U,Idx> Set<U> for $range<Idx>
46 where 52 where
47 Idx : PartialOrd<U>, 53 U : Space<Decomp=BasicDecomposition>,
48 U : PartialOrd<Idx> + Space, 54 U::Principal : PartialOrd<Idx>,
49 Idx : PartialOrd 55 Idx : PartialOrd + PartialOrd<U::Principal>,
50 { 56 {
51 #[inline] 57 #[inline]
52 fn contains<I : Instance<U>>(&self, item : I) -> bool { 58 fn contains<I : Instance<U>>(&self, item : I) -> bool {
53 item.eval(|x| $range::contains(&self, x)) 59 item.eval(|x| $range::contains(&self, x))
54 } 60 }
55 } 61 }
56 )* } 62 )* }
57 } 63 }
58 64
59 impl_ranges!(RangeFrom,Range,RangeInclusive,RangeTo,RangeToInclusive); 65 impl_ranges!(RangeFrom, Range, RangeInclusive, RangeTo, RangeToInclusive);
60 66
61 /// Halfspaces described by an orthogonal vector and an offset. 67 /// Halfspaces described by an orthogonal vector and an offset.
62 /// 68 ///
63 /// The halfspace is $H = \\{ t v + a \mid a^⊤ v = 0 \\}$, where $v$ is the orthogonal 69 /// The halfspace is $H = \\{ t v + a \mid a^⊤ v = 0 \\}$, where $v$ is the orthogonal
64 /// vector and $t$ the offset. 70 /// vector and $t$ the offset.
65 #[derive(Clone,Copy,Debug,Serialize,Eq,PartialEq)] 71 #[derive(Clone, Copy, Debug, Serialize, Eq, PartialEq)]
66 pub struct Halfspace<A, F> where A : Euclidean<F>, F : Float { 72 pub struct Halfspace<A, F>
67 pub orthogonal : A, 73 where
68 pub offset : F, 74 A: Euclidean<F>,
75 F: Float,
76 {
77 pub orthogonal: A,
78 pub offset: F,
69 } 79 }
70 80
71 impl<A,F> Halfspace<A,F> where A : Euclidean<F>, F : Float { 81 impl<A, F> Halfspace<A, F>
82 where
83 A: Euclidean<F>,
84 F: Float,
85 {
72 #[inline] 86 #[inline]
73 pub fn new(orthogonal : A, offset : F) -> Self { 87 pub fn new(orthogonal: A, offset: F) -> Self {
74 Halfspace{ orthogonal : orthogonal, offset : offset } 88 Halfspace { orthogonal: orthogonal, offset: offset }
75 } 89 }
76 } 90 }
77 91
78 /// Trait for generating a halfspace spanned by another set `Self` of elements of type `U`. 92 /// Trait for generating a halfspace spanned by another set `Self` of elements of type `U`.
79 pub trait SpannedHalfspace<F> where F : Float { 93 pub trait SpannedHalfspace<F>
94 where
95 F: Float,
96 {
80 /// Type of the orthogonal vector describing the halfspace. 97 /// Type of the orthogonal vector describing the halfspace.
81 type A : Euclidean<F>; 98 type A: Euclidean<F>;
82 /// Returns the halfspace spanned by this set. 99 /// Returns the halfspace spanned by this set.
83 fn spanned_halfspace(&self) -> Halfspace<Self::A, F>; 100 fn spanned_halfspace(&self) -> Halfspace<Self::A, F>;
84 } 101 }
85 102
86 // TODO: Gram-Schmidt for higher N. 103 // TODO: Gram-Schmidt for higher N.
87 impl<F : Float> SpannedHalfspace<F> for [Loc<F, 1>; 2] { 104 impl<F: Float> SpannedHalfspace<F> for [Loc<1, F>; 2] {
88 type A = Loc<F, 1>; 105 type A = Loc<1, F>;
89 fn spanned_halfspace(&self) -> Halfspace<Self::A, F> { 106 fn spanned_halfspace(&self) -> Halfspace<Self::A, F> {
90 let (x0, x1) = (self[0], self[1]); 107 let (x0, x1) = (self[0], self[1]);
91 Halfspace::new(x1-x0, x0[0]) 108 Halfspace::new(x1 - x0, x0[0])
92 } 109 }
93 } 110 }
94 111
95 // TODO: Gram-Schmidt for higher N. 112 // TODO: Gram-Schmidt for higher N.
96 impl<F : Float> SpannedHalfspace<F> for [Loc<F, 2>; 2] { 113 impl<F: Float> SpannedHalfspace<F> for [Loc<2, F>; 2] {
97 type A = Loc<F, 2>; 114 type A = Loc<2, F>;
98 fn spanned_halfspace(&self) -> Halfspace<Self::A, F> { 115 fn spanned_halfspace(&self) -> Halfspace<Self::A, F> {
99 let (x0, x1) = (&self[0], &self[1]); 116 let (x0, x1) = (&self[0], &self[1]);
100 let d = x1 - x0; 117 let d = x1 - x0;
101 let orthog = loc![d[1], -d[0]]; // We don't normalise for efficiency 118 let orthog = loc![d[1], -d[0]]; // We don't normalise for efficiency
102 let offset = x0.dot(&orthog); 119 let offset = x0.dot(&orthog);
103 Halfspace::new(orthog, offset) 120 Halfspace::new(orthog, offset)
104 } 121 }
105 } 122 }
106 123
107 impl<A,F> Set<A> for Halfspace<A,F> 124 impl<A, F> Set<A> for Halfspace<A, F>
108 where 125 where
109 A : Euclidean<F>, 126 A: Euclidean<F>,
110 F : Float, 127 F: Float,
111 { 128 {
112 #[inline] 129 #[inline]
113 fn contains<I : Instance<A>>(&self, item : I) -> bool { 130 fn contains<I: Instance<A>>(&self, item: I) -> bool {
114 self.orthogonal.dot(item) >= self.offset 131 self.orthogonal.dot(item) >= self.offset
115 } 132 }
116 } 133 }
117 134
118 /// Polygons defined by `N` `Halfspace`s. 135 /// Polygons defined by `N` `Halfspace`s.
119 #[derive(Clone,Copy,Debug,Eq,PartialEq)] 136 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
120 pub struct NPolygon<A, F, const N : usize>(pub [Halfspace<A,F>; N]) 137 pub struct NPolygon<A, const N: usize, F = f64>(pub [Halfspace<A, F>; N])
121 where A : Euclidean<F>, F : Float; 138 where
139 A: Euclidean<F>,
140 F: Float;
122 141
123 impl<A,F,const N : usize> Set<A> for NPolygon<A,F,N> 142 impl<A, F, const N: usize> Set<A> for NPolygon<A, N, F>
124 where 143 where
125 A : Euclidean<F>, 144 A: Euclidean<F>,
126 F : Float, 145 F: Float,
127 { 146 {
128 fn contains<I : Instance<A>>(&self, item : I) -> bool { 147 fn contains<I: Instance<A>>(&self, item: I) -> bool {
129 let r = item.ref_instance(); 148 item.eval_ref(|r| self.0.iter().all(|halfspace| halfspace.contains(r)))
130 self.0.iter().all(|halfspace| halfspace.contains(r))
131 } 149 }
132 } 150 }

Mercurial Repository: alg_tools

mercurial