Created
December 16, 2013 05:05
-
-
Save johnynek/7982567 to your computer and use it in GitHub Desktop.
CatSeq: O(1) concatenation of sequences. What is this called?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import scala.collection.immutable.Seq | |
| object CatSeq { | |
| val empty: CatSeq[Nothing] = CatSeq[Nothing](0, Seq.empty, Seq.empty) | |
| } | |
| /** Data structure to do O(1) concatenation of lists | |
| */ | |
| case class CatSeq[+T](leftLen: Int, left: Seq[T], right: Seq[T]) extends Seq[T] { | |
| override def isEmpty = left.isEmpty && right.isEmpty | |
| override def head = if(left.isEmpty) right.head else left.head | |
| override def tail = if(left.isEmpty) right.tail else CatSeq(leftLen - 1, left.tail, right) | |
| def iterator = // go through this trouble to avoid calling right until the last minute. | |
| new Iterator[T] { | |
| var isLeft = true | |
| var iter = left.iterator | |
| def hasNext = iter.hasNext || (isLeft && { | |
| iter = right.iterator | |
| isLeft = false | |
| iter.hasNext | |
| }) | |
| def next = { | |
| val res = iter.next | |
| if(!iter.hasNext && isLeft) { | |
| iter = right.iterator | |
| isLeft = false | |
| } | |
| res | |
| } | |
| } | |
| def apply(idx: Int) = if(idx < leftLen) left(idx) else right(idx - leftLen) | |
| lazy val length = leftLen + right.length | |
| // TODO: jumping through the CanBuildFrom to make this the default | |
| // also, could be optimized when that is a CatSeq | |
| def concat[U>:T](that: Seq[U]): CatSeq[U] = CatSeq(length, this, that) | |
| override def toString = "CatSeq(%s, %s)".format(left, right) | |
| } | |
| val example = CatSeq.empty concat (List(1, 2)) concat (List(3, 4)) | |
| println("%s".format(example)) | |
| // use the iterator | |
| example.foreach(println(_)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment