gistfile1.scala

  /** For every collection that is a sequence, pimp the method groupedSeq */
  implicit class GroupedSeq[SEQ[X]<:Seq[X], T](val seq: SEQ[T]) extends AnyVal {

    /** Takes a function that maps elems of type T to the grouping kind U
      * All sequential elements that has the same group U will be grouped in a SEQ
      * Example {{{
      *   class Person(name: String)
      *   val people = List(Person("ADAM"), Person("adam"), Person("pelle"))
      *   people.groupeSeq{ _.name.toUpperCase } => List(List(Person(ADAM), Person(adam)), List(pelle))
      * }}}
      * Example 2 {{{
      *   class Person(name: String)
      *   val people = IndexedSeq(Person("ADAM"), Person("adam"), Person("pelle"))
      *   people.groupeSeq{ _.name.toUpperCase } => IndexedSeq(IndexedSeq(Person(ADAM), Person(adam)), IndexedSeq(pelle))
      * }}}
      * @param groupCreator function that takes an element T and creates the group for
      * implicit parameters that creates the inner Seqs and the outer Seq
      */
    def groupedSeq[U](groupCreator: T => U)(implicit
        cbfInner: CanBuildFrom[SEQ[T], T, SEQ[T]],
        cbfOuter: CanBuildFrom[SEQ[T], SEQ[T], SEQ[SEQ[T]]]): SEQ[SEQ[T]] = {
      if(seq.isEmpty) cbfOuter().result() else {
        // cache the builders with an int that indicates the insertion order, kinda good to have it preserved
        type CacheValueType = (Int, mutable.Builder[T, SEQ[T]])
        val cache = collection.mutable.Map[U, CacheValueType]()
        // We keep track of insertion order so that the outer sequence elements comes in the same
        // order that they were seen originally
        // eg SEQ("AA", "b", "aa").groupedSeq{ _.toUpperCase } == SEQ(SEQ(AA, aa), SEQ(b))
        var insertionOrder = 0
        
        // Get the builder for the specific key
        def getGroup(key: U) = cache.getOrElseUpdate(key, {
          insertionOrder += 1
          insertionOrder -> cbfInner()
        })

        /** Recursively traverse the sequence,
          * pattern match the head of the remaining sequence,
          * find the group builder in cache,
          * add the elem to the group that is given by groupCreator(head)
          */
        @tailrec def traverseSeq(remaining: Seq[T]): Unit = remaining match {
          case Seq(head, tail @ _*) =>
            val (_, builder) = getGroup(groupCreator(head)) // 0th element is the index, not needed here though
            builder += head // add the head to the builder that corresponds to group of type U
            traverseSeq(tail) // treverse the tail
          case Seq() => // noop, were done, no more elems
        }
        traverseSeq(seq)
        // traverse the values in the cache by insertion order and insert them into the builder for SEQ[SEQ[T]]
        cache.valuesIterator.toSeq.sortBy{ _._1 }.foldLeft(cbfOuter()) {
          _ += _._2.result()
        }.result()
      }
    }