Path: csiph.com!usenet.pasdenom.info!news.etla.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Peter Otten <__peter__@web.de>
Subject: Re: which data structure to use?
Date: Tue, 21 Jan 2014 19:39:33 +0100
Organization: None
References: <a0d3734d-5275-4b28-9a3f-6957474674d7@googlegroups.com> <mailman.5780.1390305003.18130.python-list@python.org> <cfa3e258-1f7d-4c08-81d5-41d9c84d40ac@googlegroups.com> <lblv1a$lnb$1@ger.gmane.org> <mailman.5785.1390313974.18130.python-list@python.org> <ed9fa449-e981-4286-a63b-d776bd30af86@googlegroups.com> <e626e8fd-ab23-4428-97e0-7f944f34f9b1@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8Bit
User-Agent: KNode/4.7.3
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.5808.1390329555.18130.python-list@python.org>
Lines: 79
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:64437

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.