Conc-tree list

Not to be confused with cons.

A Conc Tree is a data-structure that stores element sequences, and provides amortized O(1) time append and prepend operations, O(log n) time insert and remove operations and O(log n) time concatenation. This data structure is particularly viable for functional task-parallel and data-parallel programming, and is relatively simple to implement compared to other data-structures with similar asymptotic complexity . Conc-Trees were designed to improve efficiency of data-parallel operations that do not depend on the iteration order , and improve constant factors in these operations by avoiding unnecessary copies of the data . Orthogonally, they are used to efficiently aggregate data in functional-style task-parallel algorithms, as an implementation of the conc-list abstraction , which are a parallel programming counterpart to functional cons-lists, and originally introduced by the Fortress language Fortress (programming language)..

Operations

The basic Conc-Tree operation is concatenation. Conc-Trees work on the following basic data-types:

trait Conc[T] {
  def left: Conc[T]
  def right: Conc[T]
  def level: Int
  def size: Int
}

case class Empty[T] extends Conc[T] {
  def level = 0
  def size = 0
}

case class Single[T](elem: T) extends Conc[T] {
  def level = 0
  def size = 1
}

case class <>[T](left: Conc[T], right: Conc[T]) extends Conc[T] {
  val level = 1 + math.max(left.level, right.level)
  val size = left.size + right.size
}

Concatenation in O(log n) time then works by ensuring that the difference in levels (i.e. heights) between any two sibling trees is one or less, similar to invariants maintained in AVL trees. This invariant ensures that the height of the tree (length of the longest path from the root to some leaf) is always logarithmic in the number of elements in the tree. Concatenation is implemented as follows:

def concat(xs: Conc[T], ys: Conc[T]) {
  val diff = xs.level - ys.level
  if (math.abs(diff) <= 1) new <>(xs, ys)
  else if (diff < -1) {
    if (xs.left.level >= xs.right.level) {
      val nr = concat(xs.right, ys)
      new <>(xs.left, nr)
    } else {
      val nrr = concat(xs.right.right, ys)
      if (nrr.level == xs.level - 3) {
        val nr = new <>(xs.right.left, nrr)
        new <>(xs.left, nr)
      } else {
        val nl = new <>(xs.left, xs.right.left)
        new <>(nl, nrr)
      }
    }
  } else {
    // symmetric case
  }
}

Amortized O(1) time appends (or prepends) are achieved by introducing a new inner node type called Append, and using it to encode a logarithmic-length list of Conc trees, strictly decreasing in height. . The following is an implementation of an append method that is worst-case O(log n) time and amortized O(1) time:

private def append[T](xs: Append[T], ys: Conc[T]) =
  if (xs.right.level > ys.level) new Append(xs, ys)
  else {
    val zs = new <>(xs.right, ys)
    xs.left match {
      case ws @ Append(_, _) => append(ws, zs)
      case ws => if (ws.level <= xs.level) concat(ws, zs) else new Append(ws, zs)
    }
  }
}

A detailed demonstration of these operations can be found in online resources, or in the original Conc-Tree paper. It was shown that these basic operations can be extended to support worst-case O(1) deque operations , while keeping the O(log n) concatenation time bound, at the cost of increasing the constant factors of all operations.