Java > Open Source Codes > org > apache > batik > ext > awt > geom > RectListManager


1 /*
2
3    Copyright 2002-2003 The Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16
17  */
18 package org.apache.batik.ext.awt.geom;
19
20 import java.awt.Rectangle ;
21 import java.io.Serializable ;
22 import java.util.Arrays ;
23 import java.util.Collection ;
24 import java.util.List ;
25 import java.util.Comparator ;
26 import java.util.Iterator ;
27 import java.util.ListIterator ;
28 import java.util.NoSuchElementException ;
29
30 /**
31  * RectListManager is a class to manage a list of rectangular regions.
32  * This class contains methods to add new rectangles to the List, to
33  * merge rectangles in the list (based on a cost function), and
34  * functions to subract one RectListManager from another. The main
35  * purpose of this class is to manage dirty regions on a display (for
36  * this reason it uses Rectangle not Rectangle2D).
37  *
38  * @author <a HREF="mailto:deweese@apache.org">Thomas DeWeese</a>
39  * @version $Id: RectListManager.java,v 1.9 2004/08/18 07:13:47 vhardy Exp $ */
40
41 public class RectListManager implements Collection {
42     Rectangle [] rects = null;
43     int size = 0;
44
45     Rectangle bounds = null;
46
47     /**
48      * The comparator used to sort the elements of this List.
49      * Sorts on x value of Rectangle.
50      */
51     public static Comparator comparator = new RectXComparator();
52
53     /**
54      * Construct a <tt>RectListManager</tt> from a Collection of Rectangles
55      * @param rects Collection that must only contain rectangles.
56      */
57     public RectListManager(Collection rects) {
58         this.rects = new Rectangle [rects.size()];
59         Iterator i = rects.iterator();
60         int j=0;
61         while (i.hasNext())
62             this.rects[j++] = (Rectangle )i.next();
63         this.size = this.rects.length;
64
65         Arrays.sort(this.rects, comparator);
66     }
67
68     /**
69      * Construct a <tt>RectListManager</tt> from an Array of
70      * <tt>Rectangles</tt>
71      * @param rects Array of <tt>Rectangles</tt>, must not contain
72      * any null entries.
73      */
74     public RectListManager(Rectangle [] rects) {
75         this(rects, 0, rects.length);
76     }
77
78     /**
79      * Construct a <tt>RectListManager</tt> from an Array of
80      * <tt>Rectangles</tt>
81      * @param rects Array of <tt>Rectangles</tt>, must not contain
82      * any null entries in the range [off, off+sz-1].
83      * @param off The offset to start copying from in rects.
84      * @param sz The number of entries to copy from rects.
85      */
86     public RectListManager(Rectangle [] rects, int off, int sz) {
87         this.size = sz;
88         this.rects = new Rectangle [sz];
89         System.arraycopy(rects, off, this.rects, 0, sz);
90         Arrays.sort(this.rects, comparator);
91     }
92
93     /**
94      * Construct a <tt>RectListManager</tt> from another
95      * <tt>RectListManager</tt> (data is copied).
96      * @param rlm RectListManager to copy.
97      */
98     public RectListManager(RectListManager rlm) {
99         this(rlm.rects);
100     }
101
102     /**
103      * Construct a <tt>RectListManager</tt> with one rectangle
104      * @param rect The rectangle to put in this rlm.
105      */
106     public RectListManager(Rectangle rect) {
107         this();
108         add(rect);
109     }
110
111     
112     /**
113      * Construct an initially empty <tt>RectListManager</tt>.
114      */
115     public RectListManager() {
116         this.rects = new Rectangle [10];
117         size = 0;
118     }
119
120     /**
121      * Construct an initially empty <tt>RectListManager</tt>,
122      * with initial <tt>capacity</tt>.
123      * @param capacity The inital capacity for the list. Setting
124      * this appropriately can save reallocations.
125      */
126     public RectListManager(int capacity) {
127         this.rects = new Rectangle [capacity];
128     }
129
130     public Rectangle getBounds() {
131         if (bounds != null )
132             return bounds;
133         if (size == 0) return null;
134         bounds = new Rectangle (rects[0]);
135         for (int i=1; i< size; i++) {
136             Rectangle r = rects[i];
137             if (r.x < bounds.x) {
138                 bounds.width = bounds.x+bounds.width-r.x;
139                 bounds.x = r.x;
140             }
141             if (r.y < bounds.y) {
142                 bounds.height = bounds.y+bounds.height-r.y;
143                 bounds.y = r.y;
144             }
145             if (r.x+r.width > bounds.x+bounds.width)
146                 bounds.width = r.x+r.width-bounds.x;
147             if (r.y+r.height > bounds.y+bounds.height)
148                 bounds.height = r.y+r.height-bounds.y;
149         }
150         return bounds;
151     }
152
153     /**
154      * Standard <tt>Object</tt> clone method.
155      */
156     public Object clone() {
157         return copy();
158     }
159
160     /**
161      * Similar to clone only strongly typed
162      */
163     public RectListManager copy() {
164         return new RectListManager(rects);
165     }
166
167     /**
168      * Returns the number of elements currently stored in this collection.
169      */
170     public int size() { return size; }
171
172
173     /**
174      * Returns true if this collection contains no elements.
175      */
176     public boolean isEmpty() { return (size==0); }
177     
178     public void clear() {
179         for (int i=0; i<size; i++)
180             rects[i] = null;
181         size=0;
182     }
183
184     /**
185      * Returns an iterator over the elements in this collection
186      */
187     public Iterator iterator() {
188         return new RLMIterator();
189     }
190
191     /**
192      * Returns a list iterator of the elements in this list
193      * (in proper sequence).
194      */
195     public ListIterator listIterator() {
196         return new RLMIterator();
197     }
198
199     public Object [] toArray() {
200         Object [] ret = new Rectangle [size];
201         System.arraycopy(rects, 0, ret, 0, size);
202         return ret;
203     }
204
205     public Object [] toArray(Object []a) {
206         Class t = a.getClass().getComponentType();
207         if ((t != Object .class) &
208             (t != Rectangle .class)) {
209             // Nothing here for it...
210 for (int i=0; i<a.length; i++)
211                 a[i] = null;
212             return a;
213         }
214         
215         if (a.length < size)
216             a = new Rectangle [size];
217         System.arraycopy(rects, 0, a, 0, size);
218         for (int i=size; i<a.length; i++)
219             a[i] = null;
220
221         return a;
222     }
223
224     public boolean add(Object o) {
225         add((Rectangle )o);
226         return true;
227     }
228
229     /**
230      * Ensures that this collection contains the specified element
231      * @param rect The rectangle to add
232      */
233     public void add(Rectangle rect) {
234         add(rect, 0, size-1);
235     }
236
237     /**
238      * Ensures that this collection contains the specified element
239      * l is the lower bound index for insertion r is upper
240      * bound index for insertion.
241      * @param rect The rectangle to add
242      * @param l the lowest possible index for a rect with
243      * greater 'x' coord.
244      * @param r the highest possible index for a rect with
245      * greater 'x' coord.
246      */
247     protected void add(Rectangle rect, int l, int r) {
248         ensureCapacity(size+1);
249         int idx=l;
250         while (l <= r) {
251             idx = (l+r)/2;
252             while ((rects[idx] == null) && (idx <r)) idx++;
253             if (rects[idx] == null) {
254                 // All 'null' from center to r so skip them
255 r = (l+r)/2;
256                 idx = (l+r)/2;
257                 if (l>r)
258                     idx=l;
259                 while ((rects[idx] == null) && (idx > l)) idx--;
260                 if (rects[idx] == null) {
261                     rects[idx] = rect;
262                     return;
263                 }
264             }
265             if (rect.x == rects[idx].x) break;
266             if (rect.x < rects[idx].x) {
267                 if (idx == 0) break;
268                 if ((rects[idx-1] != null) &&
269                     (rect.x >= rects[idx-1].x)) break;
270                 r = idx-1;
271             } else {
272                 if (idx == size-1) {idx++; break; }
273                 if ((rects[idx+1] != null) &&
274                     (rect.x <= rects[idx+1].x)) { idx++; break;}
275                 l = idx+1;
276             }
277         }
278
279         if (idx < size) {
280             System.arraycopy(rects, idx,
281                              rects, idx+1, size-idx);
282         }
283
284         // if (idx!=0) System.out.print(rects[idx-1].x);
285 // else System.out.print("[First]");
286 // System.out.print(" " + rect.x + " ");
287 // if (idx<size) System.out.print(rects[idx+1].x);
288 // else System.out.print("[last]");
289 // System.out.println("");
290
291         rects[idx] = rect;
292         size++;
293     }
294
295     public boolean addAll(Collection c) {
296         if (c instanceof RectListManager) {
297             add((RectListManager)c);
298         } else {
299             add(new RectListManager(c));
300         }
301
302         return (c.size() != 0);
303     }
304
305     public boolean contains(Object o) {
306         Rectangle rect = (Rectangle )o;
307         int l=0, r=size-1, idx=0;
308         while (l <= r) {
309             idx = (l+r)/2;
310             if (rect.x == rects[idx].x) break;
311             if (rect.x < rects[idx].x) {
312                 if (idx == 0) break;
313                 if (rect.x >= rects[idx-1].x) break;
314                 r = idx-1;
315             } else {
316                 if (idx == size-1) {idx++; break; }
317                 if (rect.x <= rects[idx+1].x) { idx++; break;}
318                 l = idx+1;
319             }
320         }
321         // Didn't find any rect with the same x value.
322 if (rects[idx].x != rect.x) return false;
323
324         // Search towards 0 from idx for rect that matches
325 for (int i=idx; i>=0; i--){
326             if (rects[idx].equals(rect)) return true;
327             if (rects[idx].x != rect.x) break;
328         }
329
330         // Search towards size from idx for rect that matches
331 for (int i=idx+1; i<size; i++) {
332             if (rects[idx].equals(rect)) return true;
333             if (rects[idx].x != rect.x) break;
334         }
335
336         // No match...
337 return false;
338     }
339
340     /**
341      * Returns true if this collection contains all of the elements in
342      * the specified collection.
343      */
344     public boolean containsAll(Collection c) {
345         if (c instanceof RectListManager)
346             return containsAll((RectListManager)c);
347         return containsAll(new RectListManager(c));
348     }
349
350     public boolean containsAll(RectListManager rlm) {
351         int x, xChange = 0;
352         for (int j=0, i=0; j<rlm.size; j++) {
353             i=xChange;
354             while(rects[i].x < rlm.rects[j].x) {
355                 i++;
356                 if (i == size) return false;
357             }
358             xChange = i;
359             x = rects[i].x;
360             while (!rlm.rects[j].equals(rects[i])) {
361                 i++;
362                 if (i == size) return false; // out of rects
363 if (x != rects[i].x)
364                     return false; // out of the zone.
365 }
366         }
367         return true;
368     }
369
370     /**
371      * Removes a single instance of the specified element from this
372      * collection, if it is present.
373      * @param o Object to remove an matching instance of.
374      */
375     public boolean remove(Object o) {
376         return remove((Rectangle )o);
377     }
378
379     /**
380      * Removes a single instance of the specified Rectangle from this
381      * collection, if it is present.
382      * @param rect Rectangle to remove an matching instance of.
383      */
384     public boolean remove(Rectangle rect) {
385         int l=0, r=size-1, idx=0;
386         while (l <= r) {
387             idx = (l+r)/2;
388             if (rect.x == rects[idx].x) break;
389             if (rect.x < rects[idx].x) {
390                 if (idx == 0) break;
391                 if (rect.x >= rects[idx-1].x) break;
392                 r = idx-1;
393             } else {
394                 if (idx == size-1) {idx++; break; }
395                 if (rect.x <= rects[idx+1].x) { idx++; break;}
396                 l = idx+1;
397             }
398         }
399         // Didn't find any rect with the same x value.
400 if (rects[idx].x != rect.x) return false;
401
402         // Search towards 0 from idx for rect that matches
403 for (int i=idx; i>=0; i--){
404             if (rects[idx].equals(rect)) {
405                 System.arraycopy(rects, idx+1, rects, idx, size-idx);
406                 size--;
407                 return true;
408             }
409             if (rects[idx].x != rect.x) break;
410         }
411
412         // Search towards size from idx for rect that matches
413 for (int i=idx+1; i<size; i++) {
414             if (rects[idx].equals(rect)) {
415                 System.arraycopy(rects, idx+1, rects, idx, size-idx);
416                 size--;
417                 return true;
418             }
419             if (rects[idx].x != rect.x) break;
420         }
421
422         // No match...
423 return false;
424     }
425
426     public boolean removeAll(Collection c) {
427         if (c instanceof RectListManager)
428             return removeAll((RectListManager)c);
429         return removeAll(new RectListManager(c));
430     }
431
432     public boolean removeAll(RectListManager rlm) {
433         int x, xChange = 0;
434         boolean ret = false;
435         for (int j=0, i=0; j<rlm.size; j++) {
436             i=xChange;
437             while ((rects[i] == null) ||
438                    (rects[i].x < rlm.rects[j].x)) {
439                 i++;
440                 if (i == size) break;
441             }
442
443             if (i == size) break;
444
445             xChange = i;
446             x = rects[i].x;
447             while (true) {
448                 if (rects[i] == null) {
449                     i++;
450                     if (i == size) break; // out of rects
451 continue;
452                 }
453                 if (rlm.rects[j].equals(rects[i])) {
454                     rects[i] = null;
455                     ret = true;
456                 }
457                 i++;
458                 if (i == size) break; // out of rects
459 if (x != rects[i].x) break; // out of the zone.
460 }
461         }
462
463         // Now we will go through collapsing the nulled entries.
464 if (ret) {
465             int j=0, i=0;
466             while (i<size) {
467                 if (rects[i] != null)
468                     rects[j++] = rects[i];
469                 i++;
470             }
471             size = j;
472         }
473         return ret;
474     }
475
476     public boolean retainAll(Collection c) {
477         if (c instanceof RectListManager)
478             return retainAll((RectListManager)c);
479         return retainAll(new RectListManager(c));
480     }
481     public boolean retainAll(RectListManager rlm) {
482         int x, xChange = 0;
483         boolean ret = false;
484
485         for (int j=0, i=0; j<size; j++) {
486             i=xChange;
487             while (rlm.rects[i].x < rects[j].x) {
488                 i++;
489                 if (i == rlm.size) break;
490             }
491             if (i == rlm.size) {
492                 ret = true;
493                 // No more rects will match anything from rlm
494 // so remove them from this RLM.
495 for (int k=j; k<size; k++)
496                     rects[k] = null;
497                 size = j;
498                 break;
499             }
500
501             xChange = i;
502             x = rlm.rects[i].x;
503             while (true) {
504                 if (rects[j].equals(rlm.rects[i])) break;
505                 i++;
506                 if ((i == rlm.size) ||
507                     (x != rlm.rects[i].x)) {
508                     // Out of zone or rects
509 rects[j] = null;
510                     ret = true;
511                     break;
512                 }
513             }
514         }
515
516         // Now we will go through collapsing the nulled entries.
517 if (ret) {
518             int j=0, i=0;
519             while (i<size) {
520                 if (rects[i] != null)
521                     rects[j++] = rects[i];
522                 i++;
523             }
524             size = j;
525         }
526         return ret;
527     }
528
529     /**
530      * Adds the contents of <tt>rlm</tt> to this RectListManager. No
531      * collapsing of rectangles is done here the contents are simply
532      * added (you should generally call 'mergeRects' some time after
533      * this operation before using the contents of this
534      * RectListManager.
535      * @param rlm The RectListManager to add the contents of. */
536     public void add(RectListManager rlm) {
537         if (rlm.size == 0)
538             return;
539
540         Rectangle [] dst = rects;
541         if (rects.length < (size+rlm.size)) {
542             dst = new Rectangle [size+rlm.size];
543         }
544         
545         if (size == 0) {
546             System.arraycopy(rlm.rects, 0, dst, size, rlm.size);
547             size = rlm.size;
548             return;
549         }
550         
551         Rectangle [] src1 = rlm.rects;
552         int src1Sz = rlm.size;
553         int src1I = src1Sz-1;
554
555         Rectangle [] src2 = rects;
556         int src2Sz = size;
557         int src2I = src2Sz-1;
558
559         int dstI = size+rlm.size-1;
560         int x1 = src1[src1I].x;
561         int x2 = src2[src2I].x;
562         
563         while (dstI >= 0) {
564             if (x1 <= x2) {
565                 dst[dstI] = src2[src2I];
566                 if (src2I == 0) {
567                     System.arraycopy(src1, 0, dst, 0, src1I+1);
568                     break;
569                 }
570                 src2I--;
571                 x2 = src2[src2I].x;
572             } else {
573                 dst[dstI] = src1[src1I];
574                 if (src1I == 0) {
575                     System.arraycopy(src2, 0, dst, 0, src2I+1);
576                     break;
577                 }
578                 src1I--;
579                 x1 = src1[src1I].x;
580             }
581             dstI--;
582         }
583         rects = dst;
584         size += rlm.size;
585     }
586
587     public void mergeRects(int overhead, int lineOverhead) {
588         if (size == 0) return;
589         Rectangle r, cr, mr;
590         int cost1, cost2, cost3;
591         mr = new Rectangle ();
592         Rectangle []splits = new Rectangle [4];
593         for (int j, i=0; i<size; i++) {
594             r = rects[i];
595             if (r == null) continue;
596             cost1 = (overhead +
597                      (r.height*lineOverhead) +
598                      (r.height*r.width));
599             do {
600                 int maxX = r.x+r.width+overhead/r.height;
601                 for (j=i+1; j<size; j++) {
602                     cr = rects[j];
603                     if ((cr == null) || (cr == r)) continue;
604                     if (cr.x >= maxX) {
605                         // No more merges can happen.
606 j = size;
607                         break;
608                     }
609                     cost2 = (overhead +
610                              (cr.height*lineOverhead) +
611                              (cr.height*cr.width));
612
613                     mr = r.union(cr);
614                     cost3 = (overhead +
615                              (mr.height*lineOverhead) +
616                              (mr.height*mr.width));
617                     if (cost3 <= cost1+cost2) {
618                         r = rects[i] = mr;
619                         rects[j] = null;
620                         cost1 = cost3;
621                         j=-1;
622                         break;
623                     }
624
625                     if (!r.intersects(cr)) continue;
626
627                     splitRect(cr, r, splits);
628                     int splitCost=0;
629                     int l=0;
630                     for (int k=0; k<4; k++) {
631                         if (splits[k] != null) {
632                             Rectangle sr = splits[k];
633                             // Collapse null entries in first three
634 // (That share common 'x').
635 if (k<3) splits[l++] = sr;
636                             splitCost += (overhead +
637                                           (sr.height*lineOverhead) +
638                                           (sr.height*sr.width));
639                         }
640                     }
641                     if (splitCost >= cost2) continue;
642
643                     // Insert the splits.
644 if (l == 0) {
645                         // only third split may be left (no common 'x').
646 rects[j] = null;
647                         if (splits[3] != null)
648                             add(splits[3], j, size-1);
649                         continue;
650                     }
651
652                     rects[j] = splits[0];
653                     if (l > 1)
654                         insertRects(splits, 1, j+1, l-1);
655                     if (splits[3] != null)
656                         add(splits[3], j, size-1);
657                 }
658
659                 // if we merged it with another rect then
660 // we need to check all the rects up to i again,
661 // against the merged rect.
662 } while (j != size);
663         }
664
665         // Now we will go through collapsing the nulled entries.
666 int j=0, i=0;
667         float area=0;
668         while (i<size) {
669             if (rects[i] != null) {
670                 r = rects[i];
671                 rects[j++] = r;
672                 area += overhead + (r.height*lineOverhead) +
673                     (r.height*r.width);
674             }
675             i++;
676         }
677         size = j;
678         r = getBounds();
679         if (r == null) return;
680         if (overhead + (r.height*lineOverhead) + (r.height*r.width) < area) {
681             rects[0] = r;
682             size=1;
683         }
684     }
685
686     public void subtract(RectListManager rlm, int overhead, int lineOverhead) {
687         Rectangle r, sr;
688         int cost;
689         int jMin=0;
690         Rectangle [] splits = new Rectangle [4];
691
692         for(int i=0; i<size; i++) {
693             r = rects[i]; // Canidate rect...
694 cost = (overhead +
695                     (r.height*lineOverhead) +
696                     (r.height*r.width));
697             for (int j=jMin; j<rlm.size; j++) {
698                 sr = rlm.rects[j]; // subtraction rect.
699
700                 // Check if the canidate rect starts after
701 // the end of this rect in 'x' if so
702 // go to the next one.
703 if (sr.x+sr.width < r.x) {
704                     // If this was jMin then increment jMin (no
705 // future canidate rect will intersect this rect).
706 if (j == jMin) jMin++;
707                     continue;
708                 }
709
710                 // Check if the rest of the rects from rlm are past
711 // the end of the canidate rect. If so we are
712 // done with this canidate rect.
713 if (sr.x > r.x+r.width)
714                     break;
715
716                 // If they don't insersect then go to next sub rect.
717 if (!r.intersects(sr))
718                     continue;
719
720                 // Now we know they intersect one another lets
721 // figure out how...
722
723                 splitRect(r, sr, splits);
724
725                 int splitCost=0;
726                 Rectangle tmpR;
727                 for (int k=0; k<4; k++) {
728                     tmpR = splits[k];
729                     if (tmpR != null)
730                         splitCost += (overhead +
731                                       (tmpR.height*lineOverhead) +
732                                       (tmpR.height*tmpR.width));
733                 }
734
735                 if (splitCost >= cost)
736                     // This isn't ideal as depending on the order
737 // Stuff is done in we might later kill some of
738 // these rectangles (hence lowering the cost).
739 // For this reason it is probably best of the
740 // subtract list has been merged as this will help
741 // reduce the instances where this will happen.
742 continue;
743                 
744                 // Collapse null entries in first three elements
745 // split 0, 1, 2 (entries that share a common 'x').
746 int l = 0;
747                 for (int k=0; k<3; k++) {
748                     if (splits[k] != null)
749                         splits[l++] = splits[k];
750                 }
751
752                 // Fully covered (or only split 3 survived which we
753 // will visit later) this canidate rect goes away.
754 if (l==0) {
755                     rects[i].width = 0;
756                     // Insert the third split (if any) at the
757 // proper place in rects list.
758 if (splits[3] != null)
759                         add(splits[3], i, size-1);
760                     break;
761                 }
762
763                 // Otherwise replace the canidate with the top of
764 // the split, since it only shrunk it didn't grow,
765 // we know that the previous subtract rects don't
766 // intersect it.
767 r = splits[0];
768                 rects[i] = r;
769                 cost = (overhead +
770                         (r.height*lineOverhead) +
771                         (r.height*r.width));
772
773                 // Add the remainder of the rects that
774 // share 'r.x' (if any). Possible
775 // are split 1, and split 2.
776 if (l > 1)
777                     insertRects(splits, 1, i+1, l-1);
778
779                 // Insert the third split (if any) at the
780 // proper place in rects list.
781 if (splits[3] != null)
782                     add(splits[3], i+l, size-1);
783             }
784         }
785
786         // Now we will go through collapsing the nulled entries.
787 int j=0, i=0;
788         while (i<size) {
789             if (rects[i].width == 0)
790                 rects[i] = null;
791             else
792                 rects[j++] = rects[i];
793             i++;
794         }
795         size = j;
796     }
797
798     protected void splitRect(Rectangle r, Rectangle sr,
799                              Rectangle []splits) {
800         // We split the canidate rectrect into four parts. In
801 // many cases one or more of these will be empty.
802 //
803 // +-------------------------------------+ ry0
804 // | |
805 // | |
806 // | Split 0 |
807 // | |
808 // | |
809 // ------------+-----------------+--------------- sry0
810 // | | | |
811 // | Split2 | subtracted | Split 3 |
812 // | | rect | |
813 // | | | |
814 // ------------+-----------------+--------------- sry1
815 // | srx0 srx1 |
816 // | |
817 // | Split 1 |
818 // | |
819 // +-------------------------------------+ ry1
820 // rx0 rx1
821
822         int rx0 = r.x;
823         int rx1 = rx0+r.width-1;
824         int ry0 = r.y;
825         int ry1 = ry0+r.height-1;
826
827         int srx0 = sr.x;
828         int srx1 = srx0+sr.width-1;
829         int sry0 = sr.y;
830         int sry1 = sry0+sr.height-1;
831
832         if ((ry0 < sry0) && (ry1 >= sry0)) {
833             splits[0] = new Rectangle (rx0, ry0, r.width, sry0-ry0);
834             ry0 = sry0;
835         } else {
836             splits[0] = null;
837         }
838
839         if ((ry0 <= sry1) && (ry1 > sry1)) {
840             splits[1] = new Rectangle (rx0, sry1+1, r.width, ry1-sry1);
841             ry1 = sry1;
842         } else {
843             splits[1] = null;
844         }
845                 
846         if ((rx0 < srx0) && (rx1 >= srx0)) {
847             splits[2] = new Rectangle (rx0, ry0, srx0-rx0, ry1-ry0+1);
848         } else {
849             splits[2] = null;
850         }
851                 
852         if ((rx0 <= srx1) && (rx1 > srx1)) {
853             splits[3]= new Rectangle (srx1+1, ry0, rx1-srx1, ry1-ry0+1);
854         } else {
855             splits[3] = null;
856         }
857     }
858
859     protected void insertRects(Rectangle [] rects, int srcPos,
860                                int dstPos, int len) {
861         if (len == 0) return;
862
863         // Make sure we have room.
864 ensureCapacity(size+len);
865
866         // Move everything after pos up...
867 for (int i=size-1; i>=dstPos; i--)
868             this.rects[i+len] = this.rects[i];
869
870         // Put the new rects in.
871 for (int i=0; i<len; i++)
872             this.rects[i+dstPos] = rects[i+srcPos];
873
874         size += len;
875     }
876
877     public void ensureCapacity(int sz) {
878         if (sz <= rects.length)
879             return;
880         int nSz = rects.length + (rects.length>>1) + 1;
881         while (nSz < sz)
882             nSz+=(nSz>>1)+1;
883         
884         Rectangle [] nRects = new Rectangle [nSz];
885         System.arraycopy(rects, 0, nRects, 0, size);
886
887         rects = nRects;
888     }
889
890     /**
891      * Comparator for ordering rects in X.
892      *
893      * Note: this comparator imposes orderings that are inconsistent
894      * with equals.
895      */
896     private static class RectXComparator implements Comparator , Serializable {
897
898         RectXComparator() { }
899
900         public final int compare(Object o1, Object o2) {
901             return ((Rectangle )o1).x-((Rectangle )o2).x;
902         }
903     }
904
905
906     private class RLMIterator implements ListIterator {
907         int idx = 0;
908         boolean removeOk = false;
909         boolean forward = true;
910         RLMIterator() { }
911
912         public boolean hasNext() { return idx < size; }
913         public int nextIndex() { return idx; }
914         public Object next() {
915             if (idx >= size)
916                 throw new NoSuchElementException ("No Next Element");
917             forward = true;
918             removeOk = true;
919             return rects[idx++];
920         }
921
922         public boolean hasPrevious() { return idx > 0; }
923         public int previousIndex() { return idx-1; }
924         public Object previous() {
925             if (idx <= 0)
926                 throw new NoSuchElementException ("No Previous Element");
927             forward = false;
928             removeOk = true;
929             return rects[--idx];
930         }
931             
932         public void remove() {
933             if (!removeOk)
934                 throw new IllegalStateException
935                     ("remove can only be called directly after next/previous");
936
937             if (forward) idx--;
938             if (idx != size-1)
939                 System.arraycopy(rects, idx+1, rects, idx, size-(idx+1));
940             size--;
941             rects[size] = null;
942             removeOk = false;
943         }
944
945
946         public void set(Object o) {
947             Rectangle r = (Rectangle )o;
948
949             if (!removeOk)
950                 throw new IllegalStateException
951                     ("set can only be called directly after next/previous");
952
953             if (forward) idx--;
954
955             if (idx+1<size) {
956                 if (rects[idx+1].x < r.x)
957                     throw new UnsupportedOperationException
958                         ("RectListManager entries must be sorted");
959             }
960             if (idx>=0) {
961                 if (rects[idx-1].x > r.x)
962                     throw new UnsupportedOperationException
963                         ("RectListManager entries must be sorted");
964             }
965
966             rects[idx] = r;
967             removeOk = false;
968         }
969
970         public void add(Object o) {
971             Rectangle r = (Rectangle )o;
972             if (idx<size) {
973                 if (rects[idx].x < r.x)
974                     throw new UnsupportedOperationException
975                         ("RectListManager entries must be sorted");
976             }
977             if (idx!=0) {
978                 if (rects[idx-1].x > r.x)
979                     throw new UnsupportedOperationException
980                         ("RectListManager entries must be sorted");
981             }
982             ensureCapacity(size+1);
983             if (idx != size)
984                 System.arraycopy(rects, idx, rects, idx+1, size-idx);
985             rects[idx] = r;
986             idx++;
987             removeOk = false;
988         }
989     }
990 }
991

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags