Circular Buffer Python implementation

Question

I wrote the code for a circular buffer for an interviewstreet question. But as it happened, two testcases passed and the others are failing. The failure of the cause: index out f range. I tried several testcases after that to reproduce the failure. Unfortunately none of them reproduce the error. Here is the code.

Implement a circular buffer of size N. Allow the caller to append, remove and list the contents of the buffer. Implement the buffer to achieve maximum performance for each of the operations.

"A" n - Append the following n lines to the buffer. If the buffer is full they replace the older entries.
"R" n - Remove first n elements of the buffer. These n elements are the ones that were added earliest among the current elements.
"L" - List the elements of buffer in order of their inserting time.
"Q" - Quit.

class circbuffer():

    #initialization
    def __init__(self,size):
            self.maximum=size
            self.data=[]
            self.current=0


    #appending when the buffer is not full
    def append(self,x):
            if len(self.data)==self.maximum:
                    self.current=0
                    self.data[self.current]=x
                    self.current=(self.current+1)%self.maximum
                    self.__class__=bufferfull
            else:
                    self.data.append(x)

    def remove(self,x):
            if self.data:
                    self.data.pop(0)

    def cget(self):
            return self.data

class bufferfull:

    def append(self,x):
            if len(self.data)<self.maximum:
                    self.data.insert(self.current, x)
            else:
                    self.data[self.current]=x
            self.current=(self.current+1)%self.maximum

    def remove(self,x):
            if self.data:
                    if self.current>len(self.data):
                            self.current=0
                    self.data.pop(self.current)

    def cget(self):
            return self.data[self.current:]+self.data[:self.current]
n=input()

buf=circbuffer(n)
outputbuf=[]

while True:
    com=raw_input().split(' ')
    if com[0]=='A':
            n=int(com[1])
            cominput=[]
            for i in xrange(n):
                    cominput.append(raw_input())
            for j in cominput:
                    buf.append(j)
    elif com[0]=="R":
            n=int(com[1])
            for i in range(n):
                    buf.remove(i)
    elif com[0]=="L":
            for i in buf.cget():
                    outputbuf.append(i)
    elif com[0]=="Q":
            break

for i in outputbuf:
    print i

The error is pointing to self.data.pop(self.current) in class bufferfull. I cannot get the test data from the interviewstreet people. I am trying to come up with testcase myself to reproduce the error.

Any insights?

Answer 1

It looks like you are trying to stop the index out of range error with the code below, but the condition you are checking is wrong.

if self.current > len(self.data):
    self.current = 0
self.data.pop(self.current)

If you call self.data.pop(len(self.data)) you will definitely get that error since lists are 0-indexed. You probably meant:

if self.current >= len(self.data):
    self.current = 0
self.data.pop(self.current)

Answer 2

One bug is here:

def remove(self,x):
        if self.data:
                if self.current>len(self.data):
                        self.current=0
                self.data.pop(self.current)

If self.current == len(self.data), you'll try to pop a non-existent element.

As a general remark, your implementation is way too complicated and for that reason wouldn't score very highly in my book (others might view this differently). @9000's comment to your question sums it up nicely:

Keep it simple. Don't be clever when you can be straightforward in the same number of lines. All you need is a head pointer, a tail pointer, and a list of a fixed size. You don't need any fancy metaprogramming stuff whatsoever. – @9000