blog.petitviolet.net

    Merge sorted arrays with ordering in some manner in TypeScript

    2022-02-14

    TypeScript

    In Rust, iterable objects have peek method to get the next value without advancing the iterator. Peekable in std::iter - Rust

    This concept could be used to achieve the purpose. In merging 2 arrays with giving a certain order, peek each of them and then compare them to determine which one go first. My sample implementation of Peekable is:

    peekable.ts
    export const peekable = <T>(arr: T[]) => {
      const iterator = arr[Symbol.iterator]()
      let state = iterator.next()
      const peek = (): IteratorResult<T, null> => state
    
      type Next<T> = ReturnType<typeof peek> extends IteratorReturnResult<null> ? IteratorReturnResult<null> : IteratorYieldResult<T>
    
      return {
        peek: () => state,
        next: (): Next<T> => {
          const value = peek()
          state = iterator.next()
          return <Next<T>>value
        },
      }
    }
    

    Key takeaways are:

    • In JavaScript, Symbol.iterator is to get an iterator over an object
    • Store the first element in state so that peek() method can use the value without advancing iterator.
    • Declare Next<T> type and cast value before returning it in next so that the return type of next() can correspond to what peek() is going to return.
      • In other words, when peek() returns IteratorReturnResult which represents the end of the iterator, it's ensured that next() returns IteratorReturnResult as well.

    Thanks to peekable, it's easy to merge arrays with comparing thier first elements which is the purpose of this article.

    mergearrays.ts
    // compFn(t, u):  -1(t < u) | 0(t == u) | 1(t > u)
    export const mergeArrays = <T, U>(ts: T[], us: U[], compFn: (t: T, u: U) => -1 | 0 | 1) => {
      const tIterator = peekable(ts)
      const uIterator = peekable(us)
    
      const arr: (T | U)[] = []
      while (true) {
        const tPeek = tIterator.peek()
        const uPeek = uIterator.peek()
        if (tPeek.done && uPeek.done) {
          break
        }
        if (tPeek.done) {
          arr.push(uIterator.next().value)
        } else if (uPeek.done) {
          arr.push(tIterator.next().value)
        } else {
          if (compFn(tPeek.value, uPeek.value) >= 0) {
            arr.push(tIterator.next().value)
          } else {
            arr.push(uIterator.next().value)
          }
        }
      }
      return arr
    }
    

    Thanks to the Next<T> type restriction tIterator.next() is ensured being IteratorYieldResult<T> after guarding on tPeek.done. Besides, the second argument compFn returns a number, which is following Java's Comparable interface that returns a number as the result of comparing 2 given objects.