Kazimir recently posted an implementation of Heap (priority queue).
Looking at the code made me realize that this was a natural for
a class implementation as well. In talking this over with Kazimir
several other improvements came to mind that help make the Heap
implementation more general (whether it's implemented as a class
or not).
One improvement involves the use of "closures" - a language construct
not found in Icon or Unicon. My son Kevin had implemented code that
supports the concept of closures (in either Icon or Unicon) - it is
a simple matter to extend this foundation into a new class "Closure"
that provides the needed functionality.
What is a closure? There are several definitions, but the most
convenient one is that a closure allows the runtime definition
of new functions by binding some parameters of an existing function
to fixed ("invariant") values at the point of definition. The
closure can then be called later by just supplying the unbound
parameters.
An example might help:
Kazimir provided the following simple function for accessing
an element in a structure:
procedure heap_demo3(x,d)
return x[d]
end
It's possible to define new functions based on this to (say)
access the 1st, 2nd, and 3rd elements:
procedure f1(x)
return heap_demo3(x,1)
end
procedure f2(x)
return heap_demo3(x,2)
end
procedure f3(x)
return heap_demo3(x,3)
end
However, note that this done at program implementation time, not
runtime. With closures, the equivalent to the above three functions
can be done at runtime:
f1 := Closure(heap_demo3, AGap(), 1)
f2 := Closure(heap_demo3, AGap(), 2)
f3 := Closure(heap_demo3, AGap(), 3)
Here, AGap() is a singleton class used to denote the unbound
parameters, while the invariant parameters are just assigned values.
The Closure class provides a single public method for invoking the
"new" function:
write( f2.call(["a","b","c"]) )
would output "b".
There are lots of uses for closures. In the case of the Heap,
closures can be used to avoid having to pass extra arguments into
the Heap constructor for use as the 'fixed' arguments. (If you look
at Kazimir's code, the record field "x" is just such an argument,
it's used as an invariant to calls of heap_demo3 when that function
is passed in (and as an invariant in other cases, as well). By
passing in a closure instead, this invariant can be bound directly
instead of Heap having to know about it.
It's also possible to use a Closure to denote the priority comparison
operation. In the original code this comparison is always "<" but it
would be useful to allow arbitrary operations for defining the
priority.
Strictly speaking, using a Closure isn't necessary, you could define
(at implementation time) a series of functions to use and write a
Heap class that uses procedures instead of Closures. Closures are
a convenience however, making it easier to write generic code.
The code for the Heap class (the implementation changes a few names
from Kazimir's code but preserves the algorithms) is attached. This
version is built based on code available in the "unilib" code library
found at:
http://tapestry.tucson.az.us/unicon
and in also available in that library itself. The Closure class is
provided as part of that library.
Also attached is a variation of Kazimir's demonstration program
adapted for using Closure and Heap classes. (It also is written
as a class, but there's really no reason for it - I just got carried
away!).
I hope people find this useful.
-Steve
--
Steve Wampler <[EMAIL PROTECTED]>
#<p>
# The Collections package provides advanced data structures.
#</p>
package Collections
import Utils
link "Class"
#<p>
# A Heap is a dense binary tree ordered as a <i>priority queue</i>.
# The priority order is from lowest to highest priority where the
# priority of two elements can be compared through the results
# of invoking the Closure <i>f</i> on each. The priority operation
# defaults to Closure("<") but can be the Closure of any binary
# comparison operation.
#</p>
class Heap : Class (L, f, p)
#<p>
# Generates the heap elements(non-destructively) in order.
#</p>
method gen()
local temp
temp := Heap(,f,p)
temp.L := copy(L)
suspend |temp.get()
end
#<p>
# Produces the number of heap elements.
#</p>
method size()
return *L
end
#<p>
# Destructively generates the heap elements in order.
#</p>
method get()
local up, down, result
if *L > 0 then {
L[up:=1] :=: L[-1]
result := pull(L)
while (down := 2*up) <= *L do {
if p.call(f.call(L[down+1]), f.call(L[down])) then down +:= 1
if p.call(f.call(L[down]), f.call(L[up])) then L[up] :=: L[down]
up := down
}
return result
}
end
#<p>
# Add a new element to the heap.
#</p>
method add(a)
local i
put(L,a)
i := *L
while p.call(f.call(L[i]), f.call(L[i/2])) do {
L[i] :=: L[i/2]
i /:= 2
}
return a
end
#<p>
# Construct a Heap.
#</p>
#<p>
# S -- optional list of initial values to insert into heap.
# fVal -- a Utils::Closure to use in comparisons.
# when needed, the Closure is called with a single
# argument that is a heap element. Defaults to
# Closure(1).
# pVal -- a Utils::Closure implementing comparion operation.
# Defaults to Closure("<").
#</p>
initially (S, fVal, pVal)
L := []
f := \fVal | Closure(1)
p := \pVal | Closure("<")
every self.add(!\S)
end
import Utils
import Collections
#<p>
# Demonstrate the Heap and Closure classes.
#</p>
class HeapDemo()
method showTriple(x)
return write("\t",x[1],", ",x[2],", ",x[3])
end
method processTriples(H)
write("Inserted:")
every showTriple(H.add([j := 1 to 5, ?0, j]))
write("All generated:")
every showTriple(H.gen())
write("Get:")
while showTriple(H.get())
write("Size of heap: ", H.size())
end
method processReals(H)
write("Inserted:")
every write("\t",(1 to 5, H.add(?0)))
write("All generated:")
every write("\t",H.gen())
write("Get:")
while write("\t",H.get())
write("Size of heap: ", H.size())
end
method header(msg)
write("==============")
write(msg)
write("==============")
end
initially # demonstration and test
header("Triplets, sorted by 2nd coordinate")
processTriples(Heap(, Closure(heap_demo3,AGap(),2) ))
header("Heap of reals, sorted by their own value")
processReals(Heap())
header("Heap of reals, sorted by inverse order.")
processReals(Heap(, Closure("*",-1)))
header("Heap of reals, sorted by reverse order.")
processReals(Heap(,,Closure(">")))
header("Heap of reals, minimal are those closest to 1/2.")
processReals(Heap(, Closure(heap_demo2) ))
header("Heap of reals, sorted by their own value, non-empty start")
processReals(Heap([0.2,0.3,0.1,0.5,0.4], Closure(1) ))
end
procedure heap_demo2(x); return abs(x-0.5); end # internal use
procedure heap_demo3(x,d); return x[d]; end # internal use
procedure main()
HeapDemo()
end
