ActiveState Code

Recipe 435902: Ring List. A fixed size circular list

The RingList is a class implementing a circular list. The ring have a fixed size and when it is full and you append a new element, the first one will be deleted. The class lets you access to the data like a python list or like a string.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class RingList:
    def __init__(self, length):
        self.__data__ = []
        self.__full__ = 0
        self.__max__ = length
        self.__cur__ = 0

    def append(self, x):
        if self.__full__ == 1:
            for i in range (0, self.__cur__ - 1):
                self.__data__[i] = self.__data__[i + 1]
            self.__data__[self.__cur__ - 1] = x
        else:
            self.__data__.append(x)
            self.__cur__ += 1
            if self.__cur__ == self.__max__:
                self.__full__ = 1

    def get(self):
        return self.__data__

    def remove(self):
        if (self.__cur__ > 0):
            del self.__data__[self.__cur__ - 1]
            self.__cur__ -= 1

    def size(self):
        return self.__cur__

    def maxsize(self):
        return self.__max__

    def __str__(self):
        return ''.join(self.__data__)

Discussion

The data structure is a fixed size list. When it is full the first element of the list will be deleted and the new one will be appended at the end. The list can contain any kind of data. A simple str() overload function is provided in case the list elements are strings.

Usage example:

>>> import RingList
>>> test = RingList(3)
<h4>Create a RingList of size 3</h4>



>>> test.append("one")
>>> test.append("two")
>>> print str(test)
onetwo
<h4>Example of the overloaded str() operator</h4>



>>> print test.get()
['one', 'two']
<h4>Get the list</h4>



>>> test.remove()
<h4>Remove the second element ("two")</h4>



>>> test.append("three")
>>> test.append("four")
>>> print test.get()
['one', 'three', 'four']
<h4>The list is full</h4>



>>> test.append("five")
>>> print test.get()
['three', 'four', 'five']
<h4>When a new element is appended the first is removed</h4>



>>> test.remove()
>>> print test.size()
2
<h4>Current size of the RingList</h4>



>>> print test.maxsize()
3
<h4>Maximum size of the RingList object instance.</h4>

I used it in visual grep project http://greppy.sf.net to emulate the "-A" "-B" "-C" switch of the GNU grep that gives you the matched line's context.

Comments

  1. 1. At 10:51 p.m. on 9 jul 2005, Raymond Hettinger said:

    collections.deque(). FWIW, deque() objects also work for your use case.

  2. 2. At 6:24 a.m. on 20 jul 2005, Flavio Catalani (the author) said:

    Yep! collection.dequeue surely worked, but I'm using greppy as a project to learn python. It was funny to code RingList and if someone likes it... :)

Sign in to comment