Helmut Jarausch
1/23/2008 11:21:00 AM
bladedpenguin@gmail.com wrote:
> I am writing a game, and it must keep a list of objects. I've been
> representing this as a list, but I need an object to be able to remove
> itself. It doesn't know it's own index. If I tried to make each object
> keep track of it's own index, it would be invalidated when any object
> with a lower index was deleted. The error was that when I called
> list.remove(self), it just removed the first thing in hte list with
> the same type as what I wanted, rather than the object I wanted. The
> objects have no identifying charachteristics, other than thier
> location in memory
>
> So my question: How do I look something up in a list by it's location
> in memory? does python even support pointers?
>
> Is there a better way?
You could use a doubly linked list.
The class 'deque' from collections is such a list
but I don't known how to delete a specific element without
this ugly (expensive?) rotate method.
Here is my solution in pure Python
#!/usr/bin/python
import re
class Queue(object):
__slots__= 'Head', 'Tail', '__iter__','NNd'
def __init__(self):
self.Head= None
self.Tail= None
self.NNd= None
def append(self,N):
if self.Head == None:
self.Head= N
self.Tail= self
N._enqueue_after(self.Tail)
self.Tail= N
def dequeue(self,N):
Father, Son= N._dequeue()
if self.Tail == N:
self.Tail= Father
if self.Head == N:
self.Head= Son
if self.Head == None: self.Tail= None
def enqueue_after(self,N,Father):
N._enqueue_after(Father)
if self.Tail == Father:
self.Tail= N
def enqueue_before(self,N,Son):
N._enqueue_before(Son)
if self.Head == Son:
self.Head= N
def __iter__(self):
next= self.Head # allows to dequeue the current element in a loop
while True:
current= next
if current == None: raise StopIteration
next= current._next()
yield current
class Node(object): # partially application specific
__slots__= 'next', 'NNd','PNd','key','data'
def __init__(self,Key,Data,P=None,N=None): # P = Previous N = Next
if P != None: P.NNd= self
if N != None: N.PNd= self
self.PNd= P
self.NNd= N
self.key= Key
self.data= Data
def _enqueue_after(self,Father):
self.NNd= Father.NNd
self.PNd= Father
Father.NNd= self
def _enqueue_before(self,Son):
self.NNd= Son
self.PNd= Son.PNd
Son.PNd= self
def _dequeue(self):
if self.PNd != None:
self.PNd.NNd= self.NNd
if self.NNd != None:
self.NNd.PNd= self.PNd
Father= self.PNd
Son= self.NNd
self.PNd= self.NNd= None
return Father,Son
def _next(self):
return self.NNd
def __str__(self): # highly application specific
return '(%s:%s)' % (self.key,self.data)
# some tests
MyQ= Queue()
MyQ.append( Node('HJ','3949') )
print MyQ.Head,MyQ.Tail,MyQ.Head.key
MyQ.append( Node('CJ','10149') )
print MyQ.Head,MyQ.Tail,MyQ.Head.key
N= MyQ.Head
print "queue: ",N.key,"->"
N= N.NNd
print "next: ",N.key,"->"
N= N.NNd
if N != None:
print "next: ",N.key,"->"
else:
print "no next:"
for N in MyQ:
print "loop->",N
print N.key,N.data
MyQ.dequeue(MyQ.Tail)
print "--- after dequeue"
print "Head: ",MyQ.Head," Tail: ",MyQ.Tail
for N in MyQ:
print "loop2->",N
print N.key,N.data
MyQ.dequeue(MyQ.Tail)
print "after second dequeue"
print "Head: ",MyQ.Head," Tail: ",MyQ.Tail
for N in MyQ:
print "loop3->",N
print N.key,N.data
ENJOY,
Helmut.
--
Helmut Jarausch
Lehrstuhl fuer Numerische Mathematik
RWTH - Aachen University
D 52056 Aachen, Germany