// Copyright © 2024 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.

use itertools::Itertools;
use malachite_base::iterators::comparison::{is_strictly_ascending, is_strictly_descending};
use malachite_base::num::arithmetic::traits::{Abs, Floor, Parity};
use malachite_base::num::conversion::traits::IsInteger;
use malachite_base::strings::ToDebugString;
use malachite_nz::test_util::generators::integer_gen;
use malachite_q::conversion::traits::Convergents;
use malachite_q::test_util::conversion::continued_fraction::convergents::convergents_alt;
use malachite_q::test_util::generators::rational_gen;
use malachite_q::Rational;
use std::str::FromStr;

#[test]
fn test_convergents() {
    let test = |x: &str, out: &str| {
        let x = Rational::from_str(x).unwrap();
        let convergents = x.clone().convergents().collect_vec();
        assert!(convergents.iter().all(Rational::is_valid));
        assert_eq!((&x).convergents().collect_vec(), convergents);
        assert_eq!(convergents_alt(x).collect_vec(), convergents);
        assert_eq!(convergents.to_debug_string(), out);
    };
    test("0", "[0]");
    test("123", "[123]");
    test("-123", "[-123]");
    test("1/2", "[0, 1/2]");
    test("22/7", "[3, 22/7]");
    test("-22/7", "[-4, -3, -22/7]");
    test("99/100", "[0, 1, 99/100]");
    test(
        "936851431250/1397",
        "[670616629, 1341233259/2, 2011849888/3, 3353083147/5, 5364933035/8, 8718016182/13, \
        232033353767/346, 936851431250/1397]",
    );
    test(
        "6369051672525773/4503599627370496",
        "[1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, 8119/5741, \
        19601/13860, 47321/33461, 114243/80782, 275807/195025, 665857/470832, 1607521/1136689, \
        3880899/2744210, 9369319/6625109, 22619537/15994428, 54608393/38613965, \
        77227930/54608393, 131836323/93222358, 209064253/147830751, 549964829/388883860, \
        4058818056/2870017771, 4608782885/3258901631, 13276383826/9387821033, \
        442729449143/313056995720, 898735282112/635501812473, 6733876423927/4761569683031, \
        34568117401747/24443350227628, 75870111227421/53648270138287, \
        110438228629168/78091620365915, 186308339856589/131739890504202, \
        3091371666334592/2185929868433147, 6369051672525773/4503599627370496]",
    );
    test(
        "884279719003555/281474976710656",
        "[3, 22/7, 333/106, 355/113, 103993/33102, 104348/33215, 208341/66317, 312689/99532, \
        833719/265381, 1146408/364913, 4272943/1360120, 5419351/1725033, 80143857/25510582, \
        245850922/78256779, 817696623/260280919, 1881244168/598818617, 2698940791/859099536, \
        9978066541/3176117225, 32633140414/10387451211, 238410049439/75888275702, \
        509453239292/162164002615, 747863288731/238052278317, 1257316528023/400216280932, \
        4519812872800/1438701121113, 10296942273623/3277618523158, \
        436991388364966/139098679093749, 884279719003555/281474976710656]",
    );
    test(
        "6121026514868073/2251799813685248",
        "[2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, 2721/1001, \
        23225/8544, 25946/9545, 49171/18089, 517656/190435, 566827/208524, 1084483/398959, \
        13580623/4996032, 14665106/5394991, 28245729/10391023, 325368125/119696244, \
        353613854/130087267, 678981979/249783511, 1032595833/379870778, 12037536142/4428362069, \
        61220276543/22521681123, 73257812685/26950043192, 134478089228/49471724315, \
        342213991141/125893491822, 476692080369/175365216137, 2248982312617/827354356370, \
        4974656705603/1830073928877, 7223639018220/2657428285247, 12198295723823/4487502214124, \
        117008300532627/43044948212363, 2001339404778482/736251621824295, \
        6121026514868073/2251799813685248]",
    );
}

#[test]
fn convergents_properties() {
    rational_gen().test_properties(|x| {
        let convergents = x.clone().convergents().collect_vec();
        assert!(convergents.iter().all(Rational::is_valid));
        assert_eq!(convergents[0], (&x).floor());
        assert_eq!(*convergents.last().unwrap(), x);
        assert_eq!((&x).convergents().collect_vec(), convergents);
        assert_eq!(convergents_alt(x.clone()).collect_vec(), convergents);

        // The denominators of the convergents are strictly increasing, with the single exception
        // that the first two convergents may both be integers.
        if let Some(i) = convergents.iter().position(|x| !x.is_integer()) {
            assert!(i == 1 || i == 2);
            assert!(is_strictly_ascending(
                convergents[i - 1..].iter().map(Rational::denominator_ref)
            ));
        }
        assert!(is_strictly_descending(
            convergents.iter().map(|c| (c - &x).abs())
        ));
        for (i, c) in convergents.iter().enumerate() {
            if i.even() {
                assert!(*c <= x);
            } else {
                assert!(*c >= x);
            }
        }
    });

    integer_gen().test_properties(|x| {
        let convergents = Rational::from(&x).convergents().collect_vec();
        assert_eq!(convergents, &[x]);
    });
}