/*

    SDL - Simple DirectMedia Layer

    Copyright (C) 1997-2009 Sam Lantinga

    This library is free software; you can redistribute it and/or

    modify it under the terms of the GNU Lesser General Public

    License as published by the Free Software Foundation; either

    version 2.1 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,

    but WITHOUT ANY WARRANTY; without even the implied warranty of

    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public

    License along with this library; if not, write to the Free Software

    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

    Sam Lantinga

    slouken@libsdl.org

*/

#include "SDL_config.h"

#include "SDL_video.h"

#include "SDL_rect_c.h"

SDL_bool

SDL_HasIntersection(const SDL_Rect * A, const SDL_Rect * B)

{

    int Amin, Amax, Bmin, Bmax;

    /* Horizontal intersection */

    Amin = A->x;

    Amax = Amin + A->w;

    Bmin = B->x;

    Bmax = Bmin + B->w;

    if (Bmin > Amin)

        Amin = Bmin;

    if (Bmax < Amax)

        Amax = Bmax;

    if (Amax <= Amin)

        return SDL_FALSE;

    /* Vertical intersection */

    Amin = A->y;

    Amax = Amin + A->h;

    Bmin = B->y;

    Bmax = Bmin + B->h;

    if (Bmin > Amin)

        Amin = Bmin;

    if (Bmax < Amax)

        Amax = Bmax;

    if (Amax <= Amin)

        return SDL_FALSE;

    return SDL_TRUE;

}

SDL_bool

SDL_IntersectRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)

{

    int Amin, Amax, Bmin, Bmax;

    /* Horizontal intersection */

    Amin = A->x;

    Amax = Amin + A->w;

    Bmin = B->x;

    Bmax = Bmin + B->w;

    if (Bmin > Amin)

        Amin = Bmin;

    result->x = Amin;

    if (Bmax < Amax)

        Amax = Bmax;

    result->w = Amax - Amin;

    /* Vertical intersection */

    Amin = A->y;

    Amax = Amin + A->h;

    Bmin = B->y;

    Bmax = Bmin + B->h;

    if (Bmin > Amin)

        Amin = Bmin;

    result->y = Amin;

    if (Bmax < Amax)

        Amax = Bmax;

    result->h = Amax - Amin;

    return !SDL_RectEmpty(result);

}

void

SDL_UnionRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result)

{

    int Amin, Amax, Bmin, Bmax;

    /* Horizontal union */

    Amin = A->x;

    Amax = Amin + A->w;

    Bmin = B->x;

    Bmax = Bmin + B->w;

    if (Bmin < Amin)

        Amin = Bmin;

    result->x = Amin;

    if (Bmax > Amax)

        Amax = Bmax;

    result->w = Amax - Amin;

    /* Vertical intersection */

    Amin = A->y;

    Amax = Amin + A->h;

    Bmin = B->y;

    Bmax = Bmin + B->h;

    if (Bmin < Amin)

        Amin = Bmin;

    result->y = Amin;

    if (Bmax > Amax)

        Amax = Bmax;

    result->h = Amax - Amin;

}

SDL_bool

SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,

                         int *Y2)

{

    int x1, y1;

    int x2, y2;

    int rectx1;

    int recty1;

    int rectx2;

    int recty2;

    if (!rect || !X1 || !Y1 || !X2 || !Y2) {

        SDL_FALSE;

    }

    x1 = *X1;

    y1 = *Y1;

    x2 = *X2;

    y2 = *Y2;

    rectx1 = rect->x;

    recty1 = rect->y;

    rectx2 = rect->x + rect->w - 1;

    recty2 = rect->y + rect->h - 1;

    /* Check to see if entire line is inside rect */

    if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&

        y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {

        return SDL_TRUE;

    }

    /* Check to see if entire line is to one side of rect */

    if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||

        return SDL_FALSE;

    }

    if (y1 == y2) {

        /* Horizontal line, easy to clip */

        if (x1 < rectx1) {

            *X1 = rectx1;

        } else if (x1 > rectx2) {

            *X1 = rectx2;

        }

        if (x2 < rectx1) {

            *X2 = rectx1;

        } else if (x2 > rectx2) {

            *X2 = rectx2;

        }

        return SDL_TRUE;

    }

    if (x1 == x2) {

        /* Vertical line, easy to clip */

        if (y1 < recty1) {

            *Y1 = recty1;

        } else if (y1 > recty2) {

            *Y1 = recty2;

        }

        if (y2 < recty1) {

            *Y2 = recty1;

        } else if (y2 > recty2) {

            *Y2 = recty2;

        }

        return SDL_TRUE;

    }

    else {

        /* The task of clipping a line with finite slope ratios in a fixed-

         * precision coordinate space is not as immediately simple as it is

         * with coordinates of arbitrary precision. If the ratio of slopes

         * between the input line segment and the result line segment is not

         * a whole number, you have in fact *moved* the line segment a bit,

         * and there can be no avoiding it without more precision

         */

        int *x_result_[] = { X1, X2, NULL }, **x_result = x_result_;

        int *y_result_[] = { Y1, Y2, NULL }, **y_result = y_result_;

        SDL_bool intersection = SDL_FALSE;

        double b, m, left, right, bottom, top;

        int xl, xh, yl, yh;

        /* solve mx+b line formula */

        m = (double) (y1 - y2) / (double) (x1 - x2);

        b = y2 - m * (double) x2;

        /* find some linear intersections */

        left = (m * (double) rectx1) + b;

        right = (m * (double) rectx2) + b;

        top = (recty1 - b) / m;

        bottom = (recty2 - b) / m;

        /* sort end-points' x and y components individually */

        if (x1 < x2) {

            xl = x1;

            xh = x2;

        } else {

            xl = x2;

            xh = x1;

        }

        if (y1 < y2) {

            yl = y1;

            yh = y2;

        } else {

            yl = y2;

            yh = y1;

        }

#define RISING(a, b, c) (((a)<=(b))&&((b)<=(c)))

        /* check for a point that's entirely inside the rect */

        if (RISING(rectx1, x1, rectx2) && RISING(recty1, y1, recty2)) {

            x_result++;

            y_result++;

            intersection = SDL_TRUE;

        } else

            /* it was determined earlier that *both* end-points are not contained */

        if (RISING(rectx1, x2, rectx2) && RISING(recty1, y2, recty2)) {

            **(x_result++) = x2;

            **(y_result++) = y2;

            intersection = SDL_TRUE;

        }

        if (RISING(recty1, left, recty2) && RISING(xl, rectx1, xh)) {

            **(x_result++) = rectx1;

            **(y_result++) = (int) left;

            intersection = SDL_TRUE;

        }

        if (*x_result == NULL)

            return intersection;

        if (RISING(recty1, right, recty2) && RISING(xl, rectx2, xh)) {

            **(x_result++) = rectx2;

            **(y_result++) = (int) right;

            intersection = SDL_TRUE;

        }

        if (*x_result == NULL)

            return intersection;

        if (RISING(rectx1, top, rectx2) && RISING(yl, recty1, yh)) {

            **(x_result++) = (int) top;

            **(y_result++) = recty1;

            intersection = SDL_TRUE;

        }

        if (*x_result == NULL)

            return intersection;

        if (RISING(rectx1, bottom, rectx2) && RISING(yl, recty2, yh)) {

            **(x_result++) = (int) bottom;

            **(y_result++) = recty2;

            intersection = SDL_TRUE;

        }

        return intersection;

    }

    return SDL_FALSE;

}

void

SDL_AddDirtyRect(SDL_DirtyRectList * list, const SDL_Rect * rect)

{

    SDL_DirtyRect *dirty;

    /* FIXME: At what point is this optimization too expensive? */

    for (dirty = list->list; dirty; dirty = dirty->next) {

        if (SDL_HasIntersection(&dirty->rect, rect)) {

            SDL_UnionRect(&dirty->rect, rect, &dirty->rect);

            return;

        }

    }

    if (list->free) {

        dirty = list->free;

        list->free = dirty->next;

    } else {

        dirty = (SDL_DirtyRect *) SDL_malloc(sizeof(*dirty));

        if (!dirty) {

            return;

        }

    }

    dirty->rect = *rect;

    dirty->next = list->list;

    list->list = dirty;

}

void

SDL_ClearDirtyRects(SDL_DirtyRectList * list)

{

    SDL_DirtyRect *prev, *curr;

    /* Skip to the end of the free list */

    prev = NULL;

    for (curr = list->free; curr; curr = curr->next) {

        prev = curr;

    }

    /* Add the list entries to the end */

    if (prev) {

        prev->next = list->list;

    } else {

        list->free = list->list;

    }

    list->list = NULL;

}

void

SDL_FreeDirtyRects(SDL_DirtyRectList * list)

{

    while (list->list) {

        SDL_DirtyRect *elem = list->list;

        list->list = elem->next;

        SDL_free(elem);

    }

    while (list->free) {

        SDL_DirtyRect *elem = list->free;

        list->free = elem->next;

        SDL_free(elem);

    }

}

/* vi: set ts=4 sw=4 expandtab: */