source: golgotha/src/i4/area/rectlist.cc

Last change on this file was 80, checked in by Sam Hocevar, 12 years ago
  • Adding the Golgotha source code. Not sure what's going to be interesting in there, but since it's all public domain, there's certainly stuff to pick up.
File size: 9.4 KB
Line 
1/********************************************************************** <BR>
2  This file is part of Crack dot Com's free source code release of
3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for
4  information about compiling & licensing issues visit this URL</a>
5  <PRE> If that doesn't help, contact Jonathan Clark at
6  golgotha_source@usa.net (Subject should have "GOLG" in it)
7***********************************************************************/
8
9#include "area/rectlist.hh"
10#include "error/error.hh"
11#include "memory/malloc.hh"
12#include "error/error.hh"
13#include "init/init.hh"
14
15#include <stdlib.h>
16
17#ifndef max
18#define max(x,y) (((x)>(y)) ? (x) : (y))
19#define min(x,y) (((x)>(y)) ? (y) : (x))
20#endif
21
22i4_rect_list_class::area::area_allocator *i4_rect_list_class::area::area_alloc=0;
23
24
25// this class is used to ensure area_alloc is created after the memory manager is installed
26class area_allocator_initter : public i4_init_class
27{
28  public :
29  virtual void init()
30  {
31    i4_rect_list_class::area::area_alloc=
32      new i4_linear_allocator(sizeof(i4_rect_list_class::area),0,300,"areas");
33  }
34  virtual void uninit()
35  {
36    delete i4_rect_list_class::area::area_alloc;
37  }
38} ;
39
40static area_allocator_initter instance;
41
42void i4_rect_list_class::swap(i4_rect_list_class *other)
43{
44  other->list.swap(list);
45}
46
47
48void i4_rect_list_class::remove_area(i4_coord x1, i4_coord y1, i4_coord x2, i4_coord y2)
49{
50  i4_isl_list<area>::iterator a=list.begin(),last=list.end(),del;
51
52  for (;a!=list.end();)
53  {
54    if (!(x2<a->x1 || y2<a->y1 || x1>a->x2 || y1>a->y2))
55    {     
56      if (x2>=a->x2 && x1<=a->x1) // does it take a x slice off? (across)
57      {
58        if (y2>=a->y2 && y1<=a->y1)
59        {
60          del=a;
61          ++a;
62
63          if (last!=list.end())
64            list.erase_after(last);
65          else
66            list.erase();
67
68          delete_area(&*del);
69        }
70        else if (y2>=a->y2)
71        {
72          a->y2=y1-1;
73          last=a;
74          ++a;
75        }
76        else if (y1<=a->y1)
77        {
78          a->y1=y2+1;
79          last=a;
80          ++a;
81        }
82        else
83        {
84          list.insert(*(new_area(a->x1,a->y1,a->x2,y1-1)));
85          a->y1=y2+1;
86          last=a;
87          ++a;
88        }
89      }       
90      else if (y2>=a->y2 && y1<=a->y1)  // does it take a y slice off (down)
91      {
92        if (x2>=a->x2)
93        {
94          a->x2=x1-1;
95          last=a;
96          ++a;
97        }
98        else if (x1<=a->x1)
99        {
100         a->x1=x2+1;
101         last=a;
102         ++a;
103        }
104        else
105        {
106          list.insert(*(new_area(a->x1,a->y1,x1-1,a->y2)));
107          a->x1=x2+1;
108          last=a;
109          ++a;
110        }
111      }     
112      else   // otherwise it just takes a little chunk off
113      {
114        i4_coord ax1,ay1,ax2,ay2;
115        del=a;
116        ++a;
117       
118        if (last!=list.end())
119          list.erase_after(last);
120        else
121          list.erase();
122
123        if (x2>=del->x2)      { ax1=del->x1; ax2=x1-1; }
124        else if (x1<=del->x1) { ax1=x2+1; ax2=del->x2; }
125        else                  { ax1=del->x1; ax2=x1-1; }
126        if (y2>=del->y2)      { ay1=y1; ay2=del->y2; }
127        else if (y1<=del->y1) { ay1=del->y1; ay2=y2; }
128        else                  { ay1=y1; ay2=y2; }
129        {
130          list.insert(*(new_area(ax1,ay1,ax2,ay2)));
131          if (a==list.end())
132            a=list.begin();
133          else if (last==list.end())
134            last=list.begin();
135        }
136       
137       
138        if (x2>=del->x2 || x1<=del->x1)  { ax1=del->x1; ax2=del->x2; }
139        else                             { ax1=x2+1; ax2=del->x2; }
140
141        if (y2>=del->y2)
142        { if (ax1==del->x1) { ay1=del->y1; ay2=y1-1; }
143        else { ay1=y1; ay2=del->y2;   } }
144        else if (y1<=del->y1) { if (ax1==del->x1) { ay1=y2+1; ay2=del->y2; }
145        else  { ay1=del->y1; ay2=y2; } }
146        else { if (ax1==del->x1) { ay1=del->y1; ay2=y1-1; }
147        else { ay1=y1; ay2=y2; } }
148       
149        list.insert(*(new_area(ax1,ay1,ax2,ay2)));
150        if (a==list.end())
151          a=list.begin();
152        else if (last==list.end())
153          last=list.begin();
154
155        if (x1>del->x1 && x2<del->x2)
156        {
157          if (y1>del->y1 && y2<del->y2)
158          {
159            list.insert(*(new_area(del->x1,del->y1,del->x2,y1-1)));
160            list.insert(*(new_area(del->x1,y2+1,del->x2,del->y2)));
161          } else if (y1<=del->y1)
162            list.insert(*(new_area(del->x1,y2+1,del->x2,del->y2)));
163          else
164            list.insert(*(new_area(del->x1,del->y1,del->x2,y1-1)));
165        } else if (y1>del->y1 && y2<del->y2)
166          list.insert(*(new_area(del->x1,y2+1,del->x2,del->y2)));
167       
168        delete_area(&*del);
169      }
170    } else
171    {
172      last=a;
173      ++a;
174    }
175  }
176}
177
178
179void i4_rect_list_class::add_area(i4_coord x1, i4_coord y1, i4_coord x2, i4_coord y2,
180                                  i4_bool combine)
181{
182  if (x1>x2 || y1>y2)
183    return ;
184
185  if (list.begin()==list.end())
186    list.insert(*(new_area(x1,y1,x2,y2)));
187  else
188  {
189    i4_isl_list<area>::iterator a=list.begin(),last=list.end();
190
191    for (;a!=list.end();)
192    {
193      // check to see if this new rectangle completly encloses the check rectangle
194      if (x1<=a->x1 && y1<=a->y1 && x2>=a->x2 && y2>=a->y2)
195      {
196        if (last==list.end())
197          list.erase();
198        else list.erase_after(last);
199        i4_isl_list<area>::iterator q=a;
200        ++a;
201        delete_area(&*q);
202      } else if (!(x2<a->x1 || y2<a->y1 || x1>a->x2 || y1>a->y2))  // intersects another area?
203      {   
204        if (x1<a->x1)
205          add_area(x1,(i4_coord) max(y1,a->y1),(sw16)(a->x1-1),(i4_coord) min(y2,a->y2));
206        if (x2>a->x2)
207          add_area(a->x2+1,(i4_coord) max(y1,a->y1),x2,(i4_coord) min(y2,a->y2));
208        if (y1<a->y1)
209          add_area(x1,y1,x2,a->y1-1);
210        if (y2>a->y2)
211          add_area(x1,a->y2+1,x2,y2);
212
213        return ;
214      }
215      else if (combine && a->x2+1==x1 && a->y1==y1 && a->y2==y2)  // combines to the right
216      {
217        if (last==list.end())
218          list.erase();
219        else list.erase_after(last);
220
221        a->x2=x2;
222
223        add_area(a->x1, a->y1, a->x2, a->y2);
224        delete_area(&*a);
225        return;
226      }
227      else if (combine && a->x1-1==x2 && a->y1==y1 && a->y2==y2)  // combines to the left
228      {
229        if (last==list.end())
230          list.erase();
231        else list.erase_after(last);
232
233        a->x1=x1;
234
235        add_area(a->x1, a->y1, a->x2, a->y2);
236        delete_area(&*a);
237        return;
238      }
239      else if (combine && a->y1-1==y2 && a->x1==x1 && a->x2==x2)  // combines above
240      {
241        if (last==list.end())
242          list.erase();
243        else list.erase_after(last);
244
245        a->y1=y1;
246
247        add_area(a->x1, a->y1, a->x2, a->y2);
248        delete_area(&*a);
249        return;
250      }
251      else if (combine && a->y2+1==y1 && a->x1==x1 && a->x2==x2)  // combines below
252      {
253        if (last==list.end())
254          list.erase();
255        else list.erase_after(last);
256
257        a->y2=y2;
258
259        add_area(a->x1, a->y1, a->x2, a->y2);
260        delete_area(&*a);
261        return;
262      }
263      else
264      {       
265        last=a;
266        ++a;
267      }
268    }
269    list.insert(*(new_area(x1,y1,x2,y2)));
270  }
271}
272
273
274void i4_rect_list_class::intersect_area(i4_coord x1, i4_coord y1, i4_coord x2, i4_coord y2) // reduces area list to that which intersects this area
275{
276  i4_isl_list<area>::iterator a=list.begin(),last=list.end(),next;
277  for (;a!=list.end();a=next)
278  {
279    next=a;
280    ++next;
281
282    if (!(x2<a->x1 || y2<a->y1 || x1>a->x2 || y1>a->y2))
283    {
284      if (x1>a->x1) a->x1=x1;
285      if (x2<a->x2) a->x2=x2;
286      if (y1>a->y1) a->y1=y1;
287      if (y2<a->y2) a->y2=y2; 
288      last=a;
289    } else
290    {
291      if (a==list.begin())       
292        list.erase();
293      else
294        list.erase_after(last);
295      delete_area(&*a);
296    }
297  }
298}
299
300
301// return i4_T if area is totally clipped away
302// this can be used to skip expensive drawing operations
303i4_bool i4_rect_list_class::clipped_away(i4_coord x1, i4_coord y1, i4_coord x2, i4_coord y2)
304{
305  i4_rect_list_class area_left(x1,y1,x2,y2);
306
307  i4_isl_list<area>::iterator a=list.begin();
308  for (;a!=list.end();++a) 
309    area_left.remove_area(a->x1, a->y1, a->x2, a->y2);
310 
311  return area_left.empty();
312}
313
314
315i4_rect_list_class::i4_rect_list_class(i4_rect_list_class *copy_from, i4_coord xoff, i4_coord yoff)
316{
317  i4_isl_list<area>::iterator a=copy_from->list.begin(),last,q;
318  if (a!=copy_from->list.end())
319  {
320    last=new_area(a->x1+xoff,a->y1+yoff,a->x2+xoff,a->y2+yoff);
321    list.insert(*last);
322
323    ++a;
324    while (a!=copy_from->list.end())
325    {
326      q=new_area(a->x1+xoff,a->y1+yoff,a->x2+xoff,a->y2+yoff);
327      list.insert_after(last,*q);
328      last=q;
329      ++a;
330    }
331  }
332
333}
334
335void i4_rect_list_class::intersect_list(i4_rect_list_class *other)                                 // reduces area list to that which intersects this area list
336{
337  i4_rect_list_class intersection;
338  i4_isl_list<area>::iterator a,b;
339
340  for (b=other->list.begin();b!=other->list.end();++b)
341  {
342    for (a=list.begin();a!=list.end();++a)
343    {
344      if (!(b->x2<a->x1 || b->y2<a->y1 || b->x1>a->x2 || b->y1>a->y2))
345      {
346        i4_coord x1,y1,x2,y2;
347        if (b->x1>a->x1) x1=b->x1; else x1=a->x1;
348        if (b->x2<a->x2) x2=b->x2; else x2=a->x2;
349        if (b->y1>a->y1) y1=b->y1; else y1=a->y1;
350        if (b->y2<a->y2) y2=b->y2; else y2=a->y2;
351
352        intersection.list.insert(*(new_area(x1,y1,x2,y2)));
353      } 
354    }
355  }
356  intersection.list.swap(list);
357}
358
359
360void i4_rect_list_class::inspect(int print)
361{
362  for (i4_isl_list<area>::iterator a=list.begin(); a!=list.end(); ++a)
363  {
364    if (print)
365      i4_warning("(%d %d %d %d  (%d x %d)", a->x1, a->y1, a->x2, a->y2,
366                 a->x2-a->x1+1, a->y2-a->y1+1);
367  }
368
369}
370
Note: See TracBrowser for help on using the repository browser.