use integral_geometry::{Rect, Size};
use std::cmp::{max, min, Ordering};

pub struct Atlas {
    size: Size,
    free_rects: Vec<Rect>,
    used_rects: Vec<Rect>,
}

#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct Fit {
    short_size: u32,
    long_size: u32,
}

impl Fit {
    fn new() -> Self {
        Self {
            short_size: u32::max_value(),
            long_size: 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_size: min(x_leftover, y_leftover) as u32,
                long_size: max(x_leftover, y_leftover) as u32,
            })
        } else {
            None
        }
    }
}

fn split_rect(free_rect: Rect, rect: Rect) -> Vec<Rect> {
    let mut result = vec![];
    if free_rect.intersects(&rect) {
        if rect.left() > free_rect.left() {
            let trim = free_rect.right() - rect.left() + 1;
            result.push(free_rect.with_margins(0, -trim, 0, 0))
        }
        if rect.right() < free_rect.right() {
            let trim = rect.right() - free_rect.left() + 1;
            result.push(free_rect.with_margins(-trim, 0, 0, 0))
        }
        if rect.top() > free_rect.top() {
            let trim = free_rect.bottom() - rect.top() + 1;
            result.push(free_rect.with_margins(0, 0, 0, -trim));
        }
        if rect.bottom() < free_rect.bottom() {
            let trim = rect.bottom() - free_rect.top() + 1;
            result.push(free_rect.with_margins(0, 0, -trim, 0));
        }
    }
    result
}

impl Atlas {
    pub fn new(size: Size) -> Self {
        Self {
            size,
            free_rects: vec![Rect::at_origin(size)],
            used_rects: vec![],
        }
    }

    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();
    }

    pub fn insert_adaptive(&mut self, size: Size) -> Option<Rect> {
        let (rect, fit) = self.find_position(size)?;

        let mut rects_to_process = self.free_rects.len();
        let mut i = 0;

        while i < rects_to_process {
            let rects = split_rect(self.free_rects[i], rect);
            if !rects.is_empty() {
                self.free_rects.remove(i);
                self.free_rects.extend(rects);
                rects_to_process -= 1
            } else {
                i += 1;
            }
        }

        self.used_rects.push(rect);
        self.prune();
        Some(rect)
    }

    pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<Rect>
    where
        Iter: Iterator<Item = Size>,
    {
        unimplemented!()
    }

    pub fn reset(&mut self) {
        self.free_rects.clear();
        self.used_rects.clear();
        self.free_rects.push(Rect::at_origin(self.size));
    }
}

#[cfg(test)]
mod tests {
    use super::Atlas;
    use integral_geometry::{Rect, Size};

    #[test]
    fn insert() {
        let atlas_size = Size::square(16);
        let mut atlas = Atlas::new(atlas_size);

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

        let rect_size = Size::new(11, 3);
        let rect = atlas.insert_adaptive(rect_size).unwrap();
        assert_eq!(rect, Rect::at_origin(rect_size));
        assert_eq!(2, atlas.free_rects.len());
    }
}