OpenEuphoria

ADTs in Euphoria

• Posted by Michael Nelson <MichaelANelson at WORLDNET.ATT.NET> Dec 21, 2000
• 579 views

Binary trees can be implemented in Euphoria, but this imposes unnecessary
overhead (multiple subscripts) versus a simple sorted sequence.  Here are
some routines.


type sorted_sequence(sequence s)  -- slow, use this only when essential
    integer len
    len=length(s)
    if len<2 then return 1 end if
    for i=1 to len-1 do
        if compare(s[1],s[2])>0 then  return 0 end if -- out of order
    end for
    return 1 -- order is OK
end type

function find_sorted(object x,sequence s) -- find x in s
-- returns position if found, negative of position it would go in if not
found
    integer min,max,mid,test
    min=1
    max=length(s)
    while min<=max do
        mid=floor((min+max)/2)
        test=compare(x,s[mid])
    if test=1 then  -- in top half  of sequence
        min=mid+1
    elseif test=-1 -- in bottom half of sequence
        max=mid-1
    else  -- equal
        return mid
    end while
    return -min
end  function

function insert_sorted(object x,sequence s) -- insert x into s, unless
duplicated
    integer index
    index=find_sorted(x)
    if index<0 then
        return s[1..-index-1]&{x}&s[-index..length(s)]  --return new
sequence
    else
        --error handling code could be added
        return s
    end if
end function

function remove_sorted(object x,sequence s) -- removes x from s, if present
    integer index
    index=find_sorted(x,s)
    if index>0 then
        return s[1..index-1]&s[index+1..length(s)] -- return  new sequence
    else
        -- error handling code could be added
        return s
    end if
end function

-- Mike