termat/hatena_treemap.html

## hatena_treemap.html
<html lang="jp" class="ui-mobile landscape">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta http-equiv="X-UA-Compatible" content="IE=8"/>
<base href=".">
<title>Hatemap</title>
<style type="text/css">
#toptitle{
	width:600px;
	margin: 0 auto;
	font-family: Georgia, Times, serif;
	font-size: 24px;
	font-weight: bold;
	color: #ffffff;
	background-color: #cccccc;
	vertical-align : bottom;
	line-height: 38px;
}
</style>
<script src="http://ajax.googleapis.com/ajax/libs/jquery/2.1.3/jquery.min.js"></script>
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/processing.js/1.4.8/processing.js"></script>
<script type="text/javascript" src="https://www.google.com/jsapi"></script>
<script type="text/javascript">
var scwidth;
var scheight;
var proc;
var root;
var tmp=[];
var urls=[
	['http://feeds.feedburner.com/hatena/b/hotentry'],
	['http://b.hatena.ne.jp/hotentry/social.rss',
		'http://b.hatena.ne.jp/hotentry/economics.rss',
		'http://b.hatena.ne.jp/hotentry/life.rss',
		'http://b.hatena.ne.jp/hotentry/entertainment.rss',
		'http://b.hatena.ne.jp/hotentry/knowledge.rss',
		'http://b.hatena.ne.jp/hotentry/it.rss',
		'http://b.hatena.ne.jp/hotentry/game.rss',
		'http://b.hatena.ne.jp/hotentry/fun.rss'],
	['http://b.hatena.ne.jp/entrylist?sort=hot&threshold=&mode=rss&']
];

google.load("feeds", "1");

$(document).ready(function(){
	scwidth=600;
	scheight=600;
	$("#canvas").attr("width",scwidth);
	$("#canvas").attr("height",scheight);
	initLayer();
	$("#layer").css("font-size","16px");
	$("#layer").css("padding","10px 0px 0px 10px");
	var canvas = document.getElementById('canvas');
	var codeElm = document.getElementById('processing-code');
	var code = codeElm.textContent || codeElm.innerText;
	proc=new Processing(canvas, code);
	var list=[];
	for(var i=0;i<urls[2].length;i++)list[i]=urls[2][i];
	hatebu_Init(list);
});

var initLayer=function(){
	var off=$("#canvas").offset();
	var ox=off.left;
	var oy=off.top+20;
	$("#layer").css("z-index","0");
	$("#layer").css("position","absolute");
	$("#layer").css("top",oy+10+"px");
	$("#layer").css("line-height","20px");
	$("#layer").css("left",(ox+20)+"px");
	$("#layer").css("width",(scwidth-40)+"px");
	var mm=Math.max(300,(scheight*0.45));
	$("#layer").css("height",mm+"px");
	$("#layer").css("background-color","#ffffff");
	$("#layer").css("opacity","0.9");
	$("#layer").css("display","none");
};

var hatebu_Init=function(list){
	page=0;
	numOfBookmark=0;
	tmp=[];
	root={name:"TOP",size:0};
	root.array=[];
	var now=new Date();
	var q=now.getMonth();
	var q2=now.getDate();
	var q3=now.getHours();
	hatebu_Analyze(list,q+"0"+q2+"0"+q3);
};

var hatebu_Analyze=function(list,dummy){
	startLoading();
	var url=list.shift();
	if(dummy)url=url+"?"+dummy;
	var feed = new google.feeds.Feed(url);
	feed.setNumEntries(100);
	feed.setResultFormat(google.feeds.Feed.MIXED_FORMAT);
	feed.load(function(result) {
		if (!result.error) {
			var entries = result.feed.entries;
			if(entries.length>0){
				for (var i = 0; i < entries.length; i++) {
					var obj=new Object();
					obj.name=entries[i].title;
					obj.link=entries[i].link;
					obj.content=entries[i].content;
					var category=$(entries[i].xmlNode.getElementsByTagNameNS("http://purl.org/dc/elements/1.1/","subject")[0]).text();
					if(!tmp[category]){
						tmp[category]={name:category};
						tmp[category].size=0;
						tmp[category].array=[];
						root.array.push(tmp[category]);
					}
					obj.size=parseInt($(entries[i].xmlNode.getElementsByTagNameNS("http://www.hatena.ne.jp/info/xmlns#","bookmarkcount")[0]).text());
					tmp[category].array.push(obj);
				}
			}
		}else{
			alert("エントリが見つかりませんでした。");
			return;
		}
		if(list.length>0){
			hatebu_Analyze(list,dummy);
		}else{
			proc.setRoot(root);
		}
	});
};

var startLoading=function(){
	closeLayer();
	proc.loading();
};

var showLayer=function(html,link){
	initLayer();
	var code=html.replace("blockquote","div");
	setTimeout(function(){
		$("#layer").css("display","inline");
		$("#layer").html(code);

		var msg=$("#layer div").text();
		var aa=$("#layer div p a").text();
		msg=msg.replace(aa,"");
		msg=msg.replace("続きを読む","");
		msg=replaceAll(msg,"\n","");
		msg=replaceAll(msg," ","");
		$("#layer div cite a").attr("target","_blank");
		var name=$("#layer div p a img:first").attr("src");
		if(name&&name.indexOf("http://b.hatena.ne.jp/")==-1)
			$("#layer div p a img:first").attr("height","90px");
		$("#layer div p a").attr("target","_blank");
		if($("#layer div p").length>=4){
			$("#layer div p:last").remove();
		}
	},500);
};

var closeLayer=function(){
	$("#layer").css("display","none");
	$("#layer").empty();
};

var arraycopy=function(src,srcPos,dest,destPos,length){
	while (length > 0){
	 dest[destPos] = src[srcPos];
	 srcPos++;
	 destPos++;
	 length--;
	}
};

var replaceAll=function(expression, org, dest){
	return expression.split(org).join(dest);
};
</script>

<script id="processing-code" type="application/processing">
BoundsIntegrator zoomBounds;
GroupItem rootItem;
LeafItem rolloverItem;
GroupItem taggedItem;
LeafItem zoomItem;
final int PIVOT_BY_MIDDLE = 1;
final int PIVOT_BY_SPLIT_SIZE = 2;
final int PIVOT_BY_BIGGEST = 3;
boolean isLoading=false;
float ATTRACTION = 0.8f;
float DAMPING = 0.4f;
int alphaL=25;

void setup() {
	size(scwidth,scheight);
	PFont font=createFont("FFScala", 24);
	textFont(font);
	textSize(16);
	zoomBounds = new BoundsIntegrator(0, 0, width, height);
	rectMode(CORNERS);
	smooth();
	noStroke();
	textMode(SCREEN);
}

void setRoot(array) {
	closeLayer();
	GroupItem tm = new GroupItem(null, array, 0, 0);
	tm.setBounds(0, 0, width, height);
	tm.contentsVisible = true;
	rootItem = tm;
	rootItem.zoomIn();
	rootItem.updateColors();
	isLoading=false;
}

void loading(){
	isLoading=true;
}

void drawLoading(){
	background(0);
	frameRate(10);
	noStroke();
	int r=5;
	int rr=10;
	int sx=scwidth/2-rr*2;
	int sy=scheight/2-rr*2;
	fill(126,126,126,alphaL);alphaL=(alphaL+10)%256;
	ellipse(sx+3*rr, sy+0*rr, 2*r, 2*r);
	fill(126,126,126,alphaL);alphaL=(alphaL+25)%256;
	ellipse(sx+5*rr, sy+1*rr, 2*r, 2*r);
	fill(126,126,126,alphaL);alphaL=(alphaL+25)%256;
	ellipse(sx+6*rr, sy+3*rr, 2*r, 2*r);
	fill(126,126,126,alphaL);alphaL=(alphaL+25)%256;
	ellipse(sx+5*rr, sy+5*rr, 2*r, 2*r);
	fill(126,126,126,alphaL);alphaL=(alphaL+25)%256;
	ellipse(sx+3*rr, sy+6*rr, 2*r, 2*r);
	fill(126,126,126,alphaL);alphaL=(alphaL+25)%256;
	ellipse(sx+1*rr, sy+5*rr, 2*r, 2*r);
	fill(126,126,126,alphaL);alphaL=(alphaL+25)%256;
	ellipse(sx+0*rr, sy+3*rr, 2*r, 2*r);
	fill(126,126,126,alphaL);alphaL=(alphaL+25)%256;
	ellipse(sx+1*rr, sy+1*rr, 2*r, 2*r);
}

void draw() {
	if(isLoading){
		drawLoading();
		return;
	}
	background(0);
	frameRate(30);
	zoomBounds.update();
	rolloverItem = null;
	taggedItem = null;
	if (rootItem != null) rootItem.draw();
	if (rolloverItem != null) rolloverItem.drawTitleBar();
	if (taggedItem != null) taggedItem.drawTag();
}

void mousePressed() {
	if (zoomItem != null) {
		zoomItem.mousePressed();
	}
}

void zoomOut(){
	if (zoomItem != null) {
		mouseButton=RIGHT;
		zoomItem.mousePressed();
	}
}

class BoundsIntegrator {
	float valueX, velocityX, accelerationX;
	float valueY, velocityY, accelerationY;
	float valueW, velocityW, accelerationW;
	float valueH, velocityH, accelerationH;
	float damping;
	float attraction;
	boolean targeting;
	float targetX, targetY, targetW, targetH;

	BoundsIntegrator(float x, float y, float w, float h) {
		this.valueX = x;
		this.valueY = y;
		this.valueW = w;
		this.valueH = h;
		this.damping = DAMPING;
		this.attraction = ATTRACTION;
	}

	void set(float x, float y, float w, float h) {
		this.valueX = x;
		this.valueY = y;
		this.valueW = w;
		this.valueH = h;
	}

	float getX() {
		return valueX;
	}

	float getY() {
		return valueY;
	}

	float getW() {
		return valueW;
	}

	float getH() {
		return valueH;
	}

	float spanX(float pointX, float start, float span) {
		if (valueW != 0) {
			float n = (pointX - valueX) / valueW;
			return start + n*span;
		} else {
			return Float.NaN;
		}
	}

	float spanY(float pointY, float start, float span) {
		if (valueH != 0) {
			float n = (pointY - valueY) / valueH;
			return start + n*span;
		} else {
			return Float.NaN;
		}
	}

	void setAttraction(float a) {
		attraction = a;
	}

	void setDamping(float d) {
		damping = d;
	}

	boolean update() {
		if (targeting) {
			accelerationX += attraction * (targetX - valueX);
			velocityX = (velocityX + accelerationX) * damping;
			valueX += velocityX;
			accelerationX = 0;
			boolean updated = (Math.abs(velocityX) > 0.0001f);
			accelerationY += attraction * (targetY - valueY);
			velocityY = (velocityY + accelerationY) * damping;
			valueY += velocityY;
			accelerationY = 0;
			updated |= (Math.abs(velocityY) > 0.0001f);
			accelerationW += attraction * (targetW - valueW);
			velocityW = (velocityW + accelerationW) * damping;
			valueW += velocityW;
			accelerationW = 0;
			updated |= (Math.abs(velocityW) > 0.0001f);
			accelerationH += attraction * (targetH - valueH);
			velocityH = (velocityH + accelerationH) * damping;
			valueH += velocityH;
			accelerationH = 0;
			updated |= (Math.abs(velocityH) > 0.0001f);
		}
		return false;
	}

	void target(float tx, float ty, float tw, float th) {
		targeting = true;
		targetX = tx;
		targetY = ty;
		targetW = tw;
		targetH = th;
	}

	void targetLocation(float tx, float ty) {
		targeting = true;
		targetX = tx;
		targetY = ty;
	}

	void targetSize(float tw, float th) {
		targeting = true;
		targetW = tw;
		targetH = th;
	}

	void targetX(float tx) {
		targeting = true;
		targetX = tx;
	}

	void targetY(float ty) {
		targeting = true;
		targetY = ty;
	}

	void targetW(float tw) {
		targeting = true;
		targetW = tw;
	}

	void targetH(float th) {
		targeting = true;
		targetH = th;
	}
}

class LeafItem extends SimpleMapItem {
	GroupItem parent;
	Object obj;
	String name;
	int level;
	color c;
	float hue;
	float brightness;
	float textPadding = 8;
	float boxLeft, boxTop;
	float boxRight, boxBottom;

	LeafItem(GroupItem parent, Object obj, int level, int order) {
		this.parent = parent;
		this.obj = obj;
		this.order = order;
		this.level = level;
		name=obj.name;
		if(name.length>30)name=name.substring(0,30)+"...";
		size = obj.size;
	}
	void updateColors() {
		if (parent != null) {
			hue = map(order, 0, parent.getItemCount(), 0, 360);
		}
		brightness = Math.min(100.0/((float)level*0.8),100.0);
		colorMode(HSB, 360, 100, 100);
		if (parent == zoomItem) {
			c = color(hue, 60, 60);
		} else if (parent != null) {
			color pc = color(parent.hue, 60, 60);
			c = color(hue, brightness, brightness);
			colorMode(RGB, 255);
			c=blendColor(c,pc,SCREEN)
		}
		colorMode(RGB, 255);
	}

	void calcBox() {
		boxLeft = zoomBounds.spanX(x, 0, width);
		boxRight = zoomBounds.spanX(x+w, 0, width);
		boxTop = zoomBounds.spanY(y, 0, height);
		boxBottom = zoomBounds.spanY(y+h, 0, height);
	}

	void draw() {
		calcBox();
		if(mouseInside()){
			fill(c,255);
		}else{
			fill(c,200);
		}
//		fill(c);
		rect(boxLeft, boxTop, boxRight, boxBottom);
		stroke(128);
		rect(boxLeft, boxTop, boxRight, boxBottom);
		if (textFits()) {
			drawTitle();
			drawTitle3();
		}else if(textFits2()){
			drawTitle2(14);
			drawTitle3();
		} else if (mouseInside()) {
			rolloverItem = this;
		}else{
			textSize(12);
			if(textFits2()){
				drawTitle2(12);
			}else{
				textSize(10);
				if(textFits2())drawTitle2(10)
			}
			drawTitle3();
		}
	}

	void drawTitleBar(){
		if (textFits()) {
			drawTitle();
			drawTitle3();
		}else if (textFits3()) {
			drawTitle();
			drawTitle3();
		}else if(textFits2()){
			drawTitle2(14);
			drawTitle3();
		}else{
			textSize(12);
			if(textFits2()){
				drawTitle2(12);
			}else{
				textSize(10);
				drawTitle2(10)
			}
			drawTitle3();
		}
		textSize(16);
	}

	void drawTitle() {
		fill(255, 200);
		textAlign(LEFT);
		text(name, boxLeft + textPadding, boxBottom - textPadding);
	}

	void drawTitle2(int n) {
		fill(255, 200);
		textSize(n);
		float ascent = textAscent();
		text(name,boxLeft + textPadding, boxBottom -ascent - textPadding*2,boxRight-boxLeft,ascent + textPadding*2);
		textSize(16);
	}
	void drawTitle3() {
		if(zoomItem!=this){
			fill(255, 200);
			float middleX = (boxLeft + boxRight) / 2;
			float middleY = (boxTop + boxBottom) / 2;
			String tp=this.size;
			int ww=(boxRight-boxLeft)/2;
			ww=(int)Math.min(ww,(boxBottom-boxTop)/2);
			if(ww>=192){
				textSize(128);
			}else if(ww>=96){
				textSize(64);
			}else if(ww>=48){
				textSize(32);
			}else if(ww>=24){
				textSize(16);
			}else if(ww>=18){
				textSize(12);
			}else if(ww>=12){
				textSize(8);
			}else{
				return ;
			}
			float ascent = textAscent();
			text(tp, boxLeft+5,boxTop+ascent+5);
			textSize(16);
		}
	}

	boolean textFits() {
		int s=64;
		while(s>16){
			textSize(s);
			if(checkTextFits(name)){
				return true;
			}else{
				s *=0.75;
			}
		}
		return false;
	}

	boolean checkTextFits(String n){
		float wide = textWidth(n) + textPadding*2;
		float high = textAscent() + textDescent() + textPadding*2;
		return (boxRight - boxLeft > wide) && (boxBottom - boxTop > high);
	}

	boolean textFits2() {
		int l=name.length()/2;
		if(l%2!=0)l++;
		String n2=name.substring(0,l);
		float wide = textWidth(n2) + textPadding*4;
		float high = textAscent()*3 + textDescent()*3 + textPadding*6;
		return (boxRight - boxLeft > wide) && (boxBottom - boxTop > high);
	}

	boolean textFits3() {
		float wide = textWidth(name) + textPadding*2;
		return (boxRight - boxLeft > wide);
	}

	boolean mouseInside() {
		return (mouseX > boxLeft && mouseX < boxRight &&
			mouseY > boxTop && mouseY < boxBottom);
	}

	boolean mousePressed() {
		if (mouseInside()) {
			if (mouseButton == LEFT) {
				if(parent.contentsVisible){
					if(parent.isZoom){
						if(zoomItem!=this){
							zoomItem = this;
							zoomBounds.target(x, y, w, h);
							showLayer(obj.content,obj.link);
						}else{
							showLayer(obj.content,obj.link);
						}
					}else{
						parent.zoomIn();
					}
				}else{
					parent.zoomIn();
				}
				return true;
			} else if (mouseButton == RIGHT) {
				if(zoomItem == this){
					zoomItem = parent;
					parent.zoomIn();
				}else if (parent == zoomItem) {
					parent.zoomOut();
				} else {
					parent.hideContents();
				}
				closeLayer();
				return true;
			}
		}
		return false;
	}
}

class GroupItem extends LeafItem implements MapModel {
	MapLayout algorithm = new SquarifiedLayout();
	Mappable[] items;
	boolean contentsVisible;
	boolean layoutValid;
	float darkness;
	boolean isZoom=false;
	GroupItem(GroupItem parent, Object folder, int level, int order) {
		super(parent, folder, level, order);
		ArrayList contents = folder.array;
		if (contents) {
			contents = sort(contents);
			items = new Mappable[contents.length];
			int count = 0;
			for (int i = 0; i < contents.length; i++) {
				if (contents[i].array) {
					GroupItem newItem = new GroupItem(this, contents[i], level+1, count);
					items[count++] = newItem;
					size += newItem.getSize();
				} else {
					LeafItem newItem = new LeafItem(this, contents[i], level+1, count);
					items[count++] = newItem;
					size += newItem.getSize();
				}
			}
			if (count != items.length) {
				items = (Mappable[]) subset(items, 0, count);
			}
		} else {
			items = new Mappable[0];
		}
	}

	void updateColors() {
		super.updateColors();
		for (int i = 0; i < items.length; i++) {
			LeafItem fi = (LeafItem) items[i];
			fi.updateColors();
		}
	}

	void checkLayout() {
		if (!layoutValid) {
			if (getItemCount() != 0) {
				algorithm.layout(this, bounds);
			}
			layoutValid = true;
		}
	}

	boolean mousePressed() {
		if (mouseInside()) {
			if (contentsVisible) {
				for (int i = 0; i < items.length; i++) {
					LeafItem fi = (LeafItem) items[i];
					if (fi.mousePressed()) {
						return true;
					}
				}
			} else {
				if (mouseButton == LEFT) {
					if (parent == zoomItem) {
						showContents();
					} else {
						parent.zoomIn();
					}
				} else if (mouseButton == RIGHT) {
					if (parent == zoomItem) {
						parent.zoomOut();
					} else {
						parent.hideContents();
					}
				}
				return true;
			}
		}
		return false;
	}

	void zoomOut() {
		if (parent != null) {
			for (int i = 0; i < items.length; i++) {
				if (items[i] instanceof GroupItem) {
					((GroupItem)items[i]).hideContents();
				}
			}
			parent.zoomIn();
		}
		isZoom=false;
	}

	void zoomIn() {
		zoomItem = this;
		zoomBounds.target(x, y, w, h);
		isZoom=true;
	}

	void showContents() {
		contentsVisible = true;
	}

	void hideContents() {
		if (parent != null)contentsVisible = false;
	}

	void draw() {
		checkLayout();
		calcBox();
		if (contentsVisible) {
			for (int i = 0; i < items.length; i++) {
				items[i].draw();
			}
		} else {
			super.draw();
		}
		if (contentsVisible) {
			if (mouseInside()) {
				if (parent == zoomItem) {
					taggedItem = this;
				}
			}
		}
		if (mouseInside()) {
			darkness *= 0.05;
		} else {
			darkness += (150 - darkness) * 0.05;
		}
		darkness=Math.min(darkness,80);
		if (parent == zoomItem) {
			colorMode(RGB, 255);
			fill(0, darkness);
			rect(boxLeft, boxTop, boxRight, boxBottom);
		}
	}

	void drawTitle() {
		if (!contentsVisible) super.drawTitle();
	}

	void drawTag() {
		float boxHeight = textAscent() + textPadding*2;
		if (boxBottom - boxTop > boxHeight*2) {
			fill(0, 128);
			rect(boxLeft, boxTop, boxRight, boxTop+boxHeight);
			fill(255);
			textAlign(LEFT, TOP);
			text(name, boxLeft+textPadding, boxTop+textPadding);
		} else if (boxTop > boxHeight) {
			fill(0, 128);
			rect(boxLeft, boxTop-boxHeight, boxRight, boxTop);
			fill(255);
			text(name, boxLeft+textPadding, boxTop-textPadding);
		} else if (boxBottom + boxHeight < height) {
			fill(0, 128);
			rect(boxLeft, boxBottom, boxRight, boxBottom+boxHeight);
			fill(255);
			textAlign(LEFT, TOP);
			text(name, boxLeft+textPadding, boxBottom+textPadding);
		}
	}

	Mappable[] getItems() {
		return items;
	}

	int getItemCount() {
		return items.length;
	}
}

class Rect{
	double x,y,w,h;

	Rect(){
		this(0,0,1,1);
	}

	Rect(Rect r){
		setRect(r.x, r.y, r.w, r.h);
	}

	Rect(double x, double y, double w, double h){
		setRect(x, y, w, h);
	}

	void setRect(double x, double y, double w, double h) {
		this.x = x;
		this.y = y;
		this.w = w;
		this.h = h;
    }

	double aspectRatio(){
		return Math.max(w/h, h/w);
	}

	double distance(Rect r){
		return Math.sqrt((r.x-x)*(r.x-x)+
					(r.y-y)*(r.y-y)+
					(r.w-w)*(r.w-w)+
					(r.h-h)*(r.h-h));
	}

	Rect copy(){
		return new Rect(x,y,w,h);
	}

	String toString(){
		return "Rect: "+x+", "+y+", "+w+", "+h;
	}
}
interface MapModel{
	Mappable[] getItems();
}

interface MapLayout{
	void layout(MapModel model, Rect bounds);
	void layout(MapModel model, double x, double y, double w, double h);
}

interface Mappable {
	double getSize();
	void setSize(double size);
	Rect getBounds();
	void setBounds(Rect bounds);
	void setBounds(double x, double y, double w, double h);
	int getOrder();
	void setOrder(int order);
	int getDepth();
	void setDepth(int depth);
	void draw();
}

class SimpleMapItem implements Mappable {
	double size;
	Rect bounds;
	int order = 0;
	int depth;
	float x, y, w, h;

	SimpleMapItem() {
		this(1, 0);
	}

	SimpleMapItem(double size, int order) {
		this.size = size;
		this.order = order;
		bounds = new Rect();
	}

	double getSize() {
		return size;
	}

	void setSize(double size) {
		this.size = size;
	}

	void incrementSize() {
		size++;
	}

	Rect getBounds() {
		return bounds;
	}

	void setBounds(Rect bounds) {
		this.bounds = bounds;
		x = (float) bounds.x;
		y = (float) bounds.y;
		w = (float) bounds.w;
		h = (float) bounds.h;
	}

	void setBounds(double bx, double by, double bw, double bh) {
		setBounds(new Rect(bx, by, bw, bh));
	}

	int getOrder() {
		return order;
	}

	void setOrder(int order) {
		this.order = order;
	}

	void setDepth(int depth) {
		this.depth = depth;
	}

	int getDepth() {
		return depth;
	}

	void draw() {}
}

class SquarifiedLayout implements MapLayout{
	int VERTICAL=0, HORIZONTAL=1;
	int ASCENDING=0, DESCENDING=1;

	void layout(MapModel model, Rect bounds){
		layout(model.getItems(),bounds);
	}
	void layout(MapModel model, double x, double y, double w, double h){
		layout(model, new Rect(x, y, w, h));
	}

	void layout(Mappable[] items, Rect bounds){
		if(!items.length)items=items.getItems();
		layout(sortDescending(items),0,items.length-1,bounds);
	}

	void layout(Mappable[] items, int start, int end, Rect bounds){
		if (start>end) return;
		if (end-start<2){
			layoutBest(items,start,end,bounds);
			return;
		}
		double x=bounds.x, y=bounds.y, w=bounds.w, h=bounds.h;
		double total=sum(items, start, end);
		int mid=start;
		double a=items[start].getSize()/total;
		double b=a;
		if (w<h){
			while (mid<=end){
				double aspect=normAspect(h,w,a,b);
				double q=items[mid].getSize()/total;
				if (normAspect(h,w,a,b+q)>aspect) break;
				mid++;
				b+=q;
			}
			layoutBest(items,start,mid,new Rect(x,y,w,h*b));
			layout(items,mid+1,end,new Rect(x,y+h*b,w,h*(1-b)));
		}else{
			while (mid<=end){
				double aspect=normAspect(w,h,a,b);
				double q=items[mid].getSize()/total;
				if (normAspect(w,h,a,b+q)>aspect) break;
				mid++;
				b+=q;
			}
			layoutBest(items,start,mid,new Rect(x,y,w*b,h));
			layout(items,mid+1,end,new Rect(x+w*b,y,w*(1-b),h));
		}
	}

	void layoutBest(Mappable[] items, int start, int end, Rect bounds){
		sliceLayout(items,start,end,bounds,
			bounds.w>bounds.h ? HORIZONTAL : VERTICAL, ASCENDING);
	}

	void layoutBest(Mappable[] items, int start, int end, Rect bounds, int order){
		sliceLayout(items,start,end,bounds,
			bounds.w>bounds.h ? HORIZONTAL : VERTICAL, order);
	}

	double aspect(double big, double small, double a, double b){
		return (big*b)/(small*a/b);
	}

	double normAspect(double big, double small, double a, double b){
		double x=aspect(big,small,a,b);
		if (x<1) return 1/x;
		return x;
	}

	double sum(Mappable[] items, int start, int end){
		double s=0;
		for (int i=start; i<=end; i++)
			s+=items[i].getSize();
		return s;
	}

	String getName(){
		return "Squarified";
	}

	public String getDescription(){
		return "Algorithm used by J.J. van Wijk.";
	}

	double totalSize(Mappable[] items){
		return totalSize(items,0,items.length-1);
	}

	double totalSize(Mappable[] items, int start, int end){
		double sum=0;
		for (int i=start; i<=end; i++)
			sum+=items[i].getSize();
		return sum;
	}

	Mappable[] sortDescending(Mappable[] items){
		Mappable[] s=new Mappable[items.length];
		arraycopy(items,0,s,0,items.length);
		int n=s.length;
		boolean outOfOrder=true;
		while (outOfOrder){
			outOfOrder=false;
			for (int i=0; i<n-1; i++){
				boolean wrong=(s[i].getSize()<s[i+1].getSize());
				if (wrong){
					Mappable temp=s[i];
					s[i]=s[i+1];
					s[i+1]=temp;
					outOfOrder=true;
				}
			}
		}
		return s;
	}

	void sliceLayout(Mappable[] items, int start, int end, Rect bounds, int orientation){
		sliceLayout(items,start,end,bounds,orientation,ASCENDING);
	}

	void sliceLayout(Mappable[] items, int start, int end, Rect bounds, int orientation, int order){
		double total=totalSize(items, start, end);
		double a=0;
		boolean vertical=orientation==VERTICAL;
		for (int i=start; i<=end; i++){
			Rect r=new Rect();
			double b=items[i].getSize()/total;
			if (vertical){
				r.x=bounds.x;
				r.w=bounds.w;
				if (order==ASCENDING){
					r.y=bounds.y+bounds.h*a;
				}else{
					r.y=bounds.y+bounds.h*(1-a-b);
				}
				r.h=bounds.h*b;
			}else{
				if (order==ASCENDING){
					r.x=bounds.x+bounds.w*a;
				}else{
					r.x=bounds.x+bounds.w*(1-a-b);
				}
				r.w=bounds.w*b;
				r.y=bounds.y;
				r.h=bounds.h;
			}
			items[i].setBounds(r);
			a+=b;
		}
	}
}
</script>
</head>
<body>
	<div id="toptitle">　はてなブックマーク TreeMap</div><br />
	<div><center><canvas id="canvas"></canvas></center></div>
	<div id="layer"></div>
</body>
</html>