Removing objects

[Helmut Jarausch]

bladedpenguin at 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