001    /*
002     * ArrayRotation
003     * 
004     * Copyright (c) 2000, 2001, 2002 Marco Schmidt <marcoschmidt@users.sourceforge.net>
005     * All rights reserved.
006     */
007    
008    package net.sourceforge.jiu.util;
009    
010    /**
011     * Provides static methods to rotate (in steps of 90 degrees), flip and mirror array elements.
012     * The image data is expected to be available as an array of integer values, being stored as rows top-to-bottom.
013     * Within each row, the data is laid out from left to right.
014     * This class may also been useful for transposing matrices.
015     * <p>
016     * The rotation by 90 and 270 degrees in-place (i.e., without using a 
017     * second array to copy to) is based on ideas and code developed
018     * by others.
019     * See <a target="_top" href="http://facweb.cs.depaul.edu/tchristopher/rotates.htm">Rotation of arrays</a>
020     * by Thomas W. Christopher.
021     * <p>
022     * I also got very useful advice from Hans-Bernhard Broeker and others in 
023     * <a href="news:comp.graphics.algorithms">comp.graphics.algorithms</a>.
024     * There is a thread titled <em>In-place rotation of pixel images</em> starting Oct 11, 2000.
025     * <p>
026     * <em>Note: This class should be adjusted if Java ever supports genericity.
027     * Then rotation functionality could be provided for all kinds of arrays.</em>
028     * @author Hans-Bernhard Broeker
029     * @author Thomas W. Christopher
030     * @author Marco Schmidt
031     */
032    public class ArrayRotation
033    {
034            private ArrayRotation()
035            {
036            }
037    
038            /**
039             * This method checks several properties of the arguments.
040             * If any of the properties is not fulfilled, an explaining 
041             * {@link java.lang.IllegalArgumentException} is thrown.
042             * Otherwise, nothing happens.
043             * This method is supposed to be called at the beginning of several
044             * other methods in this class.
045             * Properties checked:
046             * <ul>
047             * <li><code>pixels</code> is non-null</li>
048             * <li><code>width</code> and <code>height</code> are larger than zero</li>
049             * <li>number of elements in <code>pixels</code> is at least <code>width</code> times <code>height</code></li>
050             * </ul>
051             */
052            public static void checkPixelArray(int[] pixels, int width, int height)
053            {
054                    if (pixels == null)
055                    {
056                            throw new IllegalArgumentException("Error -- the pixel array must be initialized.");
057                    }
058                    if (width < 1 || height < 1)
059                    {
060                            throw new IllegalArgumentException("Error -- width and height must be >= 1 (width=" + 
061                                    width + ", height=" + height + ").");
062                    }
063                    if (pixels.length < width * height)
064                    {
065                            throw new IllegalArgumentException("Error -- pixel array must have at least width * height pixels, has only " + 
066                                    pixels.length + " pixels.");
067                    }
068            }
069    
070            /**
071             * Flips the argument image, i.e., the top line becomes the bottom line
072             * and vice versa, etc.
073             * This method first checks the validity of the arguments that define the image
074             * by a call to {@link checkPixelArray}.
075             * Then the image data is flipped in place, no additional memory is required.
076             * Note that after applying this operation twice you will get the original
077             * image back.
078             *
079             * @param pixels the array of pixels that form the image to be flipped
080             * @param width the horizontal resolution of the image; must be larger than 0
081             * @param height the vertical resolution of the image; must be larger than 0
082             * @exception IllegalArgumentException if the arguments are invalid
083             */
084            private static final void flipInPlace(int[] pixels, int width, int height)
085            {
086                    checkPixelArray(pixels, width, height);
087                    int y1 = 0;
088                    int y2 = height - 1;
089                    while (y1 < y2)
090                    {
091                            int offset1 = y1 * width;
092                            int offset2 = y2 * width;
093                            for (int x = 0; x < width; x++)
094                            {
095                                    int temp = pixels[offset1];
096                                    pixels[offset1++] = pixels[offset2];
097                                    pixels[offset2++] = temp;
098                            }
099                    }
100            }
101    
102            private static final int[] flip(int[] pixels, int width, int height)
103            {
104                    checkPixelArray(pixels, width, height);
105                    int[] result = new int[width * height];
106                    for (int y1 = 0, y2 = height - 1; y1 < height; y1++, y2--)
107                    {
108                            int offset1 = y1 * width;
109                            int offset2 = y2 * width;
110                            for (int x = 0; x < width; x++)
111                            {
112                                    result[offset2++] = pixels[offset1++];
113                            }
114                    }
115                    return result;
116            }
117    
118            /**
119             * Flips the image given by the arguments.
120             * The inPlace argument determines if the pixels array is modified or not.
121             * If inPlace is true, no additional array is allocated.
122             * Otherwise, an array of width times height items is allocated and the 
123             * flipped image will be stored in this array.
124             * @param inPlace if <code>true</code> all work is done on the <code>pixels</code> array;
125             *                otherwise, a second array is allocated and the <code>pixels</code> array
126             *                remains unmodified
127             * @param pixels the array of pixels that form the image to be flipped
128             * @param width the horizontal resolution of the image; must be larger than 0
129             * @param height the vertical resolution of the image; must be larger than 0
130             * @return the flipped image as int array; equals <code>pixels</code> if 
131             * <code>inPlace</code> is true
132             * @exception IllegalArgumentException if the pixel resolution 
133             * is invalid or the pixels array is not initialized or its length smaller
134             * than <code>width</code> times <code>height</code>
135             */
136            public static final int[] flip(boolean inPlace, int[] pixels, int width, int height)
137            {
138                    if (inPlace)
139                    {
140                            flipInPlace(pixels, width, height);
141                            return pixels;
142                    }
143                    else
144                    {
145                            return flip(pixels, width, height);
146                    }
147            }
148    
149            /**
150             * Mirrors the image given by the arguments.
151             * For each row, pixels are swapped, leftmost and rightmost,
152             * second-leftmost and second-rightmost, and so on.
153             * The inPlace argument determines if the pixels array is modified or not.
154             * If inPlace is true, no additional array is used.
155             * Otherwise, an array of width times height items is allocated and the 
156             * mirrored image will be stored in this array.
157             * @param inPlace if <code>true</code> all work is done on the <code>pixels</code> array;
158             *                otherwise, a second array is allocated and the <code>pixels</code> array
159             *                remains unmodified
160             * @param pixels the array of pixels that form the image to be flipped
161             * @param width the horizontal resolution of the image; must be larger than 0
162             * @param height the vertical resolution of the image; must be larger than 0
163             * @return the flipped image as int array; equals <code>pixels</code> if 
164             * <code>inPlace</code> is true
165             * @exception IllegalArgumentException if the pixel resolution 
166             * is invalid or the pixels array is not initialized or its length smaller
167             * than <code>width</code> times <code>height</code>
168             */
169            public static int[] mirror(boolean inPlace, int[] pixels, int width, int height)
170            {
171                    if (inPlace)
172                    {
173                            //flipInPlace(pixels, width, height);
174                            return pixels;
175                    }
176                    else
177                    {
178                            return pixels;//flip(pixels, width, height);
179                    }
180            }
181    
182            /**
183             * Rotates the argument image by 180 degrees.
184             * The resulting image will have exactly the same pixel resolution.
185             * Note that this operation is the same as two consecutive 90 degree
186             * rotations in the same direction.
187             * Another way of implementing a 180 degree rotation is first flipping
188             * and then mirroring the original image (or vice versa).
189             * <p>
190             * If <code>inPlace</code> is true, the rotation is done on the 
191             * argument <code>pixels</code> array.
192             * Otherwise a new array of sufficient length is allocated and the 
193             * rotated image will be stored in this new array, not modifying the 
194             * content of the <code>pixels</code> array.
195             * <p>
196             * @param inPlace determines whether the rotated image is written to the argument array
197             * @param pixels the array of pixels that form the image to be rotated
198             * @param width the horizontal resolution of the image; must be larger than 0
199             * @param height the vertical resolution of the image; must be larger than 0
200             * @return the flipped image as int array; equals <code>pixels</code> if 
201             * <code>inPlace</code> is true
202             * @exception IllegalArgumentException if the pixel resolution 
203             * is invalid or the pixels array is not initialized or its length smaller
204             * than <code>width</code> times <code>height</code>
205             */
206            public static int[] rotate180(boolean inPlace, int[] pixels, int width, int height)
207            {
208                    if (inPlace)
209                    {
210                            rotateInPlace180(pixels, width, height);
211                            return pixels;
212                    }
213                    else
214                    {
215                            return pixels;//rotateToCopy180(pixels, width, height);
216                    }
217            }
218    
219            private static int[] rotate180(int[] pixels, int width, int height)
220            {
221                    checkPixelArray(pixels, width, height);
222                    int numPixels = width * height;
223                    int[] result = new int[numPixels];
224                    int x1 = 0;
225                    int x2 = numPixels - 1;
226                    while (x1 < x2)
227                    {
228                            int temp = pixels[x1];
229                            pixels[x1++] = pixels[x2];
230                            pixels[x2--] = temp;
231                    }
232                    return result;
233            }
234    
235            private static void rotateInPlace180(int[] pixels, int width, int height)
236            {
237                    checkPixelArray(pixels, width, height);
238                    int x1 = 0;
239                    int x2 = width * height - 1;
240                    while (x1 < x2)
241                    {
242                            int temp = pixels[x1];
243                            pixels[x1++] = pixels[x2];
244                            pixels[x2--] = temp;
245                    }
246            }
247    
248            private static void rotateToArray90Left(int[] src, int[] dest, int width, int height)
249            {
250                    //System.out.println("90 left (to copy) width=" + width + " height=" + height + " dest.length=" + dest.length);
251                    checkPixelArray(src, width, height);
252                    checkPixelArray(dest, width, height);
253                    if (src == dest)
254                    {
255                            throw new IllegalArgumentException("rotate90Left assumes that the argument arrays are not the same.");
256                    }
257                    int x_ = -1;
258                    int y_ = -1;
259                    try
260                    {
261                            int offset = 0;
262                    for (int y = 0; y < height; y++)
263                    {
264                            for (int x = 0; x < width; x++)
265                            {
266                                    x_ = x;
267                                    y_ = y;
268                                    dest[(width - x - 1) * height + y] = src[offset++];
269                            }
270                    }
271                    }
272                    catch (ArrayIndexOutOfBoundsException ae)
273                    {
274                            System.out.println("bounds; x=" + x_ + " y=" + y_);
275                    }
276            }
277    
278            private static int pred(int k, int width, int height)
279            {
280                    return (k % height) * width + k / height;
281            }
282    
283            private static void rotateInPlace90Left(int[] pixels, int width, int height)
284            {
285                    //System.out.println("90 left in-place");
286                    int LxM = height * width;
287                    int i, j, k, stillToMove;
288                    for (i = 0, stillToMove = LxM; stillToMove > 0; i++)
289                    {
290                            for (j = pred(i, width, height); j > i; j = pred(j, width, height))
291                            ;
292                    if (j < i)
293                    {
294                            continue;
295                    }
296                        for (k = i, j = pred(i, width, height); j != i; k = j,
297                            j = pred(j, width, height))
298                        {
299                            //exchange(k,j);
300                            int temp = pixels[k];
301                            pixels[k] = pixels[j];
302                            pixels[j] = temp;
303                            --stillToMove;
304                    }
305                    --stillToMove;
306                    }
307            }
308    
309            public static void rotate90Left(int width, int height, byte[] src, int srcOffset, byte[] dest, int destOffset)
310            {
311                    int offset = srcOffset;
312                    for (int y = 0; y < height; y++)
313                    {
314                            for (int x = 0; x < width; x++)
315                            {
316                                    dest[destOffset + (width - x - 1) * height + y] = src[offset++];
317                            }
318                    }
319            }
320    
321            public static void rotate90Right(int width, int height, byte[] src, int srcOffset, byte[] dest, int destOffset)
322            {
323                    int offset = srcOffset;
324                    for (int y = 0; y < height; y++)
325                    {
326                            for (int x = 0; x < width; x++)
327                            {
328                                    dest[destOffset + x * height + (height - 1 - y)] = src[offset++];
329                            }
330                    }
331            }
332    
333            public static void rotate180(int width, int height, byte[] src, int srcOffset, byte[] dest, int destOffset)
334            {
335                    int n = width * height;
336                    destOffset = destOffset + n - 1;
337                    while (n-- > 0)
338                    {
339                            dest[destOffset--] = src[srcOffset++];
340                    }
341            }
342    
343            /*      public static int[] rotate90Left(boolean inPlace, int[] pixels, int width,
344                    int height) throws IllegalArgumentException
345            {
346                    if (inPlace)
347                    {
348                            rotateInPlace90Left(pixels, width, height);
349                            return pixels;
350                    }
351                    else
352                    {
353                            int[] dest = new int[width * height];
354                            rotateToArray90Left(pixels, dest, width, height);
355                            return dest;
356                    }
357            }*/
358    
359            private static void rotateInPlace90Right(int[] pixels, int width, int height)
360            {
361                    //System.out.println("90 right in-place (empty)");
362                    throw new IllegalArgumentException("This method not implemented yet.");
363            }
364    
365            private static int[] rotate90Right(int[] pixels, int width, int height)
366            {
367                    int[] result = new int[width * height];
368                    int offset = 0;
369                    for (int y = 0; y < height; y++)
370                    {
371                            int srcOffset = height - 1 - y;
372                            for (int x = 0; x < width; x++)
373                            {
374                                    result[srcOffset] = pixels[offset++];
375                                    srcOffset += height;
376                            }
377                    }
378                    return result;
379            }
380    
381            public static int[] rotate90Right(boolean inPlace, int[] pixels, int width, int height)
382            {
383                    if (inPlace)
384                    {
385                            rotateInPlace90Right(pixels, width, height);
386                            return pixels;
387                    }
388                    else
389                    {
390                            return rotate90Right(pixels, width, height);
391                    }
392            }
393    }