binary tree iterators

binarytreeIterator:
    stack, prevn
    ctor(tree):
        if tree == null:
            throw
        stack = new
        prevn = null
        if tree.root != null:
            stack.push(tree.root)
    
    bool hasnext():
        return stack.any()
    
    //O(n)
    bool isVisited(n, visited):
        return visited.has(n)
    
    //O(1), and O(logn) due to stack
    bool isVisited(n, prevn):
        return prevn == n
    
    // pre-order
    x current():
        if stack.isEmpty():
            throw "empty"
        n = stack.pop()
        if n.right != null:
            stack.push(n.right)
        if n.left != null:
            stack.push(n.left)
        return n.value
        
    // in-order
    x current():
        if stack.isempty():
            throw "empty"
        while stack.any():
            n, isVisited = stack.pop()
            if !isVisited && n.left != null:
                stack.push(n, isVisited: true)
                stack.push(n.left, isVisited: false)
                continue
            if n.right != null:
                stack.push(n.right, isVisited: false)
            return n
    
    // post-order
    x current():
        if stack.isEmpty():
            throw "empty"
        while stack.any():
            n = stack.pop()
            if n.left != null 
                && !isVisited(n.left, prevn) && !isVisited(n.right, prevn):
                stack.push(n)
                stack.push(n.left)
                continue
            if n.right != null && !isVisited(n.right, prevn):
                stack.push(n)
                stack.push(n.right)
                continue
            prevn = n
            return n.value
        throw "invalid op"

[Hat tip to J]

ordered hashset

OrderedHashSet:
    map     // {T, {node{T}}
    dq      // {T}
    add(x):
        if has(x):
            // don't change position in queue
            // as it's a subtle behavior, instead let
            // the caller explicity call remove(x) and add(x)
            return
        map[x] = dq.enqueue(x)
    bool has(x):
        return map.hasKey(x)
    bool remove(x):
        if !has(x):
            return false
        dq.removeNode(map[x])
        map.remove(x)
        return true
    [] foreach():
        for x in dq:
            yield x

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

implement hashmap

k cannot be null as cannot calculate hash of k.

hashmap:
    store = new // deque{{k, v}}[]
    
    add(k, v):
        i = index(k)
        dq = store[i]
        if dq == null:
            dq = new dq()
            store[i] = dq
        for kv in dq:
            if kv.key == k:
                kv.value = v
                return
        dq.enqueue(new {k, v})
    
    bool hasKey(k):
        dq = store[index(k)]
        if dq == null:
            return false
        for kv in dq:
            if kv.key == k:
                return true
        return false
    
    bool removeKey(k):
        i = index(k)
        dq = store[i]
        if dq == null:
            return false
        // dq.nodes() is a copy
        for node in dq.nodes():
            if node.kv.key == k:
                dq.removeNode(node)
                if dq.isEmpty():
                    store[i] = null
                return true
        return false
    
    // O(n)
    bool remove(v):
        for i = 0, i < store.length(), i++:
            dq = store[i]
            if dq == null:
                continue
            // dq.nodes() is a copy
            for node in dq.nodes():
                if node.kv.value == v:
                    dq.removeNode(node)
                    if dq.isEmpty():
                        store[i] = null
                    return true
        return false
    
    // helpers
    int index(k):
        return hash(k) %store.length()
    int hash(k):
        if k == null:
            throw
        // ...

if binary tree is full, perfect, complete

full: each node has 0 or 2 child nodes.

// full
    x
 x     x
      x x

// not full
    x
 x     x
x     x x

bool isfull(n):
    if n == null:
        return true
    if n.left == null != n.right == null: // same as ^
        return false
    return (n.left) && (n.right)

perfect: tree has 2^depth -1 nodes (i.e. each level is full).
tip: The depths of left and right subtrees are equal at all levels.

// perfect
    x
 x     x
x x   x x

bool isPerfect(n):
    return depthPerfect(n) != null

int? depthPerfect(n):
    if n == null:
        return 0
    ldepth = (n.left)
    if rdepth == null:
        return null
    rdepth = (n.right)
    if rdepth == null:
        return null
    if ldepth != rdepth:
        return null
    return ldepth +1 // or rdepth +1

complete: nodes at last level are filled from left.
tip: After encountering a null child, no nodes in queue should have any children.

// complete
    x
 x     x
x x   x

// not complete
    x
 x     6
x x     7

    4
 2     6
1     5

// bfs
bool isComplete(node):
    if node == null:
        return true
    q = new
    q.enqueue(node)
    ended = false
    while !q.isEmpty():
        n = q.dequeue()
        if ended && n.left != null:
            return false
        if n.left != null:
            q.enqueue(n.left)
        else:
            ended = true
        if ended && n.right != null:
            return false
        if n.right != null:
            q.enqueue(n.right)
        else:
            ended = true
    return true

// bfs
bool isComplete(node):
    if node == null:
        return true
    q = new
    q.enqueue(node)
    ended = false
    while !q.isEmpty():
        n = q.dequeue()
        if ended && (n.left != null || n.right != null):
            return false        
        if n.left == null && n.right != null:
            return false
        ended = n.left == null || n.right == null
        if n.left != null:
            q.enqueue(n.left)
        if n.right != null:
            q.enqueue(n.right)
    return true

// dfs
bool isComplete(n):
    return (n, count(n) -1)

bool isComplete(n, maxi, i = 0):
    if n == null:
        return true
    if i > maxi:
        return false
    // faster to check right subtree first as
    // right subtree returns false if not complete
    return isComplete(n.right, maxi, i*2 +2)
        && isComplete(n.left, maxi, i*2 +1)

int count(n):
    if n == null:
        return 0
    return 1 + count(n.left) + count(n.right)

// dfs
bool isComplete(n):
    isComplete(n, count: {value: 0}, maxi: {value: 0}, i: 0)
    return count.value < i.value +1

isComplete(n, count, maxi, i):
    if n == null:
        return
    count.value++
    maxi.value = max(maxi.value, i)
    (n.left, count, maxi, i*2 +1)
    (n.right, count, maxi, i*2 +2)

// bfs
bool isComplete(node):
    if node == null:
        return true
    q = new
    q.enqueue((node, iexp: 0))
    i = 0
    while !q.isEmpty():
        n, iexp = q.dequeue()
        if iexp > i:
            return false
        i++
        if n.left != null:
            q.enqueue((n.left, iexp*2 +1))
        if n.right != null:
            q.enqueue((n.right, iexp*2 +2))
    return true

[Hat tip to ctci]

queue with 1 stack

Using recursion and backtracking, i.e. using the method call stack as the "other" stack to hold on to the elements.

// O(n)
enqueue(x):
    if stack.isEmpty():
        stack.push(x)
        return
    temp = stack.pop()
    enqueue(x)
    stack.push(temp)

// O(1)
x dequeue():
    return stack.pop()

// O(1)
enqueue(x):
    stack.push(x)

// O(n)
x dequeue():
    temp = stack.pop()
    if stack.isEmpty():
        x = temp
    else:
        x = dequeue()
        stack.push(temp)
    return x

[Hat tip to SO]

reentrant lock, unlock

Given two primitive locking constructs, write reentrant acquire() and release().

// blocks others
acquire(obj):
// unblocks others, throws ex if called without lock(obj) first
release(obj):

acquire(obj) should be called as early as possible. release(obj) should be called as late as possible.

acquire(obj) cannot be the 1st statement for lock(obj) to be reentrant. It is ok if 1+ threads pass the if as acquire(obj) will allow only 1st thread and block others.

Calling release(obj) without acquire(obj) will throw.

locker:
    obj
    count = 0
    thread = null
    //ctor
    locker(obj):
        obj = obj

    lock():
        // any other thread gets blocked (reentrant)
        if thread != thread.current:
            acquire(obj)
            thread = thread.current
        count++
    unlock():
        if thread != thread.current:
            throw //as release called without lock
        count--
        if count == 0:
            thread = null
            // unblocks blocked threads
            release(obj)

Used as:

lockobj1 = new locker(obj1)
lockobj1.lock() //1st
// critical section
// ok to call lock() again
lockobj1.lock() //2nd
...
lockobj1.unlock() //2nd
lockobj1.unlock() //1st

[Hat tip to PK]

if array is in heap property

bool isminheap(a):
    if a == null:
        throw
    lasti = a.length() -1
    lastparent = (lasti-1) /2
    for i = 0, i <= lastparent, i++:
        left  = i*2 +1
        right = left +1
        // left is never out of range
        if left < a.length()  && a[i] > a[left]:
            return false
        // right may be out of range
        if right < a.length() && a[i] > a[right]:
            return false
    return true

staque, a stack+queue combo data structure

staque:
    a
    count = start = end = 0
    staque(capacity):
        a = new [capacity]

    push(x):
        if isfull():
            throw
        a[end] = x
        count++
        end = mod(end+1, a.length())
    pop(x):
        if isempty():
            throw
        end = mod(end-1, a.length())
        count--
        return a[end]
    enqueue(x):
        if isfull():
            throw
        a[end] = x
        count++
        end = mod(end+1, a.length())
    x dequeue():
        if isempty():
            throw
        x = a[start]
        start = mod(start+1, a.length())
        count--
        return x
    isempty():
        return count == 0
    isfull():
        return count == a.length()
    clear():
        count = start = end = 0
    
    top():
        if isempty():
            throw
        return a[end]
    start():
        if isempty():
            throw
        return a[start]
    end():
        if isempty():
            throw
        return a[end]
    
    mod(x, n):
        m = x % n
        if m < 0:
            m += n
        return m

min() and max() for stack in O(1)

//example
1    1   -
1    1   -
6    -   6
6    -   6
5    5   5
main min max

stack:
    main = new stack()
    min = new stack()
    max = new stack()
    
    push(x):
        main.push(x)
        if min.isempty() || x <= min.peek():
            min.push(x)
        if max.isempty() || x >= max.peek():
            max.push(x)
    
    x pop():
        if main.isempty():
            throw
        x = main.pop()
        if x == min.peek():
            min.pop() //ignore
        if x == max.peek():
            max.pop() //ignore
        return x
    
    // time: O(1), space: O(n)
    x min():
        if min.isempty():
            throw
        return min.peek()
    
    // time: O(1), space: O(n)
    x max():
        if max.isempty():
            throw
        return max.peek()

bitset

int has 32 bits
long has 64 bits
x /32 = x >> 5
x %32 = x & 0x1f

bitset:
    int[] flags
    long max
    
    //0..n
    bitset(long n):
        if n < 0:
            throw "out of range"
        // n >> 5 is always 1 less, so add 1
        //1 11111 : 1 +1 <- no bits wasted
        //  11111 : 0 +1 <- no bits wasted
        //1 00000 : 1 +1 <- 31 bits wasted
        //  00000 : 0 +1 <- 31 bits wasted
        long size = n >> 5 +1
        max = n
        flags = new int[size]
        
    set(long x):
        if x < 0 || x > max:
            throw "out of range"
        index = x >> 5
        offset = x & 0x1f
        flags[index] |= (1 << offset)

    clear(long x):
        if x < 0 || x > max:
            throw "out of range"
        index = x >> 5
        offset = x & 0x1f
        flags[index] &= ~(1 << offset)

    toggle(long x):
        if x < 0 || x > max:
            throw "out of range"
        index = x >> 5
        offset = x & 0x1f
        flags[index] ^= (1 << offset)

    has(long x):
        if x < 0 || x > max:
            throw "out of range"
        index = x >> 5
        offset = x & 0x1f
        return ((flags[index] >> offset) & 1) == 1

[Hat tip to ctci, NH]

devious binary tree

This compiles.

node:
    node left
    node right
    node():
        left = right = this

heap / max heap / priority queue

Using array. Could use list as a backing store. All heap-changing operations are O(logn) - occasionally O(n) when list resizes. When top has to be replaced, displace() avoids having to call delete() and insert().

// interface
heap:
    insert(T)     // uses siftup()
    T delete()    // uses siftdown()
    T displace(T) // replaces top, uses siftdown()
    T peek()
    int size()
    int capacity()
    [] foreach()

// max-heap uses array (or list) as a backing store
max-heap: heap
    store
    
    max-heap(capacity)
        if capacity < 0:
            throw
        store = new [capacity]
    
    // add, siftup
    insert(x):
        if isfull():
            throw
        store[count] = x
        count++
        siftup()
    
    // return 0th, [0] = [last], siftdown
    delete():
        if isempty():
            throw
        x = store[0]
        store[0] = store[count-1]
        count--
        siftdown()
        return x
    
    // replace top, siftdown 
    displace(x):
        if isempty():
            throw
        top = store[0]
        store[0] = x
        siftdown()
        return top
    
    peek():
        if isempty():
            throw
        return store[0]
    
    siftup(end = count-1):
        i = end
        while i > 0:
            parent = (i-1) /2
            if store[parent] >= store[i]:
                break
            swap(store, i, parent)
            i = parent
    
    siftdown(start = 0):
        i = start
        while i < count:
            left = i*2 +1
            right = left +1
            max = i
            if left < count && store[left] > store[max]:
                max = left
            if right < count && store[right] > store[max]:
                max = right
            if max == i:
                break
            swap(store, i, max)
            i = max

    //or count()    
    size():
        return count
    isempty():
        return count == 0
    isfull():
        return count == store.length()
    capacity():
        return capacity
    [] foreach():
        for i = 0, i < count, i++:
            yield return store[i]

append(x) is useful in some cases where a delayed call to heapify() is efficient. Heapify() using siftdown() is faster than siftup() as siftdown() only has ~n swaps (0*n/2 + 1*n/4 + 2*n/8 + h*1 = n) i.e O(n) but siftup() has nlogn swaps (h*n/2 + (h-1)*n/4 + (h-2)*n/8... + 2*1 + 0*1) i.e. O(nlogn).

    isheapified = true
    append(x):
        if isfull():
            throw
        store[count] = x
        count++
        isheapified = false
    
    // note: heapify using siftdown is faster
    heapify():
        heapify-siftdown()
        isheapified = true
    // O(n)
    heapify-siftdown():
        start = count/2 -1 // last parent
        while start >= 0:
            siftdown(start)
            start--
    // O(nlogn)
    heapify-siftup():
        end = count-1
        while end > 0:
            siftup(end)
            end--
    
    // delayed call to heapify()
    peek():
        if isempty():
            throw
        if !isheapified:
            heapify()
        return store[0]

lru cache for n items

lru cache for n items with O(1) add, remove, has, get.

With queue, add() is not O(1), get() is difficult/hacky to implement. So deque.

// caches n recently used items
lru-cache:
    n // items
    ctor(n):
        n = n
    count = 0
    
    map
    q
    add(key, value):
        if map.has(key):
            // update value, move node to end of dq
            item = map[key]
            item.value = value
            // difficult: item.node need to be put at end
            return
        if count == n:
            // remove lru item
            // handle delayed removal from queue
            lrukey = q.dequeue()
            while !map.has(lrukey):
                lrukey = q.dequeue()
            map.remove(lrukey)
            count--
        // add key
        count++
        q.enqueue(key)
        map.add(key, value)
    remove(key):
        if !map.has(key):
            return // or throw "error"
        count--
        // only remove from map, delay removal from queue during add
        map.remove(key)
    has(key):
        return map.has(key)
    get(key):
        // difficult/hacky to implement

    dq = new deque{key}()
    nodemap = new map{key, node{key}}()
    valuemap = new map{key, value}()

    add(key, value):
        if key == null || value == null: throw
        if has(key):
            // nodemap does not change
            dq.makeTail(nodemap[key])
            valuemap[key] = value
            return
        if count == n:
            // remove lru
            lrukey = dq.peek()
            removeInternal(lrukey)
        // add to end
        addInternal(key, value)
    
    value removeInternal(key):
        dq.removeNode(nodemap[key])
        nodemap.remove(key)
        value = valuemap[key]
        valuemap.remove(key)
        count--
        return value
    addInternal(key, value):
        node = dq.enqueue(key)
        nodemap[key] = node
        valuemap[key] = value
        count++
    
    bool remove(key):
        if key == null: throw
        // do not throw if key no exists
        if !has(key):
            return false
        removeInternal(key)
        return true
    
    value get(key):
        if key == null: throw
        // do not throw if key no exists
        if !has(key):
            return null // default(value)
        dq.makeTail(nodemap[key])
        return valuemap[key]
    
    bool haskey(key):
        if key == null: throw
        return valuemap.haskey(key)
    
    int count():
        return count
    
// deque interface
deque{key}:
    // for removal in O(1) time
    node{key} enqueue(key):
    removeNode(node{key})
    // moves dq node to end
    makeTail(node):
    key peek():
    // not used
    key dequeue():

semaphore

//counting semaphore
semaphore:
    maxsize
    count = 0
    lock = new
    int acquire():
        lock(lock):
            while count == maxsize:
                monitor.wait(lock)
            if count == 0:
                monitor.pulseall(lock)
            return ++count // returns 1..maxsize
    int release():
        lock(lock):
            while count == 0:
                monitor.wait(lock)
            if count == maxsize:
                monitor.pulseall(lock)
            return --count // returns 0..maxsize-1

// below statements are equivalent
lock(lock):
    // do something

monitor.enter(lock)
try:
    // do something
finally:
    monitor.exit(lock)

Note:
- pulse/all when count is 1+ does nothing
- pulse/all when count is (maxsize-1)- does nothing
As there will be no threads in waiting queue to be moved to ready queue.

[Hat tip to MG]

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]

trie

// interface
add-word(word)
bool is-word(word)
string[] get-all-words()
string[] get-words-by(prefix)
string[] get-longest-words()
remove-word(word)

trienode:
    // members
    char c
    map<char, trienode> children
    int wordcount
    trienode parent
    
    // ctors
    trienode(c, parent):
        c = c
        children = new
        wordcount = 0
        parent = parent
    
    // methods
    is-word():
        return wordcount > 0

trie:
    // members
    root = new trienode(' ', parent: null)
    
    // methods
    add-word(word):
        node = root
        foreach c in word:
            child = node.children[c]
            if child == null:
                child = new trienode(c: c, parent: node)
                node.children[c] = child
            node = child
        node.wordcount++
    
    is-word(word):
        node = get-trienode-by(word)
        return node != null && node.is-word()
    
    get-all-words():
        return get-words-wrapper(root, prefix: "")
    get-words-by(prefix):
        node = get-trienode-by(prefix)
        if node != null:
            words = get-words-wrapper(node, prefix)
        else:
            words = new // empty if prefix does not exists
        return words
    get-words-wrapper(node, prefix):
        words = new
        get-words-recursive(words, node, new buffer(prefix))
        return words
    get-words-recursive(words, node, buffer):
        if node.is-word():
            words.add(buffer.tostring())
        foreach child in node.children:
            buffer.append(child.c)
            get-words-recursive(words, child, buffer):
            buffer.length--
    get-trienode-by(s):
        node = root
        foreach c in s:
            node = node.children[c]
            if node == null:
                break
        return node
    
    get-longest-words():
        words = new
        length = 0
        get-longest-words-recursive(words, root, new buffer(), ref length):
        return words
    get-longest-words-recursive(words, node, buffer, ref length):
        if node.is-word():
            if buffer.length > length:
                words.clear()
                length = buffer.length
            if buffer.length == length:
                words.add(buffer.tostring())
        foreach child in node.children:
            buffer.append(child.c)
            get-longest-words-recursive(words, child, buffer, ref length):
            buffer.length--
    
    remove-word(word):
        node = get-trienode-by(word)
        if node == null || !node.is-word():
            throw
        node.wordcount = 0
        while node.children.count == 0 && !node.is-word() && node != root:
            parent = node.parent
            parent.children.remove(node.c)
            node.parent = null
            node = parent

circular stack

Used for undo operations.

circular-stack:
    a, capacity
    count = 0
    top = 0
    circular-stack(capacity):
        capacity = capacity
        a = new [capacity]
        
    push(x):
        a[top] = x
        top = wrapIndex(top +1, capacity)
        if count < capacity:
            count++
    x pop():
        if isempty():
            throw
        top = wrapIndex(top -1, capacity)
        count--
        return a[top]
    x peek():
        if isempty():
            throw
        return a[wrapIndex(top -1, capacity)]
    isempty():
        return count == 0
    count():
        return count
    clear():
        top = count = 0
    foreach():
        tos = top
        for i = 0, i < count, i++:
            tos = wrapIndex(tos -1, capacity)
            yield a[tos]
    
    wrapIndex(i, n):
        index = i %n
        if index < 0:
            index += n
        return index

[Hat tip to 2048]

stack with array

stack
    a = new T[SIZE]
    i = 0
    
    push(T x):
        if i == a.length():
            resize()
        a[i++] = x
        
    T pop():
        if i == 0:
            throw "empty"
        return a[--i]
        
    resize():
        anew = new[a.length() * 2] //overflow possible
        for j=0 to <a.length():
            anew[j] = a[j]
        a = anew

queue with 2 stacks, stack with 2 queues

queue with 2 stacks. for enqueue, out->in and push into in. for dequeue, in->out and pop from out.

enqueue(x):
    while !out.isEmpty():
        in.push(out.pop())
    in.push(x)

x dequeue():
    while !in.isEmpty():
        out.push(in.pop())
    return out.pop()

Elements in out are already in dequeue order so no need to move to in.

enqueue(x):
    in.push(x)

x dequeue():
    if !out.isEmpty():
        while !in.isEmpty():
            out.push(in.pop())
    return out.pop()

stack with 2 queues. for push, enqueue into non-empty queue (or q2). for pop, dequeue all from non-empty queue, enqueue into other and return last.

push(T x):
    if !q1.isEmpty():
        q = q1
    else
        q = q2
    q.enqueue(x)

T pop():
    if q1.isEmpty() && q2.isEmpty():
        throw "empty"
    if !q1.isEmpty():
        q = q1
        other = q2
    else
        q = q2
        other = q1
    n = null
    while !q.isEmpty():
        n = q.dequeue()
        if q.isEmpty():
            break;
        other.enqueue(n)
    return n

deque

node:
    next
    prev
    value
    
dq:
    head, tail = null
    
    node enqueue(T t):
        n = new node(t)
        if head == tail == null:
            head = tail = n
        else:
            tail.next = n
            n.prev = tail
            tail = n
        return n
    
    T dequeue():
        if head == null:
            throw "empty"
        n = head
        if head == tail:
            head = tail = null
        else:
            head = head.next
            n.next = head.prev = null
        return n.value
    
    delete(n):
        if n == null || head == null || tail == null:
            throw
        if n == head && head == tail:
            head = tail = null
        else if n == head:
            head = head.next
            n.next = head.prev = null
        else if n == tail:
            tail = tail.prev
            n.prev = tail.next = null
        else:
            n.prev.next = n.next
            n.next.prev = n.prev
            n.prev = n.next = null
    
    // make an existing node in deque the tail.
    // note: deque cannot be empty, as it has at least 1 node
    // to make the tail.
    makeTail(n):
        if n == null || head == null || tail == null:
            throw
        if n == tail:
            return
        if n == head:
            head = head.next
            head.prev = null
        else:
            n.prev.next = n.next
            n.next.prev = n.prev
        n.prev = n.next = null
        tail.next = n
        n.prev = tail
        tail = n