/*
  XBubble - rectangle.c

  Copyright (C) 2002  Ivan Djelic <ivan@savannah.gnu.org>
  
  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 <stdlib.h>
#include <string.h>

#include "utils.h"
#include "rectangle.h"

RectangleList new_rectangle_list( int max_size ) {
  RectangleList rl = (RectangleList) xmalloc( sizeof( struct _RectangleList ));
  rl->element = (Rectangle *) xmalloc( sizeof( Rectangle ) * max_size);
  rl->max_size = max_size;
  rl->size = 0;
  return rl;
}

void delete_rectangle_list( RectangleList rl ) {
  free(rl->element);
  free(rl);
}

#define RECTANGLE_LIST_BLOCK (100)

static void add_rectangle_to_list( RectangleList rl, 
				   int x1,
				   int y1,
				   int x2,
				   int y2 ) {
  if (( x2 > x1 )&&( y2 > y1 )) {
    if ( rl->size >= rl->max_size ) {
      rl->max_size += RECTANGLE_LIST_BLOCK;
      rl->element = (Rectangle *) xrealloc( rl->element, 
					    sizeof(Rectangle) * rl->max_size );
    }
    rl->element[rl->size].x1 = x1;
    rl->element[rl->size].y1 = y1;
    rl->element[rl->size].x2 = x2;
    rl->element[rl->size].y2 = y2;
    rl->size++;
  }
}

static void remove_rectangle_from_list_at( RectangleList rl, int i ) {
  if ( i < rl->size )
    rl->element[i] = rl->element[--rl->size];
}

void empty_rectangle_list( RectangleList rl ) {
  rl->size = 0;
}

void add_disjoint_rectangle_to_list( RectangleList rl, 
				     int x1,
				     int y1,
				     int x2,
				     int y2 ) {
  int i, overlap, done = 0;
  RectangleList addlist;
  Rectangle *r;
  addlist = new_rectangle_list( rl->size );
  /* we assume that rl is list of disjoint rectangles */
  for ( i = 0; i < rl->size; i++ ) {
    r = &rl->element[i];
    if (( r->x1 < x2 )&&
	( r->y1 < y2 )&&
	( r->x2 > x1 )&&
	( r->y2 > y1 )) {
      overlap  = (( x1 >= r->x1 )? 1 : 0) + (( y1 >= r->y1 )? 2 : 0);
      overlap += (( x2 <= r->x2 )? 4 : 0) + (( y2 <= r->y2 )? 8 : 0);
      /* merge r with (x1,y1)->(x2,y2) */ 
      switch ( overlap ) {
      case 0: /* r subset of new rectangle */
	remove_rectangle_from_list_at( rl, i-- );
	break;
      case 1:  r->x2 = x1; break;
      case 2:  r->y2 = y1; break;
      case 3:
	add_rectangle_to_list( addlist, r->x1, y1, x1, r->y2 );
	r->y2 = y1;
	break;
      case 4:  r->x1 = x2; break;
      case 5:
	add_rectangle_to_list( addlist, x2, r->y1, r->x2, r->y2 );
	r->x2 = x1;
	break;
      case 6:
	add_rectangle_to_list( addlist, x2, y1, r->x2, r->y2 );
	r->y2 = y1;
	break;
      case 7:  y1 = r->y2; break;
      case 8:  r->y1 = y2; break;
      case 9:
	add_rectangle_to_list( addlist, r->x1, r->y1, x1, y2 );
	r->y1 = y2; 
	break;
      case 10:
	add_rectangle_to_list( addlist, r->x1, y2, r->x2, r->y2 );
	r->y2 = y1;
	break;
      case 11: x1 = r->x2; break;
      case 12:
	add_rectangle_to_list( addlist, x2, r->y1, r->x2, y2 );
	r->y1 = y2;
	break;
      case 13: y2 = r->y1; break;
      case 14: x2 = r->x1; break;
      case 15: /* new rectangle is a subset of r */
	done = 1;
	break;
      }
    }
    if ( done ) {
      delete_rectangle_list(addlist);
      return;
    }
  }
  if ( rl->size + addlist->size >= rl->max_size ) {
    rl->max_size += addlist->size + RECTANGLE_LIST_BLOCK;
    rl->element = (Rectangle *) xrealloc( rl->element, 
					  sizeof(Rectangle) * rl->max_size );
  }
  memcpy( &rl->element[rl->size], 
	  addlist->element, sizeof(Rectangle)*addlist->size );
  rl->size += addlist->size;

  delete_rectangle_list(addlist);
  add_rectangle_to_list( rl, x1, y1, x2, y2 );
}