jordanlewis

sealed abstract class BinaryTree[+T]
case object BinaryTreeLeaf extends BinaryTree[Nothing]
final case class BinaryTreeNode[T](left: BinaryTree[T], value: T, right: BinaryTree[T]) extends BinaryTree[T]

jordanlewis

object UnbalancedTreeSet {
  private def insert[T](x: T, t: BinaryTree[T])(implicit ordering: Ordering[T]): BinaryTree[T] = t match {
    case BinaryTreeLeaf => BinaryTreeNode(BinaryTreeLeaf, x, BinaryTreeLeaf)
    case tn @ BinaryTreeNode(a, y, b) =>
      if (ordering.lt(x, y)) BinaryTreeNode(insert(x, a), y, b)
      else if (ordering.lt(y, x)) BinaryTreeNode(a, y, insert(x, b))
      else tn
  }
  private def member[T](x: T, t: BinaryTree[T])(implicit ordering: Ordering[T]): Boolean = (x, t) match {
    case (_, BinaryTreeLeaf) => false

jordanlewis

class UnbalancedTreeSet[T] private (tree: BinaryTree[T]) (implicit val ordering: Ordering[T])
  extends Set[T] {

  def this()(implicit ordering : Ordering[T]) = this(BinaryTreeLeaf)(ordering)
  private def newSet(tree: BinaryTree[T]) = new UnbalancedTreeSet[T](tree);

  def insert(x: T) = newSet(UnbalancedTreeSet.insert(x, tree))
  def member(x: T) = UnbalancedTreeSet.member(x, tree)
}

jordanlewis

public class CacheTest {
    private Logger logger = LoggerFactory.getLogger(CacheTest.class);
    public AtomicInteger numEvicted = new AtomicInteger(0);
    private final LoadingCache<String, Integer> testCache = CacheBuilder.newBuilder()
            .maximumWeight(10)
            .weigher(new Weigher<String, Integer>() {
                @Override
                public int weigh(String key, Integer value) {
                    return key.length();
                }

jordanlewis

Exception in thread "main" java.io.IOError: java.io.IOException: Invalid argument
	at org.apache.cassandra.io.util.MmappedSegmentedFile$Builder.createSegments(MmappedSegmentedFile.java:225)
	at org.apache.cassandra.io.util.MmappedSegmentedFile$Builder.complete(MmappedSegmentedFile.java:202)
	at org.apache.cassandra.io.sstable.SSTableReader.load(SSTableReader.java:412)
	at org.apache.cassandra.io.sstable.SSTableReader.open(SSTableReader.java:186)
	at org.apache.cassandra.io.sstable.SSTableReader.open(SSTableReader.java:142)
	at org.apache.cassandra.io.sstable.SSTableLoader$1.accept(SSTableLoader.java:87)
	at java.io.File.list(File.java:1010)
	at org.apache.cassandra.io.sstable.SSTableLoader.openSSTables(SSTableLoader.java:58)
	at org.apache.cassandra.io.sstable.SSTableLoader.stream(SSTableLoader.java:108)

jordanlewis

class UnbalancedTreeSet[T] private (tree: BinaryTree[T]) (implicit val ordering: Ordering[T]) extends Set[T] {
  // ...
  def member(x: T) = UnbalancedTreeSet.member(x, tree, None)
  // ...
}

object UnbalancedTreeSet {
  // ...
  private def member[T](x: T, t: BinaryTree[T], c: Option[T])(implicit ordering: Ordering[T]): Boolean = (t, c) match {
    case (BinaryTreeLeaf, None) => false

jordanlewis

class ElementAlreadyExistsException extends RuntimeException

class UnbalancedTreeSet[T] private (tree: BinaryTree[T]) (implicit val ordering: Ordering[T]) extends Set[T] {
  // ...
  def insert(x: T) = try {
    newSet(UnbalancedTreeSet.insert(x, tree))
  } catch {
    case _:ElementAlreadyExistsException => this
  }
  // ...

jordanlewis

class ElementAlreadyExistsException extends RuntimeException

class UnbalancedTreeSet[T] private (tree: BinaryTree[T]) (implicit val ordering: Ordering[T]) extends Set[T] {
  // ...
  def insert(x: T) = try {
    newSet(UnbalancedTreeSet.insert(x, tree, None))
  } catch {
    case _:ElementAlreadyExistsException => this
  }
  // ...

jordanlewis

object BinaryTree {
  def complete[T](x: T, d: Int): BinaryTree[T] = d match {
    case 0 => BinaryTreeLeaf
    case _ => {
      val subtree = complete(x, d - 1)
      BinaryTreeNode(subtree, x, subtree)
    }
  }

  def balanced[T](x: T, d: Int)(implicit ordering: Ordering[T]): BinaryTree[T] = d match {

jordanlewis

class BinaryTreeTest extends Spec with ShouldMatchers with Checkers {
  describe("A complete tree") {
    it("should have 2^n - 1 nodes") {
      check(forAll(choose(0, 25)){n: Int =>
          BinaryTree.complete(0, n).size == scala.math.pow(2, n) - 1 })
    }
  }

  describe("A balanced tree") {
    it("should have n nodes") {