Wednesday, May 06, 2015

circular queue, overwrite when full

Used for last n items from a stream.
circular-queue:
    capacity
    buffer
    head = 0
    tail = 0
    count = 0

    //ctor
    circular-queue(capacity):
        if capacity <= 0:
            throw
        capacity = capacity
        buffer = new [capacity]

    enqueue(x):
        buffer[tail] = x
        if count < capacity:
            count++
        tail = wrapindex(tail +1, n)
        //when queue is full, head = tail
        if count == capacity:
            head = tail

    x dequeue():
        if isempty():
            throw "empty"
        x = buffer[head]
        count--
        head = wrapindex(head +1, n)
        return x

    bool isempty():
        return count == 0

    int size():
        return count

    clear():
        head = tail = count = 0

    x peek():
        if isempty():
            throw "empty"
        return a[head]
    
    x[] foreach():
        index = head
        for i = 0, i < count, i++:
            yield buffer[index]
            index = wrapindex(index +1)
    
    int wrapindex(i, n):
        index = i %n // -1 or -6 %5 is -1
        if index < 0:
            index += n
        return index
last-n-items(stream, n):
    if n < 0:
        throw
    if n == 0:
        return [] //empty
    q = new circular-queue(n)
    foreach item in stream:
        q.enqueue(item)
    for item in queue:
        yield item

[Hat tip to ctci]

No comments:

Post a Comment