1 //------------------------------------------------------------------------------
2 // emClipRects.h
3 //
4 // Copyright (C) 2011-2012,2014 Oliver Hamann.
5 //
6 // Homepage: http://eaglemode.sourceforge.net/
7 //
8 // This program is free software: you can redistribute it and/or modify it under
9 // the terms of the GNU General Public License version 3 as published by the
10 // Free Software Foundation.
11 //
12 // This program is distributed in the hope that it will be useful, but WITHOUT
13 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
14 // FOR A PARTICULAR PURPOSE. See the GNU General Public License version 3 for
15 // more details.
16 //
17 // You should have received a copy of the GNU General Public License version 3
18 // along with this program. If not, see <http://www.gnu.org/licenses/>.
19 //------------------------------------------------------------------------------
20
21 #ifndef emClipRects_h
22 #define emClipRects_h
23
24 #ifndef emList_h
25 #include <emCore/emList.h>
26 #endif
27
28
29 //==============================================================================
30 //================================ emClipRects =================================
31 //==============================================================================
32
33 template <class NUM> class emClipRects {
34
35 public:
36
37 // Template class for a disjoint set of clip rectangles with
38 // copy-on-write behavior. The template parameter NUM is the type of the
39 // rectangle coordinates (usually int or double).
40
41 emClipRects();
42 // Construct an empty set of clip rectangles.
43
44 emClipRects(const emClipRects & clipRects);
45 // Construct a copied set of clip rectangles.
46 // Arguments:
47 // clipRects - The set to be copied.
48
49 emClipRects(NUM x1, NUM y1, NUM x2, NUM y2);
50 // Construct a set of clip rectangles with a single rectangle.
51 // Arguments:
52 // x1,y1,x2,y2 - Coordinates of the rectangle.
53
54 ~emClipRects();
55 // Destruct a set of clip rectangles.
56
57 emClipRects & operator = (const emClipRects & clipRects);
58 // Copy a set of clip rectangles.
59
60 class Rect {
61 public:
62
63 // Class for one rectangle of a set of clip rectangles.
64
65 NUM GetX1() const;
66 NUM GetY1() const;
67 NUM GetX2() const;
68 NUM GetY2() const;
69 void Get(NUM * pX1, NUM * pY1, NUM * pX2, NUM * pY2) const;
70 // Get the coordinates of the rectangle.
71
72 const Rect * GetNext() const;
73 // Get the next rectangle in the list of rectangles.
74
75 private:
76 friend class emClipRects<NUM>;
77 NUM X1,Y1,X2,Y2;
78 Rect * Next;
79 };
80
81 const Rect * GetFirst() const;
82 // Get a pointer to the first rectangle. The rectangles are
83 // organized in a single-linked NULL-terminated list. So you can
84 // iterate the rectangles with:
85 //
86 // for (r=clipRects.GetFirst(); r; r=r->GetNext()) {...}
87 //
88 // The rectangles have no order, except after one has called
89 // Sort().
90 //
91 // At least because of the copy-on-write feature, the pointers
92 // are valid only until calling any non-const method or operator
93 // on this list, or giving this list as a non-const argument to
94 // any call in the world.
95
96 int GetCount() const;
97 // Get the number of rectangles.
98
99 void GetMinMax(NUM * pX1, NUM * pY1, NUM * pX2, NUM * pY2) const;
100 // Calculate the min/max rectangle. That is the smallest
101 // rectangle which encloses the whole set of clip rectangles. If
102 // the set is empty, the rectangle (0,0,0,0) is returned.
103 // Arguments:
104 // pX1,pY1,pX2,pY2 - Pointers for returning the coordinates of
105 // the min/max rectangle.
106
107 void SetToMinMax();
108 // Set this set of clip rectangles to its min/max rectangle.
109
110 void SetToMinMaxOf(const emClipRects & clipRects);
111 // Set this set of clip rectangles to the min/max rectangle of
112 // another set of clip rectangles.
113
114 void Set(NUM x1, NUM y1, NUM x2, NUM y2);
115 // Set this set of clip rectangles to a single rectangle.
116 // Arguments:
117 // x1,y1,x2,y2 - Coordinates of the rectangle.
118
119 void Set(const emClipRects & clipRects);
120 // Set this set of clip rectangles equal to another set of clip
121 // rectangles.
122 // clipRects - The set to be copied.
123
124 void Unite(NUM x1, NUM y1, NUM x2, NUM y2);
125 void Unite(const emClipRects & clipRects);
126 emClipRects & operator += (const emClipRects & clipRects);
127 emClipRects operator + (const emClipRects & clipRects) const;
128 emClipRects & operator |= (const emClipRects & clipRects);
129 emClipRects operator | (const emClipRects & clipRects) const;
130 // Perform the OR operation.
131
132 void Intersect(NUM x1, NUM y1, NUM x2, NUM y2);
133 void Intersect(const emClipRects & clipRects);
134 emClipRects & operator &= (const emClipRects & clipRects);
135 emClipRects operator & (const emClipRects & clipRects) const;
136 // Perform the AND operation.
137
138 void Subtract(NUM x1, NUM y1, NUM x2, NUM y2);
139 void Subtract(const emClipRects & clipRects);
140 emClipRects & operator -= (const emClipRects & clipRects);
141 emClipRects operator - (const emClipRects & clipRects) const;
142 // Perform the AND-NOT operation.
143
144 void Sort();
145 // Sort the list of rectangles primarily by Y1 and secondarily
146 // by X1.
147
148 void Clear();
149 // Empty the set of clip rectangles.
150
151 bool IsEmpty() const;
152 // Ask whether the set of clip rectangles is empty.
153
154 bool IsSubsetOf(NUM x1, NUM y1, NUM x2, NUM y2) const;
155 bool IsSubsetOf(const emClipRects & clipRects) const;
156 // Ask whether the set of clip rectangles is contained in
157 // another rectangle or set.
158
159 bool IsSupersetOf(NUM x1, NUM y1, NUM x2, NUM y2) const;
160 bool IsSupersetOf(const emClipRects & clipRects) const;
161 // Ask whether the set of clip rectangles is containing
162 // another rectangle or set.
163
164 bool operator == (const emClipRects & clipRects) const;
165 bool operator != (const emClipRects & clipRects) const;
166 // Compare sets of clip rectangles.
167
168 unsigned int GetDataRefCount() const;
169 // Get number of references to the data behind this set of clip
170 // rectangles.
171
172 void MakeNonShared();
173 // This must be called before handing the object to another
174 // thread.
175
176 private:
177
178 void PrivUnite(Rect * * list, NUM x1, NUM y1, NUM x2, NUM y2);
179 void DeleteData();
180 Rect * AllocRect();
181 void FreeRect(Rect * rect);
182 void AllocBlock();
183 static int CompareRects(void * r1, void * r2, void * context);
184
185 struct MemBlock {
186 Rect Rects[16];
187 MemBlock * Next;
188 };
189
190 struct SharedData {
191 Rect * List;
192 Rect * FreeList;
193 MemBlock * BlockList;
194 unsigned int Count;
195 unsigned int RefCount;
196 bool IsStaticEmpty;
197 };
198
199 SharedData * Data;
200 static SharedData EmptyData;
201 };
202
203
204 //==============================================================================
205 //============================== Implementations ===============================
206 //==============================================================================
207
208 //--------------------------- Inline implementations ---------------------------
209
emClipRects()210 template <class NUM> inline emClipRects<NUM>::emClipRects()
211 {
212 Data=&EmptyData;
213 }
214
215
216 template <class NUM> inline
emClipRects(const emClipRects & clipRects)217 emClipRects<NUM>::emClipRects(const emClipRects & clipRects)
218 {
219 Data=clipRects.Data;
220 Data->RefCount++;
221 }
222
223
~emClipRects()224 template <class NUM> inline emClipRects<NUM>::~emClipRects()
225 {
226 if (!--Data->RefCount) DeleteData();
227 }
228
229
230 template <class NUM> inline
231 emClipRects<NUM> & emClipRects<NUM>::operator = (const emClipRects & clipRects)
232 {
233 clipRects.Data->RefCount++;
234 if (!--Data->RefCount) DeleteData();
235 Data=clipRects.Data;
236 return *this;
237 }
238
239
GetX1()240 template <class NUM> inline NUM emClipRects<NUM>::Rect::GetX1() const
241 {
242 return X1;
243 }
244
245
GetY1()246 template <class NUM> inline NUM emClipRects<NUM>::Rect::GetY1() const
247 {
248 return Y1;
249 }
250
251
GetX2()252 template <class NUM> inline NUM emClipRects<NUM>::Rect::GetX2() const
253 {
254 return X2;
255 }
256
257
GetY2()258 template <class NUM> inline NUM emClipRects<NUM>::Rect::GetY2() const
259 {
260 return Y2;
261 }
262
263
264 template <class NUM> inline
Get(NUM * pX1,NUM * pY1,NUM * pX2,NUM * pY2)265 void emClipRects<NUM>::Rect::Get(NUM * pX1, NUM * pY1, NUM * pX2, NUM * pY2) const
266 {
267 *pX1=X1;
268 *pY1=Y1;
269 *pX2=X2;
270 *pY2=Y2;
271 }
272
273
274 template <class NUM> inline
GetNext()275 const typename emClipRects<NUM>::Rect * emClipRects<NUM>::Rect::GetNext() const
276 {
277 return Next;
278 }
279
280
281 template <class NUM> inline
GetFirst()282 const typename emClipRects<NUM>::Rect * emClipRects<NUM>::GetFirst() const
283 {
284 return Data->List;
285 }
286
287
GetCount()288 template <class NUM> inline int emClipRects<NUM>::GetCount() const
289 {
290 return Data->Count;
291 }
292
293
SetToMinMax()294 template <class NUM> inline void emClipRects<NUM>::SetToMinMax()
295 {
296 SetToMinMaxOf(*this);
297 }
298
299
300 template <class NUM> inline
Set(const emClipRects & clipRects)301 void emClipRects<NUM>::Set(const emClipRects & clipRects)
302 {
303 clipRects.Data->RefCount++;
304 if (!--Data->RefCount) DeleteData();
305 Data=clipRects.Data;
306 }
307
308
309 template <class NUM> inline
310 emClipRects<NUM> & emClipRects<NUM>::operator += (const emClipRects & clipRects)
311 {
312 Unite(clipRects);
313 return *this;
314 }
315
316
317 template <class NUM> inline
318 emClipRects<NUM> & emClipRects<NUM>::operator |= (const emClipRects & clipRects)
319 {
320 return *this+=clipRects;
321 }
322
323
324 template <class NUM> inline
325 emClipRects<NUM> emClipRects<NUM>::operator | (const emClipRects & clipRects) const
326 {
327 return *this+clipRects;
328 }
329
330
331 template <class NUM> inline
332 emClipRects<NUM> & emClipRects<NUM>::operator &= (const emClipRects & clipRects)
333 {
334 Intersect(clipRects);
335 return *this;
336 }
337
338
339 template <class NUM> inline
340 emClipRects<NUM> & emClipRects<NUM>::operator -= (const emClipRects & clipRects)
341 {
342 Subtract(clipRects);
343 return *this;
344 }
345
346
Clear()347 template <class NUM> inline void emClipRects<NUM>::Clear()
348 {
349 if (!--Data->RefCount) DeleteData();
350 Data=&EmptyData;
351 }
352
353
IsEmpty()354 template <class NUM> inline bool emClipRects<NUM>::IsEmpty() const
355 {
356 return !Data->Count;
357 }
358
359
360 template <class NUM> inline
IsSupersetOf(const emClipRects & clipRects)361 bool emClipRects<NUM>::IsSupersetOf(const emClipRects & clipRects) const
362 {
363 return clipRects.IsSubsetOf(*this);
364 }
365
366
367 template <class NUM> inline
368 bool emClipRects<NUM>::operator != (const emClipRects & clipRects) const
369 {
370 return !(*this == clipRects);
371 }
372
373
GetDataRefCount()374 template <class NUM> inline unsigned int emClipRects<NUM>::GetDataRefCount() const
375 {
376 return Data->IsStaticEmpty ? UINT_MAX/2 : Data->RefCount;
377 }
378
379
380 template <class NUM> inline
AllocRect()381 typename emClipRects<NUM>::Rect * emClipRects<NUM>::AllocRect()
382 {
383 Rect * r;
384
385 r=Data->FreeList;
386 if (!r) {
387 AllocBlock();
388 r=Data->FreeList;
389 }
390 Data->FreeList=r->Next;
391 Data->Count++;
392 return r;
393 }
394
395
FreeRect(Rect * rect)396 template <class NUM> inline void emClipRects<NUM>::FreeRect(Rect * rect)
397 {
398 Data->Count--;
399 rect->Next=Data->FreeList;
400 Data->FreeList=rect;
401 }
402
403
404 //------------------------- Non-inline implementations -------------------------
405
406 template <class NUM>
emClipRects(NUM x1,NUM y1,NUM x2,NUM y2)407 emClipRects<NUM>::emClipRects(NUM x1, NUM y1, NUM x2, NUM y2)
408 {
409 Rect * r;
410
411 Data=new SharedData;
412 Data->List=NULL;
413 Data->FreeList=NULL;
414 Data->BlockList=NULL;
415 Data->Count=0;
416 Data->RefCount=1;
417 Data->IsStaticEmpty=false;
418 r=AllocRect();
419 r->X1=x1;
420 r->Y1=y1;
421 r->X2=x2;
422 r->Y2=y2;
423 r->Next=NULL;
424 Data->List=r;
425 }
426
427
428 template <class NUM>
GetMinMax(NUM * pX1,NUM * pY1,NUM * pX2,NUM * pY2)429 void emClipRects<NUM>::GetMinMax(NUM * pX1, NUM * pY1, NUM * pX2, NUM * pY2) const
430 {
431 NUM x1,y1,x2,y2;
432 Rect * r;
433
434 r=Data->List;
435 if (!r) {
436 x1=0;
437 y1=0;
438 x2=0;
439 y2=0;
440 }
441 else {
442 x1=r->X1;
443 y1=r->Y1;
444 x2=r->X2;
445 y2=r->Y2;
446 for (r=r->Next; r; r=r->Next) {
447 if (x1>r->X1) x1=r->X1;
448 if (y1>r->Y1) y1=r->Y1;
449 if (x2<r->X2) x2=r->X2;
450 if (y2<r->Y2) y2=r->Y2;
451 }
452 }
453 *pX1=x1;
454 *pY1=y1;
455 *pX2=x2;
456 *pY2=y2;
457 }
458
459
460 template <class NUM>
SetToMinMaxOf(const emClipRects & clipRects)461 void emClipRects<NUM>::SetToMinMaxOf(const emClipRects & clipRects)
462 {
463 NUM x1,y1,x2,y2;
464
465 if (clipRects.Data->Count<=1) {
466 clipRects.Data->RefCount++;
467 if (!--Data->RefCount) DeleteData();
468 Data=clipRects.Data;
469 }
470 else {
471 GetMinMax(&x1,&y1,&x2,&y2);
472 Set(x1,y1,x2,y2);
473 }
474 }
475
476
477 template <class NUM>
Set(NUM x1,NUM y1,NUM x2,NUM y2)478 void emClipRects<NUM>::Set(NUM x1, NUM y1, NUM x2, NUM y2)
479 {
480 Rect * r;
481
482 if (!--Data->RefCount) DeleteData();
483 Data=new SharedData;
484 Data->List=NULL;
485 Data->FreeList=NULL;
486 Data->BlockList=NULL;
487 Data->Count=0;
488 Data->RefCount=1;
489 Data->IsStaticEmpty=false;
490 r=AllocRect();
491 r->X1=x1;
492 r->Y1=y1;
493 r->X2=x2;
494 r->Y2=y2;
495 r->Next=NULL;
496 Data->List=r;
497 }
498
499
500 template <class NUM>
Unite(NUM x1,NUM y1,NUM x2,NUM y2)501 void emClipRects<NUM>::Unite(NUM x1, NUM y1, NUM x2, NUM y2)
502 {
503 if (x1>=x2 || y1>=y2) return;
504 MakeNonShared();
505 PrivUnite(&Data->List,x1,y1,x2,y2);
506 }
507
508
509 template <class NUM>
Unite(const emClipRects & clipRects)510 void emClipRects<NUM>::Unite(const emClipRects & clipRects)
511 {
512 const Rect * r;
513
514 if (Data==clipRects.Data || !clipRects.Data) return;
515 MakeNonShared();
516 for (r=clipRects.Data->List; r; r=r->Next) {
517 PrivUnite(&Data->List,r->X1,r->Y1,r->X2,r->Y2);
518 }
519 }
520
521
522 template <class NUM>
523 emClipRects<NUM> emClipRects<NUM>::operator + (const emClipRects & clipRects) const
524 {
525 emClipRects cr(*this);
526 cr.Unite(clipRects);
527 return cr;
528 }
529
530
531 template <class NUM>
Intersect(NUM x1,NUM y1,NUM x2,NUM y2)532 void emClipRects<NUM>::Intersect(NUM x1, NUM y1, NUM x2, NUM y2)
533 {
534 Rect * * pr;
535 Rect * r;
536
537 if (x1>=x2 || y1>=y2) {
538 Clear();
539 return;
540 }
541 MakeNonShared();
542 pr=&Data->List;
543 for (;;) {
544 r=*pr;
545 if (!r) break;
546 if (r->X1<x1) r->X1=x1;
547 if (r->X2>x2) r->X2=x2;
548 if (r->X1<r->X2) {
549 if (r->Y1<y1) r->Y1=y1;
550 if (r->Y2>y2) r->Y2=y2;
551 if (r->Y1<r->Y2) {
552 pr=&r->Next;
553 continue;
554 }
555 }
556 *pr=r->Next;
557 FreeRect(r);
558 }
559 }
560
561
562 template <class NUM>
Intersect(const emClipRects & clipRects)563 void emClipRects<NUM>::Intersect(const emClipRects & clipRects)
564 {
565 Rect * r1, * r2;
566
567 if (Data!=clipRects.Data) {
568 r1=Data->List;
569 if (r1) {
570 r2=clipRects.Data->List;
571 if (!r2) {
572 Clear();
573 }
574 else if (!r2->Next) {
575 Intersect(r2->X1,r2->Y1,r2->X2,r2->Y2);
576 }
577 else if (!r1->Next) {
578 emClipRects cr(clipRects);
579 cr.Intersect(r1->X1,r1->Y1,r1->X2,r1->Y2);
580 Set(cr);
581 }
582 else {
583 emClipRects cr;
584 cr.SetToMinMaxOf(*this);
585 cr.Subtract(clipRects);
586 Subtract(cr);
587 }
588 }
589 }
590 }
591
592
593 template <class NUM>
594 emClipRects<NUM> emClipRects<NUM>::operator & (const emClipRects & clipRects) const
595 {
596 emClipRects cr(*this);
597 cr.Intersect(clipRects);
598 return cr;
599 }
600
601
602 template <class NUM>
Subtract(NUM x1,NUM y1,NUM x2,NUM y2)603 void emClipRects<NUM>::Subtract(NUM x1, NUM y1, NUM x2, NUM y2)
604 {
605 NUM rx1,ry1,rx2,ry2,sy1,sy2;
606 Rect * * pr;
607 Rect * r;
608
609 if (!Data->List || x1>=x2 || y1>=y2) return;
610 MakeNonShared();
611 pr=&Data->List;
612 for (;;) {
613 r=*pr;
614 if (!r) break;
615 if (
616 (rx1=r->X1)<x2 &&
617 (rx2=r->X2)>x1 &&
618 (ry1=r->Y1)<y2 &&
619 (ry2=r->Y2)>y1
620 ) {
621 if (ry2>y2) sy2=y2;
622 else sy2=ry2;
623 if (ry1<y1) {
624 r->Y2=y1;
625 sy1=y1;
626 pr=&r->Next;
627 }
628 else {
629 sy1=ry1;
630 *pr=r->Next;
631 FreeRect(r);
632 }
633 if (rx1<x1) {
634 r=AllocRect();
635 r->X1=rx1;
636 r->Y1=sy1;
637 r->X2=x1;
638 r->Y2=sy2;
639 r->Next=*pr;
640 *pr=r;
641 pr=&r->Next;
642 }
643 if (rx2>x2) {
644 r=AllocRect();
645 r->X1=x2;
646 r->Y1=sy1;
647 r->X2=rx2;
648 r->Y2=sy2;
649 r->Next=*pr;
650 *pr=r;
651 pr=&r->Next;
652 }
653 if (ry2>y2) {
654 r=AllocRect();
655 r->X1=rx1;
656 r->Y1=y2;
657 r->X2=rx2;
658 r->Y2=ry2;
659 r->Next=*pr;
660 *pr=r;
661 pr=&r->Next;
662 }
663 }
664 else {
665 pr=&r->Next;
666 }
667 }
668 }
669
670
671 template <class NUM>
Subtract(const emClipRects & clipRects)672 void emClipRects<NUM>::Subtract(const emClipRects & clipRects)
673 {
674 const Rect * r;
675
676 if (Data==clipRects.Data) {
677 Clear();
678 return;
679 }
680 for (r=clipRects.Data->List; r; r=r->Next) {
681 if (!Data->List) break;
682 Subtract(r->X1,r->Y1,r->X2,r->Y2);
683 }
684 }
685
686
687 template <class NUM>
688 emClipRects<NUM> emClipRects<NUM>::operator - (const emClipRects & clipRects) const
689 {
690 emClipRects cr(*this);
691 cr.Subtract(clipRects);
692 return cr;
693 }
694
695
Sort()696 template <class NUM> void emClipRects<NUM>::Sort()
697 {
698 if (Data->Count>1) {
699 MakeNonShared();
700 emSortSingleLinkedList(
701 (void**)&Data->List,
702 offsetof(Rect,Next),
703 CompareRects,
704 NULL
705 );
706 }
707 }
708
709
710 template <class NUM>
IsSubsetOf(NUM x1,NUM y1,NUM x2,NUM y2)711 bool emClipRects<NUM>::IsSubsetOf(NUM x1, NUM y1, NUM x2, NUM y2) const
712 {
713 Rect * r;
714
715 for (r=Data->List; r; r=r->Next) {
716 if (r->X1<x1 || r->Y1<y1 || r->X2>x2 || r->Y2>y2) return false;
717 }
718 return true;
719 }
720
721
722 template <class NUM>
IsSubsetOf(const emClipRects & clipRects)723 bool emClipRects<NUM>::IsSubsetOf(const emClipRects & clipRects) const
724 {
725 Rect * r;
726
727 if (Data==clipRects.Data) return true;
728 if (!Data->List) return true;
729 r=clipRects.Data->List;
730 if (!r) return false;
731 if (!r->Next) return IsSubsetOf(r->X1,r->Y1,r->X2,r->Y2);
732 return (*this - clipRects).IsEmpty();
733 }
734
735
736 template <class NUM>
IsSupersetOf(NUM x1,NUM y1,NUM x2,NUM y2)737 bool emClipRects<NUM>::IsSupersetOf(NUM x1, NUM y1, NUM x2, NUM y2) const
738 {
739 return emClipRects(x1,y1,x2,y2).IsSubsetOf(*this);
740 }
741
742
743 template <class NUM>
744 bool emClipRects<NUM>::operator == (const emClipRects & clipRects) const
745 {
746 if (Data==clipRects.Data) return true;
747 return IsSubsetOf(clipRects) && clipRects.IsSubsetOf(*this);
748 }
749
750
MakeNonShared()751 template <class NUM> void emClipRects<NUM>::MakeNonShared()
752 {
753 SharedData * d1, * d2;
754 Rect * r1, *r2;
755 Rect * * pr;
756
757 d1=Data;
758 if (d1->RefCount>1 || d1->IsStaticEmpty) {
759 d2=new SharedData;
760 d2->List=NULL;
761 d2->FreeList=NULL;
762 d2->BlockList=NULL;
763 d2->Count=0;
764 d2->RefCount=1;
765 d2->IsStaticEmpty=false;
766 d1->RefCount--;
767 Data=d2;
768 r1=d1->List;
769 if (r1) {
770 pr=&d2->List;
771 do {
772 r2=AllocRect();
773 r2->X1=r1->X1;
774 r2->Y1=r1->Y1;
775 r2->X2=r1->X2;
776 r2->Y2=r1->Y2;
777 *pr=r2;
778 pr=&r2->Next;
779 r1=r1->Next;
780 } while (r1);
781 *pr=NULL;
782 }
783 }
784 }
785
786
787 template <class NUM>
PrivUnite(Rect ** list,NUM x1,NUM y1,NUM x2,NUM y2)788 void emClipRects<NUM>::PrivUnite(Rect * * list, NUM x1, NUM y1, NUM x2, NUM y2)
789 {
790 NUM rx1,ry1,rx2,ry2;
791 Rect * r;
792
793 for (;;) {
794 r=*list;
795 if (!r) break;
796 if (
797 (ry1=r->Y1)>y2 || (ry2=r->Y2)<y1 ||
798 (rx1=r->X1)>x2 || (rx2=r->X2)<x1
799 ) {
800 list=&r->Next;
801 }
802 else if (rx1<=x1 && rx2>=x2 && ry1<=y1 && ry2>=y2) {
803 return;
804 }
805 else if (rx1>=x1 && rx2<=x2 && ry1>=y1 && ry2<=y2) {
806 *list=r->Next;
807 FreeRect(r);
808 }
809 else if (rx1==x1 && rx2==x2) {
810 if (y1>ry1) y1=ry1;
811 if (y2<ry2) y2=ry2;
812 *list=r->Next;
813 FreeRect(r);
814 }
815 else if (ry1<y2 && ry2>y1) {
816 if (ry2>y2) {
817 r->Y1=y2;
818 if (ry1<y1) {
819 r=AllocRect();
820 r->X1=rx1;
821 r->Y1=ry1;
822 r->X2=rx2;
823 r->Y2=y1;
824 r->Next=*list;
825 *list=r;
826 }
827 }
828 else if (ry1<y1) {
829 r->Y2=y1;
830 }
831 else {
832 *list=r->Next;
833 FreeRect(r);
834 }
835 if (y1<ry1) {
836 PrivUnite(list,x1,y1,x2,ry1);
837 y1=ry1;
838 }
839 if (y2>ry2) {
840 PrivUnite(list,x1,ry2,x2,y2);
841 y2=ry2;
842 }
843 if (x1>rx1) x1=rx1;
844 if (x2<rx2) x2=rx2;
845 }
846 else {
847 list=&r->Next;
848 }
849 }
850 r=AllocRect();
851 r->X1=x1;
852 r->Y1=y1;
853 r->X2=x2;
854 r->Y2=y2;
855 r->Next=NULL;
856 *list=r;
857 }
858
859
DeleteData()860 template <class NUM> void emClipRects<NUM>::DeleteData()
861 {
862 MemBlock * b;
863
864 EmptyData.RefCount=UINT_MAX/2;
865
866 // Never do a
867 // if (Data!=&EmptyData)...
868 // instead of
869 // if (!Data->IsStaticEmpty)...
870 // because static member variables of template classes could exist
871 // multiple times for the same final type (e.g. with Windows DLLs).
872 if (!Data->IsStaticEmpty) {
873 while ((b=Data->BlockList)!=NULL) {
874 Data->BlockList=b->Next;
875 delete b;
876 }
877 delete Data;
878 }
879 }
880
881
AllocBlock()882 template <class NUM> void emClipRects<NUM>::AllocBlock()
883 {
884 MemBlock * b;
885 Rect * r, * e;
886 int n;
887
888 b=new MemBlock;
889 b->Next=Data->BlockList;
890 Data->BlockList=b;
891 n=sizeof(b->Rects)/sizeof(Rect);
892 e=b->Rects+n-1;
893 for (r=b->Rects; r<e; r++) r->Next=r+1;
894 e->Next=Data->FreeList;
895 Data->FreeList=b->Rects;
896 }
897
898
899 template <class NUM>
CompareRects(void * r1,void * r2,void * context)900 int emClipRects<NUM>::CompareRects(void * r1, void * r2, void * context)
901 {
902 if (((const Rect*)r1)->Y1<((const Rect*)r2)->Y1) return -1;
903 if (((const Rect*)r1)->Y1>((const Rect*)r2)->Y1) return 1;
904 if (((const Rect*)r1)->X1<((const Rect*)r2)->X1) return -1;
905 if (((const Rect*)r1)->X1>((const Rect*)r2)->X1) return 1;
906 return 0;
907 }
908
909
910 template <class NUM>
911 typename emClipRects<NUM>::SharedData emClipRects<NUM>::EmptyData=
912 {
913 NULL,NULL,NULL,0,UINT_MAX/2,true
914 };
915
916
917 #endif
918