adfasdfPARENT.java

package upperenv;

import java.util.ArrayList;

public abstract class UpperEnvelope {
	ArrayList<Bar> bars = new ArrayList<Bar>();
	ArrayList<Point> points = new ArrayList<Point>();
	
	int width = 0;
	int height = 0;
	
	
	private void _addBar (Bar bar) {
		this.bars.add(bar);
		
		this.width = bar.r > this.width ? bar.r : this.width;
		this.height = bar.height > this.height ? bar.height : this.height;
	}
	
	public void addBar (Bar bar) {
		_addBar(bar);
		calculateUpperEnvelope();
	}
	
	public void addBars (Bar[] bars) {
		for (int i = 0; i < bars.length; i++) {
			_addBar(bars[i]);
		}
		
		calculateUpperEnvelope();
	}
	
	public ArrayList<Point> getUpperEnvelope() {
		return points;
	}
	
	@Override
	public String toString() {		
		return points.toString();
	}
	
	protected abstract void calculateUpperEnvelope();
}

upperenvburtrforce.java

package upperenv;

import java.util.ArrayList;

public class UpperEnvelopeBruteForce extends UpperEnvelope {
	@Override
	protected void calculateUpperEnvelope() {
		ArrayList<Point> env = new ArrayList<Point>();
		
		int currentHeight = -1;
		
		for(int i = 1; i < this.width; i++) {
			int heightAtIndex = maxHeightAtPoint(i);
			if (heightAtIndex != currentHeight) {
				currentHeight = heightAtIndex;
				env.add(new Point(i, currentHeight));
			}
		}
		
		this.points = env;
	}
	
	private int maxHeightAtPoint(int x) {
		int max = 0;
		
		for (int i = 0; i < this.bars.size(); i++) {
			Bar b = this.bars.get(i);
			if (x >= b.l && x < b.r) {
				max = b.height > max ? b.height : max;
			}
		}
		
		return max;
	}
}