// SPDX-License-Identifier: UNLICENSED

pragma solidity =0.8.18;

import "@openzeppelin/contracts/utils/structs/EnumerableSet.sol";

library SortedList {
    struct ListItemDetails {
        bool exists;
        uint64 id;
        uint64 nextId;
        uint64 prevId;
    }

    struct ListItem {
        ListItemDetails details;
        uint256 value;
    }

    struct ListDetails {
        uint64 head;
        uint64 tail;
        uint64 current;
        uint64 length;
    }

    struct AscendingList {
        ListDetails __details;
        mapping(uint256 => ListItem) __items;
        mapping(uint256 => bytes32) __keys;
    }

    function head(AscendingList storage list) internal view returns (uint256 id) {
        return list.__details.head;
    }

    function tail(AscendingList storage list) internal view returns (uint256 id) {
        return list.__details.tail;
    }

    function get(AscendingList storage list, uint256 id) internal view returns (bytes32 key, uint256 nextId) {
        require(list.__items[id].details.exists, "SortedList: INVALID_ID");
        key = list.__keys[id];
        nextId = list.__items[id].details.nextId;
    }

    function exists(AscendingList storage list, uint256 id) internal view returns (bool) {
        return list.__items[id].details.exists;
    }

    function length(AscendingList storage list) internal view returns (uint256) {
        return list.__details.length;
    }

    function at(AscendingList storage list, uint256 index) internal view returns (bytes32 key, uint256 curId) {
        ListDetails memory details = list.__details;
        require(index < details.length, "SortedList: OUT_OF_BOUNDS");

        curId = details.head;
        for (uint256 i = 0; i < index; ++i) {
            curId = list.__items[curId].details.nextId;
        }
        key = list.__keys[curId];
    }

    function add(AscendingList storage list, bytes32 key, uint256 value) internal {
        ListDetails memory details = list.__details;

        // when it hits the end loop back around to the beginning
        uint64 id;
        unchecked {
            id = details.current + 1;
        }

        ListItemDetails memory itemDetails = list.__items[id].details;

        // we want to override the previous values if they exist
        if (itemDetails.exists) _remove(list, id);

        ListItem memory nextItem;
        ListItem memory prevItem;
        uint64 curId = details.head;
        while (curId != 0) {
            ListItem memory curListItem = list.__items[curId];
            // sort until we find first value that is larger.
            // then this item should go on the right. so it is ascending
            if (curListItem.value > value) {
                nextItem = curListItem;
                break;
            }

            prevItem = curListItem;
            curId = curListItem.details.nextId;
        }

        list.__details = ListDetails({
            length: details.length + 1,
            head: nextItem.details.id == details.head ? id : details.head,
            tail: prevItem.details.id == details.tail ? id : details.tail,
            current: id
        });
        list.__keys[id] = key;
        list.__items[id] = ListItem({
            value: value,
            details: ListItemDetails({exists: true, id: id, prevId: prevItem.details.id, nextId: nextItem.details.id})
        });

        if (prevItem.details.exists) {
            prevItem.details.nextId = id;
            list.__items[prevItem.details.id].details = prevItem.details;
        }
        if (nextItem.details.exists) {
            nextItem.details.prevId = id;
            list.__items[nextItem.details.id].details = nextItem.details;
        }
    }

    function remove(AscendingList storage list, uint256 id) internal returns (bytes32 key) {
        return _remove(list, id);
    }

    function _remove(AscendingList storage list, uint256 id) private returns (bytes32 key) {
        ListDetails memory listDetails = list.__details;
        ListItemDetails memory itemDetails = list.__items[id].details;

        require(listDetails.length > 0, "SortedList: LIST_EMPTY");
        require(itemDetails.exists, "SortedList: INVALID_ID");

        key = list.__keys[id];

        if (listDetails.length == 1) {
            delete list.__details;
        } else {
            if (uint64(id) == listDetails.head) {
                listDetails.head = itemDetails.nextId;
            }
            if (uint64(id) == listDetails.tail) {
                listDetails.tail = itemDetails.prevId;
            }
            if (itemDetails.prevId != 0) {
                list.__items[itemDetails.prevId].details.nextId = itemDetails.nextId;
            }
            if (itemDetails.nextId != 0) {
                list.__items[itemDetails.nextId].details.prevId = itemDetails.prevId;
            }

            --listDetails.length;
            list.__details = listDetails;
        }

        // TODO confirm the gas of this -- does this clear all the structs?
        delete list.__items[id];
        delete list.__keys[id];
    }
}