parent $frob_class
object $heap_class

var $root child_index 0
var $root owners [$heap_class]
var $root owned [$heap_class]
var $root fertile 0
var $root inited 1
var $root manager $heap_class
var $root writable [$heap_class]
var $root readable ['parameters, 'methods, 'code]
var $root dbref 'heap_class

method new
    arg list, [key];
    var ret_heap;
    
    // returns list as a valid heap sorted on key || 1
    key = [@key, 1][1];
    if (!list)
        return <this(), #[['key, key], ['data, []]]>;
    ret_heap = .new([], key);
    while (list) {
        ret_heap = ret_heap.add(list[1]);
        list = delete(list, 1);
    }
    return ret_heap;
.

method data
    arg self;
    
    return self['data];
.

method should_swap
    arg self, element1, element2;
    
    // returns true iff data[element2] should appear earlier in the list to maintain
    // consistent data structure.
    // re-define in children of $heap_class to adjust sort order
    return 0;
.

method swap
    arg self, a, b;
    
    return <this(), self.replace('data, $list.swap(self['data], a, b))>;
.

method add
    arg self, element;
    var swap, cur_element, element_above;
    
    // add element to self
    // tack it on the end and change self from rep (a dict) to heap_class
    self = <this(), self.replace('data, (self['data]) + [element])>;
    
    // loop percolates new element up
    cur_element = self.length();
    element_above = cur_element / 2;
    swap = 1;
    while (element_above && swap) {
        if (self.should_swap(element_above, cur_element))
            self = self.swap(element_above, cur_element);
        else
            swap = 0;
        cur_element = element_above;
        element_above = cur_element / 2;
    }
    return self;
.

method del
    arg self, element;
    var data, cur_element, next_element, len;
    
    // remove element'th element from self
    // this method works by pushing element down the heap, swapping it with
    // the element below it that should be on top (of the two).
    // self rep changed to frob for swapping
    self = <this(), self>;
    
    // data = self['data];
    len = self.length();
    if ((element > len) || (element < 1))
        throw(~range, "Element index out of range.");
    cur_element = element;
    next_element = cur_element * 2;
    while (next_element < len) {
        if (self.should_swap(next_element, next_element + 1))
            next_element = next_element + 1;
        self = self.swap(cur_element, next_element);
        cur_element = next_element;
        next_element = cur_element * 2;
    }
    
    // if it didn't trickle down to the end...
    if (cur_element != len) {
        // swap cur w/ last (so we can delete it)
        self = self.swap(cur_element, len);
    
        // tricle swapped element up
        next_element = cur_element / 2;
        while (next_element) {
            if (self.should_swap(next_element, cur_element))
                self = self.swap(next_element, cur_element);
            else
                next_element = 0;
            cur_element = next_element;
            next_element = cur_element / 2;
        }
    }
    self = self._drop_last();
    return self;
.

method _drop_last
    arg rep;
    
    if (!(rep['data]))
        throw(~range, "Attempt to kill last element of null heap.");
    return <this(), rep.replace('data, delete(rep['data], listlen(rep['data])))>;
.

method element
    arg self, index;
    
    return (self['data])[index];
.

method length
    arg self;
    
    return listlen(self['data]);
.

method heaped
    arg self;
    var element;
    
    // returns true if data structure is consistent
    if (!(self['data]))
        return 1;
    element = 1;
    
    // loop through elements
    while (1) {
        if ((!(| .should_swap(self, element, element * 2) |)) && (!(| .should_swap(self, element, (element * 2) + 1) |)))
            element = element + 1;
        else
            return 0;
        if (element >= ((.length(self)) / 2))
            return 1;
    }
.