pathikrit

/**
  * An util that provides synchronization using value equality rather than referential equality
  * It is guaranteed that if two objects are value-equal, their corresponding blocks are invoked mutually exclusively.
  * But the converse may not be true i.e. if two objects are not value-equal, they may be invoked exclusively too
  * Note: Typically, no need to create instances of this class. The default instance in the companion object can be safely reused
  *
  * @param size There is a 1/size probability that two invocations that could be invoked concurrently is invoked sequentially
  *
  * Example usage:
  *   import EquivalenceLock.{defaultInstance => lock}

pathikrit

class BiMap[A, B] private(var a2b: Map[A, B], var b2a: Map[B, A]) extends Tuple2(a2b, b2a) with collection.mutable.MapLike[A, B, BiMap[A, B]] {
  override def +=(kv: (A, B)) = {
    a2b = a2b + kv
    b2a = b2a + kv.swap
    this
  }

  override def -=(a: A) = {
    get(a).foreach {b => b2a = b2a - b}
    a2b = a2b - a

pathikrit

trait DataTable[PK, C, V] {
  type Row = C => V
  type Filter = Row => Boolean

  val table: PK => Row
  def apply(id: PK): Row = table(id)

  def keys: Iterable[PK]
  def rows: Iterable[Row] = keys.map(apply)

pathikrit

object TypedRest {
  type Id[A] = Long

  object Request {
    private[this] trait HasId[A] {
      val id: Id[A]
    }
    trait Get[A] extends HasId[A]
    trait Put[A] extends HasId[A]
    trait Post[A]

pathikrit

import java.io._
import java.nio.file.{Files, Path}
import java.util.StringTokenizer

import scala.io.Codec

/**
 * Scala implementation of a faster java.util.Scanner
 * See: http://codeforces.com/blog/entry/21125
 * All next methods throw NoSuchElementException when !hasNext

pathikrit

import java.util.ArrayList;

public class FastPrependArrayList<A> {
    private ArrayList<A> appends = new ArrayList<A>();
    private ArrayList<A> prepends = new ArrayList<A>();

    public void append(A element) {
        appends.add(element);
    }

pathikrit

class OrderLearner[A](root: A) {
  import scala.collection.mutable.{Map => Dict}
  private val next = Dict.empty[A, Set[A]] withDefaultValue Set.empty[A]

  def learn(words: Seq[A]*) = for {
    i <- words.indices
    _ = words(i).foreach(u => next(root) += u)
    j <- words.indices drop (i+1)
    (u, v) <- words(i) zip words(j) find {case (a, b) => a != b}
  } next(u) += v

pathikrit

class NorvigSpellChecker(corpus: String, alphabet: Seq[Char] = 'a' to 'z', level: Int = 2) {
  val words = s"[${alphabet.head}-${alphabet.last}]+".r.findAllIn(corpus.toLowerCase).toSeq

  val count = words.groupBy(_.toSeq).mapValues(_.size) withDefaultValue 0

  def edit(n: Int)(word: Seq[Char]): Set[Seq[Char]] = n match {
    case 0 => Set(word)
    case 1 =>
      val splits = word.indices map word.splitAt
      val deletes = splits collect {case (a, b0 +: b1) => a ++ b1}

pathikrit

class AutoSuggest(corpus: String, alphabet: Seq[Char] = 'a' to 'z', depth: Int = 2) {
  val words = s"[${alphabet.head}-${alphabet.last}]+".r
    .findAllIn(corpus.toLowerCase).toSeq
    .groupBy(_.toSeq).mapValues(_.size)
    .par withDefaultValue 0

  def editDistance(a: Seq[Char], b: Seq[Char]) = {
    lazy val d: Stream[Stream[Int]] = Stream.tabulate(a.length + 1, b.length + 1) {
      case (i, j) if (i - j).abs > depth => Int.MaxValue
      case (i, 0) => i

pathikrit

trait NotSubTypeOf[A, B] // encoding to capture A is not a subtype of B
// Note: We can use infix notation to write `A NotSubTypeOf B` instead of `NotSubTypeOf[A, B]`

// evidence for any two arbitrary types A and B, A is not a subtype of B
implicit def isSub[A, B]: A NotSubTypeOf B = null

// define ambigous implicits to trigger compile error in case A is a subtype of B (or A =:= B)
implicit def iSubAmbig1[A, B >: A]: A NotSubTypeOf B = null
implicit def iSubAmbig2[A, B >: A]: A NotSubTypeOf B = null