1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  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 * @author Denis M. Kishenko
19 * @version $Revision$
20 */
21package org.apache.harmony.awt.gl;
22
23import java.awt.Rectangle;
24import java.awt.Shape;
25import java.awt.geom.AffineTransform;
26import java.awt.geom.PathIterator;
27import java.awt.geom.Point2D;
28import java.awt.geom.Rectangle2D;
29import java.util.ArrayList;
30import java.util.NoSuchElementException;
31
32import org.apache.harmony.awt.internal.nls.Messages;
33
34public class MultiRectArea implements Shape {
35
36    /**
37     * If CHECK is true validation check active
38     */
39    private static final boolean CHECK = false;
40
41    boolean sorted = true;
42
43    /**
44     * Rectangle buffer
45     */
46    public int[] rect;
47
48    /**
49     * Bounding box
50     */
51    Rectangle bounds;
52
53    /**
54     * Result rectangle array
55     */
56    Rectangle[] rectangles;
57
58    /**
59     * LineCash provides creating MultiRectArea line by line. Used in JavaShapeRasterizer.
60     */
61    public static class LineCash extends MultiRectArea {
62
63        int lineY;
64        int bottomCount;
65        int[] bottom;
66
67        public LineCash(int size) {
68            super();
69            bottom = new int[size];
70            bottomCount = 0;
71        }
72
73        public void setLine(int y) {
74            lineY = y;
75        }
76
77        public void skipLine() {
78            lineY++;
79            bottomCount = 0;
80        }
81
82        public void addLine(int[] points, int pointCount) {
83            int bottomIndex = 0;
84            int pointIndex = 0;
85            int rectIndex = 0;
86            int pointX1 = 0;
87            int pointX2 = 0;
88            int bottomX1 = 0;
89            int bottomX2 = 0;
90            boolean appendRect = false;
91            boolean deleteRect = false;
92            int lastCount = bottomCount;
93
94            while (bottomIndex < lastCount || pointIndex < pointCount) {
95
96                appendRect = false;
97                deleteRect = false;
98
99                if (bottomIndex < lastCount) {
100                    rectIndex = bottom[bottomIndex];
101                    bottomX1 = rect[rectIndex];
102                    bottomX2 = rect[rectIndex + 2];
103                } else {
104                    appendRect = true;
105                }
106
107                if (pointIndex < pointCount) {
108                    pointX1 = points[pointIndex];
109                    pointX2 = points[pointIndex + 1];
110                } else {
111                    deleteRect = true;
112                }
113
114                if (!deleteRect && !appendRect) {
115                    if (pointX1 == bottomX1 && pointX2 == bottomX2) {
116                        rect[rectIndex + 3] = rect[rectIndex + 3] + 1;
117                        pointIndex += 2;
118                        bottomIndex++;
119                        continue;
120                    }
121                    deleteRect = pointX2 >= bottomX1;
122                    appendRect = pointX1 <= bottomX2;
123                }
124
125                if (deleteRect) {
126                    if (bottomIndex < bottomCount - 1) {
127                        System.arraycopy(bottom, bottomIndex + 1, bottom, bottomIndex, bottomCount - bottomIndex - 1);
128                        rectIndex -= 4;
129                    }
130                    bottomCount--;
131                    lastCount--;
132                }
133
134                if (appendRect) {
135                    int i = rect[0];
136                    bottom[bottomCount++] = i;
137                    rect = MultiRectAreaOp.checkBufSize(rect, 4);
138                    rect[i++] = pointX1;
139                    rect[i++] = lineY;
140                    rect[i++] = pointX2;
141                    rect[i++] = lineY;
142                    pointIndex += 2;
143                }
144            }
145            lineY++;
146
147            invalidate();
148        }
149
150    }
151
152    /**
153     * RectCash provides simple creating MultiRectArea
154     */
155    public static class RectCash extends MultiRectArea {
156
157        int[] cash;
158
159        public RectCash() {
160            super();
161            cash = new int[MultiRectAreaOp.RECT_CAPACITY];
162            cash[0] = 1;
163        }
164
165        public void addRectCashed(int x1, int y1, int x2, int y2) {
166            addRect(x1, y1, x2, y2);
167            invalidate();
168/*
169            // Exclude from cash unnecessary rectangles
170            int i = 1;
171            while(i < cash[0]) {
172                if (rect[cash[i] + 3] >= y1 - 1) {
173                    if (i > 1) {
174                        System.arraycopy(cash, i, cash, 1, cash[0] - i);
175                    }
176                    break;
177                }
178                i++;
179            }
180            cash[0] -= i - 1;
181
182            // Find in cash rectangle to concatinate
183            i = 1;
184            while(i < cash[0]) {
185                int index = cash[i];
186                if (rect[index + 3] != y1 - 1) {
187                    break;
188                }
189                if (rect[index] == x1 && rect[index + 2] == x2) {
190                    rect[index + 3] += y2 - y1 + 1;
191
192                    int pos = i + 1;
193                    while(pos < cash[0]) {
194                        if (rect[index + 3] <= rect[cash[i] + 3]) {
195                            System.arraycopy(cash, i + 1, cash, i, pos - i);
196                            break;
197                        }
198                        i++;
199                    }
200                    cash[pos - 1] = index;
201
202                    invalidate();
203                    return;
204                }
205                i++;
206            }
207
208            // Add rectangle to buffer
209            int index = rect[0];
210            rect = MultiRectAreaOp.checkBufSize(rect, 4);
211            rect[index + 0] = x1;
212            rect[index + 1] = y1;
213            rect[index + 2] = x2;
214            rect[index + 3] = y2;
215
216            // Add rectangle to cash
217            int length = cash[0];
218            cash = MultiRectAreaOp.checkBufSize(cash, 1);
219            while(i < length) {
220                if (y2 <= rect[cash[i] + 3]) {
221                    System.arraycopy(cash, i, cash, i + 1, length - i);
222                    break;
223                }
224                i++;
225            }
226            cash[i] = index;
227            invalidate();
228*/
229        }
230
231        public void addRectCashed(int[] rect, int rectOff, int rectLength) {
232            for(int i = rectOff; i < rectOff + rectLength;) {
233                addRect(rect[i++], rect[i++], rect[i++], rect[i++]);
234//              addRectCashed(rect[i++], rect[i++], rect[i++], rect[i++]);
235            }
236        }
237
238    }
239
240    /**
241     * MultiRectArea path iterator
242     */
243    class Iterator implements PathIterator {
244
245        int type;
246        int index;
247        int pos;
248
249        int[] rect;
250        AffineTransform t;
251
252        Iterator(MultiRectArea mra, AffineTransform t) {
253            rect = new int[mra.rect[0] - 1];
254            System.arraycopy(mra.rect, 1, rect, 0, rect.length);
255            this.t = t;
256        }
257
258        public int getWindingRule() {
259            return WIND_NON_ZERO;
260        }
261
262        public boolean isDone() {
263            return pos >= rect.length;
264        }
265
266        public void next() {
267            if (index == 4) {
268                pos += 4;
269            }
270            index = (index + 1) % 5;
271        }
272
273        public int currentSegment(double[] coords) {
274            if (isDone()) {
275                // awt.4B=Iiterator out of bounds
276                throw new NoSuchElementException(Messages.getString("awt.4B")); //$NON-NLS-1$
277            }
278            int type = 0;
279
280            switch(index) {
281            case 0 :
282                type = SEG_MOVETO;
283                coords[0] = rect[pos + 0];
284                coords[1] = rect[pos + 1];
285                break;
286            case 1:
287                type = SEG_LINETO;
288                coords[0] = rect[pos + 2];
289                coords[1] = rect[pos + 1];
290                break;
291            case 2:
292                type = SEG_LINETO;
293                coords[0] = rect[pos + 2];
294                coords[1] = rect[pos + 3];
295                break;
296            case 3:
297                type = SEG_LINETO;
298                coords[0] = rect[pos + 0];
299                coords[1] = rect[pos + 3];
300                break;
301            case 4:
302                type = SEG_CLOSE;
303                break;
304            }
305
306            if (t != null) {
307                t.transform(coords, 0, coords, 0, 1);
308            }
309            return type;
310        }
311
312        public int currentSegment(float[] coords) {
313            if (isDone()) {
314                // awt.4B=Iiterator out of bounds
315                throw new NoSuchElementException(Messages.getString("awt.4B")); //$NON-NLS-1$
316            }
317            int type = 0;
318
319            switch(index) {
320            case 0 :
321                type = SEG_MOVETO;
322                coords[0] = rect[pos + 0];
323                coords[1] = rect[pos + 1];
324                break;
325            case 1:
326                type = SEG_LINETO;
327                coords[0] = rect[pos + 2];
328                coords[1] = rect[pos + 1];
329                break;
330            case 2:
331                type = SEG_LINETO;
332                coords[0] = rect[pos + 2];
333                coords[1] = rect[pos + 3];
334                break;
335            case 3:
336                type = SEG_LINETO;
337                coords[0] = rect[pos + 0];
338                coords[1] = rect[pos + 3];
339                break;
340            case 4:
341                type = SEG_CLOSE;
342                break;
343            }
344
345            if (t != null) {
346                t.transform(coords, 0, coords, 0, 1);
347            }
348            return type;
349        }
350
351    }
352
353    /**
354     * Constructs a new empty MultiRectArea
355     */
356    public MultiRectArea() {
357        rect = MultiRectAreaOp.createBuf(0);
358    }
359
360    public MultiRectArea(boolean sorted) {
361       this();
362       this.sorted = sorted;
363    }
364
365    /**
366     * Constructs a new MultiRectArea as a copy of another one
367     */
368    public MultiRectArea(MultiRectArea mra) {
369        if (mra == null) {
370            rect = MultiRectAreaOp.createBuf(0);
371        } else {
372            rect = new int[mra.rect.length];
373            System.arraycopy(mra.rect, 0, rect, 0, mra.rect.length);
374            check(this, "MultiRectArea(MRA)"); //$NON-NLS-1$
375        }
376    }
377
378    /**
379     * Constructs a new MultiRectArea consists of single rectangle
380     */
381    public MultiRectArea(Rectangle r) {
382        rect = MultiRectAreaOp.createBuf(0);
383        if (r != null && !r.isEmpty()) {
384            rect[0] = 5;
385            rect[1] = r.x;
386            rect[2] = r.y;
387            rect[3] = r.x + r.width - 1;
388            rect[4] = r.y + r.height - 1;
389        }
390        check(this, "MultiRectArea(Rectangle)"); //$NON-NLS-1$
391    }
392
393    /**
394     * Constructs a new MultiRectArea consists of single rectangle
395     */
396    public MultiRectArea(int x0, int y0, int x1, int y1) {
397        rect = MultiRectAreaOp.createBuf(0);
398        if (x1 >= x0 && y1 >= y0) {
399            rect[0] = 5;
400            rect[1] = x0;
401            rect[2] = y0;
402            rect[3] = x1;
403            rect[4] = y1;
404        }
405        check(this, "MultiRectArea(Rectangle)"); //$NON-NLS-1$
406    }
407
408    /**
409     * Constructs a new MultiRectArea and append rectangle from buffer
410     */
411    public MultiRectArea(Rectangle[] buf) {
412        this();
413        for (Rectangle element : buf) {
414            add(element);
415        }
416    }
417
418    /**
419     * Constructs a new MultiRectArea and append rectangle from array
420     */
421    public MultiRectArea(ArrayList<Rectangle> buf) {
422        this();
423        for(int i = 0; i < buf.size(); i++) {
424            add(buf.get(i));
425        }
426    }
427
428    /**
429     * Sort rectangle buffer
430     */
431    void resort() {
432        int[] buf = new int[4];
433        for(int i = 1; i < rect[0]; i += 4) {
434            int k = i;
435            int x1 = rect[k];
436            int y1 = rect[k + 1];
437            for(int j = i + 4; j < rect[0]; j += 4) {
438                int x2 = rect[j];
439                int y2 = rect[j + 1];
440                if (y1 > y2 || (y1 == y2 && x1 > x2)) {
441                    x1 = x2;
442                    y1 = y2;
443                    k = j;
444                }
445            }
446            if (k != i) {
447                System.arraycopy(rect, i, buf, 0, 4);
448                System.arraycopy(rect, k, rect, i, 4);
449                System.arraycopy(buf, 0, rect, k, 4);
450            }
451        }
452        invalidate();
453    }
454
455    /**
456     * Tests equals with another object
457     */
458    @Override
459    public boolean equals(Object obj) {
460        if (obj == this) {
461            return true;
462        }
463        if (obj instanceof MultiRectArea) {
464            MultiRectArea mra = (MultiRectArea) obj;
465            for(int i = 0; i < rect[0]; i++) {
466                if (rect[i] != mra.rect[i]) {
467                    return false;
468                }
469            }
470            return true;
471        }
472        return false;
473    }
474
475    /**
476     * Checks validation of MultiRectArea object
477     */
478    static MultiRectArea check(MultiRectArea mra, String msg) {
479        if (CHECK && mra != null) {
480            if (MultiRectArea.checkValidation(mra.getRectangles(), mra.sorted) != -1) {
481                // awt.4C=Invalid MultiRectArea in method {0}
482                new RuntimeException(Messages.getString("awt.4C", msg)); //$NON-NLS-1$
483            }
484        }
485        return mra;
486    }
487
488    /**
489     * Checks validation of MultiRectArea object
490     */
491    public static int checkValidation(Rectangle[] r, boolean sorted) {
492
493        // Check width and height
494        for(int i = 0; i < r.length; i++) {
495            if (r[i].width <= 0 || r[i].height <= 0) {
496                return i;
497            }
498        }
499
500        // Check order
501        if (sorted) {
502            for(int i = 1; i < r.length; i++) {
503                if (r[i - 1].y > r[i].y) {
504                    return i;
505                }
506                if (r[i - 1].y == r[i].y) {
507                    if (r[i - 1].x > r[i].x) {
508                        return i;
509                    }
510                }
511            }
512        }
513
514        // Check override
515        for(int i = 0; i < r.length; i++) {
516            for(int j = i + 1; j < r.length; j++) {
517                if (r[i].intersects(r[j])) {
518                    return i;
519                }
520            }
521        }
522
523        return -1;
524    }
525
526    /**
527     * Assigns rectangle from another buffer
528     */
529    protected void setRect(int[] buf, boolean copy) {
530        if (copy) {
531            rect = new int[buf.length];
532            System.arraycopy(buf, 0, rect, 0, buf.length);
533        } else {
534            rect = buf;
535        }
536        invalidate();
537    }
538
539    /**
540     * Union with another MultiRectArea object
541     */
542    public void add(MultiRectArea mra) {
543        setRect(union(this, mra).rect, false);
544        invalidate();
545    }
546
547    /**
548     * Intersect with another MultiRectArea object
549     */
550    public void intersect(MultiRectArea mra) {
551        setRect(intersect(this, mra).rect, false);
552        invalidate();
553    }
554
555    /**
556     * Subtract another MultiRectArea object
557     */
558    public void substract(MultiRectArea mra) {
559        setRect(subtract(this, mra).rect, false);
560        invalidate();
561    }
562
563    /**
564     * Union with Rectangle object
565     */
566    public void add(Rectangle rect) {
567        setRect(union(this, new MultiRectArea(rect)).rect, false);
568        invalidate();
569    }
570
571    /**
572     * Intersect with Rectangle object
573     */
574    public void intersect(Rectangle rect) {
575        setRect(intersect(this, new MultiRectArea(rect)).rect, false);
576        invalidate();
577    }
578
579    /**
580     * Subtract rectangle object
581     */
582    public void substract(Rectangle rect) {
583        setRect(subtract(this, new MultiRectArea(rect)).rect, false);
584    }
585
586    /**
587     * Union two MutliRectareArea objects
588     */
589    public static MultiRectArea intersect(MultiRectArea src1, MultiRectArea src2) {
590        MultiRectArea res = check(MultiRectAreaOp.Intersection.getResult(src1, src2), "intersect(MRA,MRA)"); //$NON-NLS-1$
591        return res;
592    }
593
594    /**
595     * Intersect two MultiRectArea objects
596     */
597    public static MultiRectArea union(MultiRectArea src1, MultiRectArea src2) {
598        MultiRectArea res = check(new MultiRectAreaOp.Union().getResult(src1, src2), "union(MRA,MRA)"); //$NON-NLS-1$
599        return res;
600    }
601
602    /**
603     * Subtract two MultiRectArea objects
604     */
605    public static MultiRectArea subtract(MultiRectArea src1, MultiRectArea src2) {
606        MultiRectArea res = check(MultiRectAreaOp.Subtraction.getResult(src1, src2), "subtract(MRA,MRA)"); //$NON-NLS-1$
607        return res;
608    }
609
610    /**
611     * Print MultiRectArea object to output stream
612     */
613    public static void print(MultiRectArea mra, String msg) {
614        if (mra == null) {
615            System.out.println(msg + "=null"); //$NON-NLS-1$
616        } else {
617            Rectangle[] rects = mra.getRectangles();
618            System.out.println(msg + "(" + rects.length + ")"); //$NON-NLS-1$ //$NON-NLS-2$
619            for (Rectangle element : rects) {
620                System.out.println(
621                        element.x + "," + //$NON-NLS-1$
622                        element.y + "," + //$NON-NLS-1$
623                        (element.x + element.width - 1) + "," + //$NON-NLS-1$
624                        (element.y + element.height - 1));
625            }
626        }
627    }
628
629    /**
630     * Translate MultiRectArea object by (x, y)
631     */
632    public void translate(int x, int y) {
633        for(int i = 1; i < rect[0];) {
634            rect[i++] += x;
635            rect[i++] += y;
636            rect[i++] += x;
637            rect[i++] += y;
638        }
639
640        if (bounds != null && !bounds.isEmpty()) {
641            bounds.translate(x, y);
642        }
643
644        if (rectangles != null) {
645            for (Rectangle element : rectangles) {
646                element.translate(x, y);
647            }
648        }
649    }
650
651    /**
652     * Add rectangle to the buffer without any checking
653     */
654    public void addRect(int x1, int y1, int x2, int y2) {
655        int i = rect[0];
656        rect = MultiRectAreaOp.checkBufSize(rect, 4);
657        rect[i++] = x1;
658        rect[i++] = y1;
659        rect[i++] = x2;
660        rect[i++] = y2;
661    }
662
663    /**
664     * Tests is MultiRectArea empty
665     */
666    public boolean isEmpty() {
667        return rect[0] == 1;
668    }
669
670    void invalidate() {
671        bounds = null;
672        rectangles = null;
673    }
674
675    /**
676     * Returns bounds of MultiRectArea object
677     */
678    public Rectangle getBounds() {
679        if (bounds != null) {
680            return bounds;
681        }
682
683        if (isEmpty()) {
684            return bounds = new Rectangle();
685        }
686
687        int x1 = rect[1];
688        int y1 = rect[2];
689        int x2 = rect[3];
690        int y2 = rect[4];
691
692        for(int i = 5; i < rect[0]; i += 4) {
693            int rx1 = rect[i + 0];
694            int ry1 = rect[i + 1];
695            int rx2 = rect[i + 2];
696            int ry2 = rect[i + 3];
697            if (rx1 < x1) {
698                x1 = rx1;
699            }
700            if (rx2 > x2) {
701                x2 = rx2;
702            }
703            if (ry1 < y1) {
704                y1 = ry1;
705            }
706            if (ry2 > y2) {
707                y2 = ry2;
708            }
709        }
710
711        return bounds = new Rectangle(x1, y1, x2 - x1 + 1, y2 - y1 + 1);
712    }
713
714    /**
715     * Recturn rectangle count in the buffer
716     */
717    public int getRectCount() {
718        return (rect[0] - 1) / 4;
719    }
720
721    /**
722     * Returns Rectangle array
723     */
724    public Rectangle[] getRectangles() {
725        if (rectangles != null) {
726            return rectangles;
727        }
728
729        rectangles = new Rectangle[(rect[0] - 1) / 4];
730        int j = 0;
731        for(int i = 1; i < rect[0]; i += 4) {
732            rectangles[j++] = new Rectangle(
733                    rect[i],
734                    rect[i + 1],
735                    rect[i + 2] - rect[i] + 1,
736                    rect[i + 3] - rect[i + 1] + 1);
737        }
738        return rectangles;
739    }
740
741    /**
742     * Returns Bounds2D
743     */
744    public Rectangle2D getBounds2D() {
745        return getBounds();
746    }
747
748    /**
749     * Tests does point lie inside MultiRectArea object
750     */
751    public boolean contains(double x, double y) {
752        for(int i = 1; i < rect[0]; i+= 4) {
753            if (rect[i] <= x && x <= rect[i + 2] && rect[i + 1] <= y && y <= rect[i + 3]) {
754                return true;
755            }
756        }
757        return false;
758    }
759
760    /**
761     * Tests does Point2D lie inside MultiRectArea object
762     */
763    public boolean contains(Point2D p) {
764        return contains(p.getX(), p.getY());
765    }
766
767    /**
768     * Tests does rectangle lie inside MultiRectArea object
769     */
770    public boolean contains(double x, double y, double w, double h) {
771        throw new RuntimeException("Not implemented"); //$NON-NLS-1$
772    }
773
774    /**
775     * Tests does Rectangle2D lie inside MultiRectArea object
776     */
777    public boolean contains(Rectangle2D r) {
778        throw new RuntimeException("Not implemented"); //$NON-NLS-1$
779    }
780
781    /**
782     * Tests does rectangle intersect MultiRectArea object
783     */
784    public boolean intersects(double x, double y, double w, double h) {
785        Rectangle r = new Rectangle();
786        r.setRect(x, y, w, h);
787        return intersects(r);
788    }
789
790    /**
791     * Tests does Rectangle2D intersect MultiRectArea object
792     */
793    public boolean intersects(Rectangle2D r) {
794        if (r == null || r.isEmpty()) {
795            return false;
796        }
797        for(int i = 1; i < rect[0]; i+= 4) {
798            if (r.intersects(rect[i], rect[i+1], rect[i + 2]-rect[i]+1, rect[i + 3]-rect[i + 1]+1)) {
799                return true;
800            }
801        }
802        return false;
803    }
804
805    /**
806     * Returns path iterator
807     */
808    public PathIterator getPathIterator(AffineTransform t, double flatness) {
809        return new Iterator(this, t);
810    }
811
812    /**
813     * Returns path iterator
814     */
815    public PathIterator getPathIterator(AffineTransform t) {
816        return new Iterator(this, t);
817    }
818
819    /**
820     * Returns MultiRectArea object converted to string
821     */
822    @Override
823    public String toString() {
824        int cnt = getRectCount();
825        StringBuffer sb = new StringBuffer((cnt << 5) + 128);
826        sb.append(getClass().getName()).append(" ["); //$NON-NLS-1$
827        for(int i = 1; i < rect[0]; i += 4) {
828            sb.append(i > 1 ? ", [" : "[").append(rect[i]).append(", ").append(rect[i + 1]). //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
829            append(", ").append(rect[i + 2] - rect[i] + 1).append(", "). //$NON-NLS-1$ //$NON-NLS-2$
830            append(rect[i + 3] - rect[i + 1] + 1).append("]"); //$NON-NLS-1$
831        }
832        return sb.append("]").toString(); //$NON-NLS-1$
833    }
834
835}
836
837