vkostyukov

/**
 * A tiny class that extends a list with four combinatorial operations:
 * ''combinations'', ''subsets'', ''permutations'', ''variations''.
 *
 * You can find all the ideas behind this code at blog-post:
 *
 *   http://vkostyukov.ru/posts/combinatorial-algorithms-in-scala/
 *
 * How to use this class.
 *

vkostyukov

/**
 * Time - O(n)
 * Space - O(1)
 */
def waterfall(a: Array[Int]): Int = {
  // get the max index
  var maxIndex = a.indexOf(a.max)

  // answer
  var v = 0

vkostyukov

// Heap.scala for lambdadays.org
abstract sealed class Heap {

  def min: Int
  def left: Heap
  def right: Heap

  def size: Int
  def height: Int

vkostyukov

abstract sealed class Tree {
  def value: Int
  def left: Tree
  def right: Tree
  def isEmpty: Boolean
  def isBlack: Boolean

  /**
   * Time - O(log n)
   * Space - O(log n)

vkostyukov

import scala.annotation.tailrec
abstract sealed class Tree {
  def value: Int
  def left: Tree
  def right: Tree
  def isEmpty: Boolean

  /**
   * Time - O(log n)
   * Space - O(log n)

vkostyukov

import scala.annotation.tailrec
abstract sealed class List {
  def head: Int
  def tail: List
  def isEmpty: Boolean

  /**
   * Time - O(n)
   * Space - O(n)
   */ 

vkostyukov

import scala.annotation.tailrec
abstract sealed class Tree[+A] {
  def value: A
  def left: Tree[A]
  def right: Tree[A]
  def isEmpty: Boolean
  def size: Int

  /**
   * Time - O(log n)

vkostyukov

class Queue[+A](in: List[A] = Nil, out: List[A] = Nil) {

  /**
   * Time - O(1)
   * Space - O(1)
   */
  def enqueue[B >: A](x: B): Queue[B] = new Queue(x :: in, out)

  /**
   * Time - O(1)

vkostyukov

import scala.annotation.tailrec
abstract sealed class List[+A] {
  def head: A
  def tail: List[A]
  def isEmpty: Boolean

  /**
   * Time - O(n)
   * Space - O(n)
   */ 

vkostyukov

/**
 * Experiments with Dual-Pivot Binary Search.
 * Written by Vladimir Kostyukov, http://vkostyukov.ru
 */

package dpbs;

import org.openjdk.jmh.annotations.GenerateMicroBenchmark;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Scope;