pchiusano · August 6, 2014 01:21 · Aug 6, 2014
diff --git a/buffer.scala b/buffer.scala
@@ -0,0 +1,27 @@
+import java.util.concurrent.atomic._
+import collection.mutable.ArrayBuffer
+
+/**
+ * Buffer type with purely functional API, using mutable
+ * `ArrayBuffer` and cheap copy-on-write scheme.
+ * Idea described by Bryan O'Sullivan in http://www.serpentine.com/blog/2014/05/31/attoparsec/
+ */
+class Buffer[A](id: AtomicLong, stamp: Long, values: ArrayBuffer[A], size: Int) {
+
+  /** Snoc a value onto the end of this `Buffer`, possibly using (unobservable) mutation of `values`! */
+  def :+(a: A): Buffer[A] =
+    if (id.compareAndSet(stamp, stamp+1)) { // threads race to be able to mutably update 'values'
+      values += a
+      new Buffer(id, stamp+1, values, size+1)
+    }
+    else // losers are forced to make a copy of the buffer
+      new Buffer(new AtomicLong(0), 0, ArrayBuffer.empty[A] ++ values.take(size) :+ a, size + 1)
+
+  def toSeq: Seq[A] = values.view.take(size)
+
+  override def toString = "Buffer(" ++ toSeq.mkString(", ") ++ ")"
+}
+
+object Buffer {
+  def empty[A]: Buffer[A] = new Buffer(new AtomicLong(0), 0, ArrayBuffer.empty[A], 0)
+}