buckyos / dcrm Goto Github PK

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

// todo: getDataSize 必须不要回答0（现在可以回答0）

library TopN {
    // stores the top N scores, order is undefined, except that any zero scores are at the end
    struct List {
        uint256 maxLength;
        mapping(uint256 => bytes32) public keys;
        mapping(uint256 => uint256) public values;
    }

    error InvalidKey(bytes32 key);

    error ValueTooSmall(uint256 value);

    error MaxLengthCannotShrink();

    /// @notice 获取一个值
    /// @param  self      TopN数据结构
    /// @param  maxLength 最大长度， 必须不小于当前最大长度
    function setMaxLength(List storage self, uint256 maxLength) public {
        if (maxLength < self.maxLength) {
            revert MaxLengthCannotShrink();
        }
        self.maxLength = maxLength;
    }

    /// @notice 更新一个值
    /// @param  self  TopN数据结构
    /// @param  key   键，必须部位0
    /// @param  value 值，必须大于当前这个key的值
    function updateValue(List storage self, bytes32 key, uint256 value) public {
        if (key == bytes32(0)) {
            revert InvalidKey(key);
        }
        if (value == 0) {
            revert ValueTooSmall(value);
        }

        // 找最小的值，如果比最小的值还小，就不用更新了
        uint256 replaceAt = 0;
        uint256 replaceValue = 0;
        bool found = false;
        for (uint256 i = 0; i < self.maxLength; i++) {
            uint256 v = self.values[i];
            if (v == 0) {
                // insert
                self.keys[i] = key;
                self.values[i] = value;
                return;
            }
            if (self.keys[i] == key) {
                if (value <= v) {
                    revert InvalidValue(value);
                }
                self.values[i] = value;
                return;
            }
            if (value > v && (v < replaceValue || !found)) {
                replaceValue = v;
                replaceAt = i;
                found = true;
            }
        }
        if (found) {
            self.keys[replaceAt] = key;
            self.values[replaceAt] = value;
        }
    }

    // todo: 如果不同的key有相同的value，他们每一个ranking一样。这个好吗？

    /// @notice 考虑一个key的排名
    /// @param  self  TopN数据结构
    /// @param  key   键，必须部位0
    /// @return 最大为1，第二大为2。。。。。。，如果不存在，返回0
    function getRanking(List storage self, bytes32 key) public view returns (uint256) {
        // 找key和value
        uint256 keyValue = 0;
        for (uint256 i = 0; i < self.maxLength; i++) {
            if (self.keys[i] == key) {
                keyValue = self.values[i];
                break;
            }
            if (self.keys[i] == bytes32(0)) {
                return 0;
            }
        }
        if (keyValue == 0) {
            return 0;
        }

        // 找比这个值大的值
        uint256 ranking = 1;
        for (uint256 i = 0; i < self.maxLength; i++) {
            if (self.values[i] > keyValue) {
                ranking += 1;
            }
            if (self.values[i] == 0) {
                break;
            }
        }
        return ranking;
    }
}