Docjar: A Java Source and Docuemnt Enginecom.*    java.*    javax.*    org.*    all    new    plug-in

Quick Search    Search Deep
Overview  Package   Class  Use  Deprecated  Index 
Home >> All >> cgsuite >> [ util overview ]  PREV CLASS  NEXT CLASS
SUMMARY: JavaDoc of cgsuite.util.Grid JAVADOC | Sourc code of cgsuite.util.Grid SOURCE | Download cgsuite.util.Grid DOWNLOAD | NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

cgsuite.util
Class Grid  view Grid download Grid.java

java.lang.Object
  extended bycgsuite.util.Grid
All Implemented Interfaces:
java.lang.Cloneable, java.lang.Comparable, java.io.Serializable
public class Grid
extends java.lang.Object
implements java.lang.Cloneable, java.lang.Comparable, java.io.Serializable

A two-dimensional array suitable for representing grid-based games. The array is stored in a compact, memory-efficient structure. In addition, several utilities are provided, including methods to decompose a grid into its connected components and to compare grids while ignoring symmetries.

In addition to the size of the grid, it's possible to specify the number of bits to use per grid entry. The smaller the number of bits per entry, the more efficient memory usage will be. However, fewer bits per entry also restricts the range of values that each entry can have. See the documentation for the BITS_PER_ENTRY_* constants for details. Note that for speed reasons, no internal checks are performed to insure that each entry falls within the specified range. If an entry is set to a value outside the specified range, the resulting behavior is undefined.

Setting the bits per entry below 32 causes a marginal performance deficit when accessing the grid. However, the smaller memory footprint means that the grid will be cloned substantially faster. In most applications (such as canonicalizing games) this leads to an overall gain in speed as well as memory efficiency.

Version:
0.3

Nested Class Summary
private static class Grid.RegionInfo
           
 
Field Summary
private static int[] bits
           
static int BITS_PER_ENTRY_1
          Indicates that this grid should use one bit per grid entry.
static int BITS_PER_ENTRY_16
          Indicates that this grid should use 16 bits per grid entry.
static int BITS_PER_ENTRY_2
          Indicates that this grid should use two bits per grid entry.
static int BITS_PER_ENTRY_32
          Indicates that this grid should use 32 bits per grid entry.
static int BITS_PER_ENTRY_4
          Indicates that this grid should use four bits per grid entry.
static int BITS_PER_ENTRY_8
          Indicates that this grid should use eight bits per grid entry.
private  int bitsPerEntry
           
static int DECOMPOSITION_TYPE_DIAGONAL
          Indicates that the grid should be decomposed into diagonally connected subregions.
static int DECOMPOSITION_TYPE_ORTHOGONAL
          Indicates that the grid should be decomposed into orthogonally connected subregions.
static int DIR_EAST
           
static int DIR_NORTH
           
static int DIR_NORTHEAST
           
static int DIR_NORTHWEST
           
static int DIR_SOUTH
           
static int DIR_SOUTHEAST
           
static int DIR_SOUTHWEST
           
static int DIR_WEST
           
private  int[] grid
           
private static int[] markers
           
private static int[] mask
           
private  int numColumns
           
private  int numRows
           
private static int[] perInt
           
private static int regionAt
           
private static Grid.RegionInfo[] regions
           
private  int[][] symmetries
           
 
Constructor Summary
private Grid()
           
  Grid(int numRows, int numColumns)
          Constructs a new Grid with the specified dimensions and 32 bits per entry.
  Grid(int numRows, int numColumns, int bitsPerEntry)
          Constructs a new Grid with the specified dimensions and bits per entry.
 
Method Summary
private  void buildSymmetries()
           
private static boolean checkSymmetries(int[][] symmetriesToCheck, int[] grid)
           
 java.lang.Object clone()
          This method may be called to create a new copy of the Object.
 java.lang.Object clone(int newBitsPerEntry)
           
private static int compareArrays(int[] grid1, int[] grid2)
           
 int compareTo(Grid other)
           
 int compareTo(java.lang.Object o)
          Compares this object with another, and returns a numerical result based on the comparison.
private  void constructGrid(int numRows, int numColumns, int bitsPerEntry)
           
 Grid[] decompose(int boundaryType, int decompositionType)
           
 boolean equals(java.lang.Object o)
          Tests whether two grids are equal.
 boolean equalsSymmetryInvariant(Grid other)
           
 int getAt(int row, int column)
           
static int getColumnShift(int direction, int distance)
           
 int getNumColumns()
           
 int getNumRows()
           
static int getRowShift(int direction, int distance)
           
 int hashCode()
          Get a value that represents this Object, as uniquely as possible within the confines of an int.
 int hashCodeSymmetryInvariant()
           
 boolean isValidShift(int row, int column, int direction, int distance)
           
private  void markRegion(int boundaryType, int decompositionType, int regionIndex, int row, int col)
           
private  void putAt(int[] array, int row, int column, int value)
           
 void putAt(int row, int column, int value)
           
private  void readObject(java.io.ObjectInputStream in)
           
 java.lang.String toString(java.lang.String charMap)
           
private  void writeObject(java.io.ObjectOutputStream out)
           
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DECOMPOSITION_TYPE_ORTHOGONAL

public static final int DECOMPOSITION_TYPE_ORTHOGONAL
Indicates that the grid should be decomposed into orthogonally connected subregions.

See Also:
Constant Field Values

DECOMPOSITION_TYPE_DIAGONAL

public static final int DECOMPOSITION_TYPE_DIAGONAL
Indicates that the grid should be decomposed into diagonally connected subregions.

See Also:
Constant Field Values

DIR_NORTH

public static final int DIR_NORTH
See Also:
Constant Field Values

DIR_EAST

public static final int DIR_EAST
See Also:
Constant Field Values

DIR_SOUTH

public static final int DIR_SOUTH
See Also:
Constant Field Values

DIR_WEST

public static final int DIR_WEST
See Also:
Constant Field Values

DIR_NORTHEAST

public static final int DIR_NORTHEAST
See Also:
Constant Field Values

DIR_SOUTHEAST

public static final int DIR_SOUTHEAST
See Also:
Constant Field Values

DIR_SOUTHWEST

public static final int DIR_SOUTHWEST
See Also:
Constant Field Values

DIR_NORTHWEST

public static final int DIR_NORTHWEST
See Also:
Constant Field Values

BITS_PER_ENTRY_1

public static final int BITS_PER_ENTRY_1
Indicates that this grid should use one bit per grid entry. The value of each entry must be either 0 or 1.

See Also:
Constant Field Values

BITS_PER_ENTRY_2

public static final int BITS_PER_ENTRY_2
Indicates that this grid should use two bits per grid entry. The value of each entry must be between 0 and 3, inclusive.

See Also:
Constant Field Values

BITS_PER_ENTRY_4

public static final int BITS_PER_ENTRY_4
Indicates that this grid should use four bits per grid entry. The value of each entry must be between 0 and 7, inclusive.

See Also:
Constant Field Values

BITS_PER_ENTRY_8

public static final int BITS_PER_ENTRY_8
Indicates that this grid should use eight bits per grid entry. The value of each entry must be between 0 and 255, inclusive.

See Also:
Constant Field Values

BITS_PER_ENTRY_16

public static final int BITS_PER_ENTRY_16
Indicates that this grid should use 16 bits per grid entry. The value of each entry must be between 0 and 65535, inclusive.

See Also:
Constant Field Values

BITS_PER_ENTRY_32

public static final int BITS_PER_ENTRY_32
Indicates that this grid should use 32 bits per grid entry. No restrictions are placed on the entry values.

See Also:
Constant Field Values

mask

private static final int[] mask

bits

private static final int[] bits

perInt

private static final int[] perInt

markers

private static int[] markers

regionAt

private static int regionAt

regions

private static Grid.RegionInfo[] regions

numRows

private int numRows

numColumns

private int numColumns

bitsPerEntry

private int bitsPerEntry

grid

private int[] grid

symmetries

private transient int[][] symmetries
Constructor Detail

Grid

private Grid()

Grid

public Grid(int numRows,
            int numColumns)
Constructs a new Grid with the specified dimensions and 32 bits per entry.

Grid

public Grid(int numRows,
            int numColumns,
            int bitsPerEntry)
Constructs a new Grid with the specified dimensions and bits per entry.

Method Detail

constructGrid

private void constructGrid(int numRows,
                           int numColumns,
                           int bitsPerEntry)

equals

public boolean equals(java.lang.Object o)
Tests whether two grids are equal. Two grids are considered equal if they have the same dimensions and all their entries agree; the number of bits per entry is ignored.

equalsSymmetryInvariant

public boolean equalsSymmetryInvariant(Grid other)

hashCode

public int hashCode()
Description copied from class: java.lang.Object
Get a value that represents this Object, as uniquely as possible within the confines of an int.

There are some requirements on this method which subclasses must follow:

  • Semantic equality implies identical hashcodes. In other words, if a.equals(b) is true, then a.hashCode() == b.hashCode() must be as well. However, the reverse is not necessarily true, and two objects may have the same hashcode without being equal.
  • It must be consistent. Whichever value o.hashCode() returns on the first invocation must be the value returned on all later invocations as long as the object exists. Notice, however, that the result of hashCode may change between separate executions of a Virtual Machine, because it is not invoked on the same object.

Notice that since hashCode is used in java.util.Hashtable and other hashing classes, a poor implementation will degrade the performance of hashing (so don't blindly implement it as returning a constant!). Also, if calculating the hash is time-consuming, a class may consider caching the results.

The default implementation returns System.identityHashCode(this)

hashCodeSymmetryInvariant

public int hashCodeSymmetryInvariant()

toString

public java.lang.String toString(java.lang.String charMap)

clone

public java.lang.Object clone()
Description copied from class: java.lang.Object
This method may be called to create a new copy of the Object. The typical behavior is as follows:
  • o == o.clone() is false
  • o.getClass() == o.clone().getClass() is true
  • o.equals(o) is true

However, these are not strict requirements, and may be violated if necessary. Of the three requirements, the last is the most commonly violated, particularly if the subclass does not override Object.equals(Object)>Object.equals(Object) 55 .

If the Object you call clone() on does not implement java.lang.Cloneable (which is a placeholder interface), then a CloneNotSupportedException is thrown. Notice that Object does not implement Cloneable; this method exists as a convenience for subclasses that do.

Object's implementation of clone allocates space for the new Object using the correct class, without calling any constructors, and then fills in all of the new field values with the old field values. Thus, it is a shallow copy. However, subclasses are permitted to make a deep copy.

All array types implement Cloneable, and override this method as follows (it should never fail):

 public Object clone()
 {
   try
     {
       super.clone();
     }
   catch (CloneNotSupportedException e)
     {
       throw new InternalError(e.getMessage());
     }
 }

clone

public java.lang.Object clone(int newBitsPerEntry)

compareTo

public int compareTo(Grid other)

compareArrays

private static int compareArrays(int[] grid1,
                                 int[] grid2)

compareTo

public int compareTo(java.lang.Object o)
Description copied from interface: java.lang.Comparable
Compares this object with another, and returns a numerical result based on the comparison. If the result is negative, this object sorts less than the other; if 0, the two are equal, and if positive, this object sorts greater than the other. To translate this into boolean, simply perform o1.compareTo(o2) <op> 0, where op is one of <, <=, =, !=, >, or >=.

You must make sure that the comparison is mutual, ie. sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) (where sgn() is defined as -1, 0, or 1 based on the sign). This includes throwing an exception in either direction if the two are not comparable; hence, compareTo(null) should always throw an Exception.

You should also ensure transitivity, in two forms: x.compareTo(y) > 0 && y.compareTo(z) > 0 implies x.compareTo(z) > 0; and x.compareTo(y) == 0 implies x.compareTo(z) == y.compareTo(z).

Specified by:
compareTo in interface java.lang.Comparable

getNumRows

public int getNumRows()

getNumColumns

public int getNumColumns()

getAt

public int getAt(int row,
                 int column)

putAt

public void putAt(int row,
                  int column,
                  int value)

putAt

private void putAt(int[] array,
                   int row,
                   int column,
                   int value)

isValidShift

public boolean isValidShift(int row,
                            int column,
                            int direction,
                            int distance)

getRowShift

public static int getRowShift(int direction,
                              int distance)

getColumnShift

public static int getColumnShift(int direction,
                                 int distance)

decompose

public Grid[] decompose(int boundaryType,
                        int decompositionType)

markRegion

private void markRegion(int boundaryType,
                        int decompositionType,
                        int regionIndex,
                        int row,
                        int col)

checkSymmetries

private static boolean checkSymmetries(int[][] symmetriesToCheck,
                                       int[] grid)

buildSymmetries

private void buildSymmetries()

writeObject

private void writeObject(java.io.ObjectOutputStream out)
                  throws java.io.IOException

readObject

private void readObject(java.io.ObjectInputStream in)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException
Overview  Package   Class  Use  Deprecated  Index 
Home >> All >> cgsuite >> [ util overview ]  PREV CLASS  NEXT CLASS
SUMMARY: JavaDoc of cgsuite.util.Grid JAVADOC | Sourc code of cgsuite.util.Grid SOURCE | Download cgsuite.util.Grid DOWNLOAD | NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD