1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267
//! //!Traits for ordered structures //! use crate::algebra::*; pub use core::cmp::{PartialOrd, Ord}; /// ///A marker trait signifying that for `x > y`, `x+z > x+z` and `z+x > z+x` for all `z` /// ///Note that for [monoids](AddMonoid) with some negative or positive element `x` this ///_automatically_ means that the magma is infinite, as otherwise, there would be a ///maximum element `M` and minimum `m`, contradicting `M + x > M + 0 = M` (if `x > 0`) ///or `m + x < m + 0 = m` (if `x < 0`). (Of course, the bitwise representations of these ///structures size limited by size, but in practice, we treat them as infinite anyway.) /// ///Futhermore, for [monoids](AddMonoid) and [groups](AddGroup), this provides a way to embed the ///[Naturals](Natural) and [Integers](Integer) into the structure respectively, and if the structure also is ///an ordered semiring with [one](One), then there is even a canonical embedding following both addition ///and multiplication rules /// pub trait AddOrdered: PartialOrd {} /// ///A marker trait signifying that for `x > y`, `x*z > x*z` and `z*x > z*x` for all `z > 0` /// ///Like for [AddOrdered], for this also implies for non-trivial structures that they are infinite ///and provides for embeddings of the [Naturals](Natural) and [Integers](Integer) in much the same ///way. /// pub trait MulOrdered: PartialOrd {} ///Helpful methods for measuring an element's order relative to 0 pub trait Signed: PartialOrd + Zero { ///If this element is strictly greater than zero fn positive(&self) -> bool; ///If this element is strictly less than zero fn negative(&self) -> bool; ///If this element is greater than or equal to zero fn non_negative(&self) -> bool; ///If this element is less than or equal to zero fn non_positive(&self) -> bool; } ///Auto-implemented using `default` to allow for specialization if desired impl<G: PartialOrd + Zero> Signed for G { #[inline] default fn positive(&self) -> bool { self > &Self::zero() } #[inline] default fn negative(&self) -> bool { self < &Self::zero() } #[inline] default fn non_negative(&self) -> bool { self >= &Self::zero() } #[inline] default fn non_positive(&self) -> bool { self <= &Self::zero() } } ///Helpful methods for manipulating an element's order relative to 0 pub trait Sign: Signed { ///Returns 1 if positive, -1 if negative, or itself (ie. 0 or NaN) if neither fn signum(self) -> Self; ///Returns this element's negative if less than 0 or itself otherwise fn abs(self) -> Self; } /// ///The property that if `x < y`, there exists some natural `n` where `n*x = x*...*x > y` /// ///This is often interpreted as the structure having no "infinite" elements, since any element ///can be reached from any other non-zero element (even the smallest of elements) through _only_ ///repeated addition. /// ///Now, it is worth noting that in practice, implementing structs _might_ still have some form ///of infinite elements, so long as they aren't "distinguished" in some way. In particular, ///IEEE floating points have INF, -INF, and NaN as standard values, all of which violate this property ///however, in order to simplify the API and still have [f32] and [f64] be considered [reals](crate::analysis::Real), ///these values are interpreted as errors. Of course, in general, new structs implementing this trait ///should avoid this if possible. /// pub trait ArchimedeanProperty: AddOrdered + AddAssociative {} /// ///Division with remainder using an ordering and the Archimedean Property /// ///In a sense, this is extremely similar to [Euclidean division](EuclideanDiv) and in certain ///contexts (like the [Integers](Integer) and [Naturals](Natural)), this division satisfies the ///same relevant axioms. However, they are not _always_ equivalent, the real numbers being a notable ///exception. /// pub trait ArchimedeanDiv: Sized + ArchimedeanProperty { /// ///Maps a natural number into this structure preserving addition and ///using the relevant canonical representation /// ///For rings and semirings with [One], this representation should map the [Natural] 1 to 1 in ///the structure and should also preserve multiplication /// fn embed_nat<N:Natural>(n:N) -> Self; ///the unique integer `n` such that `n*rhs <= self` and `(n+1)*rhs > self` fn div_arch(self, rhs: Self) -> Self; ///the remaining difference after dividing by rhs (ie. `self - self.div_arch(rhs)*rhs`) fn rem_arch(self, rhs: Self) -> Self; /// ///Divides `self` by `rhs` with remainder using the archimdean property /// ///Specifically, this function finds the unique Integer `n` and element `r` such that: /// * `self = n*rhs + r` /// * `n*rhs <= self` /// * `(n+1)*rhs > self` /// ///Note that the meaning of "Integer" here refers to the canonical representation/mapping ///of the Integers into this structure by nature of the [additive ordering](AddOrdered) on ///this structure and _not_ the integers themselves. As such, the quotient returned must ///be a possible output or [negation](Neg) a possibile output of ///[embed_nat()](ArchimedeanDiv::embed_nat). /// ///Furthermore, because the choice of quotient, the remainder returned must _always_ be non-negative. ///For this reason, for primitive types, this method corresponds to the div_euclid and ///rem_euclid methods and _not_ the `/` and `%` operators. /// fn div_alg_arch(self, rhs: Self) -> (Self, Self); } ///An additive magma with an ordered addition operation pub trait OrdMagma = AddMagma + AddOrdered; ///An additive semigroup with an ordered addition operation pub trait OrdSemigroup = OrdMagma + AddSemigroup; ///An additive loop with an ordered addition operation pub trait OrdLoop = OrdMagma + AddLoop; ///An additive monoid with an ordered addition operation pub trait OrdMonoid = OrdSemigroup + AddMonoid + Signed; ///An additive group with an ordered addition operation pub trait OrdGroup = OrdMonoid + AddGroup; ///An additive abelian group with an ordered addition operation pub trait OrdAbelianGroup = OrdGroup + AddAbelianGroup; ///A semiring with ordered addition and multiplication pub trait OrdSemiring = Semiring + OrdMonoid + MulOrdered; ///A unitial semiring with ordered addition and multiplication pub trait OrdUnitalSemiring = OrdSemiring + UnitalSemiring; ///A commutative semiring with ordered addition and multiplication pub trait OrdCommutativeSemiring = OrdUnitalSemiring + CommutativeSemiring; ///A division semiring with ordered addition and multiplication pub trait OrdDivisionSemiring = OrdUnitalSemiring + DivisionSemiring; ///A ring with ordered addition and multiplication pub trait OrdRing = Ring + OrdAbelianGroup + MulOrdered; ///A unital ring with ordered addition and multiplication pub trait OrdUnitalRing = OrdRing + UnitalRing + Sign; ///A commutative ring with ordered addition and multiplication pub trait OrdCommutativeRing = OrdUnitalRing + CommutativeRing; ///A division ring with ordered addition and multiplication pub trait OrdDivisionRing = OrdCommutativeRing + DivisionRing; ///A field with ordered addition and multiplication pub trait OrdField = OrdUnitalRing + Field; ///An ordered semigroup with the Archimedean property pub trait ArchSemigroup = OrdSemigroup + ArchimedeanProperty; ///An ordered monoid with the Archimedean property pub trait ArchMonoid = ArchSemigroup + OrdMonoid; ///An ordered group with the Archimedean property pub trait ArchGroup = ArchMonoid + OrdGroup; ///An ordered abeliean group with the Archimedean property pub trait ArchAbelianGroup = ArchMonoid + OrdAbelianGroup; ///An ordered semiring with the Archimedean property pub trait ArchSemiring = ArchMonoid + OrdSemiring; ///An ordered unital semiring with the Archimedean property and Archimedean division pub trait ArchUnitalSemiring = ArchSemiring + OrdUnitalSemiring + ArchimedeanDiv; ///An ordered commutative semiring with the Archimedean property and Archimedean division pub trait ArchCommutativeSemiring = ArchUnitalSemiring + OrdCommutativeSemiring; ///An ordered division semiring with the Archimedean property and Archimedean division pub trait ArchDivisionSemiring = ArchCommutativeSemiring + OrdDivisionSemiring; ///An ordered ring with the Archimedean property pub trait ArchRing = ArchAbelianGroup + OrdRing; ///An ordered unital ring with the Archimedean property and Archimedean division pub trait ArchUnitalRing = ArchRing + OrdUnitalRing + ArchimedeanDiv; ///An ordered commutative ring with the Archimedean property and Archimedean division pub trait ArchCommutativeRing = ArchUnitalRing + OrdCommutativeRing; ///An ordered division ring with the Archimedean property and Archimedean division pub trait ArchDivisionRing = ArchCommutativeRing + OrdDivisionRing; ///An ordered field ring with the Archimedean property and Archimedean division pub trait ArchField = ArchUnitalRing + OrdField; macro_rules! impl_ordered_int { ($($t:ident)*) => {$( impl AddOrdered for $t {} impl MulOrdered for $t {} impl ArchimedeanProperty for $t {} impl Sign for $t { #[inline] fn signum(self) -> Self { $t::signum(self) } #[inline] fn abs(self) -> Self { $t::abs(self) } } impl ArchimedeanDiv for $t { #[inline] fn embed_nat<N:Natural>(n:N) -> Self { (1).mul_n(n) } #[inline] fn div_arch(self, rhs:Self) -> Self {self.div_euclid(rhs)} #[inline] fn rem_arch(self, rhs:Self) -> Self {self.rem_euclid(rhs)} #[inline] fn div_alg_arch(self, rhs:Self) -> (Self, Self) {(self.div_arch(rhs), self.rem_arch(rhs))} } )*} } macro_rules! impl_ordered_uint { ($($t:ty)*) => {$( impl AddOrdered for $t {} impl MulOrdered for $t {} impl ArchimedeanProperty for $t {} impl Sign for $t { #[inline] fn signum(self) -> Self { if self==0 {0} else {1} } #[inline] fn abs(self) -> Self { self } } impl ArchimedeanDiv for $t { #[inline] fn embed_nat<N:Natural>(n:N) -> Self { (1).mul_n(n) } #[inline] fn div_arch(self, rhs:Self) -> Self {self / rhs} #[inline] fn rem_arch(self, rhs:Self) -> Self {self % rhs} #[inline] fn div_alg_arch(self, rhs:Self) -> (Self, Self) {(self / rhs, self % rhs)} } )*} } macro_rules! impl_ordered_float { ($($t:ident)*) => {$( impl AddOrdered for $t {} impl MulOrdered for $t {} impl ArchimedeanProperty for $t {} impl Sign for $t { #[inline] fn signum(self) -> Self { #[cfg(feature = "std")] {$t::signum(self)} #[cfg(not(feature = "std"))] {if self<0.0 {-1.0} else if self>0.0 {1.0} else {0.0}} } #[inline] fn abs(self) -> Self { #[cfg(feature = "std")] {$t::abs(self)} #[cfg(not(feature = "std"))] {if self<0.0 {-self} else {self}} } } impl ArchimedeanDiv for $t { #[inline] fn embed_nat<N:Natural>(n:N) -> Self { (1.0).mul_n(n) } #[inline] fn rem_arch(self, rhs:Self) -> Self { let rem = self % rhs; if rem < 0.0 { rem + rhs.abs() } else { rem } } #[inline] fn div_arch(self, rhs:Self) -> Self { self.div_alg_arch(rhs).0 } #[inline] fn div_alg_arch(self, rhs:Self) -> (Self, Self) { let rem = self.rem_arch(rhs); ((self - rem) / rhs, rem) } } )*} } // Necessary do to issue #60021 mod impls { use super::{ AddOrdered, MulOrdered, ArchimedeanProperty, Sign, ArchimedeanDiv, Natural, MulN }; impl_ordered_int!(i8 i16 i32 i64 i128 isize); impl_ordered_uint!(u8 u16 u32 u64 u128 usize); impl_ordered_float!(f32 f64); }