Skip to content

Instantly share code, notes, and snippets.

@Arneball Arneball/gist:8399601
Last active Jan 3, 2016

Embed
What would you like to do?
/** 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()
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.