woodl@yvax.byu.edu (02/21/90)
I have a binary search handler that I have found very useful for
maintaing dynamic lists of cards in both HyperCard and SuperCard
applications. It is very fast and can be used to create the lists, one
item at a time, and for adding items to the list as well as deleting
items from the list. The code for the routine as used in SuperCard is
as follows: It can be adapted for use in HyperCard by taking out
references to windows. It will automatically insert an item in an
empty field, and when there is at least one item already in the field
it will return a line number and either "before" or
"after" to indicate where the new item should be placed. It the item
exits, it will return just the line number so it can be used for
deleting the item. The code for the handler is as follows:
function BinarySearch WindowName, CardName, FieldName, value
--Designed for use in searching for an item contained in a field
-- or for determining where a new item should be placed to
-- maintain the items in ascending order
-- When the field is empty, it inserts the item directly into
-- the field. When there are items in the field, it returns
-- the relevant line number, a space, and either the word
-- "before" or the word "after". The second word of the returned
-- value can then be tested to see if the item should be inserted
-- before or after the returned line # in the field.
-- For deleting items, it returns the line number of an item
-- found in a field. That then can be used to delete that line.
--Handle the special case of an empty field on insert
If number of lines in field FieldName of card CardName of window B
WindowName > 0 then
--Handle the special case of only one item in the field
If the number of lines in field FieldName of card CardName of B
window WindowName = 1 then put 1 into n
--Handle the other cases when two or more items in the field
put 1 into lower
put the number of lines in field FieldName of card CardName of B
window WindowName into upper
repeat until lower > upper
put (lower+upper) div 2 into n
put line n of field FieldName of card CardName of window B
WindowName into lineNvalue
-- the case when the item is contained in the field
if lineNvalue = value then return n
if lineNvalue > value then put n-1 into upper
else put n+1 into lower
end repeat
put line n of field FieldName of card CardName of window B
WindowName into lineNvalue
-- the case where the item should go before after or before line n
If value > LineNvalue then return n && "after" B
else return n && "before"
-- the special case of an empty field
else Put value into field FieldName of card CardName of window B
WindowName
end BinarySearch
An example of a handler on an insert button might as follows:
on mouseUp
ask "give value to be inserted"
-- handle the "Cancel" response
If it = empty then pass mouseup
-- handle the "OK" response
put it into value
-- TestField is a background field into which the items are put
put binarysearch (testwindow, testcard, TestField, value) into temp
-- special case of empy field already handled in the binarysearch
-- routine
If temp = empty then
choose browse tool
pass mouseup
end if
-- handle the other cases
If line word 1 of temp of field TestField = value
then answer "the list already contains the value:" with value or "OK"
else
put word 2 of temp into position
put word 1 of temp into linenumber
If position = "before" then put value & return before lineB
linenumber of field TestField
else put return & value after line linenumber of field TestField
end If
choose browse tool
end mouseUp
An example of a button handler for deleting an item might be as
follows:
on mouseUp
ask "give value to be inserted"
-- handle the "Cancel" response
If it = empty then pass mouseup
-- handle the "OK" response
put it into value
-- TestField is a background field into which the items are put
put binarysearch (testwindow, testcard, TestField, value) into temp
-- special case of empy field already handled in the binarysearch
-- routine
If temp = empty then
choose browse tool
pass mouseup
end if
-- handle the other cases
If line word 1 of temp of field TestField = value
then answer "the list already contains the value:" with value or "OK"
else
put word 2 of temp into position
put word 1 of temp into linenumber
If position = "before" then put value & return before lineB
linenumber of field TestField
else put return & value after line linenumber of field TestField
end If
choose browse tool
end mouseUp
Larry Wood, Brigham Young University, WoodL@BYUVAX.bitnetbaum@Apple.COM (Allen J. Baum) (02/22/90)
[] >In article <1124woodl@yvax.byu.edu> woodl@yvax.byu.edu writes: > > I have a binary search handler that I have found very useful for >maintaing dynamic lists of cards in both HyperCard and SuperCard >applications. It is very fast and can be used to create the lists, one >item at a time, and for adding items to the list as well as deleting >items from the list. ... >function BinarySearch WindowName, CardName, FieldName, value ... I wrote one of these also, and found it useful to handle the special cases where the new line(item, word, whatever) to be inserted would be inserted immediately after the last thing that was inserted, or after the last thing in the field. This optimizes the common cases of partially sorted inputs. -- baum@apple.com (408)974-3385 {decwrl,hplabs}!amdahl!apple!baum