ForwardLinkedList_Sorted_Unique.sol

ForwardLinkedList_Sorted_Unique.sol

// SPDX-License-Identifier: BSD-3-Clause

pragma solidity ^0.8.0;

/************************
 * @author: squeebo_nft *
 ************************/

import "@openzeppelin/contracts/utils/Strings.sol";

contract ForwardLinkedList_Sorted_Unique{
  using Strings for uint256;

  struct Node{
    uint next;
    uint value;
  }

  constructor(){}

  function sort( uint[] calldata items ) external pure returns( uint[] memory ){
    uint head;
    uint head_;
    uint tail;
    uint tail_;
    bool result;

    uint total;
    Node[] memory nodes = new Node[]( items.length );
    unchecked{
      for( uint i; i < items.length; ++i ){
        ( result, head_, tail_ ) = binaryInsert( items[i], nodes, head, tail, total );
        if( result ){
          head = head_;
          tail = tail_;
          ++total;
        }
      }
    }


    uint[] memory sorted = new uint[]( total );
    Node memory curNode = nodes[ head ];
    unchecked{
      for( uint i = 0; i < total - 1; ++i ){
        sorted[ i ] = curNode.value;
        curNode = nodes[ curNode.next ];
      }
    }

    sorted[ total - 1 ] = nodes[ tail ].value;
    return sorted;
  }

  function binaryInsert( uint value, Node[] memory nodes, uint head, uint tail, uint total ) internal pure
      returns( bool, uint, uint ){
    if( total == 0 ){
      //push
      nodes[total] = Node( 0, value );
      return ( true, head, total );
    }

    Node memory curNode = nodes[ head ];
    if( value < curNode.value ){
      //unshift
      nodes[total] = Node( head, value );
      return ( true, total, tail );
    }

    if( value == curNode.value )
      return ( false, 0, 0 );


    while( curNode.next != tail ){
      Node memory prevNode = curNode;
      curNode = nodes[ prevNode.next ];
      if( value > curNode.value )
        continue;

      if( value == curNode.value )
        return ( false, 0, 0 );


      //insertAfter prevNode
      nodes[total] = Node( prevNode.next, value );
      prevNode.next = total;
      return ( true, head, tail );
    }


    //push
    nodes[tail].next = total;
    nodes[total] = Node( 0, value );
    return ( true, head, total );
  }
}