Have ideas to improve npm?Join in the discussion! »

    warraysorted

    0.3.99 • Public • Published

    wArraySorted Build Status

    Collection of routines to operate effectively sorted arrays. For that ArraySorted provides customizable quicksort algorithm and a dozen functions to optimally find/add/remove single/multiple elements into a sorted array, add/remove sorted array to/from another sorted array. Use it to increase the performance of your algorithms.

    Try out

    npm install
    node sample/Sample.s
    

    Binary search

    Binary search algorithm is used for finding an item from an ordered list of elements. Its based on dividing in half the part of list that can contain the element, until the count of the possible locations is decreased to just one. More about binary search.

    Comparator vs Evaluator

    • Comparator - function that makes comparison between two values of two elements.

    Default comparator looks like:

    function comparator( a, b )
    {
      return a - b;
    }
    • Evaluator - function that makes some operations on passed values before they will be compared default comparison in that case looks like : evaluator( a ) - evaluator( b )

    Both can be combined together to perform some custom features. See examples.

    Difference between Index,Value and no-sufix versions

    • Index methods returns index of element as result or -1 if nothing founded.

    • Value methods returns element value as result or undefined if nothing founded.

    • Non sufix methods returns object with properties: value, index if element exists. Otherwise returns object with undefined as value and -1 as index.

      Examples.

    Methods

    • arraySortedLookUp - binary search of element in array, returns object containing properties: value, index. If nothing founded returns object with value property setted to undefined and index to -1.

    • arraySortedLookUpIndex - binary search of element in array, returns index of the element if it is found, otherwise returns -1.

    • arraySortedLookUpClosest - binary search of element in array, finds element equal to passed value or element with smallest possible difference. Returns object with properties: value, index. If nothing founded returns zero or length of array as index, it depends on element value, if its bigger/lower then last/first element of the array.

    • arraySortedLookUpInterval - looks for elements from passed interval that exists in array and returns range where this elements are locaded.

    • arraySortedLookUpEmbrace - returns range where all elements from interval can be located even if they do not exist in the current array, range can go out of interval boundaries for minimal possible value.

    • arraySortedLeftMostIndex - returns index of first element that is equal or bigger with smallest difference to passed value.

    • arraySortedRightMostIndex - returns index of last element that is equal or bigger with smallest difference to passed value.

    • arraySortedAdd - method adds the passed value to the array, no matter whether it has there or hasn't, and returns the new added or the updated index.

    Example #1

    let _ = wTools;
     
    let arr = [ 3,5,6,7,9 ];
    let e = 5
    let i = _.arraySortedLookUp( arr,);
    console.log( 'arraySortedLookUp(',e,') :',);
    // arraySortedLookUp( 5 ) : { value: 5, index: 1 }

    Example #2

    let _ = wTools;
     
    let arr = [ 3,5,6,7,9 ];
    let e = 4
    let i = _.arraySortedLookUpIndex( arr,);
    console.log( 'arraySortedLookUpIndex(',e,') :',);
    // arraySortedLookUpIndex( 4 ) : -1

    Example #3

    let _ = wTools;
     
    let arr = [ 1,2,5,9 ];
    let e = 4
    let i = _.arraySortedLookUpClosest( arr,);
    console.log( 'arraySortedLookUpClosest(',e,') :',);
    // arraySortedLookUpClosest( 4 ) : { value: 5, index: 2 }

    Example #4

    let _ = wTools;
     
    let arr = [ 0,1,4,5 ];
     
    let interval = [ 2, 5 ];
     
    let range = _.arraySortedLookUpInterval( arr,interval );
    console.log( 'arraySortedLookUpInterval(',interval,') :',range );
    // arraySortedLookUpInterval( [ 2, 5 ] ) : [ 2, 4 ]
     
    let range = _.arraySortedLookUpEmbrace( arr,interval );
    console.log( 'arraySortedLookUpEmbrace(',interval,') :',range );
     // arraySortedLookUpEmbrace( [ 2, 5 ] ) : [ 1, 4 ]

    For more examples see: samples/Interval.js, samples/Embrace.js, sample/LookUpDifference.js

    Example #5

    let _ = wTools;
     
    let arr = [ 0,0,0,0,1,1,1,1 ];
     
    let e = 1;
    let leftMost = _.arraySortedLeftMostIndex( arr, e );
    console.log( 'arraySortedLeftMostIndex(',e,') :',leftMost );
    // arraySortedLeftMostIndex( 1 ) : 4
     
    let e = 0;
    let rightMost = _.arraySortedRightMostIndex( arr, 0 );
    console.log( 'arraySortedRightMostIndex(',e,') :',rightMost );
    // arraySortedRightMostIndex( 0 ) : 3

    Example #6

    let _ = wTools;
    let arr = [ 1,2,5,9 ];
     
    let e = 0;
    let i = _.arraySortedAdd( arr,);
    console.log( 'arraySortedAdd(',e,') inserted to index :',i, "array: ", arr );
    // arraySortedAdd( 0 ) inserted to index : 0 array:  [ 0, 1, 2, 5, 9 ]

    Install

    npm i warraysorted

    DownloadsWeekly Downloads

    16,603

    Version

    0.3.99

    License

    MIT

    Unpacked Size

    38.4 kB

    Total Files

    5

    Last publish

    Collaborators

    • avatar