public class Terrain
{
public int X[];
public int Y[];
public double k;
public int minY;
public int maxY;
public int size;
public Space parent;
public int depth;
public int lpY;
public int lpX;
public int lpSize;
public int lpRealSize;
    
public Terrain(Space canvas, int d, double coeff, int y0, int y1, int mnY, int mxY)
    {
	k = coeff;
	minY = mnY;
	maxY = mxY;
	parent = canvas;
	if(d < 4)
	    depth = 4;
	else
	    depth = d;
	
	TerrainVertexStack TVS = new TerrainVertexStack();
	TVS.add(0, y0);
	TVS.add(parent.width, y1);
	generate(0, parent.width, y0, y1, depth, TVS);
	size = TVS.count+2;
	X = new int[size];
	Y = new int[size];
	X[0] = 0;
	Y[0] = parent.height;
	X[size-1] = parent.width;
	Y[size-1] = parent.height;
	int pos = 1;
	TerrainVertexLink index = TVS.head;
	while(index != null)
	    {
		X[pos] = index.X;
		Y[pos] = parent.height - index.Y;
		pos++;
		index = index.next;
	    }
	int len = (int)Math.pow(2, depth - 4);
	lpX = (int)(Math.random()*(size-len-2)+1);
	lpY = Y[lpX];
	lpSize = (int)(parent.width/size*len + 0.5);
	for(int i=1; i<=len; i++)
	    {
		Y[lpX+i]=lpY;
	    }
	lpRealSize = (int)(X[lpX+len]-X[lpX] + 0.5);
	lpX = X[lpX];
    }

private void generate(int X1, int X2, int Y1, int Y2, int depth, TerrainVertexStack TVS)
    {
	if(depth == 0)
	    return;
	int tempX;
	int tempY;
	
	tempX = (int)(X2+X1)/2;
	while(true)
	    {
		tempY = (int)((X2-X1)/2*k*(Math.random()-0.5)+(Y2+Y1)/2);
		if(tempY <= maxY && tempY >= minY)
		    break;
	    }
	TVS.add(tempX, tempY);
	generate(X1, tempX, Y1, tempY,depth-1, TVS);
	generate(tempX, X2, tempY, Y2, depth-1, TVS);
    }

public EdgeList span(int Xmin, int Xmax)
    {
	EdgeList EL = new EdgeList();
	int limit = size-2;
	for(int i=1; i<limit; i++)
	    {
		if(X[i]<=Xmin && X[i+1]>=Xmin)
		    EL.add(X[i], Y[i], X[i+1], Y[i+1]);
		else if(X[i]<=Xmax && X[i+1]>=Xmax)
		    EL.add(X[i], Y[i], X[i+1], Y[i+1]);
		else if(X[i]>=Xmin && X[i+1]<=Xmax)
		    EL.add(X[i], Y[i], X[i+1], Y[i+1]);
	    }
	if((X[limit]-parent.width-1)<=Xmin && X[1]>=Xmin)
	    EL.add(X[limit]-parent.width-1, Y[limit], X[1], Y[1]);
	else if((X[limit]-parent.width-1)<=Xmax && X[1]>=Xmax)
	    EL.add((X[limit]-parent.width-1), Y[limit], X[1], Y[1]);
	else if((X[limit]-parent.width-1)>=Xmin && X[1]<=Xmax)
	    EL.add((X[limit]-parent.width-1), Y[limit], X[1], Y[1]);
	return EL;
    }


public void reset(int d, double coeff, int y0, int y1)
    {
	k = coeff;
	if(d < 4)
	    depth = 4;
	else
	    depth = d;
	
	TerrainVertexStack TVS = new TerrainVertexStack();
	TVS.add(0, y0);
	TVS.add(parent.width, y1);
	generate(0, parent.width, y0, y1, depth, TVS);
	size = TVS.count+2;
	X = null;
	Y = null;
	X = new int[size];
	Y = new int[size];
	X[0] = 0;
	Y[0] = parent.height;
	X[size-1] = parent.width-1;
	Y[size-1] = parent.height;
	int pos = 1;
	TerrainVertexLink index = TVS.head;
	while(index != null)
	    {
		X[pos] = index.X;
		Y[pos] = parent.height - index.Y;
		pos++;
		index = index.next;
	    }
	int len = (int)Math.pow(2, depth - 4);
	lpX = (int)(Math.random()*(size-len-2)+1);
	lpY = Y[lpX];
	lpSize = (int)(parent.width/size*len + 0.5);
	for(int i=1; i<=len; i++)
	    {
		Y[lpX+i]=lpY;
	    }
	lpX = X[lpX];
    }    
}