Mercurial > repos > alg_tools / file comparison

comparison: src/sets.rs

src/sets.rs

branch
dev
changeset 63
f7b87d84864d
parent 41
121cf065e9ed
child 75
e9f4550cfa18
equal deleted inserted replaced
62:d8305c9b6fdf 63:f7b87d84864d
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 std::ops::{RangeFull,RangeFrom,Range,RangeInclusive,RangeTo,RangeToInclusive};
6 use std::marker::PhantomData;
7 use crate::types::*; 6 use crate::types::*;
8 use crate::loc::Loc; 7 use crate::loc::Loc;
9 use crate::euclidean::Dot; 8 use crate::euclidean::Euclidean;
9 use crate::instance::{Space, Instance};
10 use serde::Serialize; 10 use serde::Serialize;
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 : ?Sized { 16 pub trait Set<U> where U : Space {
17 /// Check for element containment 17 /// Check for element containment
18 fn contains(&self, item : &U) -> bool; 18 fn contains<I : Instance<U>>(&self, item : I) -> bool;
19 } 19 }
20 20
21 /// Additional ordering (besides [`PartialOrd`]) of a subfamily of sets: 21 /// Additional ordering (besides [`PartialOrd`]) of a subfamily of sets:
22 /// greatest lower bound and least upper bound. 22 /// greatest lower bound and least upper bound.
23 pub trait SetOrd : Sized { 23 pub trait SetOrd : Sized {
29 } 29 }
30 30
31 impl<U, const N : usize> Set<Loc<U, N>> 31 impl<U, const N : usize> Set<Loc<U, N>>
32 for Cube<U,N> 32 for Cube<U,N>
33 where U : Num + PartialOrd + Sized { 33 where U : Num + PartialOrd + Sized {
34 fn contains(&self, item : &Loc<U, N>) -> bool { 34 fn contains<I : Instance<Loc<U, N>>>(&self, item : I) -> bool {
35 self.0.iter().zip(item.iter()).all(|(s, x)| s.contains(x)) 35 self.0.iter().zip(item.ref_instance().iter()).all(|(s, x)| s.contains(x))
36 } 36 }
37 } 37 }
38 38
39 impl<U> Set<U> for RangeFull { 39 impl<U : Space> Set<U> for RangeFull {
40 fn contains(&self, _item : &U) -> bool { true } 40 fn contains<I : Instance<U>>(&self, _item : I) -> bool { true }
41 } 41 }
42 42
43 macro_rules! impl_ranges { 43 macro_rules! impl_ranges {
44 ($($range:ident),*) => { $( 44 ($($range:ident),*) => { $(
45 impl<U,Idx> Set<U> 45 impl<U,Idx> Set<U> for $range<Idx>
46 for $range<Idx> 46 where
47 where Idx : PartialOrd<U>, U : PartialOrd<Idx> + ?Sized, Idx : PartialOrd { 47 Idx : PartialOrd<U>,
48 U : PartialOrd<Idx> + Space,
49 Idx : PartialOrd
50 {
48 #[inline] 51 #[inline]
49 fn contains(&self, item : &U) -> bool { $range::contains(&self, item) } 52 fn contains<I : Instance<U>>(&self, item : I) -> bool {
53 item.eval(|x| $range::contains(&self, x))
54 }
50 } 55 }
51 )* } 56 )* }
52 } 57 }
53 58
54 impl_ranges!(RangeFrom,Range,RangeInclusive,RangeTo,RangeToInclusive); 59 impl_ranges!(RangeFrom,Range,RangeInclusive,RangeTo,RangeToInclusive);
59 /// vector and $t$ the offset. 64 /// vector and $t$ the offset.
60 /// 65 ///
61 /// `U` is the element type, `F` the floating point number type, and `A` the type of the 66 /// `U` is the element type, `F` the floating point number type, and `A` the type of the
62 /// orthogonal (dual) vectors. They need implement [`Dot<U, F>`]. 67 /// orthogonal (dual) vectors. They need implement [`Dot<U, F>`].
63 #[derive(Clone,Copy,Debug,Serialize,Eq,PartialEq)] 68 #[derive(Clone,Copy,Debug,Serialize,Eq,PartialEq)]
64 pub struct Halfspace<A, F, U> where A : Dot<U, F>, F : Float { 69 pub struct Halfspace<A, F> where A : Euclidean<F>, F : Float {
65 pub orthogonal : A, 70 pub orthogonal : A,
66 pub offset : F, 71 pub offset : F,
67 _phantom : PhantomData<U>,
68 } 72 }
69 73
70 impl<A,F,U> Halfspace<A,F,U> where A : Dot<U,F>, F : Float { 74 impl<A,F> Halfspace<A,F> where A : Euclidean<F>, F : Float {
71 #[inline] 75 #[inline]
72 pub fn new(orthogonal : A, offset : F) -> Self { 76 pub fn new(orthogonal : A, offset : F) -> Self {
73 Halfspace{ orthogonal : orthogonal, offset : offset, _phantom : PhantomData } 77 Halfspace{ orthogonal : orthogonal, offset : offset }
74 } 78 }
75 } 79 }
76 80
77 /// Trait for generating a halfspace spanned by another set `Self` of elements of type `U`. 81 /// Trait for generating a halfspace spanned by another set `Self` of elements of type `U`.
78 pub trait SpannedHalfspace<F, U> where F : Float { 82 pub trait SpannedHalfspace<F> where F : Float {
79 /// Type of the orthogonal vector describing the halfspace. 83 /// Type of the orthogonal vector describing the halfspace.
80 type A : Dot<U, F>; 84 type A : Euclidean<F>;
81 /// Returns the halfspace spanned by this set. 85 /// Returns the halfspace spanned by this set.
82 fn spanned_halfspace(&self) -> Halfspace<Self::A, F, U>; 86 fn spanned_halfspace(&self) -> Halfspace<Self::A, F>;
83 } 87 }
84 88
85 // TODO: Gram-Schmidt for higher N. 89 // TODO: Gram-Schmidt for higher N.
86 impl<F : Float> SpannedHalfspace<F,Loc<F, 1>> for [Loc<F, 1>; 2] { 90 impl<F : Float> SpannedHalfspace<F> for [Loc<F, 1>; 2] {
87 type A = Loc<F, 1>; 91 type A = Loc<F, 1>;
88 fn spanned_halfspace(&self) -> Halfspace<Self::A, F, Loc<F, 1>> { 92 fn spanned_halfspace(&self) -> Halfspace<Self::A, F> {
89 let (x0, x1) = (self[0], self[1]); 93 let (x0, x1) = (self[0], self[1]);
90 Halfspace::new(x1-x0, x0[0]) 94 Halfspace::new(x1-x0, x0[0])
91 } 95 }
92 } 96 }
93 97
94 // TODO: Gram-Schmidt for higher N. 98 // TODO: Gram-Schmidt for higher N.
95 impl<F : Float> SpannedHalfspace<F,Loc<F, 2>> for [Loc<F, 2>; 2] { 99 impl<F : Float> SpannedHalfspace<F> for [Loc<F, 2>; 2] {
96 type A = Loc<F, 2>; 100 type A = Loc<F, 2>;
97 fn spanned_halfspace(&self) -> Halfspace<Self::A, F, Loc<F, 2>> { 101 fn spanned_halfspace(&self) -> Halfspace<Self::A, F> {
98 let (x0, x1) = (&self[0], &self[1]); 102 let (x0, x1) = (&self[0], &self[1]);
99 let d = x1 - x0; 103 let d = x1 - x0;
100 let orthog = loc![d[1], -d[0]]; // We don't normalise for efficiency 104 let orthog = loc![d[1], -d[0]]; // We don't normalise for efficiency
101 let offset = x0.dot(&orthog); 105 let offset = x0.dot(&orthog);
102 Halfspace::new(orthog, offset) 106 Halfspace::new(orthog, offset)
103 } 107 }
104 } 108 }
105 109
106 impl<A,U,F> Set<U> for Halfspace<A,F,U> where A : Dot<U,F>, F : Float { 110 impl<A,F> Set<A> for Halfspace<A,F>
111 where
112 A : Euclidean<F>,
113 F : Float,
114 {
107 #[inline] 115 #[inline]
108 fn contains(&self, item : &U) -> bool { 116 fn contains<I : Instance<A>>(&self, item : I) -> bool {
109 self.orthogonal.dot(item) >= self.offset 117 self.orthogonal.dot(item) >= self.offset
110 } 118 }
111 } 119 }
112 120
113 /// Polygons defined by `N` `Halfspace`s. 121 /// Polygons defined by `N` `Halfspace`s.
114 #[derive(Clone,Copy,Debug,Eq,PartialEq)] 122 #[derive(Clone,Copy,Debug,Eq,PartialEq)]
115 pub struct NPolygon<A, F, U, const N : usize>(pub [Halfspace<A,F,U>; N]) where A : Dot<U,F>, F : Float; 123 pub struct NPolygon<A, F, const N : usize>(pub [Halfspace<A,F>; N])
124 where A : Euclidean<F>, F : Float;
116 125
117 impl<A,U,F,const N : usize> Set<U> for NPolygon<A,F,U,N> where A : Dot<U,F>, F : Float { 126 impl<A,F,const N : usize> Set<A> for NPolygon<A,F,N>
118 fn contains(&self, item : &U) -> bool { 127 where
119 self.0.iter().all(|halfspace| halfspace.contains(item)) 128 A : Euclidean<F>,
129 F : Float,
130 {
131 fn contains<I : Instance<A>>(&self, item : I) -> bool {
132 let r = item.ref_instance();
133 self.0.iter().all(|halfspace| halfspace.contains(r))
120 } 134 }
121 } 135 }

Mercurial Repository: alg_tools

mercurial