which data structure to use?

[Peter Otten]

Robert Voigtländer wrote:

> 
>> > >     def pop(self):
>> > >         f, node = heapq.heappop()
>> > >         del lookup[node.pos]
>> > >         return node
> 
>> > That should be
>> 
>> >     def pop(self):
>> 
>> >         f, node = heapq.heappop(self.heap)
>> >         del self.lookup[node.pos]
>> >         return node
>> 
>> Hi Peter,
>> this works great. I will try to find some info about the functionality
>> you used and to understnad what you did. Maybe you can add a function to
>> remove a node? Thanks for your support and all tthe swift answers.
>> 
>> Robert
> 
> Just realized what the pop function is for. I changed it from:
> def pop(self):
> to
> def pop(self,pos):
> 
> and it works.

Unlikely. Are you sure that .heap and .lookup contents are still in sync 
with your modification?

> Now I go on with trying to understand it.

The pop() method as posted can only remove the "lowest" node. If contrary to 
your initial spec

> 2. find the object with the lowest Node.f attribute and update or remove 
it

you want to remove arbitrary nodes a heap may not be the appropriate data 
structure. The modified

import operator

#...

class Nodes():
    def __init__(self):
        self.lookup = {}
    def add(self, node):
        self.lookup[node.pos] = node
    def __iter__(self):
        return iter(self.lookup.itervalues())
    def __contains__(self, pos):
        return pos in self.lookup
    def lowest(self):
        return min(self, key=operator.attrgetter("f"))
    def __delitem__(self, pos):
        del self.lookup[pos]

nodes = Nodes()

nodes.add(Node((1,1), None, 1, 5))
nodes.add(Node((1,2), (1,1), 4, 6))
nodes.add(Node((1,3), (1,2), 9, 10))

del nodes[1, 2]


allows you to delete random nodes, but the lowest() method will slow down as 
it has to iterate over all dict values.

One important caveat: both Nodes classes lead to data corruption if you 
modify a .pos attribute while the node is in a Nodes instance. The same goes 
for the first implementation and the .f attribute.