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

/// Implementation of the Opus range encoder.
pub mod opus {
    /// A c2rust-ified version of the Opus range decoder.
    mod imported_decode;
    mod imported_encode;

    mod encode;
    mod decode;

    pub use self::encode::Writer;
    pub use self::decode::Reader;
}

/// Determine whether the symbol needs to be somehow
/// injected in a dictionary.
pub struct DefinitionRequirement {
    symbol: bool,
    distribution_total: bool,
}
impl DefinitionRequirement {
    pub fn symbol(&self) -> bool {
        self.symbol
    }
    pub fn distribution_total(&self) -> bool {
        self.distribution_total
    }
}


#[derive(Clone)]
pub struct Segment {
    /// First value part of the segment.
    low: u32,

    /// First value >= low **not** part of the segment.
    next: u32,

    /// `true` if we have already returned at least one instance of this Segment.
    already_encountered: bool,
}
impl Segment {
    pub fn new(low: u32, next: u32) -> Segment {
        Segment {
            low,
            next,
            already_encountered: false
        }
    }
    pub fn width(&self) -> u32 {
        self.next - self.low
    }
}

pub struct IndexedSegment {
    pub segment: Segment,
    pub index: usize,
}

pub struct CumulativeDistributionFrequency {
    /// Ordered, contiguous list of segments, starting at 0.
    segments: Box<[Segment]>,

    /// The width, which is exactly `segments.last.width`.
    width: u32,

    already_encountered: bool,
}
impl CumulativeDistributionFrequency {
    pub fn new(probabilities: Vec<u32>) -> Self {
        let mut segments = Vec::with_capacity(probabilities.len());
        let mut start = 0;
        for probability in probabilities {
            let next = start + probability;
            segments.push(Segment::new(start, next));
            start = next;
        }
        Self {
            segments: segments
                .into_boxed_slice(),
            width: start,
            already_encountered: false,
        }
    }

    /// Return the total frequency of symbols in this distribution.
    pub fn width(&self) -> u32 {
        self.width
    }

    /// Iterate through the widths of the symbols.
    pub fn widths<'a>(&'a self) -> impl Iterator<Item = u32> + 'a {
        self.segments.iter()
            .map(Segment::width)
    }

    /// Find a value from its frequency.
    pub fn find(&self, probability: u32) -> Option<IndexedSegment> {
        if probability >= self.width {
            return None
        }
        let index = self.segments.binary_search_by(|segment| {
            use std::cmp::Ordering;
            if segment.low > probability {
                return Ordering::Greater
            }
            if segment.next <= probability {
                return Ordering::Less
            }
            Ordering::Equal
        }).ok()?;
        Some(IndexedSegment {
            index,
            segment: self.segments[index].clone()
        })
    }

    /// Find a value from its index
    pub fn at_index<'a>(&'a mut self, index: usize) -> Option<&'a mut Segment> {
        if index >= self.segments.len() {
            return None;
        }
        Some(&mut self.segments[index])
    }

    pub fn requirements_for_index(&self, index: usize) -> Option<DefinitionRequirement> {
        if index >= self.segments.len() {
            return None;
        }
        Some(DefinitionRequirement {
            distribution_total: !self.already_encountered,
            symbol: !self.segments[index].already_encountered
        })
    }

    /// Return the number of values in this CDF
    pub fn len(&self) -> usize {
        self.segments.len()
    }
}