use integral_geometry::{Rect, Size};

use std::cmp::{max, min, Ordering};

#[derive(PartialEq, Eq, PartialOrd, Ord, Clone)]

struct Fit {

    short_side: u32,

    long_side: u32,

}

impl Fit {

    fn new() -> Self {

        Self {

            short_side: u32::max_value(),

            long_side: u32::max_value(),

        }

    }

    fn measure(container: Size, size: Size) -> Option<Self> {

        if container.contains(size) {

            let x_leftover = container.width - size.width;

            let y_leftover = container.height - size.height;

            Some(Self {

                short_side: min(x_leftover, y_leftover) as u32,

                long_side: max(x_leftover, y_leftover) as u32,

            })

        } else {

            None

        }

    }

}

#[derive(PartialEq, Eq)]

pub struct UsedSpace {

    used_area: usize,

    total_area: usize,

}

impl UsedSpace {

    const fn new(used_area: usize, total_area: usize) -> Self {

        Self {

            used_area,

            total_area,

        }

    }

    const fn used(&self) -> usize {

        self.used_area

    }

    const fn total(&self) -> usize {

        self.total_area

    }

}

impl std::fmt::Debug for UsedSpace {

    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {

        write!(

            f,

            "{:.2}%",

            self.used() as f32 / self.total() as f32 / 100.0

        )?;

        Ok(())

    }

}

pub struct Atlas {

    size: Size,

    free_rects: Vec<Rect>,

    used_rects: Vec<Rect>,

}

impl Atlas {

    pub fn new(size: Size) -> Self {

        Self {

            size,

            free_rects: vec![Rect::at_origin(size)],

            used_rects: vec![],

        }

    }

    pub fn size(&self) -> Size {

        self.size

    }

    pub fn used_space(&self) -> UsedSpace {

        let used = self.used_rects.iter().map(|r| r.size().area()).sum();

        UsedSpace::new(used, self.size.area())

    }

    fn find_position(&self, size: Size) -> Option<(Rect, Fit)> {

        let mut best_rect = Rect::EMPTY;

        let mut best_fit = Fit::new();

        for rect in &self.free_rects {

            if let Some(fit) = Fit::measure(rect.size(), size) {

                if fit < best_fit {

                    best_fit = fit;

                    best_rect = Rect::from_size(rect.top_left(), size);

                }

            }

            if let Some(fit) = Fit::measure(rect.size(), size.transpose()) {

                if fit < best_fit {

                    best_fit = fit;

                    best_rect = Rect::from_size(rect.top_left(), size.transpose());

                }

            }

        }

        if best_rect == Rect::EMPTY {

            None

        } else {

            Some((best_rect, best_fit))

        }

    }

    fn prune(&mut self) {

        self.free_rects = self

            .free_rects

            .iter()

            .filter(|inner| {

                self.free_rects

                    .iter()

                    .all(|outer| outer == *inner || !outer.contains_rect(inner))

            })

            .cloned()

            .collect();

    }

        let mut splits = vec![];

        for i in (0..self.free_rects.len()).rev() {

            if split_rect(self.free_rects[i], rect, &mut splits) {

                self.free_rects.swap_remove(i as usize);

            }

        }

        self.free_rects.extend(splits);

        self.prune();

        Some(rect)

    }

    pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<Rect>

    where

        Iter: Iterator<Item = Size>,

    {

        let mut sizes: Vec<_> = sizes.collect();

        let mut result = vec![];

        while let Some((index, (rect, _))) = sizes

            .iter()

            .enumerate()

            .filter_map(|(i, s)| self.find_position(*s).map(|res| (i, res)))

            .min_by_key(|(_, (_, fit))| fit.clone())

        {

            result.push(rect);

            sizes.swap_remove(index);

        }

    }

    pub fn reset(&mut self) {

        self.free_rects.clear();

        self.used_rects.clear();

        self.free_rects.push(Rect::at_origin(self.size));

    }

}

pub struct AtlasCollection {

    texture_size: Size,

    atlases: Vec<Atlas>,

}

impl AtlasCollection {

    pub fn new(texture_size: Size) -> Self {

        Self {

            texture_size,

            atlases: vec![],

        }

    }

    fn repack(&mut self, size: Size) -> bool {

        for atlas in &mut self.atlases {

            let mut temp_atlas = Atlas::new(atlas.size());

            let sizes = atlas

                .used_rects

                .iter()

                .map(|r| r.size())

                .chain(std::iter::once(size));

            if !temp_atlas.insert_set(sizes).is_empty() {

                std::mem::swap(atlas, &mut temp_atlas);

                return true;

            }

        }

        false

    }

    pub fn insert_sprite(&mut self, size: Size) -> bool {

        if !self.texture_size.contains(size) {

            false

        } else {

            if let Some(rect) = self.atlases.iter_mut().find_map(|a| a.insert(size)) {

            } else if !self.repack(size) {

                let mut atlas = Atlas::new(self.texture_size);

                atlas.insert(size);

                self.atlases.push(atlas);

            }

            true

        }

    }

}

fn split_rect(free_rect: Rect, rect: Rect, output: &mut Vec<Rect>) -> bool {

    let split = free_rect.intersects(&rect);

    if split {

        if rect.left() > free_rect.left() {

            let trim = free_rect.right() - rect.left() + 1;

            output.push(free_rect.with_margins(0, -trim, 0, 0))

        }

        if rect.right() < free_rect.right() {

            let trim = rect.right() - free_rect.left() + 1;

            output.push(free_rect.with_margins(-trim, 0, 0, 0))

        }

        if rect.top() > free_rect.top() {

            let trim = free_rect.bottom() - rect.top() + 1;

            output.push(free_rect.with_margins(0, 0, 0, -trim));

        }

        if rect.bottom() < free_rect.bottom() {

            let trim = rect.bottom() - free_rect.top() + 1;

            output.push(free_rect.with_margins(0, 0, -trim, 0));

        }

    }

    split

}

#[cfg(test)]

mod tests {

    use super::Atlas;

    use integral_geometry::{Rect, Size};

    use itertools::Itertools as _;

    use proptest::prelude::*;

    #[test]

    fn insert() {

        let atlas_size = Size::square(16);

        let mut atlas = Atlas::new(atlas_size);

        assert_eq!(None, atlas.insert(Size::square(20)));

        let rect_size = Size::new(11, 3);

        let rect = atlas.insert(rect_size).unwrap();

        assert_eq!(rect, Rect::at_origin(rect_size));

        assert_eq!(2, atlas.free_rects.len());

    }

    #[derive(Debug, Clone)]

    struct TestRect(Size);

    struct TestRectParameters(Size);

    impl Default for TestRectParameters {

        fn default() -> Self {

            Self(Size::square(64))

        }

    }

    impl Arbitrary for TestRect {

        type Parameters = TestRectParameters;

        fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {

            (1..=args.0.width, 1..=args.0.height)

                .prop_map(|(w, h)| TestRect(Size::new(w, h)))

                .boxed()

        }

        type Strategy = BoxedStrategy<TestRect>;

    }

    trait HasSize {

        fn size(&self) -> Size;

    }

    impl HasSize for TestRect {

        fn size(&self) -> Size {

            self.0

        }

    }

    impl HasSize for Rect {

        fn size(&self) -> Size {

            self.size()

        }

    }

    fn sum_area<S: HasSize>(items: &[S]) -> usize {

        items.iter().map(|s| s.size().area()).sum()

    }

    proptest! {

        #[test]

        fn prop_insert(rects in Vec::<TestRect>::arbitrary()) {

            let container = Rect::at_origin(Size::square(2048));

            let mut atlas = Atlas::new(container.size());

            let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size)).collect();

            let mut inserted_pairs = inserted.iter().cartesian_product(inserted.iter());

            assert!(inserted.iter().all(|r| container.contains_rect(r)));

            assert!(inserted_pairs.all(|(r1, r2)| r1 == r2 || r1 != r2 && !r1.intersects(r2)));

            assert_eq!(inserted.len(), rects.len());

            assert_eq!(sum_area(&inserted), sum_area(&rects));

        }

    }

    proptest! {

        #[test]

        fn prop_insert_set(rects in Vec::<TestRect>::arbitrary()) {

            let container = Rect::at_origin(Size::square(2048));

            let mut atlas = Atlas::new(container.size());

            let mut set_atlas = Atlas::new(container.size());

            let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size)).collect();

            let set_inserted: Vec<_> = set_atlas.insert_set(rects.iter().map(|TestRect(size)| *size));

            let mut set_inserted_pairs = set_inserted.iter().cartesian_product(set_inserted.iter());

            assert!(set_inserted_pairs.all(|(r1, r2)| r1 == r2 || r1 != r2 && !r1.intersects(r2)));

            assert!(set_atlas.used_space().used() <= atlas.used_space().used());

            assert_eq!(sum_area(&set_inserted), sum_area(&inserted));

        }

    }

}