Re: DS_CIRCULAR

Brian Heilig:

> 1. iteration is circular (iteration over the `last' item brings the 
> cursor back to the `first', and vice versa)

We could add this trivially to all cursors if that's useful:

 forth_circular is
   require
     not off
   do
     forth
     if after then
         start
     end
   ensure
     not off
   end

> 2. removal of items from the beginning of the list is done in O(1)

DS_LINKED_LIST already has this property, it's removing from 
the end that is O(n). The first cell is the start, not the 
end, adding at the end is still O(1) because we know the 
last cell. It only iterating backwards that is not a good 
idea.

You could also make a version of DS_ARRAYED_LIST that has this 
property (amortised): you add a start offset and copy only 
when a resize is required (your storage is too empty) or you 
add at the end and reach the end of storage.

Even a more circular version as you suggest with wraparound (where 
'before' can be after 'last') need only be an implementation of 
DS_LIST (and probably, but not necessarily, descendant of 
DS_ARRAYED_LIST for implementation purposes), as this does not 
introduce any interesting new feature beyond the faster inserts 
at the start, so it's an implementation detail.



To Post a message, send it to:   [email protected]
To Unsubscribe, send a blank message to: [email protected] 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/gobo-eiffel/

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/