win/gem/gr_rect.c

   1 /*      SCCS Id: @(#)gr_rect.c  3.4     2001/12/10                              */
   2 /* Copyright (c) Christian Bressler, 2001                                       */
   3 /* NetHack may be freely redistributed.  See license for details. */
   4 /* This is an almost exact copy of qt_clust.cpp */
   5 /* gr_rect.c */
   6 #include <stdlib.h>
   7 #include <stdio.h>
   8 #include <limits.h>
   9 #include "gr_rect.h"
  10 dirty_rect *new_dirty_rect(int size){
  11         dirty_rect *new=NULL;
  12         if(size>0){
  13                 new=(dirty_rect *)calloc(1L,sizeof(dirty_rect));
  14                 if(new){
  15                         new->rects=(GRECT *)calloc((long)size,sizeof(GRECT));
  16                         if(new->rects==NULL){
  17                                 free(new);
  18                                 return(NULL);
  19                         }
  20                         new->max=size;
  21                 }
  22         }
  23         return(new);
  24 }
  25 void delete_dirty_rect(dirty_rect *this){
  26         if(this==NULL)
  27                 return;
  28         if(this->rects)
  29                 free(this->rects);
  30         /* In case the Pointer is reused wrongly */
  31         this->rects=NULL;
  32         this->max=0;
  33         this->used=0;
  34         free(this);
  35 }
  36 static int gc_inside(GRECT *frame,GRECT *test);
  37 static int gc_touch(GRECT *frame,GRECT *test);
  38 static void gc_combine(GRECT *frame,GRECT *test);
  39 static long gc_area(GRECT *area);
  40 int add_dirty_rect(dirty_rect *dr,GRECT *area){
  41         int cursor;
  42         long lowestcost=9999999L;
  43         int cheapest=-1;
  44         int cheapestmerge1=-1;
  45         int cheapestmerge2=-1;
  46         int merge1;
  47         int merge2;
  48         for (cursor=0; cursor<dr->used; cursor++) {
  49                 if (gc_inside(&dr->rects[cursor],area)) {
  50                         /* Wholly contained already. */
  51                         return(TRUE);
  52                 }
  53         }
  54         for (cursor=0; cursor<dr->used; cursor++) {
  55                 if (gc_touch(&dr->rects[cursor],area)) {
  56                         GRECT larger=dr->rects[cursor];
  57                         long cost;
  58                         gc_combine(&larger,area);
  59                         cost=gc_area(&larger)-gc_area(&dr->rects[cursor]);
  60                         if (cost < lowestcost) {
  61                                 int bad=FALSE,c;
  62                                 for (c=0; c<dr->used && !bad; c++) {
  63                                         bad=gc_touch(&dr->rects[c],&larger) && c!=cursor;
  64                                 }
  65                                 if (!bad) {
  66                                         cheapest=cursor;
  67                                         lowestcost=cost;
  68                                 }
  69                         }
  70                 }
  71         }
  72         if (cheapest>=0) {
  73                 gc_combine(&dr->rects[cheapest],area);
  74                 return(TRUE);
  75         }
  76         if (dr->used < dr->max) {
  77                 dr->rects[dr->used++]=*area;
  78                 return(TRUE);
  79         }
  80         // Do cheapest of:
  81         //      add to closest cluster
  82         //      do cheapest cluster merge, add to new cluster
  83         lowestcost=9999999L;
  84         cheapest=-1;
  85         for (cursor=0; cursor<dr->used; cursor++) {
  86                 GRECT larger=dr->rects[cursor];
  87                 long cost;
  88                 gc_combine(&larger,area);
  89                 cost=gc_area(&larger)-gc_area(&dr->rects[cursor]);
  90                 if (cost < lowestcost) {
  91                         int bad=FALSE, c;
  92                         for (c=0; c<dr->used && !bad; c++) {
  93                                 bad=gc_touch(&dr->rects[c],&larger) && c!=cursor;
  94                         }
  95                         if (!bad) {
  96                                 cheapest=cursor;
  97                                 lowestcost=cost;
  98                         }
  99                 }
 100         }
 101         // XXX could make an heuristic guess as to whether we
 102         // XXX need to bother looking for a cheap merge.
 103         for (merge1=0; merge1<dr->used; merge1++) {
 104                 for (merge2=0; merge2<dr->used; merge2++) {
 105                         if (merge1!=merge2) {
 106                                 GRECT larger=dr->rects[merge1];
 107                                 long cost;
 108                                 gc_combine(&larger,&dr->rects[merge2]);
 109                                 cost=gc_area(&larger)-gc_area(&dr->rects[merge1])-gc_area(&dr->rects[merge2]);
 110                                 if (cost < lowestcost) {
 111                                         int bad=FALSE, c;
 112                                         for (c=0; c<dr->used && !bad; c++) {
 113                                                 bad=gc_touch(&dr->rects[c],&larger) && c!=cursor;
 114                                         }
 115                                         if (!bad) {
 116                                                 cheapestmerge1=merge1;
 117                                                 cheapestmerge2=merge2;
 118                                                 lowestcost=cost;
 119                                         }
 120                                 }
 121                         }
 122                 }
 123         }
 124         if (cheapestmerge1>=0) {
 125                 gc_combine(&dr->rects[cheapestmerge1],&dr->rects[cheapestmerge2]);
 126                 dr->rects[cheapestmerge2]=dr->rects[dr->used-1];
 127                 dr->rects[dr->used-1]=*area;
 128         } else {
 129                 gc_combine(&dr->rects[cheapest],area);
 130         }
 131         // NB: clusters do not intersect (or intersection will
 132         //       overwrite).  This is a result of the above algorithm,
 133         //       given the assumption that (x,y) are ordered topleft
 134         //       to bottomright.
 135         return(TRUE);
 136 }
 137 int get_dirty_rect(dirty_rect* dr,GRECT *area){
 138         if(dr==NULL || area==NULL || dr->rects==NULL || dr->used<=0 || dr->max<=0)
 139                 return(FALSE);
 140         *area=dr->rects[--dr->used];
 141         return(TRUE);
 142 }
 143 int clear_dirty_rect(dirty_rect *dr){
 144         if(dr)
 145                 dr->used=0;
 146         return(TRUE);
 147 }
 148 int resize_dirty_rect(dirty_rect *dr,int new_size){
 149         return(FALSE);
 150 }
 151 static int gc_inside(GRECT *frame,GRECT *test){
 152         if(frame && test && frame->g_x<=test->g_x && frame->g_y<=test->g_y &&
 153                 frame->g_x+frame->g_w>=test->g_x+test->g_w &&
 154                 frame->g_y+frame->g_h>=test->g_y+test->g_h
 155         )
 156                 return(TRUE);
 157         return(FALSE);
 158 }
 159 static int gc_touch(GRECT *frame,GRECT *test){
 160         GRECT tmp={test->g_x-1,test->g_y-1,test->g_w+2,test->g_h+2};
 161         return(rc_intersect(frame,&tmp));
 162 }
 163 static void gc_combine(GRECT *frame,GRECT *test){
 164         if(!frame || !test)
 165                 return;
 166         if(frame->g_x>test->g_x){
 167                 frame->g_w+=frame->g_x-test->g_x;
 168                 frame->g_x=test->g_x;
 169         }
 170         if(frame->g_y>test->g_y){
 171                 frame->g_h+=frame->g_y-test->g_y;
 172                 frame->g_y=test->g_y;
 173         }
 174         if(frame->g_x+frame->g_w<test->g_x+test->g_w)
 175                 frame->g_w=test->g_x+test->g_w-frame->g_x;
 176         if(frame->g_y+frame->g_h<test->g_y+test->g_h)
 177                 frame->g_h=test->g_y+test->g_h-frame->g_y;
 178 }
 179 static long gc_area(GRECT *area){
 180         return((long)area->g_h*(long)area->g_w);
 181 }