Monday, November 13, 2017

ordered hashset

OrderedHashSet:
    map     // {T, {node{T}}
    dq      // {T}
    add(x):
        if hasKey(x):
            dq.moveToEnd(map[x])
            return
        map[x] = dq.enqueue(x)
    bool hasKey(x):
        return map.hasKey(x)
    bool removeKey(x):
        if !hasKey(x):
            return false
        dq.removeNode(map[x])
        map.removeKey(x)
        return true
    [] foreach():
        for x in dq:
            yield x

// deque interface
dq:
    node enqueue(x):
    bool removeNode(node):
    moveToEnd(node):

No comments:

Post a Comment