import java.util.*;
class CubeSearch3
{
private static final boolean trace = false;
private static final boolean verify = false;
public static void main(String args[])
{
CubeSearch3 cubeSearch = new CubeSearch3(64);
if (trace && verify)
{
cubeSearch.search(3+" "+4+" "+5, 3,4,4); // Gefunden im 3er
cubeSearch.search(3+" "+4+" "+5, 2,3,3); // Gefunden im 5er
cubeSearch.search(3+" "+4+" "+5, 1,2,2); // Gefunden im 7er
cubeSearch.search(3+" "+4+" "+5, 0,1,1); // Gefunden im 9er
cubeSearch.search(3+"x"+4+"x"+5, 0,7,1); // Nie gefunden
}
else
{
cubeSearch.benchmark();
}
}
// NUR verwendet wenn verify==true, um zu verifizieren,
// dass nie eine Zelle doppelt geprüft wird
private HashSet checked = new HashSet();
private Object cube[][][];
private int size;
public CubeSearch3(int size)
{
this.size = size;
cube = new Object[size][size][size];
init();
}
private void init()
{
System.out.println("Initializing...");
for (int x=0; x<cube.length; x++)
{
for (int y=0; y<cube[x].length; y++)
{
for (int z=0; z<cube[x][y].length; z++)
{
cube[x][y][z] = x+" "+y+" "+z;
}
}
}
System.out.println("Initializing... DONE");
}
public void benchmark()
{
int runs = 100;
long startTime = System.currentTimeMillis();
for (int i=0; i<runs; i++)
{
int x = (int)(Math.random() * size);
int y = (int)(Math.random() * size);
int z = (int)(Math.random() * size);
int xStart = (int)(Math.random() * size);
int yStart = (int)(Math.random() * size);
int zStart = (int)(Math.random() * size);
if (x==xStart && y==yStart && z==zStart)
{
i--;
continue;
}
Object element = x+" "+y+" "+z;
if (!search(element, xStart, yStart, zStart))
{
System.out.println("Error: Element "+element+" not found!");
if (verify)
{
verifyChecked();
}
}
}
long endTime = System.currentTimeMillis();
float avgTime = (float)(endTime-startTime)/runs;
System.out.println("Average time "+avgTime+" ms");
}
private boolean search(Object element, int x, int y, int z)
{
Object start = x+" "+y+" "+z;
if (verify)
{
checked.clear();
checked.add(start);
}
System.out.println("Searching for "+element+" starting at "+start);
return searchImpl(element, x,y,z);
}
private void verifyChecked()
{
for (int x=0; x<cube.length; x++)
{
for (int y=0; y<cube[x].length; y++)
{
for (int z=0; z<cube[x][y].length; z++)
{
Object e = x+" "+y+" "+z;
if (!checked.contains(e))
{
System.out.println("Did not check "+e);
}
}
}
}
}
//------------------------------------------------------------------------
// Wird aufgerufen, um die gegebene Zelle zu überprüfen
private boolean check(Object element, int x, int y, int z)
{
if (verify)
{
if (x < 0 || x >= size || y < 0 || y >= size || z < 0 || z >= size)
{
System.out.println("Should not check "+x+" "+y+" "+z);
return false;
}
if (checked.contains(cube[x][y][z]))
{
System.out.println("Checked twice: "+cube[x][y][z]);
}
checked.add(cube[x][y][z]);
}
if (trace) System.out.println("Checking "+x+" "+y+" "+z);
if (cube[x][y][z].equals(element))
{
System.out.println("Found at "+x+" "+y+" "+z);
return true;
}
return false;
}
//------------------------------------------------------------------------
public boolean searchImpl(Object element, int x, int y, int z)
{
for (int n=1; n<size; n++)
{
if (trace) System.out.println("Checking cube of size "+(2*n+1));
if (search(element, x-n, y-n, z-n, x+n, y+n, z+n)) return true;
}
return false;
}
private boolean search(Object element,
int sx0, int sy0, int sz0,
int sx1, int sy1, int sz1)
{
if (trace) System.out.println("Search "+sx0+" "+sy0+" "+sz0+" to "+sx1+" "+sy1+" "+sz1);
int x0 = Math.max(sx0, 0);
int y0 = Math.max(sy0, 0);
int z0 = Math.max(sz0, 0);
int x1 = Math.min(sx1, size-1);
int y1 = Math.min(sy1, size-1);
int z1 = Math.min(sz1, size-1);
// Kanten entlang X
if (trace) System.out.println("Edges X");
if (sy0 >= 0 && sz0 >= 0 && checkEdgeX(element, x0, x1, sy0, sz0)) return true;
if (sy0 >= 0 && sz1 < size && checkEdgeX(element, x0, x1, sy0, sz1)) return true;
if (sy1 < size && sz0 >= 0 && checkEdgeX(element, x0, x1, sy1, sz0)) return true;
if (sy1 < size && sz1 < size && checkEdgeX(element, x0, x1, sy1, sz1)) return true;
if (sx0 >= 0) x0++;
if (sy0 >= 0) y0++;
if (sz0 >= 0) z0++;
if (sx1 < size) x1--;
if (sy1 < size) y1--;
if (sz1 < size) z1--;
// Kanten entlang Y
if (trace) System.out.println("Edges Y");
if (sx0 >= 0 && sz0 >= 0 && checkEdgeY(element, y0, y1, sx0, sz0)) return true;
if (sx0 >= 0 && sz1 < size && checkEdgeY(element, y0, y1, sx0, sz1)) return true;
if (sx1 < size && sz0 >= 0 && checkEdgeY(element, y0, y1, sx1, sz0)) return true;
if (sx1 < size && sz1 < size && checkEdgeY(element, y0, y1, sx1, sz1)) return true;
// Kanten entlang Z
if (trace) System.out.println("Edges Z");
if (sx0 >= 0 && sy0 >= 0 && checkEdgeZ(element, z0, z1, sx0, sy0)) return true;
if (sx0 >= 0 && sy1 < size && checkEdgeZ(element, z0, z1, sx0, sy1)) return true;
if (sx1 < size && sy0 >= 0 && checkEdgeZ(element, z0, z1, sx1, sy0)) return true;
if (sx1 < size && sy1 < size && checkEdgeZ(element, z0, z1, sx1, sy1)) return true;
// Linke und rechte Fläche
if (trace) System.out.println("Left and right face");
if (sx0 >= 0 && checkFaceX(element, y0, z0, y1, z1, sx0)) return true;
if (sx1 < size && checkFaceX(element, y0, z0, y1, z1, sx1)) return true;
// Untere und obere Fläche
if (trace) System.out.println("Bottom and top face");
if (sy0 >= 0 && checkFaceY(element, x0, z0, x1, z1, sy0)) return true;
if (sy1 < size && checkFaceY(element, x0, z0, x1, z1, sy1)) return true;
// Vordere und hintere Fläche
if (trace) System.out.println("Front and back face");
if (sz0 >= 0 && checkFaceZ(element, x0, y0, x1, y1, sz0)) return true;
if (sz1 < size && checkFaceZ(element, x0, y0, x1, y1, sz1)) return true;
return false;
}
private boolean checkEdgeX(Object element, int x0, int x1, int yn, int zn)
{
if (trace) System.out.println("Edge X from "+x0+" "+yn+" "+zn+" to "+x1+" "+yn+" "+zn);
for (int x=x0; x<=x1; x++)
{
if (check(element, x,yn,zn)) return true;
}
return false;
}
private boolean checkEdgeY(Object element, int y0, int y1, int xn, int zn)
{
if (trace) System.out.println("Edge Y from "+xn+" "+y0+" "+zn+" to "+xn+" "+y1+" "+zn);
for (int y=y0; y<=y1; y++)
{
if (check(element, xn,y,zn)) return true;
}
return false;
}
private boolean checkEdgeZ(Object element, int z0, int z1, int xn, int yn)
{
if (trace) System.out.println("Edge Z from "+xn+" "+yn+" "+z0+" to "+xn+" "+yn+" "+z1);
for (int z=z0; z<=z1; z++)
{
if (check(element, xn,yn,z)) return true;
}
return false;
}
private boolean checkFaceX(Object element, int y0, int z0, int y1, int z1, int xn)
{
if (trace) System.out.println("Face X from "+xn+" "+y0+" "+z0+" to "+xn+" "+y1+" "+z1);
for (int y=y0; y<=y1; y++)
{
for (int z=z0; z<=z1; z++)
{
if (check(element, xn,y,z)) return true;
}
}
return false;
}
private boolean checkFaceY(Object element, int x0, int z0, int x1, int z1, int yn)
{
if (trace) System.out.println("Face Y from "+x0+" "+yn+" "+z0+" to "+x0+" "+yn+" "+z1);
for (int x=x0; x<=x1; x++)
{
for (int z=z0; z<=z1; z++)
{
if (check(element, x,yn,z)) return true;
}
}
return false;
}
private boolean checkFaceZ(Object element, int x0, int y0, int x1, int y1, int zn)
{
if (trace) System.out.println("Face Z from "+x0+" "+y0+" "+zn+" to "+x1+" "+y1+" "+zn);
for (int x=x0; x<=x1; x++)
{
for (int y=y0; y<=y1; y++)
{
if (check(element, x,y,zn)) return true;
}
}
return false;
}
}
