/*
*Copyright(c)2016, Jeffrey Lee
*Allrightsreserved.
*
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met: 
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
*/

#include <stdio.h>
#include <string.h>
#include "dirtyrect.h"

typedef struct
{
  int start,end;
} range;

static inline int mymin(int a, int b)
{
  return (a < b ? a : b);
}

static inline int mymax(int a, int b)
{
  return (a > b ? a : b);
}

static inline int myabs(int a)
{
  return (a >= 0 ? a : -a);
}

/* True if two ranges overlap */
#define RANGE_INTERSECTS(A,B) (((A).start < (B).end) && ((B).start < (A).end))

/* True if A occurs fully before B */
#define RANGE_PRECEEDS(A,B) ((A).end <= (B).start)

/* Return the length of A that occurs before B */
#define RANGE_HEAD(A,B) mymax(mymin((A).end, (B).start) - (A).start, 0)

void dirtyrect_init(dirtyrect_buffer *buf)
{
  buf->num = 0;
}

static void merge_in_x(dirtyrect_y_slice *buf, const area *a, bool is_new)
{
  if (is_new)
  {
    buf->num = 1;
    buf->slices[0].start = a->x;
    buf->slices[0].end = a->x + a->w;
    return;
  }

  range r = { a->x, a->x + a->w };
  int i = 0;
  while ((i < buf->num) && (r.start != r.end))
  {
    if (r.end < buf->slices[i].start) /* r is fully before current slice */
    {
      if (buf->num == DIRTYRECT_X_SLICES)
      {
        buf->slices[i].start = r.start;
      }
      else
      {
        memmove(&buf->slices[i+1], &buf->slices[i], sizeof(buf->slices[0])*(buf->num-i));
        buf->num++;
        buf->slices[i].start = r.start;
        buf->slices[i].end = r.end;
      }
      return;
    }

    if (r.start > buf->slices[i].end) { i++; continue; } /* Skip if r is located after current slice */

    /* Some kind of touch or intersection. Merge with it. */
    if (r.start < buf->slices[i].start)
    {
      buf->slices[i].start = r.start;
    }
    if (r.end > buf->slices[i].end)
    {
      while ((i < buf->num-1) && (r.end >= buf->slices[i+1].start))
      {
        if (buf->slices[i+1].end > r.end)
        {
          r.end = buf->slices[i+1].end;
        }
        buf->num--;
        memmove(&buf->slices[i+1], &buf->slices[i+2], sizeof(buf->slices[0])*(buf->num-i));
      }
      buf->slices[i].end = r.end;
    }
    return;
  }
  /* Insert trailing slice */
  if (r.start != r.end)
  {
    if (buf->num == DIRTYRECT_X_SLICES)
    {
      buf->slices[buf->num-1].end = r.end;
    }
    else
    {
      buf->num++;
      buf->slices[i].start = r.start;
      buf->slices[i].end = r.end;
    }
  }
}

void dirtyrect_add(dirtyrect_buffer *buf, const area *a)
{
  if (area_is_empty(a))
  {
    return;
  }
  range r = { a->y, a->y + a->h };
  int i = 0;
  while ((i < buf->num) && (r.start != r.end))
  {
    int split = RANGE_HEAD(r, buf->slices[i]);
    if (split) /* Insert new slice if r is before current slice */
    {
      if (buf->num == DIRTYRECT_Y_SLICES)
      {
        buf->slices[i].start = r.start;
      }
      else
      {
        memmove(&buf->slices[i+1], &buf->slices[i], sizeof(buf->slices[0])*(buf->num-i));
        buf->num++;
        buf->slices[i].start = r.start;
        buf->slices[i].end = r.end;
        merge_in_x(&buf->slices[i], a, true);
        r.start += split;
      }
    }

    /* now: r.start >= buf->slices[i].start */

    if (r.start >= buf->slices[i].end) { i++; continue; } /* Skip if r is located after current slice */

    /* TODO: These next two splits should only be performed if a isn't already contained within the current slice */
    if (r.start > buf->slices[i].start) /* Split current slice if r starts after its start */
    {
      if (buf->num == DIRTYRECT_Y_SLICES)
      {
        r.start = buf->slices[i].start;
      }
      else
      {
        memmove(&buf->slices[i+1], &buf->slices[i], sizeof(buf->slices[0])*(buf->num-i));
        buf->num++;
        buf->slices[i+1].start = r.start;
        buf->slices[i].end = r.start;
        i++;
      }
    }

    /* now: r.start == buf->slices[i].start */

    if (r.end < buf->slices[i].end) /* Split current slice if r ends sooner than it */
    {
      if (buf->num == DIRTYRECT_Y_SLICES)
      {
        r.end = buf->slices[i].end;
      }
      else
      {
        memmove(&buf->slices[i+1], &buf->slices[i], sizeof(buf->slices[0])*(buf->num-i));
        buf->num++;
        buf->slices[i+1].start = r.end;
        buf->slices[i].end = r.end;
      }
    }

    /* now: r.start == buf->slices[i].start,
            r.end >= buf->slices[i].end */
    merge_in_x(&buf->slices[i], a, false);
    r.start = mymin(r.end, buf->slices[i].end);
    i++;
  }
  /* Insert trailing slice */
  if (r.start != r.end)
  {
    if (buf->num == DIRTYRECT_Y_SLICES)
    {
      buf->slices[buf->num-1].end = r.end;
      merge_in_x(&buf->slices[buf->num-1], a, false);
    }
    else
    {
      buf->num++;
      buf->slices[i].start = r.start;
      buf->slices[i].end = r.end;
      merge_in_x(&buf->slices[i], a, true);
    }
  }
}

void dirtyrect_cut(dirtyrect_buffer *source, const area *a, dirtyrect_buffer *dest)
{
  // TODO implement properly
  if (area_is_empty(a))
  {
    dirtyrect_init(dest);
    return;
  }
  *dest = *source;
  dirtyrect_init(source);
}

void dirtyrect_next(dirtyrect_buffer *buf, area *out)
{
  if (!buf->num)
  {
    reset_area(out);
    return;
  }
  int my_y = buf->num-1;
  dirtyrect_y_slice *y = &buf->slices[my_y];
  dirtyrect_x_slice *x = &y->slices[y->num-1];
  set_area(out, x->start, y->start, x->end - x->start, y->end - y->start);
  if (!--y->num)
  {
    buf->num--;
  }
  /* Trivial merge with trailing rect on preceeding lines */
  while (my_y)
  {
    my_y--;
    y--;
    if (y->end != out->y)
    {
      break;
    }
    dirtyrect_x_slice *x = &y->slices[y->num-1];
    if ((x->start == out->x) && (x->end == out->x + out->w))
    {
      out->y = y->start;
      out->h += y->end - y->start;
      if (!--y->num)
      {
        buf->num--;
        memmove(&buf->slices[my_y], &buf->slices[my_y+1], sizeof(buf->slices[0]) * (buf->num - my_y));
      }
    }
    else
    {
      break;
    }
  }
}

bool dirtyrect_intersects(const dirtyrect_buffer *buf, const area *a)
{
  if (!buf->num)
  {
    return false;
  }
  dirtyrect_buffer temp = *buf;
  area a2;
  dirtyrect_next(&temp, &a2);
  while (!area_is_empty(&a2))
  {
    if (areas_intersect(a, &a2))
    {
      return true;
    }
    dirtyrect_next(&temp, &a2);
  }
  return false;
}
