OpenEuphoria

Using include and namespaces

• Posted by OthelloVivaldi at hotmail.com Aug 14, 2002
• 611 views

Hello everyone,


I have written a small lib called heap.e (see below), but I'm not=20
certain about how to deal with Euphoria's namespaces.

A user will often need to have several heaps, so my first thought was
to keep them all in a sequence. The problem is that doing so seems to
severely increase access time, i.e.:

    heap[ id ][ element ]

is a much slower reference than simply

    heap[ element ]


My current solution is therefore to use the include ... as feature.

For example, to implement the typical a* routine, you will need
two heaps, which are often given the names 'open' and 'close'.=20
So the question is: what do you think about the following:

    include heap.e as Open
    include heap.e as Close

    Open:push(X)=20
    Close:push(Y)
    X =3D Open:pop()
    Y =3D Close:pop()

Would you recommend this kind of programming style?
Is there some horrible way this can backfire or otherwise
turn out to be a member of the set of bad things?

Sincerely Yours,

Barbarella





=20

Here follows my current version of heap.e. in case you're interested.

-- heap.e =


-- (Standard claimer):
-- I take complete responsibility for ANY damage this file may do to=20
-- you, your computer, your pets or anything else in your environment.
-- If anything bad happens, please try to evaluate the humanitarian and=20
-- material pains and costs, convert it to a sum in the currency of your
-- country and send the figure to me. I will pay through my nose to=20
-- compensate your losses. Should I run out of money, I will come and=20
-- work for you as your personal slave until you are satisfied.

without type_check
without warning

global sequence heap
global integer size

heap =3D {}
size =3D 0

global procedure push(object x)
    integer parent, child
    object parent_value

    size +=3D 1
    heap =3D append(heap, x) -- this looks strange, I know.
    child =3D size
    while child > 1 do
        parent =3D floor(child / 2)
        parent_value =3D heap[parent]
        if compare(parent_value, x) =3D 1 then -- if parent greater
            heap[child] =3D parent_value
            child =3D parent
        else
            heap[child] =3D x
            return
        end if
    end while
    heap[child] =3D x
end procedure

global function pop()
    integer parent, left, right
    object out, parent_value, left_value, right_value

    out =3D heap[1]
    parent =3D 1
    parent_value =3D heap[size]
    size -=3D 1
    heap =3D heap [1 .. size]

    while size do

        left =3D parent + parent -- left =3D parent * 2
        if left > size then
            -- there was no children to this parent
            heap[parent] =3D parent_value
            return out
        end if

        left_value =3D heap[left]
        if compare(left_value, parent_value) =3D - 1 then -- if left < =
parent
            -- swap parent with left unless right is even better
            right =3D left + 1
            if right > size then
                -- swap with left and exit
                heap[parent] =3D left_value
                heap[left] =3D parent_value
                return out
            else
                -- compare left and right
                right_value =3D heap[right]
                if compare(left_value, right_value) =3D 1 then -- if =
left > right
                    -- swap with right, set new parent
                    heap[parent] =3D right_value
                    parent =3D right
                else
                    -- swap with left, set new parent
                    heap[parent] =3D left_value
                    parent =3D left
                end if
            end if
        else
            -- left was not better, check right
            right =3D left + 1
            if right > size then
                -- nothing to the right, set parent and exit
                heap[parent] =3D parent_value
                return out
            else
                right_value =3D heap[right]
                if compare(right_value, parent_value) =3D -1 then
                    -- swap with right, set new parent
                    heap[parent] =3D right_value
                    parent =3D right
                else
                    -- set parent, exit
                    heap[parent] =3D parent_value
                    return out
                end if
            end if
        end if
    end while
    return out
end function

global function top()
    return heap[1] -- look, but don't touch...
end function


--     --  A typical sanity check; see if the heap sorts correctly:
--
-- constant NUM =3D 100
-- sequence random_sequence, ordinary_sort, heap_sort=20
--
--    -- 1. create a random sequence to be sorted
-- random_sequence =3D repeat({}, NUM)
-- for i =3D 1 to NUM do
--     if rand(5) =3D 1 then
--         -- create strange sequences
--         random_sequence[i] =3D rand(repeat(10, rand(10)))
--     else
--         -- create random integers and atoms
--         random_sequence[i] =3D rand(1000) / 3 - 500
--     end if
-- end for
--
--
--    -- 2. sort the sequence using standard sort
-- include sort.e
-- ordinary_sort =3D sort(random_sequence)
--
--
--    -- 3. sort the sequence on the heap
-- heap_sort =3D repeat({}, NUM)
-- for i =3D 1 to NUM do
--     push(random_sequence[i])
-- end for
--
-- for i =3D 1 to NUM do
--     heap_sort[i] =3D pop()
-- end for
--
--
--    -- 4. see if there is any difference
-- if equal(heap_sort, ordinary_sort) then
--     puts(1, "Everything ok.\n")
-- else
--     puts(1, "Oops! Something is wrong!\n")
-- end if