'od.popitem() -> (k, v), return and remove a (key, value) pair.
Pairs are returned in LIFO order if last is true or FIFO order if false.'

def popitem(self, last=True):

    if (not self):
        raise KeyError(u'dictionary    is    empty')
    root = self.__root
    if last:
        link = root[0]
        link_prev = link[0]
        link_prev[1] = root
        root[0] = link_prev
    else:
        link = root[1]
        link_next = link[1]
        root[1] = link_next
        link_next[0] = root
    key = link[2]
    del self.__map[key]
    value = dict.pop(self, key)
    return (key, value)
