Python Forum

Full Version: my new adt, what should i name it
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
i'm making a new abstract data type. it might exist, already. it is a list that expands as items are stored to it. if the location already exists, it replaces what is there. it not, it expands the list (virtually). you can get what's there at any time. it keeps data in a sparse way, allowing the caller to see extents of data and holes, including the highest and lowest extents. can you tell me what to name this or what the existing name is?
a list that expands: it's called append
but with this one, you can store into any position even beyond its current length.,1000000) puts data at position 1000000 leaving a sparse gap up to there. it will also do negative positions.

i think i will implement it with a tree structure.
What's important for the structure? Iterating over it? Or just random read/writes?

If the important part is just random read/writes, then it sounds like a dict, but the "index" is just the dict key.
there will mostly be ranges of indexes being filled. that is it might put data into [64] through [255]. there might also be negative ranges. it might leave out every Nth item in a few cases (if this overlaps, then previous data remains in those "holes"). the underlying implementation might be a dictionary or something more optimal in the future.

once it is filled in, access is mostly in a similar sequence as before ... same ranges in different orders.

an "infinite" list would work. if accessing an index that was never filled in, it gets the established default.