-- Copyright 1993-1998, by the Cecil Project
-- Department of Computer Science and Engineering, University of Washington
-- See the LICENSE file for license information.


(--
    This program solves the Towers of Hanoi program.
--)

template object towers;
  field stacks(@:towers):indexed[stack[disk]];
  var field moves_done(@:towers):int := 0;

template object disk;
  field id(@:disk):int;
  method print_string(d@:disk):string { d.id.print_string }


method solve_towers(size:int):void {
    "** Starting towers with ".print;
    size.print;
    " disks...".print;

    garbage_collect();

    let var t:towers := not_defined;
    let time:int := time({
	t := create_towers(size);
	move_stack(t, 0, 1, size);
    });

    "done.  ".print;
    t.moves_done.print;
    " moves; time: ".print;
    time.print;
    " ms.".print_line;
}

method create_towers(size:int):towers {
    let stack0:stack[disk] := new_stack[disk]();
    let stack1:stack[disk] := new_stack[disk]();
    let stack2:stack[disk] := new_stack[disk]();
    size.do(&(i:int){
	stack0.push(concrete object isa disk { id := size - i });
    });
    concrete object isa towers { stacks := [stack0, stack1, stack2] } }

method move_stack(t@:towers, from:int, to:int, count:int):void {
    if(count = 0, { ^ });
    let other:int := 3 - from - to;
    move_stack(t, from, other, count - 1);
    move_disk(t, from, to);
    move_stack(t, other, to, count - 1);
};

method move_disk(t@:towers, from:int, to:int):void {
    let d:disk := pop(t.stacks!from);
    if((t.stacks!to).non_empty & { (t.stacks!to).top.id < d.id }, {
	error("pushing a disk onto a smaller disk");
    });
    push(t.stacks!to, d); 
    t.moves_done := t.moves_done + 1;
}