use crate::geometry::{bottom_ex_u32, right_ex_u32, span_end_ex};
use crate::model::Rect;
use crate::runtime::ShelfPolicy;

pub(super) struct RuntimeShelfPlacement {
    border: Rect,
    policy: ShelfPolicy,
    shelves: Vec<RuntimeShelf>,
    next_y: u32,
}

#[derive(Clone, Debug)]
struct RuntimeShelf {
    y: u32,
    h: u32,
    segs: Vec<(u32, u32)>,
}

impl RuntimeShelfPlacement {
    pub(super) fn new(border: Rect, policy: ShelfPolicy) -> Self {
        Self {
            border,
            policy,
            shelves: Vec::new(),
            next_y: border.y,
        }
    }

    pub(super) fn free_area_and_rects(&self) -> (u64, usize) {
        let mut area = 0u64;
        let mut rects = 0usize;
        for shelf in &self.shelves {
            rects += shelf.segs.len();
            for (_, width) in &shelf.segs {
                area += (*width as u64) * (shelf.h as u64);
            }
        }
        (area, rects)
    }

    pub(super) fn choose(&self, allow_rotation: bool, w: u32, h: u32) -> Option<(Rect, bool)> {
        if let Some(rect) = self.try_existing_shelf(w, h) {
            return Some((rect, false));
        }
        if allow_rotation && let Some(rect) = self.try_existing_shelf(h, w) {
            return Some((rect, true));
        }
        if let Some(rect) = self.try_new_shelf(w, h) {
            return Some((rect, false));
        }
        if allow_rotation && let Some(rect) = self.try_new_shelf(h, w) {
            return Some((rect, true));
        }
        None
    }

    pub(super) fn place(&mut self, slot: &Rect) {
        if let Some(shelf) = self
            .shelves
            .iter_mut()
            .find(|shelf| shelf.y == slot.y && shelf.h >= slot.h)
        {
            consume_from_shelf(shelf, slot, &self.border);
        } else {
            let mut shelf = RuntimeShelf {
                y: slot.y,
                h: slot.h,
                segs: vec![(self.border.x, self.border.w)],
            };
            consume_from_shelf(&mut shelf, slot, &self.border);
            self.shelves.push(shelf);
            self.next_y = self.next_y.max(bottom_ex_u32(slot));
        }
    }

    pub(super) fn add_free(&mut self, rect: Rect) {
        if let Some(shelf) = self
            .shelves
            .iter_mut()
            .find(|shelf| shelf.y == rect.y && shelf.h == rect.h)
        {
            shelf.segs.push((rect.x, rect.w));
            merge_shelf_segments(shelf);
        } else {
            self.shelves.push(RuntimeShelf {
                y: rect.y,
                h: rect.h,
                segs: vec![(rect.x, rect.w)],
            });
        }
    }

    fn try_existing_shelf(&self, w: u32, h: u32) -> Option<Rect> {
        let shelves: Box<dyn Iterator<Item = &RuntimeShelf> + '_> = match self.policy {
            ShelfPolicy::FirstFit => Box::new(self.shelves.iter()),
            ShelfPolicy::NextFit => Box::new(self.shelves.iter().rev().take(1)),
        };

        for shelf in shelves {
            if h <= shelf.h
                && let Some((x, _width)) = shelf.segs.iter().find(|(x, width)| {
                    *width >= w && span_end_ex(*x, w) <= right_ex_u32(&self.border)
                })
            {
                return Some(Rect::new(*x, shelf.y, w, h));
            }
        }
        None
    }

    fn try_new_shelf(&self, w: u32, h: u32) -> Option<Rect> {
        if w <= self.border.w && span_end_ex(self.next_y, h) <= bottom_ex_u32(&self.border) {
            Some(Rect::new(self.border.x, self.next_y, w, h))
        } else {
            None
        }
    }
}

fn consume_from_shelf(shelf: &mut RuntimeShelf, slot: &Rect, border: &Rect) {
    let mut index = 0;
    while index < shelf.segs.len() {
        let (seg_x, seg_w) = shelf.segs[index];
        if slot.x >= seg_x && right_ex_u32(slot) <= span_end_ex(seg_x, seg_w) {
            shelf.segs.remove(index);
            let left_w = slot.x.saturating_sub(seg_x);
            let right_x = right_ex_u32(slot);
            let right_w = span_end_ex(seg_x, seg_w).saturating_sub(right_x);
            if left_w > 0 {
                shelf.segs.push((seg_x, left_w));
            }
            if right_w > 0 {
                shelf.segs.push((right_x, right_w));
            }
            break;
        } else {
            index += 1;
        }
    }
    merge_shelf_segments(shelf);
    shelf
        .segs
        .retain(|(x, w)| *w > 0 && *x >= border.x && span_end_ex(*x, *w) <= right_ex_u32(border));
}

fn merge_shelf_segments(shelf: &mut RuntimeShelf) {
    shelf.segs.sort_by_key(|(x, _)| *x);
    let mut out: Vec<(u32, u32)> = Vec::new();
    for (x, w) in shelf.segs.drain(..) {
        if let Some((last_x, last_w)) = out.last_mut()
            && span_end_ex(*last_x, *last_w) == x
        {
            *last_w += w;
            continue;
        }
        out.push((x, w));
    }
    shelf.segs = out;
}
