//------------------------------------------------------------------------------
// GridList2D.java
//------------------------------------------------------------------------------
package tribble.util;
import java.lang.ArrayIndexOutOfBoundsException;
import java.lang.IllegalArgumentException;
/*******************************************************************************
* Provides methods for arranging 1-dimensional array elements into a
* 2-dimensional grid.
*
*
* Consider a 1-dimensional array containing 14 elements, as shown here:
*
*
*
*
* | 0 |
* 1 |
* 2 |
* 3 |
* 4 |
* 5 |
* 6 |
* 7 |
* 8 |
* 9 |
* 10 |
* 11 |
* 12 |
* 13 |
*
*
*
*
* We wish to display the elements in a 2-dimensional grid with four columns,
* so that the elements are arranged in order from top to bottom down each row,
* and then from left to right across rows. Any left-over cells in the grid that
* do not correspond to any elements in the array are left empty. Every cell in
* each row, except possibly the last row, are filled; any remaining unfilled
* cells will be the right-most cells of the last row.
* The diagram below illustrates:
*
*
*
*
* | |
* |
* Columns (x) |
*
*
*
Rows
(y) |
*
*
*
* | |
* 0 |
* 1 |
* 2 |
* 3 |
* 4 |
*
*
* | 0 |
* 0 |
* 4 |
* 8 |
* 11 |
* −1 |
*
*
* | 1 |
* 1 |
* 5 |
* 9 |
* 12 |
* −1 |
*
*
* | 2 |
* 2 |
* 6 |
* 10 |
* 13 |
* −1 |
*
*
* | 3 |
* 3 |
* 7 |
* −1 |
* −1 |
* −1 |
*
*
* | 4 |
* −1 |
* −1 |
* −1 |
* −1 |
* −1 |
*
*
* |
*
*
*
*
* Note that cells within the 2-dimensional grid that do not have a corresponding
* element in the 1-dimensional source array, as well as cells outside the grid,
* have an index of −1.
*
*
*
* Determing the array indices for each grid cell is accomplished with code
* similar to the following:
*
*
*
* int nCols = 4;
* boolean printed = true;
*
* for (int y = 0; printed; y++)
* {
* printed = false;
* for (int x = 0; x < nCols; x++)
* {
* int i;
*
* i = GridList2D.{@link #indexFor(int,int,int,int) indexFor}(x, y, nCols, arr.length);
* if (i < 0)
* break;
*
* out.print(arr[i]);
* printed = true;
* }
* if (printed)
* out.println();
* }
*
*
* An alternative approach is to initialize a GridList2D object with the
* size of the 2-dimensional grid and the length of the 1-dimensional source
* array:
*
*
*
* int nCols = 4;
* GridList2D grid;
*
* grid = new {@link #GridList2D(int,int) GridList2D}(nCols, arr.length);
*
*
* The indexFor() method of the object can then be called for each grid
* cell coordinate to determine its corresponding index in the source array:
*
*
*
* boolean printed = true;
*
* for (int y = 0; printed; y++)
* {
* printed = false;
* for (int x = 0; ; x++)
* {
* int i;
*
* i = grid.{@link #indexFor(int,int) indexFor}(x, y);
* if (i < 0)
* break;
*
* out.print(arr[i]);
* printed = true;
* }
* if (printed)
* out.println();
* }
*
*
*
* - Source code:
* -
* http://david.tribble.com/src/java/tribble/util/GridList2D.java
*
* - Documentation:
* -
* http://david.tribble.com/docs/tribble/util/GridList2D.html
*
*
*
*
* @version $Revision: 1.3 $ $Date: 2010/10/20 22:41:32 $
* @since 2010-10-17
* @author David R. Tribble (david@tribble.com)
*
* Copyright ©2010 by David R. Tribble, all rights reserved.
* Permission is granted to any person or entity except those designated by
* by the United States Department of State as a terrorist, or terrorist
* government or agency, to use and distribute this source code provided
* that the original copyright notice remains present and unaltered.
*/
public class GridList2D
{
static final String REV =
"@(#)tribble/util/GridList2D.java $Revision: 1.3 $ $Date: 2010/10/20 22:41:32 $\n";
// ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
// Static methods
/***************************************************************************
* Determine the index of an element in a 1-dimensional array that is located
* at a particular (x, y) coordinate within a 2-dimensional grid.
*
* @param x
* X (horizontal) coordinate within the 2-dimensional grid.
*
* @param y
* Y (vertical) coordinate within the 2-dimensional grid.
*
* @param cols
* Width of the 2-dimensional grid, i.e., the number of columns it contains.
*
* @param elems
* Number of elements in the 1-dimensional array.
*
* @return
* The index of the element of the 1-dimensional array that is located at the
* (x, y) cell coordinate within the 2-dimensional
* grid, or −1 if the grid cell does not contain any array
* element (i.e., the cell is empty). This also returns −1 if
* the (x, y) cell coordinates do not lie within the
* grid.
*
* @since 1.1, 2010-10-17
*/
public static int indexFor(int x, int y, int cols, int elems)
{
int rows;
int excess;
int j;
// Bounds checks
if (elems < 0)
throw new ArrayIndexOutOfBoundsException(
"Array length is negative: " + elems);
// Compute the grid size
rows = (elems - 1)/cols;
excess = elems - cols*rows;
// Bounds check
if (x < 0 || x >= cols)
return -1;
// Compute the array index for the grid cell
if (x < excess)
{
// Bounds check
if (y < 0 || y > rows)
return -1;
j = x*(rows + 1) + y;
}
else
{
// Bounds check
if (y < 0 || y >= rows)
return -1;
j = x*rows + y + excess;
}
if (j >= elems)
return -1;
return j;
}
// ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
// Variables
/** Number of columns in the 2-D grid. */
private int m_cols;
/** Number of rows in the 2-D grid. */
private int m_rows;
/** Number of elements in the 1-D array. */
private int m_elems;
/** Number of extra cells past the last full grid row. */
private int m_excess;
// ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
// Constructors
/***************************************************************************
* Construct an object to determine the indices of the elements in a
* 1-dimensional array that are located at particular (x, y) coordinates
* within a 2-dimensional grid.
*
* @param cols
* Width of the 2-dimensional grid, i.e., the number of columns it contains.
*
* @param elems
* Number of elements in the 1-dimensional array.
*
* @since 1.1, 2010-10-17
*/
public GridList2D(int cols, int elems)
{
// Bounds checks
if (cols < 1)
throw new IllegalArgumentException("Grid columns is less than 1");
if (elems < 0)
throw new IllegalArgumentException("Array length is negative");
// Initialize
m_cols = cols;
m_elems = elems;
m_rows = (elems - 1)/cols;
m_excess = elems - cols*m_rows;
}
// ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
// Methods
/***************************************************************************
* Determine the index of an element in a 1-dimensional array that is located
* at a particular (x, y) cell coordinate within a 2-dimensional grid.
*
* @param x
* X (horizontal) coordinate within the 2-dimensional grid.
*
* @param y
* Y (vertical) coordinate within the 2-dimensional grid.
*
* @return
* The index of the element of the 1-dimensional array that is located at the
* (x, y) cell coordinate within the 2-dimensional
* grid, or −1 if the grid cell does not contain any array
* element (i.e., the cell is empty). This also returns −1 if
* the (x, y) cell coordinates do not lie within the
* grid.
*
* @since 1.1, 2010-10-17
*/
public int indexFor(int x, int y)
/*const*/
{
int rows;
int j;
// Bounds check
if (x < 0 || x >= m_cols)
return -1;
// Compute the array index for the grid cell
if (x < m_excess)
{
// Bounds check
if (y < 0 || y > m_rows)
return -1;
j = x*(m_rows + 1) + y;
}
else
{
// Bounds check
if (y < 0 || y >= m_rows)
return -1;
j = x*m_rows + y + m_excess;
}
if (j >= m_elems)
return -1;
return j;
}
/***************************************************************************
* Retrieve the number of columns in the 2-dimensional grid.
*
* @return
* Width of the 2-dimensional grid, i.e., the number of columns it contains.
*
* @since 1.2, 2010-10-18
*/
public int getColumns()
/*const*/
{
return m_cols;
}
/***************************************************************************
* Retrieve the number of rows in the 2-dimensional grid.
*
* @return
* Height of the 2-dimensional grid, i.e., the number of rows it contains.
* Note that the last row may contain empty cells.
*
* @since 1.2, 2010-10-18
*/
public int getRows()
/*const*/
{
return m_rows;
}
/***************************************************************************
* Retrieve the number of elements in the 1-dimensional source array.
*
* @return
* Number of elements in the 1-dimensional array.
*
* @since 1.2, 2010-10-18
*/
public int getArrayLength()
/*const*/
{
return m_elems;
}
}
// End GridList2D.java