SeqUtil.scala

/**
Copyright 2018 Google LLC.

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

https://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

/**
 * Seq util functions
 */
object SeqUtil
{
  /**
    * Implements Clojure's merge-with
    *
    * @param m1
    * @param m2
    * @param f
    * @tparam K
    * @tparam V
    * @return
    */
  def mergeWith[K,V](m1: Map[K,V], m2: Map[K,V], f: (V,V) => V): Map[K,V] = {
    val keys1 = m1.keySet
    val keys2 = m2.keySet
    val allKeys = keys1.union(keys2)
    def foldFn(m: Map[K,V], k: K) = {
      if (keys1.contains(k) && keys2.contains(k)) {
        m + (k -> f(m1(k), m2(k)))
      } else if (keys1.contains(k)) {
        m + (k -> m1(k))
      } else {
        m + (k -> m2(k))
      }
    }
    val init = Map[K,V]()
    val result = allKeys.foldLeft(init)(foldFn)
    result
  }

  /**
    * This is loosely based on Clojure's merge-with, but allows for
    * the return map type to be different from the input maps' type since
    * this is Scala == statically typed.
    * It probably really makes sense to use this as an argument to a
    * foldLeft type of reduction because an initial value of a different type
    * needs to be guaranteed.
    *
    * @param m1 map to merge into to create output map (akin to init val for a foldLeft)
    * @param m2 input map
    * @param initW a fn to initialize the output map value for a new key
    * @param f how to merge a value in the new map with a value in the output map
    * @tparam K key type for both input and output map
    * @tparam V key type for input map
    * @tparam W key type for output amp
    * @return
    */
  def mergeLeftWith[K,V,W](m1: Map[K,W], m2: Map[K,V], initW: K => W, f: (W,V) => W): Map[K,W] = {
    val keys1 = m1.keySet
    val keys2 = m2.keySet
    val allKeys = keys1.union(keys2)
    def foldFn(m: Map[K,W], k: K) = {
      if (keys1.contains(k) && keys2.contains(k)) {
        m + (k -> f(m1(k), m2(k)))
      } else if (keys1.contains(k)) {
        m + (k -> m1(k))
      } else {
        val newVal = f(initW(k), m2(k))
        m + (k -> newVal)
      }
    }
    val init = Map[K,W]()
    val result = allKeys.foldLeft(init)(foldFn)
    result
  }

  /**
    * Implements Clojure's partition-by fn for Scala seqs -- given a seq and a fn,
    * segment the entire seq, in order, into a seq-of-seqs, where each inner
    * seq's values all produce the same output value (when f applied) as each other
    * Note: implementation does not use lazy seqs nor lazy vals
    *
    * @param seq
    * @param f set of all possible output values must implement ==
    * @tparam T
    * @return
    */
  def partitionBy[T](seq: Seq[T], f: (T) => Any): Seq[Seq[T]] = {
    if (seq.isEmpty) {
      val emptySeq: Seq[T] = Seq.empty
      Seq(emptySeq)
    } else if (seq.tail.isEmpty) {
      val onlyElem = seq.head
      val oneElemSeq: Seq[T] = Seq(onlyElem)
      Seq(oneElemSeq)
    } else {
      val firstElem = seq.head
      var currFnVal: Any = f(firstElem)
      var currSeq: Seq[T] = Seq()
      var result: Seq[Seq[T]] = Seq()
      for (e <- seq: Seq[T]) {
        val fnVal = f(e)
        if (fnVal == currFnVal) {
          currSeq = currSeq :+ e
        } else {
          currFnVal = fnVal
          result = result :+ currSeq
          currSeq = Seq(e)
        }
      }
      result = result :+ currSeq
      result
    }
  }
}