grouped.scala

import collection.immutable.VectorBuilder

object QuickBifunctor {
  implicit def pairmap2[A, B](k: (A, B)) = new {
    def :->[C](f: B => C): (A, C) =
      (k._1, f(k._2))
  }
}

sealed trait Order 
case object LT extends Order
case object EQ extends Order
case object GT extends Order

trait Grouping[A] {
  def compare(a1: A, a2: A): Order
  def isEqual(a1: A, a2: A): Boolean =
    compare(a1, a2) == EQ
}

object Grouping {
  implicit val IntGrouping: Grouping[Int] =
    new Grouping[Int] {
      def compare(a1: Int, a2: Int) =  
        if(a1 == a2) EQ
        else if(a1 < a2) LT
        else GT
    }
}

object Grouped {
  import QuickBifunctor._
  type I[K, V] = IndexedSeq[Vector[(K, V)]]
  type O[K, V] = IndexedSeq[Map[K, Vector[(K, V)]]]
  // you want to build up the Vector based on groupCompare and once you encounter a new key-value that doesn't belong with the group, you append the Vector to the List and start building a new Vector.
  def grouped[K, V](sorted: I[K, V])(implicit grp: Grouping[K]): O[K, V] =
    sorted map { kvs =>
      val vbMap = kvs.foldLeft(Map.empty: Map[K, VectorBuilder[(K, V)]]) { case (bins, kv@(k, _)) =>
        bins + ((bins.find { case (kk, _) => grp.isEqual(kk, k) } getOrElse (k, new VectorBuilder[(K, V)]())) :-> (_ += kv))
      }

      vbMap map { case (k, vb) => (k, vb.result()) }
    }
}

object Main {
  import Grouped._
  import NicePrint._

  val t: List[(I[Int, String], O[Int, String])] =
    List(
      (
        IndexedSeq.empty
      , IndexedSeq.empty
      )
    , (
        IndexedSeq(Vector())
      , IndexedSeq(Map())
      )
    , (
        IndexedSeq(Vector((1, "abc")))
      , IndexedSeq(Map((1, Vector((1, "abc")))))
      )
    , (
        IndexedSeq(Vector((1, "abc"), (2, "def")))
      , IndexedSeq(Map((1, Vector((1, "abc"))), (2, Vector((2, "def")))))
      )
    , (
        IndexedSeq(Vector((1, "abc"), (1, "def")))
      , IndexedSeq(Map((1, Vector((1, "abc"), (1, "def")))))
      )
    , (
        IndexedSeq(Vector((1, "abc"), (1, "def"), (2, "ghi")))
      , IndexedSeq(Map((1, Vector((1, "abc"), (1, "def"))), (2, Vector((2, "ghi")))))
      )
    , (
        IndexedSeq(Vector((1, "abc")), Vector((1, "abc")))
      , IndexedSeq(Map((1, Vector((1, "abc")))), Map((1, Vector((1, "abc")))))
      )    
    , (
        IndexedSeq(Vector((1, "abc")), Vector((2, "def")))
      , IndexedSeq(Map((1, Vector((1, "abc")))), Map((2, Vector((2, "def")))))
      )
    , (
        IndexedSeq(Vector((1, "abc"), (2, "def")), Vector((2, "ghi")))
      , IndexedSeq(Map((1, Vector((1, "abc"))), (2, Vector((2, "def")))), Map((2, Vector((2, "ghi")))))
      )    
    , (
        IndexedSeq(Vector((1, "abc")), Vector((2, "def"), (2, "ghi")))
      , IndexedSeq(Map((1, Vector((1, "abc")))), Map((2, Vector((2, "def"), (2, "ghi")))))
      )
    )

  def main(args: Array[String]) {
    t foreach {
      case (i, o) => {
        val r = grouped(i)
        println(if(r == o)
                  "* " + nprints(i)
                else
                  "- " + nprints(i) + "\n    expected: " + o + "\n    actual:   " + r + " }")
      }
    }   
    println(t.length + " completed") 
  }
}

object NicePrint {
  
  def nprintf[A](i: Seq[A], f: A => String): String = {
    val b = new StringBuilder
    b += '['
    val t = i.iterator
    while(t.hasNext) {
      b append f(t.next)
      if(t.hasNext) 
        b += ','
    }
    b += ']'
    b.toString
  }

  def nprint[A](i: Seq[A]): String = 
    nprintf(i, (_: A).toString)

  def nprints[A](i: Seq[Vector[A]]): String =
    nprintf(i, nprint(_: Vector[A]))

  def nprintm[K, V](i: Seq[Map[K, Vector[(K, V)]]]): String =
    nprintf(i, (m: Map[K, Vector[(K, V)]]) => 
      "{" + nprintf(m.toList, (w: (K, Vector[(K, V)])) => "(" + w._1.toString + "," + 
        nprint(w._2)
      + ")") + "}")
}

/*

> import Data.Map(Map)
> import qualified Data.Map as M
> import Data.List
> import Data.Maybe
> import Control.Monad.Instances

> type IndexedSeq a = [a]
> type Vector a = [a]
> type I k v = IndexedSeq (Vector (k, v))
> type O k v = IndexedSeq (Map k (Vector (k, v)))

> getOrElse = 
>   fromMaybe

> grouped ::
>   Ord k =>
>   IndexedSeq (Vector (k ,v))
>   -> IndexedSeq (Map k (Vector (k, v)))
> grouped sorted =
>   fmap (\kvs -> foldr (\kv@(k, v) bins -> uncurry M.insert (fmap (kv:) ((k, []) `getOrElse` find (\(kk, _) -> kk == k) (M.toList bins))) bins) M.empty kvs) sorted

> main =
>   let t ::
>         [(I Int String, O Int String)]
>       t = [
>             (
>               []
>             , []
>             )
>           , (
>               [[(1, "abc")]]
>             , [M.fromList [(1, [(1, "abc")])]]
>             )
>           , (
>               [[(1, "abc"), (2, "def")]]
>             , [M.fromList [(1, [(1, "abc")]), (2, [(2, "def")])]]
>             )
>           , (
>               [[(1, "abc"), (1, "def")]]
>             , [M.fromList [(1, [(1, "abc"), (1, "def")])]]
>             )
>           , (
>               [[(1, "abc"), (1, "def"), (2, "ghi")]]
>             , [M.fromList [(1, [(1, "abc"), (1, "def")]), (2, [(2, "ghi")])]]
>             )
>           , (
>               [[(1, "abc")], [(1, "abc")]]
>             , [M.fromList [(1, [(1, "abc")])], M.fromList [(1, [(1, "abc")])]]
>             )
>           , (
>               [[(1, "abc")], [(2, "def")]]
>             , [M.fromList [(1, [(1, "abc")])], M.fromList [(2, [(2, "def")])]]
>             )
>           , (
>               [[(1, "abc"), (2, "def")], [(2, "ghi")]]
>             , [M.fromList [(1, [(1, "abc")]), (2, [(2, "def")])], M.fromList [(2, [(2, "ghi")])]]
>             )
>           , (
>               [[(1, "abc")], [(2, "def"), (2, "ghi")]]
>             , [M.fromList [(1, [(1, "abc")])], M.fromList [(2, [(2, "def"), (2, "ghi")])]]
>             )
>           ]          
>   in mapM_ (\(i, o) -> let r = grouped i
>                        in putStrLn $ if r == o
>                                        then
>                                          "* " ++ show i
>                                        else
>                                          concat ["- ", show i, "\n    expected: ", show o, "\n    actual:   ", show r, " }"]) t

*/