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