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.
--
https://mail.python.org/mailman/listinfo/python-list
