norman 0.0.4

Implementations of different norms for elements of vector spaces
Documentation 
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

/******************************************************************************
 * Copyright 2019 Manuel Simon
 * This file is part of the norman library.
 *
 * Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
 * https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
 * <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
 * option. This file may not be copied, modified, or distributed
 * except according to those terms.
 *****************************************************************************/

//! Utility functions that calculate norms and distances for a wide range
//! of general types, but without explicitly implementing the trait.

use std::convert::TryFrom;
use std::cmp::Ordering;

use num_traits::{Num, Float};

use crate::desc::{PNorm, PNormReal};

/// Calculates the supremum norm of an iterable.
///
/// No Absolute values are taken, so when using this function,
/// you will probably apply a `.map(|a| a.norm(Abs::new()))` to an iterator
/// before feeding it to this function.
///
/// If the iterable is empty, zero is returned.
///
/// For floating-point values, the following behaviour holds with respect to NaN and Inf:
/// NaNs are ignored, i.e. the absolute value of the greatest non-NaN value
/// is returned. The only exception is if the iterable only contains NaNs: in this
/// case, the first of these NaNs is returned.
///
/// Infinities are treated exactly like they were the smallest/largest possible value.
pub fn supnorm_iterable<I: IntoIterator<Item=R>, R: Num + PartialOrd>(iter: I) -> R {
    let mut iter = iter.into_iter();
    if let Some(mut sup) = iter.next() {
        for it in iter {
            match PartialOrd::partial_cmp(&it, &sup) {
                Some(Ordering::Greater) => sup = it,
                Some(Ordering::Equal) | Some(Ordering::Less) => (),
                // Use reflexiveness of sup and it to check whether they
                // are NaN or an equivalent to it (in a non-float-type).
                // This line makes sure that NaNs are ignored, but the
                // first NaN is returned if all items are NaN (or non-reflexive,
                // respectively).
                None => if sup.partial_cmp(&sup).is_none() && it.partial_cmp(&it).is_some() {
                    sup = it;
                },
            }
        }
        sup
    } else {
        R::zero()
    }
}

/// Calculates the _p_-norm of an iterable by summing up the _p_-th powers
/// of the items and finally taking the _p_-th root of the sum.
///
/// No absolute values are taken, so when using this function,
/// you will probably apply a `.map(|a| a.norm(Abs::new()))` to an iterator
/// before feeding it to this function.
///
/// If _p_ is too large to be represented by an integer, the supremum norm is
/// returned as an approximation.
///
/// If one item of the iterator is infinite, whether positive
/// or negative, +Inf is returned.
///
/// If the _p_-th power of one item of the iterator is infinite,
/// while the item itself is finite,
/// then the supremum norm is returned as an approximation.
pub fn pnorm_iterable<I: IntoIterator<Item=R>, R>(iter: I, desc: PNorm) -> R
where
    R: Float + From<f32>
{
    let pfloat: R = From::from(u32::from(desc.p) as f32);
    let pinv = pfloat.recip();
    if let Ok(p) = i32::try_from(u32::from(desc.p)) {
        let mut res = R::zero();
        let mut iter = iter.into_iter();
        while let Some(it) = iter.next() {
            let it_pow = it.powi(p);
            if it_pow.is_finite() {
                res = res + it_pow;
            } else if it.is_infinite() {
                return R::infinity();
            } else {
                return supnorm_iterable(iter.chain(std::iter::once(it)));
            }
        }
        res.powf(pinv)
    } else {
        supnorm_iterable(iter)
    }
}

/// Calculates the _p_-norm of an iterable with a real-valued _p_
/// by summing up the _p_-th powers
/// of the items and finally taking the _p_-th root of the sum.
///
/// No absolute values are taken, so when using this function,
/// you will probably apply a `.map(|a| a.norm(Abs::new()))` to an iterator
/// before feeding it to this function.
///
/// If one item of the iterator is infinite, whether positive
/// or negative, +Inf is returned.
///
/// If the _p_-th power of one item of the iterator is infinite,
/// while the item itself is finite,
/// then the supremum norm is returned as an approximation.
pub fn pnorm_real_iterable<I: IntoIterator<Item=R>, R>(iter: I, desc: PNormReal) -> R
where
    R: Float + From<f32>
{
    let mut res = R::zero();
    let mut iter = iter.into_iter();
    while let Some(it) = iter.next() {
        let it_pow = it.powf(From::from(desc.p.raw()));
        if it_pow.is_finite() {
            res = res + it_pow;
        } else if it.is_infinite() {
            return R::infinity();
        } else {
            return supnorm_iterable(iter.chain(std::iter::once(it)));
        }
    }
    res.powf(From::from(desc.p.raw().recip()))
}


#[cfg(test)]
mod tests {
    use std::cmp::Ordering;
    use std::f32::{NAN, INFINITY};

    use crate::Norm;
    use crate::desc::{Abs, PNorm, PNormReal};
    use super::{pnorm_iterable, pnorm_real_iterable, supnorm_iterable};

    #[test]
    fn pnorm_empty_array() {
        let a = [3.0f32; 0].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(pnorm_iterable(a, PNorm::default()), 0.0);
    }

    #[test]
    fn norm2_iterable_array() {
        let a = [3.0f32, 5.0, 7.0].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(
            pnorm_iterable(a, PNorm::eucl()),
            (3.0f32*3.0 + 5.0*5.0 + 7.0*7.0).sqrt()
        );
    }

    #[test]
    fn norm2_real_iterable_array() {
        let a = [3.0f32, 5.0, 7.0].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(
            pnorm_real_iterable(a, PNormReal::eucl()),
            (3.0f32*3.0 + 5.0*5.0 + 7.0*7.0).sqrt()
        );
    }

    #[test]
    fn pnorm_maxint_iterable_array() {
        let a = [3.0f32, 5.0, 7.0].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(pnorm_iterable(a, PNorm::new(0x80000000)), 7.0);
    }

    #[test]
    fn pnorm_infinity_iterable_array() {
        let a = [3.0f32, std::f32::INFINITY, 7.0].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(pnorm_iterable(a, PNorm::new(3)), std::f32::INFINITY);
    }

    #[test]
    fn pnorm_real_maxint_iterable_array() {
        let a = [3.0f32, 5.0, 7.0].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(pnorm_real_iterable(a, PNormReal::from_f32(10000.0)), 7.0);
    }

    #[test]
    fn pnorm_real_infinity_iterable_array() {
        let a = [3.0f32, std::f32::INFINITY, 7.0].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(pnorm_real_iterable(a, PNormReal::from_f32(3.0)), std::f32::INFINITY);
    }

    #[test]
    fn partial_cmp_float() {
        assert_eq!(PartialOrd::partial_cmp(&NAN, &1.0), None);
        assert_eq!(PartialOrd::partial_cmp(&INFINITY, &1.0), Some(Ordering::Greater));
        assert_eq!(PartialOrd::partial_cmp(&NAN, &NAN), None);
        assert_eq!(PartialOrd::partial_cmp(&INFINITY, &INFINITY), Some(Ordering::Equal));
        assert_eq!(PartialOrd::partial_cmp(&NAN, &INFINITY), None);
    }

    #[test]
    fn supnorm_iterable_array() {
        let a = [3.0f32, -5.0f32, 2.0f32].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(supnorm_iterable(a), 5.0);
    }

    #[test]
    fn supnorm_iterable_array_nan() {
        let a = [3.0f32, NAN, -2.0f32].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(supnorm_iterable(a), 3.0);

        let a = [NAN, 3.0f32, 4.0f32].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(supnorm_iterable(a), 4.0);

        let a = [NAN, NAN, 2.0f32].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(supnorm_iterable(a), 2.0);

        let a = [NAN, NAN, NAN].into_iter().map(|a| a.norm(Abs::new()));
        assert!(supnorm_iterable(a).is_nan());
    }

    #[test]
    fn supnorm_iterable_array_infinity() {
        let a = [INFINITY, 1.0f32, 1.0f32].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(supnorm_iterable(a), INFINITY);

        let a = [3.0f32, INFINITY, 3.0f32].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(supnorm_iterable(a), INFINITY);
    }

    #[test]
    fn supnorm_iterable_array_infinity_nan() {
        let a = [NAN, INFINITY, 2.0f32].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(supnorm_iterable(a), INFINITY);

        let a = [INFINITY, 2.0f32, NAN].into_iter().map(|a| a.norm(Abs::new()));
        assert_eq!(supnorm_iterable(a), INFINITY);
    }
}