#!/bin/nawk -f

BEGIN {
	num_nodes = 0
	root = -1
}

{
	start[num_nodes] = $1
	finish[num_nodes] = $2
	out[num_nodes] = $3
	weight[num_nodes] = $4
	num_nodes++
}

END {
	# Hu-Tucker algorithm (see e.g. Knuth 6.2.2)
	# Phase 1: combine min_weight weights not separated by leaves
	make_list()
	for (i = 1; i < num_nodes; i++) {
		best_l = succ[root]
		best_r = succ[best_l]
		min_weight = weight[best_l] + weight[best_r]
		for (l = succ[root]; succ[l] != root; l = succ[l]) {
			wl = weight[l]
			for (r = succ[l]; r != root; r = succ[r]) {
				wt = wl + weight[r]
				if (wt < min_weight) {
					min_weight = wt
					best_l = l
					best_r = r
				}
				if (leaf(r))
					break
			}
		}
		new = num_nodes + i - 1
		weight[new] = min_weight
		replace(new, best_l, best_r)
	}
	# Phase 2: mark all leaves with their levels
	mark(succ[root], 0)
	# Phase 3: combine by levels
	make_list()
	for (i = 1; i < num_nodes; i++) {
		max_depth = 0
		for (l = succ[root]; succ[l] != root; l = r) {
			r = succ[l]
			if (depth[l] == depth[r] && depth[l] > max_depth) {
				max_depth = depth[l];
				best_l = l
			}
		}
		new = num_nodes + i - 1
		best_r = succ[best_l]
		depth[new] = max_depth - 1
		start[new] = start[best_l]
		middle[new] = start[best_r]
		replace(new, best_l, best_r)
	}

	total_path = total_weight = 0
	for (i = 0; i < num_nodes; i++) {
		total_path += depth[i]*weight[i]
		total_weight += weight[i]
	}
	printf("\t/* average depth = %g */\n", total_path/total_weight)

	show(succ[root], 0)
}

# doubly linked list

function make_list() {
	for (i = 0; i < num_nodes; i++) {
		succ[i-1] = i
		prev[i] = i-1
	}
	succ[num_nodes-1] = root
	prev[root] = num_nodes-1
}

function replace(new, l, r) {
	left[new] = l
	right[new] = r
	add_item(new, l)
	del_item(l)
	del_item(r)
}

function del_item(np) {
	succ[prev[np]] = succ[np]
	prev[succ[np]] = prev[np]
}

function add_item(new, old) {
	succ[new] = old
	prev[new] = prev[old]
	succ[prev[old]] = new
	prev[old] = new
}

# binary tree

function leaf(np) {
	return np < num_nodes
}

function mark(np, level) {
	if (leaf(np))
		depth[np] = level
	else {
		mark(left[np], level+1)
		mark(right[np], level+1)
	}
}

function show(np) {
	if (leaf(np)) {
		indent(depth[np])
		if (start[np] == finish[np])
			print "out = OPOS(0x" out[np] "L);"
		else
			print "out = code + (OPOS(0x" out[np] "L) - IPOS(0x" start[np] "L));"
	}
	else {
		indent(depth[np])
		print "if (code < IPOS(0x" middle[np] "L))"
		show(left[np])
		indent(depth[np])
		print "else"
		show(right[np])
	}
}

function indent(level) {
	printf("\t")
	for (i = 0; i < level; i++)
		printf("  ")
}