aligner 0.1.6

// This file is part of the Rust library and binary `aligner`.
//
// Copyright (C) 2017 kaegi
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.


use arrayvec::ArrayVec;
use internal::{DeltaSegment, Rating, RatingSegment, TimeDelta, TimePoint, TimeSpan};
use std::iter::FromIterator;

/// Returns the timepoints at which the rating delta changes if we move one
/// subtitle compared to
/// an other.
///
/// If we fix one timespan and let an other timespan variable, we get such a
/// curve for the rating:
///
/// ```text
///
///          / --------- \
///         /             \
/// -------                --------------------------
/// ```
///
/// At first the rating be zero, then rise linearly, then it will be constant
/// for a time and then fall to zero again. This function computes these 4
/// special timepoints.
pub fn get_overlapping_rating_changepoints(length: TimeDelta, constspan: TimeSpan) -> [(Rating /* Delta */, TimePoint); 4] {

    let start_of_rise = constspan.start() - length;
    let end_of_rise = constspan.end() - length;
    let start_of_fall = constspan.start();
    let end_of_fall = constspan.end();

    let timepoints: [TimePoint; 4] = if end_of_rise <= start_of_fall {
        [start_of_rise, end_of_rise, start_of_fall, end_of_fall]
    } else {
        [start_of_rise, start_of_fall, end_of_rise, end_of_fall]
    };

    assert!(timepoints[0] <= timepoints[1]);
    assert!(timepoints[1] <= timepoints[2]);
    assert!(timepoints[2] <= timepoints[3]);

    let rise_delta = Rating::from_overlapping_spans(length, constspan.len());

    [
        (rise_delta, timepoints[0]),
        (-rise_delta, timepoints[1]),
        (-rise_delta, timepoints[2]),
        (rise_delta, timepoints[3]),
    ]
}

/// Creates a new vector with `prev` as first element and the sorted elements
/// of `a`.
pub fn sort_arrayvec3(prev: u64, a: ArrayVec<[u64; 3]>) -> ArrayVec<[u64; 4]> {
    #[allow(collapsible_if)]
    match a.len() {
        0 => ArrayVec::from_iter([prev].into_iter().cloned()),
        1 => ArrayVec::from_iter([prev].into_iter().cloned().chain(a.into_iter())),
        2 => {
            if a[0] <= a[1] {
                ArrayVec::from_iter([prev].into_iter().cloned().chain(a.into_iter()))
            } else {
                ArrayVec::from_iter([prev].into_iter().cloned().chain(a.into_iter().rev()))
            }
        }
        3 => {
            if a[0] <= a[1] {
                if a[1] <= a[2] {
                    ArrayVec::from([prev, a[0], a[1], a[2]])
                } else if a[0] <= a[2] {
                    ArrayVec::from([prev, a[0], a[2], a[1]])
                } else {
                    ArrayVec::from([prev, a[2], a[0], a[1]])
                }
            } else {
                // here: a[1] <= a[0]

                if a[0] <= a[2] {
                    ArrayVec::from([prev, a[1], a[0], a[2]])
                } else if a[1] <= a[2] {
                    ArrayVec::from([prev, a[1], a[2], a[0]])
                } else {
                    ArrayVec::from([prev, a[2], a[1], a[0]])
                }
            }
        }
        _ => panic!("ArrayVec<[T; 3]>::len() is greater than 3"),
    }
}

/// Removes any duplicate elements from the vector.
///
/// Requires a sorted non-empty array vector.
fn dedup_arrayvec4(a: ArrayVec<[u64; 4]>) -> ArrayVec<[u64; 4]> {
    let mut last = a[0];
    let mut result = ArrayVec::new();
    result.push(last);
    for elem in a {
        if last != elem {
            result.push(elem);
            last = elem;
        }
    }
    result
}

pub fn subseg_by_max_start<ID>(segs: [DeltaSegment<Rating, Rating>; 2], ids: [ID; 2], start: u64, end: u64) -> (RatingSegment, ID)
where
    ID: Copy + Eq,
{
    if (segs[0].value_at_index(start as i64), segs[0].delta()) >= (segs[1].value_at_index(start as i64), segs[1].delta()) {
        (segs[0].subseg(start, end), ids[0])
    } else {
        (segs[1].subseg(start, end), ids[1])
    }
}


/// Given two segments, it computes the subsegments which have the best rating
/// in their span.
///
/// The parameter `ids` is there to identify which segment the subsegment came
/// from. The length
/// of all given spans have to be same, the sum of all returned segments is the
/// orginal length.
pub fn get_best_rating_segments_of_2<ID>(segs: [DeltaSegment<Rating, Rating>; 2], ids: [ID; 2]) -> ArrayVec<[(DeltaSegment<Rating, Rating>, ID); 3]>
where
    ID: Copy + Eq,
{
    let len = segs[0].len();
    assert!(len == segs[1].len());

    match get_switch_point(segs[0], segs[1]) {
        None => ArrayVec::from_iter([subseg_by_max_start(segs, ids, 0, len)].iter().cloned()),
        Some(point) => {
            ArrayVec::from_iter(
                [
                    subseg_by_max_start(segs, ids, 0, point),
                    subseg_by_max_start(segs, ids, point, len),
                ]
                .iter()
                .cloned(),
            )
        }
    }
}


/// Given three segments, it computes the subsegments which have the best
/// rating in their span.
///
/// The parameter `ids` is there to identify which segment the subsegment came
/// from. The length
/// of all given spans have to be same, the sum of all returned segments is the
/// orginal length.
pub fn get_best_rating_segments_of_3<ID>(segs: [DeltaSegment<Rating, Rating>; 3], ids: [ID; 3]) -> ArrayVec<[(DeltaSegment<Rating, Rating>, ID); 3]>
where
    ID: Copy + Eq,
{
    let seg1 = segs[0];
    let seg2 = segs[1];
    let seg3 = segs[2];

    let id1 = ids[0];
    let id2 = ids[1];
    let id3 = ids[2];


    let len = seg1.len();
    assert!(len == seg2.len());
    assert!(len == seg3.len());

    // get best ratings segments of first 2 segments
    let mut switch_points: ArrayVec<[u64; 3]> = ArrayVec::new();
    if let Some(split_point) = get_switch_point(seg1, seg2) {
        switch_points.push(split_point);
    }
    if let Some(split_point) = get_switch_point(seg1, seg3) {
        switch_points.push(split_point);
    }
    if let Some(split_point) = get_switch_point(seg2, seg3) {
        switch_points.push(split_point);
    }

    let switch_points = sort_arrayvec3(0, switch_points);
    let switch_points = dedup_arrayvec4(switch_points);

    let mut segments: ArrayVec<[(RatingSegment, ID); 3]> = ArrayVec::new();

    let next_points = switch_points.iter().cloned().skip(1).chain(
        Some(len).into_iter(),
    );
    for (switch_point, next_point) in switch_points.iter().cloned().zip(next_points) {
        // get the best segment for the current index
        //  -> first compare their rating, in case they are the same, compare the deltas
        let value1 = (seg1.value_at_index(switch_point as i64), seg1.delta());
        let value2 = (seg2.value_at_index(switch_point as i64), seg2.delta());
        let value3 = (seg3.value_at_index(switch_point as i64), seg3.delta());

        #[allow(collapsible_if)]
        let (current_best_segment, current_id) = if value1 < value2 {
            if value2 < value3 {
                (seg3, id3)
            } else {
                (seg2, id2)
            }
        } else {
            if value1 < value3 {
                (seg3, id3)
            } else {
                (seg1, id1)
            }
        };

        if let Some(last_ref) = segments.last_mut() {
            if last_ref.1 == current_id {
                last_ref.0 = RatingSegment::with_new_length((*last_ref).0, last_ref.0.len() + next_point - switch_point);
                continue;
            }
        }

        segments.push((
            current_best_segment.subseg(switch_point, next_point),
            current_id,
        ));
    }

    assert!(segments.len() < 4);

    segments
}

/// Requires 'seg1.len() == seg2.len()'. Returns the split point index if it is
/// within "(0, len)" (borders excluded), otherwise `None`.
/// The switch point is the first index where one segment overtakes the other.
#[allow(if_same_then_else)]
fn get_switch_point(seg1: DeltaSegment<Rating, Rating>, seg2: DeltaSegment<Rating, Rating>) -> Option<u64> {
    let len = seg1.len();
    assert!(len == seg2.len());
    let (f1, f2, l1, l2) = (
        seg1.first_value(),
        seg2.first_value(),
        seg1.last_value(),
        seg2.last_value(),
    );

    if f1 <= f2 && l1 <= l2 {
        // segment1 is always smaller than segment2
        None
    } else if f2 <= f1 && l2 <= l1 {
        // segment2 is always smaller than segment1
        None
    } else {
        let (d1, d2) = (seg1.delta(), seg2.delta());

        // solve "t1 + d1 * x = t2 + d2 * x" for x
        //  =>  "x = (t1 - t2) / (d2 - d1)"
        //
        // because this is a interger division (giving us x_int): x_int <= x < x_int + 1
        //
        // switch point is then "(x_int + 1)" which is the first index where the second
        // segment is better than the
        // original
        let switch_point: u64 = ((f1 - f2) / (d2 - d1) + 1) as u64;
        assert!(0 < switch_point);
        assert!(switch_point <= len);

        Some(switch_point)
    }

}

#[cfg(test)]
mod tests {
    use arrayvec::ArrayVec;
    use internal::*;
    use rand;
    use rand::Rng;
    use std::ops::Range;

    fn get_random_rating_segment(s: Range<i64>, d: Range<i64>, len: Range<u64>) -> RatingSegment {
        let mut rng = rand::thread_rng();
        let vs = rng.gen_range(s.start, s.end + 1);
        let vd = rng.gen_range(d.start, d.end + 1);
        let vlen = rng.gen_range(len.start, len.end + 1);
        DeltaSegment::new(Rating::from(vs), Rating::from(vd), vlen)
    }

    // Test `get_best_rating_segments_of_3` by validating it with `validate_best_segments`.
    #[test]
    fn test_get_best_segments3() {
        // genrate test data
        let gen_segment = || get_random_rating_segment(-100..100, -100..100, 100..100);
        let data_vec: Vec<_> = (0..2000)
            .map(|_| [gen_segment(), gen_segment(), gen_segment()])
            .collect();

        for test_segs in data_vec {
            let ids = [0, 1, 2];
            let best_segments: ArrayVec<[(RatingSegment, i32); 3]> = get_best_rating_segments_of_3(test_segs, ids);
            validate_best_segments(
                test_segs.into_iter()
                         .map(|&seg| RatingBuffer::from(seg))
                         .collect(),
                best_segments,
            );
        }
    }

    // Test `get_best_rating_segments_of_2` by validating it with `validate_best_segments`.
    #[test]
    fn test_get_best_segments2() {

        // genrate test data
        let gen_segment = || get_random_rating_segment(-100..100, -100..100, 100..100);
        let data_vec: Vec<_> = (0..2000).map(|_| [gen_segment(), gen_segment()]).collect();

        for test_segs in data_vec {
            let ids = [0, 1];
            let best_segments: ArrayVec<[(RatingSegment, i32); 3]> = get_best_rating_segments_of_2(test_segs, ids);
            println!("Test segments: {:?}", test_segs);
            println!("Best segments: {:?}", best_segments);
            println!();
            validate_best_segments(
                test_segs.into_iter()
                         .map(|&seg| RatingBuffer::from(seg))
                         .collect(),
                best_segments,
            );
        }
    }

    /// Checks whether the current segment from `best_segs` always holds the maximum value at that position from all buffers in `segs`.
    fn validate_best_segments(segs: Vec<RatingBuffer>, best_segs: ArrayVec<[(RatingSegment, i32); 3]>) {
        assert!(segs.len() > 0);
        let len = segs[0].len();
        for seg in &segs {
            assert!(seg.len() == len);
        }
        assert_eq!(
            len,
            best_segs.iter()
                     .map(|&(ref rating_buffer, _)| rating_buffer.len())
                     .sum()
        );

        // a vector of iterators (each representing a rating buffer)
        let mut iters: Vec<_> = segs.iter().map(|seg_ref| seg_ref.iter()).collect();

        for (best_seg, id) in best_segs {
            // go through all values in this supposedly "best" segment
            for best_value_by_best_segment in RatingBuffer::from(best_seg).iter() {
                // compute the maxium value by comparing all raings at the current position
                let separate_ratings: Vec<Rating> = iters.iter_mut().map(|iter| iter.next().unwrap()).collect();
                let real_max: Rating = separate_ratings.iter().cloned().max().unwrap();

                // assert that the maximum rating really is the maximum rating
                assert_eq!(real_max, best_value_by_best_segment);

                // require that the
                assert_eq!(real_max, separate_ratings[id as usize]);
            }
        }
    }

}