import java.awt.*;
import java.util.*;
import java.awt.image.*;

public class Rects extends Vector{
	public Rectangle get(){
		Rectangle r = (Rectangle)firstElement();
		removeElement(r);
		return r;
	}
	public void add(Rectangle r){
	  synchronized(this){
		boolean indep = true;
		Enumeration e = elements();		
		while(e.hasMoreElements()){
			Rectangle a = (Rectangle)e.nextElement();
			int res = chkInc(a, r);
			if(res==1) return;
			if(res==-1) removeElement(a);
			if(res==2) indep = false;
		}
		if(indep){
			addElement(r);
			return;
		}
		add_sub(r, 0);
	  }
	}

	void add_sub(Rectangle r, int i){
		for(;i<size();i++){
			Rectangle a = (Rectangle)elementAt(i);
			int res = chkInc(a, r);
			if(res==1) return;
			if(res==2) continue;
			a = a.intersection(r);
			Vector v = div(r, a);
			for(int j=0;j<v.size();j++){
				add_sub((Rectangle)v.elementAt(j), i+1);
			}
			return;
		}
		addElement(r);
	}
	Vector div(Rectangle r, Rectangle a){
		Vector v = new Vector();
		if(r.x!=a.x){
			v.addElement(new Rectangle(r.x, r.y, a.x-r.x, r.height));
			r = new Rectangle(a.x, r.y, r.width-(a.x-r.x), r.height);
		}
		if(x2(r)!=x2(a)){
			v.addElement(new Rectangle(x2(a), r.y, x2(r)-x2(a), r.height));
			r = new Rectangle(r.x, r.y, x2(a)-r.x, r.height);
		}
		if(r.y!=a.y){
			v.addElement(new Rectangle(r.x, r.y, r.width, a.y-r.y));
			r = new Rectangle(r.x, a.y, r.width, r.height-(a.y-r.y));
		}
		if(y2(r)!=y2(a)){
			v.addElement(new Rectangle(r.x, y2(a), r.width, y2(r)-y2(a)));
			r = new Rectangle(r.x, r.y, r.width, y2(a)-r.y);
		}			
		return v;
	}

	public static int x2(Rectangle r){ return r.x+r.width; }
	public static int y2(Rectangle r){ return r.y+r.height; }

	// ex > in : return 1
	// ex < in : return -1
	// intersection ex in == null :  return 0;
	// else : return 2
	public static int chkInc(Rectangle ex, Rectangle in){
		if(!ex.intersects(in)) return 0;
		Rectangle isr = ex.intersection(in);
		if(isr.equals(in)) return 1;
		if(isr.equals(ex)) return -1;
		return 2;
	}

	//
	// len
	//
	public static double len(Point p, Rectangle r){
		return Pts.len(new Point(
			Pts.len(p.x, r.x, r.width),
			Pts.len(p.y, r.y, r.height)
		));
	}

	//
	// rot
	//
	public static Polygon rotoff(Rectangle r, Point o, Point prevV, Point nextV){
		return Polys.rotoff(poly(r), o, prevV, nextV);
	}
	public static Polygon rot(Rectangle r, Point prevV, Point nextV){
		return rotoff(r, new Point(0,0), prevV, nextV);
	}


	//
	// cast
	//
	public static Point p(Rectangle r){
		return new Point(r.x,r.y);
	}
	public static Dimension sz(Rectangle r){
		return new Dimension(r.width,r.height);
	}
	public static Point p2(Rectangle r){
		return new Point(r.x+r.width,r.y+r.height);
	}
	public static Polygon poly(Rectangle r){
		Polygon pl = new Polygon();
		Pts.add(pl, p(r));
		Pts.add(pl, new Point(p(r).x, p2(r).y));
		Pts.add(pl, p2(r));
		Pts.add(pl, new Point(p2(r).x, p(r).y));
		return pl;
	}

	public static Rectangle r(Dimension sz){
		return new Rectangle(sz);
	}
	public static Rectangle r(Point p){
		return new Rectangle(p);
	}
	public static Rectangle r(Point p, Dimension sz){
		return new Rectangle(p,sz);
	}
	public static Rectangle cenRect(Point cen, Dimension sz){
		return r(Pts.sub(cen,Pts.cen(sz)), sz);
	}

	//
	// draw
	//
	public static void draw(Graphics g, Rectangle r){
		g.drawRect(r.x,r.y,r.width,r.height);
	}
	public static void fill(Graphics g, Rectangle r){
		g.fillRect(r.x,r.y,r.width,r.height);
	}
	public static void clear(Graphics g, Rectangle r){
		g.clearRect(r.x,r.y,r.width,r.height);
	}
	public static void drawOval(Graphics g, Rectangle r){
		g.drawOval(r.x,r.y,r.width,r.height);
	}
	public static void fillOval(Graphics g, Rectangle r){
		g.fillOval(r.x,r.y,r.width,r.height);
	}
	public static void drawRound(Graphics g, Rectangle r, Dimension arc){
		g.drawRoundRect(r.x,r.y,r.width,r.height, arc.width,arc.height);
	}
	public static void draw3D(Graphics g, Rectangle r, boolean raised){
		g.draw3DRect(r.x,r.y,r.width,r.height, raised);
	}
	public static void fill3D(Graphics g, Rectangle r, boolean raised){
		g.fill3DRect(r.x,r.y,r.width,r.height, raised);
	}
	public static void drawImage(Graphics g, Image img, Rectangle r, 
			ImageObserver obs){
		g.drawImage(img, r.x,r.y,r.width,r.height, obs);
	}
}

// EOF