which data structure to use?

[Robert Voigtländer]

Am Dienstag, 21. Januar 2014 14:38:34 UTC+1 schrieb Robert Voigtländer:
> > 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

Sorry - found a bug right after my post.
Here the corrected version.

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.f
            lowestFItem = item
    return lowestFItem

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