/*
 *   GRacer
 *
 *   Copyright (C) 1999 Takashi Matsuda <matsu@users.sourceforge.net>
 *
 * This program is free software; you can redistribute it and/or 
 * modify it under the terms of the GNU General Public License as 
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 * USA
 */

#include <assert.h>
#include <stdio.h>
#include <math.h>
#include "gr_boundary.h"
#include "gr_memory.h"


static int param[] = {
  1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 50, 70, 90, 120, 140
};
static int num_param = sizeof(param) / sizeof(param[0]);


struct _GrBoundary {
  void ***data;
  int limit;
  int depth;
  float lower, width;

  GrBoundaryDestroyCB destroy_cb;
};

GrBoundary *
gr_boundary_new (int depth, float lower, float upper,
		 GrBoundaryDestroyCB callback)
{
  GrBoundary *boundary;

  if (depth <= 0)
    return NULL;

  if (lower == upper)
    return NULL;
  
  if (lower > upper)
    {
      float tmp;

      tmp =upper;
      upper = lower;
      lower = tmp;
    }

  if (depth > num_param)
    depth = num_param;
  
  boundary = gr_new0 (GrBoundary, 1);
  if (!boundary)
    return NULL;

  boundary->lower = lower;
  boundary->width = upper - lower;
  boundary->limit = depth;
  boundary->depth = 0;
  boundary->destroy_cb = callback;
  
  if ((boundary->data = gr_new0 (void **, depth)) == NULL)
    goto ERROR;

  return boundary;
  
 ERROR:
  gr_boundary_free (boundary);
  return NULL;
}


void
gr_boundary_free (GrBoundary *boundary)
{
  int i, j;
  
  if (boundary)
    {
      if (boundary->data)
	{
	  for (i=0; i<boundary->limit; i++)
	      if (boundary->data[i])
		{
		  if (boundary->destroy_cb)
		    for (j=0; j<param[i]; j++)
		      if (boundary->data[i][j])
			(*boundary->destroy_cb) (boundary->data[i][j]);

		  free (boundary->data[i]);
		}

	  free (boundary->data);
	}
      free (boundary);
    }
  
  return;
}


void *
gr_boundary_check (GrBoundary *boundary, float p, int *level)
{
  int i, j, div;
  int lvl;

  /* normalize the p [0 1] */
  p = (p - boundary->lower) / boundary->width;
  if (p < 0.0 || p >= 1.0)
    return NULL;

  lvl = *level;
  if (lvl <= 0 || lvl > boundary->depth)
    lvl = boundary->depth;

  for (i=lvl-1; i>=0; i--)
    {
      if (!boundary->data[i])
	continue;

      div = param[i];
      j = p * div;

      if (j < 0 || div <= j)
	continue;

      if (boundary->data[i][j])
	{
	  *level = i+1;
	  return boundary->data[i][j];
	}
    }

  *level = 0;
  return NULL;
}

GrSList *
gr_boundary_check_region (GrBoundary *boundary,
			  float a, float b, int *level)
{
  int i, j, ia, ib, div;
  int lvl;
  float tmp;
  GrSList *list = NULL;

  assert (level);

  /* normalize the a and b into [0 1] */
  a = (a - boundary->lower) / boundary->width;
  b = (b - boundary->lower) / boundary->width;

  if (a > b) {
    tmp = a;
    a = b;
    b = a;
  }

  if (b < 0.0 || a >= 1.0) {
    return NULL;
  }
  if (a < 0.0) {
    a = 0.0;
  }
  if (b > 1.0) {
    b = 1.0;
  }

  lvl = *level;
  if (lvl < 0 || lvl > boundary->depth)
    lvl = boundary->depth;

  for (i=lvl-1; i>=0; i--)
    {
      if (!boundary->data[i])
	continue;

      div = param[i];
      ia = a * div;
      ib = b * div;

      if (ia < 0) {
	ia = 0;
      }
      if (ib >= div) {
	ib = div - 1;
      }

      for (j=ia; j<=ib; j++) {
	if (boundary->data[i][j]) {
	  list = gr_slist_prepend (list, boundary->data[i][j]);
	}
      }
      if (list) {
	*level = i+1;
	return list;
      }
    }

  *level = 0;
  return NULL;
}

void **
gr_boundary_register (GrBoundary *boundary, float a, float b)
{
  int i, j;
  int div;

  if (boundary == NULL)
    return NULL;
  
  if (a > b)
    {
      float tmp;

      tmp = a;
      a = b;
      b = tmp;
    }
  
  a = (a - boundary->lower) / boundary->width;
  if (a < 0.0)
    a = 0.0;
  else if (a > 0.9999)
    a = 0.9999;

  b = (b - boundary->lower) / boundary->width;
  if (b < 0.0)
    b = 0.0;
  else if (b > 0.9999)
    b = 0.9999;

  for (i=boundary->limit-1; i>=0; i--)
    {
      div = param[i];
      
      if ((j = (int)(a * div)) == (int)(b * div) && j < div)
	{
	  if (!boundary->data[i])
	    {
	      if ((boundary->data[i] = gr_new0 (void *, div)) == NULL)
		return NULL;

	      if (boundary->depth <= i)
		boundary->depth = i + 1;
	    }

	  return boundary->data[i] + j;
	}
    }

  return NULL;
}