Source code: org/apache/batik/ext/awt/geom/RectListManager.java
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 }