Are there Python code for a FIFO-like structure?

[Aleksei Guzev]

Standard list class has method "pop()" which extracts list[len(list)-1].
You should only define a method push(o)

def push(L, o):
	L.insert(0,o)

Aleksei Guzev

-----Original Message-----
From: python-list-admin at python.org [mailto:python-list-admin at python.org]On
Behalf Of Christian Tismer
Sent: Friday, October 06, 2000 1:45 PM
To: Will Ware
Cc: python-list at python.org
Subject: Re: Are there Python code for a FIFO-like structure?


Will Ware wrote:
>
> Huaiyu Zhu (hzhu at users.sourceforge.net) wrote:
> > I need something like a fifo, inplemented in a fixed length list...
> > an IndexError is raised if the tail gets
> > too close to the head.
>
> I'm not aware of any standard thing like that. Generally one would
> implement a stack using list.append() and list.pop(), and I have
> implemented FIFOs using list.append() and list.pop(0), but I hadn't
> faced the constraint of keeping the list length constant.
>
> Since you can't do a put and a get literally simultaneously, you'll
> have to tolerate a list length that oscillates between two adjacent
> values. It might be useful to whip up a state diagram telling when
> it's OK to do a put or a get based on the current list length. You'll
> need to alternate puts and gets to prevent greater length variations.
> See if this does what you want:
>
> class FixedLengthFifo:
>     def __init__(self, length):
>         self.length = length
>         self.lst = length * [None]
>     def put(self, x):
>         if len(self.lst) != self.length:
>             raise IndexError
>         self.lst.append(x)
>     def get(self):
>         if len(self.lst) != self.length + 1:
>             raise IndexError
>         return self.lst.pop(0)

Hmm, why don't you really use a fixed length list, maintain
two rotating pointers, and check that they behave well?

I didn't implement it, but it is obvious (left as an exercise
for the reader :-)

But if the fixed length implementation is not the main goal,
but to achieve O(1) behavior, then the attached linked list
implementation might be helpful. It also allows for
rotations (only efficient for smal deviations).

ciao - chris

-------- linkedlist.py ---------
class LinkedList:
    def __init__(self, items=[]):
        self.data = None
        self.size = 0
        for item in items:
            self.append(item)

    def __del__(self):
        self.data[:] = []

    def append(self, item):
        if not self.data:
            thing = self.data = []
            thing[:] = [item, thing, thing]
        else:
            a = self.data
            z = self.data[-1]
            new = [item, a, z]
            a[-1] = new
            z[1] = new
        self.size = self.size+1

    def __len__(self):
        return self.size

    def _spot(self, key):
        if key < 0:
            if self.size + key < 0:
                [][key]   # error
            if 2*abs(key) > self.size:
                key = self.size + key
                dir = 1
            else:
                key = abs(key)
                dir = -1
        else:
            if key >= self.size:
                [][key]   # error
            if 2*key > self.size:
                key = self.size - key
                dir = -1
            else:
                dir = 1
        this = self.data
        while key:
            this = this[dir]
            key = key-1
        return this

    def __getitem__(self, key):
        return self._spot(key)[0]

    def __repr__(self):
        lis = []
        for i in range(self.size):
            lis.append(self[i])
        return "LinkedList(%s)" % repr(lis)

    def insert(self, pos, item):
        if not self.size:
            if pos:
                [][pos] # error
            self.append(item)
        else:
            a = self._spot(pos)
            z = a[-1]
            new = [item, a, z]
            a[-1] = new
            z[1] = new
            self.size = self.size+1

    def __delitem__(self, key):
        this = self._spot(key)
        nil, a, z = this
        a[-1] = z
        z[1] = a
        self.size = self.size-1
        if key == 0:
            self.data = a

    def rotate(self, pos=1):
        """return the current value and rotate into new location"""
        ret = self.data[0]
        self.data = self._spot(pos)
        return ret

    def move(self, pos=0):
        """return the current value and move current into new location.
        With pos==0, the behavior is identical to rotate(1)
        """
        if not pos or pos==self.size-1:
            return self.rotate()
        q = self._spot(pos+1)
        p = q[-1]
        this = self.data
        self.data = self.data[1]
        a = this[1]
        z = this[-1]
        a[-1] = z
        z[1] = a
        p[1] = this
        this[-1] = p
        this[1] = q
        q[-1] = this
        return this[0]

-------- yp.tsildeknil ---------
--
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaunstr. 26                  :    *Starship* http://starship.python.net
14163 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     where do you want to jump today?   http://www.stackless.com

--
http://www.python.org/mailman/listinfo/python-list