Saturday, February 08, 2014

queue with O(1) find() and delete()

Use deque and map.
node{T}:
    T value
    node{T} prev
    node{T} next

// dq interface for deleting node
dq{T}:
    node{T} enqueue(t):
    delete(node{T} n):

q{T}:
    dq  //{T}
    map //{T, queue{node{T}}}
    
    enqueue(T t):
        node = dq.enqueue(t)
        if has(t):
            q = map[t]
        else:
            q = new queue{node{T}}()
            map[t] = q
        q.enqueue(node)
    
    T dequeue():
        if dq.empty():
            throw "empty"
        t = dq.dequeue()
        deleteInner(t)
        return t
    
    bool has(T t):
        return map.hasKey(t)
    
    bool delete(T t):
        if !has(t):
            return false
        node = deleteInner(t)
        dq.delete(node)
        return true
    
    deleteInner(T t):
        q = map[t]
        node = q.dequeue()
        if q.isEmpty():
            map.removeKey(t)
        return node
    
    bool isEmpty():
        return dq.isEmpty()
    int count():
        return dq.count()
If the map cannot contain null keys then t cannot be null. Workaround is to use NullObject pattern as:
nullT = new T()
enqueue(T t):
    t = t ?? nullT
    ...
[Hat tip to MB]

No comments:

Post a Comment