which data structure to use?

[Peter Otten]

Robert Voigtländer wrote:

> 
>> On Tue, Jan 21, 2014 at 03:17:43AM -0800, Robert Voigtl�nder wrote:
>> 
> 
>> > I have objects like this:
>> 
>> > 
>> 
>> > class Node(object):
>> 
>> >     def __init__(self, pos, parent, g , h):
>> 
>> >         self.pos = pos
>> 
>> >         self.parent = parent
>> 
>> >         self.g = g
>> 
>> >         self.h = h
>> 
>> >         self.f = g+h
>> 
>> > 
>> 
>> > 
>> 
>> > I need to build a "list" of these objects. The amount is unknown.
>> 
>> > On this list I need to regularly
>> 
>> > 
>> 
>> > 1. check if a specific item - identified by Node.pos - is in the list.
>> 
>> > 2. find the object with the lowest Node.f attribute and update or
>> > remove it
>> 
> 
> 
> First thanks to all who responded. Although I only partially understand
> your answers as I am a Python starter. What's clear to me is the
> difference between object and instance of an object. Just didn't explain
> it well.
> 
> Maybe I give some more info on what I need / want to do. I will also
> provide a working code example. Should have done this before.
> 
> I would very much appreciate a working example of what you mean. Then I
> have a chance to understand it. :-)
> 
> I would like to implement a class for a A* pathfinding algorithm. (there
> are ready libraries out there but I would like to learn it myself) This
> requires to maintain a list of nodes to be processed and nodes already
> processed. For new nodes I need to check if they are on one of the lists.
> I also need to regularly pick the node with the lowest value f from the
> list.
> 
> Here some working code. For one function I sill need a solution. Any
> better solution is welcome.
> 
> Thanks
> Robert
> 
> ---------------
> class Node:
>     def __init__(self, pos, parent, g , h):
>         self.pos = pos
>         self.parent = parent
>         self.g = g
>         self.h = h
>         self.f = g+h
> 
> 
> def isinlist(nodeToSeatch):
>     for item in openlist:
>         if item.pos == nodeToSeatch: return True
>     return False
> 
> 
> def lowestF():
>     lowestF = ''
>     for item in openlist:
>         if item.f < lowestF: lowestF = item
>     return lowestF

def lowestF():
    return min(openlist, key=operator.attrgetter("f"))

 
> def deleteItemWithPos(pos):
>     ## need this function or different approach
>     pass
> 
> openlist=[]
> openlist.append(Node((1,1),None,1,5))
> openlist.append(Node((1,2),(1,1),4,6))
> openlist.append(Node((1,3),(1,2),9,10))
> 
> for item in openlist: print item.pos, item.f
> 
> print isinlist((1,1))
> print isinlist((1,5))
> 
> nextNode = lowestF()
> print nextNode.pos, nextNode.f

Here is an OO implementation of Chris Angelico's suggestion:

import heapq

class Node:
    def __init__(self, pos, parent, g , h):
        self.pos = pos
        self.parent = parent
        self.g = g
        self.h = h
        self.f = g+h
    def __str__(self):
        return "Node(pos={!r}, f={!r})".format(self.pos, self.f)

class Nodes():
    def __init__(self):
        self.lookup = {}
        self.heap = []
    def add(self, node):
        self.lookup[node.pos] = node
        heapq.heappush(self.heap, (node.f, node))
    def __iter__(self):
        return iter(self.lookup.values())
    def __contains__(self, pos):
        return pos in self.lookup
    def lowest(self):
        return self.heap[0][1]
    def pop(self):
        f, node = heapq.heappop()
        del lookup[node.pos]
        return node

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))

for node in nodes:
    print(node)

print((1,1) in nodes)
print((1,5) in nodes)

print(nodes.lowest())