library FifoLib {

    uint constant HEAD = 0;
    
    struct LinkedList {
        mapping (uint => uint) list;
        uint tail;
        uint size;
    }

    function size(LinkedList storage self)
        internal view returns (uint r) {
        return self.size;
    }

    function next(LinkedList storage self, uint n)
        internal view returns (uint) {
        return self.list[n];
    }

    // insert n after prev
    function insert(LinkedList storage self, uint prev, uint n) internal returns (uint) {
        require(n != HEAD && self.list[n] == HEAD && n != self.tail);
        self.list[n] = self.list[prev];
        self.list[prev] = n;
        self.size++;
        if (self.tail == prev) {
            self.tail = n;
        }
        return n;
    }
    
    // Remove node n preceded by prev
    function remove(LinkedList storage self, uint prev, uint n) internal returns (uint) {
        require(n != HEAD && self.list[prev] == n);
        self.list[prev] = self.list[n];
        delete self.list[n];
        self.size--;
        if (self.tail == n) {
            self.tail = prev;
        }
        return n;
    }

    function pushTail(LinkedList storage self, uint n) internal returns (uint) {
        return insert(self, self.tail, n);
    }
    
    function popHead(LinkedList storage self) internal returns (uint) {
        require(self.size > 0);
        return remove(self, HEAD, self.list[HEAD]);
    }
}
// solhint-disable-line
function remove(LinkedList storage self, uint prev, uint n) internal returns (uint) {
    require(n != HEAD && self.list[prev] == n);
    self.list[prev] = self.list[n];
    delete self.list[n];
    self.size--;
    if (self.tail == n) {
        self.tail = prev;
    }
    return n;
}

// Remove node n preceded by prev