library Position {
    ////////////////////////////////////////////////////////////////////////////
    // Parameters for configuration

    // How many bits a position uses per level of the tree;
    // each branch of the tree contains 2**SLOT_BITS slots.
    uint256 constant SLOT_BITS = 3;
    ////////////////////////////////////////////////////////////////////////////

    ////////////////////////////////////////////////////////////////////////////
    // Derived constants, do not touch
    uint256 constant SLOT_POINTER_MAX = (2 ** SLOT_BITS) - 1;
    uint256 constant LEAF_FLAG = 1 << 255;
    ////////////////////////////////////////////////////////////////////////////

    // Return the last 3 bits of a position number,
    // corresponding to its slot in its parent
    function slot(uint256 a) internal pure returns (uint256) {
        return a & SLOT_POINTER_MAX;
    }

    // Return the parent of a position number
    function parent(uint256 a) internal pure returns (uint256) {
        return a >> SLOT_BITS;
    }

    // Return the location of the child of a at the given slot
    function child(uint256 a, uint256 s) internal pure returns (uint256) {
        return (a << SLOT_BITS) | (s & SLOT_POINTER_MAX); // slot(s)
    }

    // Return the uint p as a flagged position uint:
    // the least significant 21 bits contain the position
    // and the 22nd bit is set as a flag
    // to distinguish the position 0x000000 from an empty field.
    function setFlag(uint256 p) internal pure returns (uint256) {
        return p | LEAF_FLAG;
    }

    // Turn a flagged position into an unflagged position
    // by removing the flag at the 22nd least significant bit.
    //
    // We shouldn't _actually_ need this
    // as all position-manipulating code should ignore non-position bits anyway
    // but it's cheap to call so might as well do it.
    function unsetFlag(uint256 p) internal pure returns (uint256) {
        return p & (~LEAF_FLAG);
    }
}
function parent(uint256 a) internal pure returns (uint256) {
    return a >> SLOT_BITS;
}

// Return the parent of a position number