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

// Author: Daniel van Niekerk <dvn.demitasse@gmail.com>
//
// Copyright 2016 The Department of Arts and Culture of the Government
// of South Africa
//
// See the "LICENCE" file for information on usage and redistribution
// of this file.

//! This module defines the Weight and other traits which specifies a
//! semiring and other properties. See the source files
//! `main_semiring.rs` and `test_semiring.rs` for simple examples of
//! intended use.
//!
//! See Mehryar Mohri, "Semiring Framework and Algorithms for
//! Shortest-Distance Problems", *Journal of Automata, Languages and
//! Combinatorics* 7(3):321-350, 2002.

use std::fmt::Debug;
use std::option::Option;

pub trait Weight: PartialEq + Clone + Debug {
    fn is_member(&self) -> bool;
    fn plus(&self, rhs: &Self) -> Self;
    fn times(&self, rhs: &Self) -> Self;
    fn zero() -> Self;
    fn one() -> Self;
    fn none() -> Self;
    fn approx_eq(&self, rhs: &Self, delta: Option<f32>) -> bool;
    fn quantize(&self, delta: Option<f32>) -> Self;
    fn divide(&self, rhs: &Self, divtype: Option<DivideType>) -> Self;
    fn reverse(&self) -> Self;
    fn wtype() -> String;
}

pub enum DivideType {
    Divleft,
    Divright,
    Divany
}

/// ∀ a,b,c: c ⊗ (a ⊕ b) = (c ⊗ a) ⊕ (c ⊗ b)
pub trait LeftSemiring {}
/// ∀ a,b,c: (a ⊕ b) ⊗ c = (a ⊗ c) ⊕ (b ⊗ c)
pub trait RightSemiring {}
/// Both `LeftSemiring` and `RightSemiring` apply
pub trait Semiring: LeftSemiring + RightSemiring {}
/// ∀ a,b: a ⊗ b = b ⊗ a
pub trait Commutative {}
/// ∀ a: a ⊕ a = a
pub trait Idempotent {}
/// ∀ a,b: a ⊕ b = a ∨ a ⊕ b = b
pub trait Path {}


// *Natural Order* by definition:
//                              a <= b iff a + b = a
// Is a negative partial order iff the semiring is Idempotent and
// forms a *total order* iff the semiring has the Path property.
//
// See Mehryar Mohri, "Semiring Framework and Algorithms for
// Shortest-Distance Problems", Journal of Automata, Languages and
// Combinatorics 7(3):321-350, 2002.
pub trait NaturalLess: Weight + Idempotent + Path { //Path?
    fn natural_less(&self, rhs: &Self) -> bool;
}


/// Power is the iterated product for arbitrary semirings such that
/// Power(w, 0) is One() for the semiring, and
/// Power(w, n) = Times(Power(w, n-1), w)
pub fn power<T: Weight>(w: &T, n: u8) -> T {
    let mut result = T::one();
    for _ in 0..n {
        result = result.times(w);
    }
    result
}


mod float;
pub mod test;
pub mod floatweight;