import java.awt.*;

abstract class Maze extends Canvas
{
    static final byte TOP = 0x01;
    static final byte RIGHT = 0x02;
    static final byte BOTTOM = 0x04;
    static final byte LEFT = 0x08;
    static final byte PATHON = 0x10;
    static final byte DIRTY = (byte) 0x80;

    protected byte [][] maze = null, path = null;
    protected int mazeWidth, mazeHeight, squareWidth, squareHeight,
	leftOffset, topOffset, pxoff, pyoff;
    protected int minXdirty, minYdirty, maxXdirty, maxYdirty;
    protected int startX, startY, finishX, finishY, destX, destY;
    protected int lineWidth = 1, lineHeight = 1, sqLineWidth, sqLineHeight,
	pathWidth, pathHeight;
    public boolean generating = false, solving = true;

    protected boolean displayPath = true;

    protected abstract byte initSq ();

    abstract boolean isOpen (int x, int y);
    abstract void generate (boolean displaySearch);
    abstract void stopGenerating ();
    abstract boolean traverse (int startX, int startY, int finishX,
			       int finishY, boolean displaySearch);
    abstract boolean traverse (int destX, int destY);
    abstract boolean won ();
    protected abstract void drawSquare (int x, int y);
    protected abstract void drawPathSquare (int px, int py, Color color);

    public boolean traverse (boolean displaySearch)
    {
	return traverse(startX, startY, finishX, finishY, displaySearch);
    }

    public byte sqr (int x, int y)
    {
	return (byte) (maze[x][y] & ~DIRTY);
    }

    public boolean inBounds (int x, int y)
    {
	return (x >= 0 && x < mazeWidth && y >= 0 && y < mazeHeight);
    }

    public Dimension getDimensions ()
    {
	return new Dimension(mazeWidth, mazeHeight);
    }

    public synchronized void setDimensions (int squaresWide, int squaresHigh)
    {
	if (mazeWidth != squaresWide || mazeHeight != squaresHigh) {
	    mazeWidth = Math.max(3, squaresWide);  // min maze width is 3 sqrs
	    mazeHeight = Math.max(3, squaresHigh);  // min maze height is 3 sqrs
	    maze = null;
	    resetMaze();
	}
    }

    protected long timer, maxFrameRate = 30L;
    protected void showMaze (boolean allDirty)
    {
	if (allDirty || offscreenImage == null)
	    repaint();
	else
	    repaint(leftOffset + minXdirty * squareWidth,
		    topOffset + minYdirty * squareHeight,
		    squareWidth * (maxXdirty - minXdirty + 1) + lineWidth,
		    squareHeight * (maxYdirty - minYdirty + 1) + lineHeight);
	try { wait(); } catch (InterruptedException e) {}
	long t = System.currentTimeMillis();
	if ((timer -= t - (1000L / maxFrameRate)) > 0)
	    try { Thread.sleep(timer); } catch (InterruptedException e) {}
	timer = System.currentTimeMillis();
    }

    protected void resetMaze ()
    {
	Dimension d = getSize();
	
	if (d.width <= 0  ||  d.height <= 0  ||  mazeWidth <= 0  ||  mazeHeight <= 0) {
	    return;
	}
	squareWidth = Math.max(2, (d.width - lineWidth) / mazeWidth);
	squareHeight = Math.max(2, (d.height - lineHeight) / mazeHeight);
	if (lineWidth >= squareWidth)  lineWidth = squareWidth - 1;
	if (lineHeight >= squareHeight)  lineHeight = squareHeight - 1;
	sqLineWidth = squareWidth + lineWidth;
	sqLineHeight = squareHeight + lineHeight;
	leftOffset = (d.width - (squareWidth * mazeWidth) - lineWidth) >> 1;
	topOffset = (d.height - (squareHeight * mazeHeight) - lineHeight) >> 1;
	
	int pw = squareWidth - lineWidth;
	pathWidth = (pw & 1) == 0 ? Math.max(2, (pw >> 1) & ~1) : Math.max(1, (pw >> 1) | 1);
	int ph = squareHeight - lineHeight;
	pathHeight = (ph & 1) == 0 ? Math.max(2, (ph >> 1) & ~1) : Math.max(1, (ph >> 1) | 1);
	pxoff = (sqLineWidth - pathWidth) >> 1;
	pyoff = (sqLineHeight - pathHeight) >> 1;

	offscreenImage = null;  // reallocate offscreenImage

	if (maze == null)
	    clearMaze();
    }

    protected int dirtySquare (int x, int y)
    {
	if (x < minXdirty) minXdirty = x;
	if (x > maxXdirty) maxXdirty = x;
	if (y < minYdirty) minYdirty = y;
	if (y > maxYdirty) maxYdirty = y;
	return maze[x][y] |= DIRTY;
    }

    protected void clearMaze ()
    {
	if (maze == null)
	    maze = new byte[mazeWidth][mazeHeight];
	byte sq = initSq();
	for (int xx = mazeWidth;  --xx >= 0; )
	    for (int yy = mazeHeight;  --yy >= 0; ) {
		maze[xx][yy] = sq;
	    }
	minXdirty = minYdirty = 0;
	maxXdirty = mazeWidth - 1;
	maxYdirty = mazeHeight - 1;
	startX = finishX = -1;
	//path = null;
    }

    public void setBounds (int x, int y, int width, int height)
    {
	Dimension d1 = getSize();
	super.setBounds (x, y, width, height);
	Dimension d2 = getSize();
	if (d1.width != d2.width  ||  d1.height != d2.height) {
	    resetMaze();
	    repaint();
	}
    }

    protected Image offscreenImage = null;
    protected Graphics offscr;

    public synchronized boolean activatePath (int x, int y) {
	path [x] [y] = PATHON;
	boolean left = inBounds (x-1, y) && path [x-1] [y] != 0
	    && (maze [x] [y] & LEFT) == 0,
	    right = inBounds (x+1, y) && path [x+1] [y] != 0
	    && (maze [x] [y] & RIGHT) == 0,
	    up = inBounds (x, y-1) && path [x] [y-1] != 0
	    && (maze [x] [y] & TOP) == 0,
	    down = inBounds (x, y+1) && path [x] [y+1] != 0
	    && (maze [x] [y] & BOTTOM) == 0;

	if (left) {
	    path [x] [y] |= LEFT;
	    path [x-1] [y] |= RIGHT;
	    dirtySquare (x-1, y);
	}
	if (right) {
	    path [x] [y] |= RIGHT;
	    path [x+1] [y] |= LEFT;
	    dirtySquare (x+1, y);
	}
	if (up) {
	    path [x] [y] |= TOP;
	    path [x] [y-1] |= BOTTOM;
	    dirtySquare (x, y-1);
	}
	if (down) {
	    path [x] [y] |= BOTTOM;
	    path [x] [y+1] |= TOP;
	    dirtySquare (x, y+1);
	}
	dirtySquare (x, y);
	return true;
    }

    public void setDest (int x, int y)
    {
	destX = (x-leftOffset) / squareWidth;
	destY = (y-topOffset) / squareHeight;
    }

    public void pathToSquare (int x, int y)
    {
	activatePath (x, y);
    }

    protected void drawTarget (int x, int y, Color color) {
	offscr.setColor(color);
	offscr.fillOval (x * squareWidth + leftOffset + pxoff,
			 y * squareHeight + topOffset + pyoff,
			 pathWidth+1, pathHeight+1);
    }

    public void paintOffscreenImage ()
    {
	boolean doAll = (offscreenImage == null);
	if (doAll) {
	    Dimension d = getSize ();
	    offscreenImage = createImage (d.width, d.height);
	    offscr = offscreenImage.getGraphics ();
	    offscr.setColor (getBackground ());
	    offscr.fillRect (0, 0, d.width, d.height);
	    minXdirty = minYdirty = 0;
	    maxXdirty = mazeWidth-1;
	    maxYdirty = mazeHeight-1;
	}
	
	offscr.setColor (Color.black);

	for (int x = minXdirty; x <= maxXdirty; x ++) {
	    for (int y = minYdirty; y <= maxYdirty; y ++) {
		if (doAll || (maze [x] [y] & DIRTY) != 0) {
		    drawSquare (x, y);
		    maze [x] [y] = sqr (x, y);

		    if (displayPath)
			drawPathSquare(x, y, Color.blue);
		    if (x == startX  &&  y == startY)
			drawTarget(x, y, Color.green);
		    if (x == finishX  &&  y == finishY)
			drawTarget(x, y, Color.red);
		}
	    }
	}

	maxXdirty = maxYdirty = -1;
	minXdirty = minYdirty = Integer.MAX_VALUE;

	if (won ()) {
	    Dimension d = getSize ();
	    offscr.setColor (Color.black);
	    int fontSize = d.width > d.height ? d.height / 5 :
		d.width / 10;
	    offscr.setFont (new Font ("Times New Roman", Font.BOLD, fontSize));
	    offscr.drawString ("You Win!", d.width/2-fontSize*2,
			       d.height /2);
	}
    }

    public synchronized void paint (Graphics g)
    {
	paintOffscreenImage ();
	if (offscreenImage != null)
	    g.drawImage (offscreenImage, 0, 0, this);
	notifyAll ();
    }

    public void update (Graphics g)
    {
	paint (g);
    }
}