Mathematical Utilities

/**
 * @dev Standard math utilities with advanced arithmetic operations
 */
library Math {
    /**
     * @dev Rounding direction for mathematical operations
     */
    enum Rounding {
        Floor,  // Round toward zero
        Ceil,   // Round away from zero  
        Trunc,  // Round toward negative infinity
        Expand  // Round away from negative infinity
    }
    
    /**
     * @dev Returns maximum of two values
     */
    function max(uint256 a, uint256 b) internal pure returns (uint256);
    
    /**
     * @dev Returns minimum of two values  
     */
    function min(uint256 a, uint256 b) internal pure returns (uint256);
    
    /**
     * @dev Returns overflow-safe average of two values
     */
    function average(uint256 a, uint256 b) internal pure returns (uint256);
    
    /**
     * @dev Integer square root using Newton's method
     */
    function sqrt(uint256 a) internal pure returns (uint256);
    function sqrt(uint256 a, Rounding rounding) internal pure returns (uint256);
    
    /**
     * @dev High-precision multiplication and division
     */
    function mulDiv(uint256 x, uint256 y, uint256 denominator) internal pure returns (uint256);
    function mulDiv(uint256 x, uint256 y, uint256 denominator, Rounding rounding) internal pure returns (uint256);
    
    /**
     * @dev Ceiling division avoiding overflow
     */
    function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256);
    
    /**
     * @dev Logarithm functions with optional rounding
     */
    function log2(uint256 value) internal pure returns (uint256);
    function log2(uint256 value, Rounding rounding) internal pure returns (uint256);
    function log10(uint256 value) internal pure returns (uint256);
    function log256(uint256 value) internal pure returns (uint256);
    
    /**
     * @dev Modular arithmetic operations
     */
    function invMod(uint256 a, uint256 n) internal pure returns (uint256);
    function modExp(uint256 b, uint256 e, uint256 m) internal pure returns (uint256);
    
    /**
     * @dev Extended precision arithmetic
     */
    function add512(uint256 a, uint256 b) internal pure returns (uint256 high, uint256 low);
    function mul512(uint256 a, uint256 b) internal pure returns (uint256 high, uint256 low);
    
    /**
     * @dev Safe arithmetic with success flags
     */
    function tryAdd(uint256 a, uint256 b) internal pure returns (bool success, uint256 result);
    function trySub(uint256 a, uint256 b) internal pure returns (bool success, uint256 result);
    function tryMul(uint256 a, uint256 b) internal pure returns (bool success, uint256 result);
    function tryDiv(uint256 a, uint256 b) internal pure returns (bool success, uint256 result);
    
    /**
     * @dev Branchless ternary operation for gas optimization
     */
    function ternary(bool condition, uint256 a, uint256 b) internal pure returns (uint256);
}

/**
 * @dev Signed math utilities for int256 operations
 */
library SignedMath {
    /**
     * @dev Returns maximum of two signed values
     */
    function max(int256 a, int256 b) internal pure returns (int256);
    
    /**
     * @dev Returns minimum of two signed values
     */
    function min(int256 a, int256 b) internal pure returns (int256);
    
    /**
     * @dev Returns overflow-safe average using bit manipulation
     */
    function average(int256 a, int256 b) internal pure returns (int256);
    
    /**
     * @dev Returns absolute value using bit twiddling
     */
    function abs(int256 n) internal pure returns (uint256);
    
    /**
     * @dev Branchless ternary for signed integers
     */
    function ternary(bool condition, int256 a, int256 b) internal pure returns (int256);
}

/**
 * @dev Safe type conversion library with overflow detection
 */
library SafeCast {
    /**
     * @dev Converts uint256 to smaller unsigned integer types
     */
    function toUint248(uint256 value) internal pure returns (uint248);
    function toUint240(uint256 value) internal pure returns (uint240);
    function toUint232(uint256 value) internal pure returns (uint232);
    function toUint224(uint256 value) internal pure returns (uint224);
    function toUint216(uint256 value) internal pure returns (uint216);
    function toUint208(uint256 value) internal pure returns (uint208);
    function toUint200(uint256 value) internal pure returns (uint200);
    function toUint192(uint256 value) internal pure returns (uint192);
    function toUint184(uint256 value) internal pure returns (uint184);
    function toUint176(uint256 value) internal pure returns (uint176);
    function toUint168(uint256 value) internal pure returns (uint168);
    function toUint160(uint256 value) internal pure returns (uint160);
    function toUint152(uint256 value) internal pure returns (uint152);
    function toUint144(uint256 value) internal pure returns (uint144);
    function toUint136(uint256 value) internal pure returns (uint136);
    function toUint128(uint256 value) internal pure returns (uint128);
    function toUint120(uint256 value) internal pure returns (uint120);
    function toUint112(uint256 value) internal pure returns (uint112);
    function toUint104(uint256 value) internal pure returns (uint104);
    function toUint96(uint256 value) internal pure returns (uint96);
    function toUint88(uint256 value) internal pure returns (uint88);
    function toUint80(uint256 value) internal pure returns (uint80);
    function toUint72(uint256 value) internal pure returns (uint72);
    function toUint64(uint256 value) internal pure returns (uint64);
    function toUint56(uint256 value) internal pure returns (uint56);
    function toUint48(uint256 value) internal pure returns (uint48);
    function toUint40(uint256 value) internal pure returns (uint40);
    function toUint32(uint256 value) internal pure returns (uint32);
    function toUint24(uint256 value) internal pure returns (uint24);
    function toUint16(uint256 value) internal pure returns (uint16);
    function toUint8(uint256 value) internal pure returns (uint8);
    
    /**
     * @dev Converts uint256 to signed integer types
     */
    function toInt256(uint256 value) internal pure returns (int256);
    function toInt248(int256 value) internal pure returns (int248);
    function toInt240(int256 value) internal pure returns (int240);
    function toInt232(int256 value) internal pure returns (int232);
    function toInt224(int256 value) internal pure returns (int224);
    function toInt216(int256 value) internal pure returns (int216);
    function toInt208(int256 value) internal pure returns (int208);
    function toInt200(int256 value) internal pure returns (int200);
    function toInt192(int256 value) internal pure returns (int192);
    function toInt184(int256 value) internal pure returns (int184);
    function toInt176(int256 value) internal pure returns (int176);
    function toInt168(int256 value) internal pure returns (int168);
    function toInt160(int256 value) internal pure returns (int160);
    function toInt152(int256 value) internal pure returns (int152);
    function toInt144(int256 value) internal pure returns (int144);
    function toInt136(int256 value) internal pure returns (int136);
    function toInt128(int256 value) internal pure returns (int128);
    function toInt120(int256 value) internal pure returns (int120);
    function toInt112(int256 value) internal pure returns (int112);
    function toInt104(int256 value) internal pure returns (int104);
    function toInt96(int256 value) internal pure returns (int96);
    function toInt88(int256 value) internal pure returns (int88);
    function toInt80(int256 value) internal pure returns (int80);
    function toInt72(int256 value) internal pure returns (int72);
    function toInt64(int256 value) internal pure returns (int64);
    function toInt56(int256 value) internal pure returns (int56);
    function toInt48(int256 value) internal pure returns (int48);
    function toInt40(int256 value) internal pure returns (int40);
    function toInt32(int256 value) internal pure returns (int32);
    function toInt24(int256 value) internal pure returns (int24);
    function toInt16(int256 value) internal pure returns (int16);
    function toInt8(int256 value) internal pure returns (int8);
    
    /**
     * @dev Converts signed to unsigned integer
     */
    function toUint256(int256 value) internal pure returns (uint256);
    
    /**
     * @dev Efficient boolean to uint256 conversion
     */
    function toUint(bool b) internal pure returns (uint256 u);
}

/**
 * @dev String manipulation library with mathematical parsing
 */
library Strings {
    /**
     * @dev Convert integers to string representation
     */
    function toString(uint256 value) internal pure returns (string memory);
    function toStringSigned(int256 value) internal pure returns (string memory);
    
    /**
     * @dev Convert to hexadecimal representation
     */
    function toHexString(uint256 value) internal pure returns (string memory);
    function toHexString(uint256 value, uint256 length) internal pure returns (string memory);
    function toHexString(address addr) internal pure returns (string memory);
    
    /**
     * @dev EIP-55 checksummed address representation
     */
    function toChecksumHexString(address addr) internal pure returns (string memory);
    
    /**
     * @dev Parse string to integer with bounds checking
     */
    function parseUint(string memory input, uint256 min, uint256 max) internal pure returns (uint256);
    function parseInt(string memory input, int256 min, int256 max) internal pure returns (int256);
    
    /**
     * @dev Parse hexadecimal strings
     */
    function parseHexUint(bytes memory input) internal pure returns (uint256);
    function parseAddress(string memory input) internal pure returns (address);
    
    /**
     * @dev String comparison
     */
    function equal(string memory a, string memory b) internal pure returns (bool);
    
    /**
     * @dev JSON escaping for safe string output
     */
    function escapeJSON(string memory input) internal pure returns (string memory);
}

/**
 * @dev Address utility library for safe operations
 */
library Address {
    /**
     * @dev Returns true if account is a contract
     */
    function isContract(address account) internal view returns (bool);
    
    /**
     * @dev Safe ETH transfer with gas limit protection
     */
    function sendValue(address payable recipient, uint256 amount) internal;
    
    /**
     * @dev Safe contract calls with error propagation
     */
    function functionCall(address target, bytes memory data) internal returns (bytes memory);
    function functionCallWithValue(address target, bytes memory data, uint256 value) internal returns (bytes memory);
    function functionStaticCall(address target, bytes memory data) internal view returns (bytes memory);
    function functionDelegateCall(address target, bytes memory data) internal returns (bytes memory);
    
    /**
     * @dev Verify and bubble up call results
     */
    function verifyCallResult(bool success, bytes memory returndata) internal pure returns (bytes memory);
}

/**
 * @dev Enhanced array operations with mathematical algorithms
 */
library Arrays {
    /**
     * @dev QuickSort implementation for different array types
     */
    function sort(uint256[] memory array) internal pure;
    function sort(address[] memory array) internal pure;
    function sort(bytes32[] memory array) internal pure;
    
    /**
     * @dev Binary search operations (O(log n))
     */
    function lowerBound(uint256[] storage array, uint256 element) internal view returns (uint256);
    function upperBound(uint256[] storage array, uint256 element) internal view returns (uint256);
    function lowerBoundMemory(uint256[] memory array, uint256 element) internal pure returns (uint256);
    function upperBoundMemory(uint256[] memory array, uint256 element) internal pure returns (uint256);
    
    /**
     * @dev Unsafe array access without bounds checking
     */
    function unsafeAccess(address[] storage arr, uint256 pos) internal pure returns (StorageSlot.AddressSlot storage);
    function unsafeAccess(bytes32[] storage arr, uint256 pos) internal pure returns (StorageSlot.Bytes32Slot storage);
    function unsafeAccess(uint256[] storage arr, uint256 pos) internal pure returns (StorageSlot.Uint256Slot storage);
    
    /**
     * @dev Memory array access without bounds checking
     */
    function unsafeMemoryAccess(uint256[] memory arr, uint256 pos) internal pure returns (uint256 res);
    function unsafeMemoryAccess(address[] memory arr, uint256 pos) internal pure returns (address res);
    function unsafeMemoryAccess(bytes32[] memory arr, uint256 pos) internal pure returns (bytes32 res);
}

/**
 * @dev Efficient boolean storage using bit manipulation
 */
library BitMaps {
    struct BitMap {
        mapping(uint256 => uint256) _data;
    }
    
    /**
     * @dev Get boolean value at index
     */
    function get(BitMap storage bitmap, uint256 index) internal view returns (bool);
    
    /**
     * @dev Set boolean value at index
     */
    function setTo(BitMap storage bitmap, uint256 index, bool value) internal;
    function set(BitMap storage bitmap, uint256 index) internal;
    function unset(BitMap storage bitmap, uint256 index) internal;
}

/**
 * @dev Historical value tracking with binary search optimization
 */
library Checkpoints {
    struct Trace224 {
        Checkpoint224[] _checkpoints;
    }
    
    struct Checkpoint224 {
        uint32 _key;
        uint224 _value;
    }
    
    /**
     * @dev Push new checkpoint with ordering validation
     */
    function push(Trace224 storage self, uint32 key, uint224 value) internal returns (uint224, uint224);
    
    /**
     * @dev Binary search for historical values
     */
    function lowerLookup(Trace224 storage self, uint32 key) internal view returns (uint224);
    function upperLookup(Trace224 storage self, uint32 key) internal view returns (uint224);
    function upperLookupRecent(Trace224 storage self, uint32 key) internal view returns (uint224);
    
    /**
     * @dev Get latest value and checkpoint
     */
    function latest(Trace224 storage self) internal view returns (uint224);
    function latestCheckpoint(Trace224 storage self) internal view returns (bool exists, uint32 key, uint224 value);
    
    /**
     * @dev Get checkpoint at specific position
     */
    function at(Trace224 storage self, uint32 pos) internal view returns (Checkpoint224 memory);
    function length(Trace224 storage self) internal view returns (uint256);
}

/**
 * @dev Double-ended queue with O(1) operations
 */
library DoubleEndedQueue {
    struct Bytes32Deque {
        uint128 _begin;
        uint128 _end;
        mapping(uint128 => bytes32) _data;
    }
    
    /**
     * @dev O(1) queue operations
     */
    function pushBack(Bytes32Deque storage deque, bytes32 value) internal;
    function popBack(Bytes32Deque storage deque) internal returns (bytes32 value);
    function pushFront(Bytes32Deque storage deque, bytes32 value) internal;
    function popFront(Bytes32Deque storage deque) internal returns (bytes32 value);
    
    /**
     * @dev O(1) access operations
     */
    function front(Bytes32Deque storage deque) internal view returns (bytes32 value);
    function back(Bytes32Deque storage deque) internal view returns (bytes32 value);
    function at(Bytes32Deque storage deque, uint256 index) internal view returns (bytes32 value);
    
    /**
     * @dev State management
     */
    function length(Bytes32Deque storage deque) internal view returns (uint256);
    function empty(Bytes32Deque storage deque) internal view returns (bool);
    function clear(Bytes32Deque storage deque) internal;
}

/**
 * @dev Enumerable set with O(1) operations
 */
library EnumerableSet {
    struct Set {
        bytes32[] _values;
        mapping(bytes32 => uint256) _positions;
    }
    
    /**
     * @dev O(1) set operations
     */
    function add(Set storage set, bytes32 value) internal returns (bool);
    function remove(Set storage set, bytes32 value) internal returns (bool);
    function contains(Set storage set, bytes32 value) internal view returns (bool);
    
    /**
     * @dev Enumeration support
     */
    function length(Set storage set) internal view returns (uint256);
    function at(Set storage set, uint256 index) internal view returns (bytes32);
    function values(Set storage set) internal view returns (bytes32[] memory);
    
    // Typed variants for common types
    struct Bytes32Set { Set _inner; }
    struct AddressSet { Set _inner; }
    struct UintSet { Set _inner; }
}

/**
 * @dev Binary heap for priority queue operations
 */
library Heap {
    struct Uint256Heap {
        uint256[] _data;
        function(uint256, uint256) view returns (bool) _comp;
    }
    
    /**
     * @dev O(1) access to highest priority element
     */
    function peek(Uint256Heap storage heap) internal view returns (uint256);
    
    /**
     * @dev O(log n) insertion and removal
     */
    function push(Uint256Heap storage heap, uint256 value) internal;
    function pop(Uint256Heap storage heap) internal returns (uint256);
    function replace(Uint256Heap storage heap, uint256 newValue) internal returns (uint256);
    
    /**
     * @dev Heap state management
     */
    function length(Uint256Heap storage heap) internal view returns (uint256);
    function empty(Uint256Heap storage heap) internal view returns (bool);
    function clear(Uint256Heap storage heap) internal;
}

/**
 * @dev Bit packing utilities for storage optimization
 */
library Packing {
    /**
     * @dev Pack multiple values into single storage slot
     */
    function pack_1_31(bytes1 left, bytes31 right) internal pure returns (bytes32 result);
    function pack_2_30(bytes2 left, bytes30 right) internal pure returns (bytes32 result);
    function pack_4_28(bytes4 left, bytes28 right) internal pure returns (bytes32 result);
    function pack_8_24(bytes8 left, bytes24 right) internal pure returns (bytes32 result);
    function pack_16_16(bytes16 left, bytes16 right) internal pure returns (bytes32 result);
    
    /**
     * @dev Extract packed values from storage slot
     */
    function extract_1_31(bytes32 packed) internal pure returns (bytes1 left, bytes31 right);
    function extract_2_30(bytes32 packed) internal pure returns (bytes2 left, bytes30 right);
    function extract_4_28(bytes32 packed) internal pure returns (bytes4 left, bytes28 right);
    function extract_8_24(bytes32 packed) internal pure returns (bytes8 left, bytes24 right);
    function extract_16_16(bytes32 packed) internal pure returns (bytes16 left, bytes16 right);
}

/**
 * @dev Bytes manipulation with mathematical search
 */
library Bytes {
    /**
     * @dev Search operations in bytes
     */
    function indexOf(bytes memory buffer, bytes1 needle) internal pure returns (uint256);
    function indexOf(bytes memory buffer, bytes memory needle) internal pure returns (uint256);
    function lastIndexOf(bytes memory buffer, bytes1 needle) internal pure returns (uint256);
    
    /**
     * @dev Extract substring from bytes
     */
    function slice(bytes memory buffer, uint256 start, uint256 length) internal pure returns (bytes memory);
}

/**
 * @dev Comparator functions for sorting algorithms
 */
library Comparators {
    /**
     * @dev Standard comparators for different types
     */
    function lt(uint256 a, uint256 b) internal pure returns (bool);
    function gt(uint256 a, uint256 b) internal pure returns (bool);
}

/**
 * @dev Math operation rounding directions
 */
enum Rounding {
    Floor,  // Round toward zero (default)
    Ceil,   // Round away from zero
    Trunc,  // Round toward negative infinity
    Expand  // Round away from negative infinity
}

/**
 * @dev Custom error types for safe operations
 */
error SafeCastOverflowedUintDowncast(uint8 bits, uint256 value);
error SafeCastOverflowedIntToUint(int256 value);
error SafeCastOverflowedIntDowncast(uint8 bits, int256 value);
error SafeCastOverflowedUintToInt(uint256 value);

/**
 * @dev Checkpoint structure for historical tracking
 */
struct Checkpoint224 {
    uint32 _key;
    uint224 _value;
}

struct Checkpoint208 {
    uint48 _key;
    uint208 _value;
}

struct Checkpoint160 {
    uint96 _key;
    uint160 _value;
}

import "@openzeppelin/contracts/utils/math/Math.sol";
import "@openzeppelin/contracts/utils/math/SafeCast.sol";
import "@openzeppelin/contracts/utils/structs/BitMaps.sol";

contract MathExample {
    using Math for uint256;
    using SafeCast for uint256;
    using BitMaps for BitMaps.BitMap;
    
    BitMaps.BitMap private permissions;
    
    function calculateReward(uint256 amount, uint256 rate) external pure returns (uint256) {
        // High precision calculation
        return Math.mulDiv(amount, rate, 10000);
    }
    
    function safeConvert(uint256 largeValue) external pure returns (uint128) {
        // Safe type conversion with overflow protection
        return largeValue.toUint128();
    }
    
    function setPermission(uint256 userId, bool hasPermission) external {
        // Efficient boolean storage
        permissions.setTo(userId, hasPermission);
    }
}