// Karmarkar-Karp algorithm for multi-way partitioning
// From Korf, Richard (1997) A complete anytime algorithm for
// number partitioning. Artificial Intelligence 106:181.
// http://www.cs.pdx.edu/~bart/cs510cs/papers/korf-ckk.pdf
// see page 20 Section 7.3 Karmarkar-Karp Heuristic.

// 6/20/2007 very wasteful of memory. Just trying to get the algorithm
// working. Also very wasteful of cpu time. Should replace all the sort
// with maintained order.

begintemplate Partition
public vec, merge
objref vec
proc init() {
	k = $2
	vec = new Vector(1)
	vec.x[0] = $1
}
proc add() {
	vec.append($1)
}
proc merge() {localobj p1, p2
	// vec and $o1 sorted largest to smallest
	// assume vec.size >= $o1.vec.size
	if ($o1.vec.size == 1) {
		if (vec.size < k) {
			if ($o1.vec.max > vec.min) {
				execerror("$o1 > vec", "")
			}
			add($o1.vec.x[0])
			if (vec.size == k) {
				vec.sub(vec.x[k-1])
			}
		}else{
			if(vec.x[k-1] != 0) {
				execerror("last partition element != 0", "")
			}
			vec.x[k-1] = $o1.vec.x[0]
			vec.sort.reverse
			vec.sub(vec.x[k-1])
		}
	}else if ($o1.vec.size != vec.size) {
printf("genmerge %d %d\n", vec.size, $o1.vec.size)
		genmerge($o1)
	}else{
printf("regular merge\n")
		vec.add($o1.vec.c.reverse).sort
		vec.sub(vec.x[0]).reverse
		// vec is sorted largest to smallest
	}
}
proc genmerge() {localobj m
	// vec should be of size k and $o1 be of size 1
	// but in an extremely wasteful way the general merge is ...
	// assert vec and $o1 are already ordered from greatest to least
	vec.resize(k)
	m = $o1.vec.c.resize(k).reverse
	vec.add(m)
	vec.sort
	vec.sub(vec.x[0]).reverse
}
endtemplate Partition

begintemplate KarmarkarKarp
public list
objref list, w, srt
proc init() {local i, j, mean  localobj p
	w = $o1.c // Vector of values
	k = $2  // Number of partitions
	list = new List(w.size)
	w.sort
	for i=0, w.size-1 {
		list.append(new Partition(w.x[i], k))
	}
	srt = w.sortindex // least to greatest
	while (w.size > 1) {
		merge()
	}
	p = list.object(0)

	mean = $o1.sum/k
	printf("max - min = %g bal = %g\n", p.vec.x[0] - p.vec.x[k-1],\
		(p.vec.x[0] - p.vec.mean)/mean + 1)
	printf("max=%g mean=%g vecmean=%g\n", p.vec.x[0], mean, p.vec.mean)
}
proc merge() {localobj p1, p2
	// srt is sorted least to greatest
	p1 = get_greatest()
	p2 = get_greatest()
	p1.merge(p2)
	put(p1)
}

obfunc get_greatest() {local n  localobj p
	n = srt.size-1
	p = list.object(srt.x[n])
	list.remove(srt.x[n])
	w.remove(srt.x[n])
	srt = w.sortindex
	return p
}

proc put() {local i
	list.append($o1)
	w.append($o1.vec.x[0])
	srt = w.sortindex
}

endtemplate KarmarkarKarp