
function overlaps(a, b) {
    return a.left < b.right && a.right > b.left && a.top < b.bottom && a.bottom > b.top;
}

export function computeAABBSize(width, height, rotationDeg = 0) {
    if (!rotationDeg) return { width, height };
    const rad = (rotationDeg * Math.PI) / 180;
    const cos = Math.abs(Math.cos(rad));
    const sin = Math.abs(Math.sin(rad));
    return {
        width: width * cos + height * sin,
        height: width * sin + height * cos
    };
}

export function packItems(items, obstacles = [], containerWidth = Infinity, options = {}) {
    const startX = options.startX ?? 0;
    const startY = options.startY ?? 0;
    const gapX = options.gapX ?? 0;
    const gapY = options.gapY ?? 0;

    const sorted = [...items].sort((a, b) => {
        const areaDiff = (b.width * b.height) - (a.width * a.height);
        return areaDiff !== 0 ? areaDiff : (b.height - a.height);
    });

    const placedRects = obstacles.map(o => ({
        left: o.x, top: o.y, right: o.x + o.width, bottom: o.y + o.height
    }));

    const dropY = (x, w, h) => {
        let y = startY;
        let guard = 0;
        while (guard++ <= placedRects.length) {
            const rect = { left: x, right: x + w, top: y, bottom: y + h };
            let maxBottom = y;
            placedRects.forEach(r => {
                if (overlaps(rect, r) && r.bottom > maxBottom) {
                    maxBottom = r.bottom;
                }
            });
            if (maxBottom === y) break; // どの矩形とも衝突しなくなった＝着地確定
            y = maxBottom;
        }
        return y;
    };

    const placed = [];

    sorted.forEach(item => {
        const aabb = computeAABBSize(item.width, item.height, item.rotation || 0);
        const w = aabb.width + gapX;
        const h = aabb.height + gapY;
        const offsetX = (aabb.width - item.width) / 2;
        const offsetY = (aabb.height - item.height) / 2;

        const candidateXs = new Set([startX]);
        placedRects.forEach(r => {
            candidateXs.add(r.right);
            candidateXs.add(r.left);
            candidateXs.add(r.left - w);
        });

        let best = null;
        candidateXs.forEach(x => {
            if (x < startX) return;
            if (containerWidth !== Infinity && x + w > startX + containerWidth) return;
            const y = dropY(x, w, h);
            if (!best || y < best.y || (y === best.y && x < best.x)) {
                best = { x, y };
            }
        });
        if (!best) {
            best = { x: startX, y: startY };
        }

        const result = { ...item, x: best.x + offsetX, y: best.y + offsetY };
        placed.push(result);
        placedRects.push({ left: best.x, top: best.y, right: best.x + w, bottom: best.y + h });
    });

    return placed;
}
