Created
August 4, 2011 21:59
-
-
Save kiritsuku/1126402 to your computer and use it in GitHub Desktop.
own implementation of Scalas List
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
package listimpl | |
import org.specs2.mutable.SpecificationWithJUnit | |
import org.specs2.specification.Scope | |
class LinkedListTest extends SpecificationWithJUnit { | |
"LinkedList" should { | |
"have elements" in new Test { | |
xs.size === 3 | |
} | |
"have a string representation" in new Test { | |
xs.toString === "LinkedList(1, 2, 3)" | |
LNil.toString === "LNil" | |
} | |
"get an element by an idex" in new Test { | |
(LNil(5): LinkedList[Int]) must throwA[IndexOutOfBoundsException] | |
xs(-1) must throwA[IndexOutOfBoundsException] | |
xs(3) must throwA[IndexOutOfBoundsException] | |
xs(1) === 2 | |
} | |
"reverse elements" in new Test { | |
xs.reverse === LinkedList(3, 2, 1) | |
} | |
"prepend another LinkedList" in new Test { | |
val ys = LinkedList(4, 5, 6) | |
(xs ++: ys) === LinkedList(1, 2, 3, 4, 5, 6) | |
} | |
"append another LinkedList" in new Test { | |
val ys = LinkedList(4, 5, 6) | |
(xs ++ ys) === LinkedList(1, 2, 3, 4, 5, 6) | |
} | |
"do something for each element" in new Test { | |
var ys = List[Int]() | |
xs foreach { x => ys = x :: ys } | |
ys === List(3, 2, 1) | |
} | |
"map the elements" in new Test { | |
val ys = xs map { _+1 } | |
ys === LinkedList(2, 3, 4) | |
} | |
"take the first elements" in new Test { | |
(xs take 1) === LinkedList(1) | |
(xs take 2) === LinkedList(1, 2) | |
(xs take 3) === xs | |
(xs take 4) === xs | |
} | |
"drop the first elements" in new Test { | |
(xs drop 0) === xs | |
(xs drop 1) === LinkedList(2, 3) | |
(xs drop 2) === LinkedList(3) | |
(xs drop 3) === LNil | |
} | |
"filter elements" in new Test { | |
(xs filter { _%2 == 0 }) === LinkedList(2) | |
(xs filter { _%2 != 0 }) === LinkedList(1, 3) | |
(LinkedList[Int]() filter { _%2 == 0 }) === LNil | |
} | |
"contain an element" in new Test { | |
(xs contains 2) === true | |
(xs contains 5) === false | |
} | |
"find an element" in new Test { | |
(xs find { _%2 == 0 }) === Some(2) | |
(xs find { _%2 != 0 }) === Some(1) | |
} | |
"test if an element exists" in new Test { | |
(xs exists { _%2 == 0}) === true | |
(xs exists { _ > 5 }) === false | |
} | |
"fold left through the elements" in new Test { | |
(xs.foldLeft(0) { _+_ }) === 6 | |
(0 /: xs) { _+_ } === 6 | |
} | |
"sum all elements" in new Test { | |
xs.sum === 6 | |
} | |
"reduce left through the elements" in new Test { | |
(xs reduceLeft { (ret, x) => ret+x }) === 6 | |
} | |
"find min and max" in new Test { | |
xs.min === 1 | |
xs.max === 3 | |
} | |
"get init elements" in new Test { | |
xs.init == List(1, 2) | |
} | |
"get last element" in new Test { | |
xs.last === 3 | |
} | |
"be sorted" in { | |
val xs = LinkedList(6, 3, 5, 1, 2, 7, 9, 8, 4) | |
xs.sorted === LinkedList((1 to 9): _*) | |
} | |
"zip two LinkedLists" in new Test { | |
(xs zip LinkedList(3, 2, 1)) === LinkedList(1 -> 3, 2 -> 2, 3 -> 1) | |
} | |
} | |
trait Test extends Scope { | |
val xs = LinkedList(1, 2, 3) | |
} | |
} | |
//================================================================================ | |
import scala.{ UnsupportedOperationException => UOE } | |
abstract class LinkedList[+A] { self => | |
def head: A | |
def tail: LinkedList[A] | |
def init: LinkedList[A] | |
def last: A | |
def isEmpty: Boolean | |
def size: Int = { | |
def loop(xs: LinkedList[A], i: Int): Int = | |
if (xs.isEmpty) i else loop(xs.tail, i+1) | |
loop(this, 0) | |
} | |
def +: [B >: A](x: B): LinkedList[B] = | |
new +:(x, this) | |
def ++: [B >: A](xs: LinkedList[B]): LinkedList[B] = | |
if (this.isEmpty) xs | |
else if (xs.isEmpty) this | |
else { | |
var ys: LinkedList[B] = this | |
for (x <- xs.reverse) | |
ys +:= x | |
ys | |
} | |
def ++ [B >: A](xs: LinkedList[B]): LinkedList[B] = | |
if (this.isEmpty) xs | |
else this ++: xs | |
def /: [B] (init: B)(f: (B, A) => B): B = this.foldLeft(init)(f) | |
def :\ [B] (init: B)(f: (A, B) => B): B = this.foldRight(init)(f) | |
def apply(index: Int): A = { | |
if (this.isEmpty || index < 0 || index >= this.size) | |
throw new IndexOutOfBoundsException(index.toString) | |
else { | |
var i = 0 | |
var cur = this | |
while (i < index) { | |
cur = cur.tail | |
i += 1 | |
} | |
cur.head | |
} | |
} | |
def foreach[B](f: A => B) { | |
var cur = this | |
while (!cur.isEmpty) { | |
f(cur.head) | |
cur = cur.tail | |
} | |
} | |
def map[B](f: A => B): LinkedList[B] = { | |
var xs: LinkedList[B] = LNil | |
for (x <- this) | |
xs +:= f(x) | |
xs.reverse | |
} | |
def take(elems: Int): LinkedList[A] = | |
if (elems <= 0) LNil | |
else if (elems >= this.size) this | |
else { | |
var i = 0 | |
var xs: LinkedList[A] = LNil | |
var ys = this | |
while (i < elems) { | |
xs +:= ys.head | |
ys = ys.tail | |
i += 1 | |
} | |
xs.reverse | |
} | |
def drop(elems: Int): LinkedList[A] = | |
if (elems <= 0) this | |
else if (elems >= this.size) LNil | |
else { | |
var i = 0 | |
var cur = this | |
while (i < elems) { | |
cur = cur.tail | |
i += 1 | |
} | |
cur | |
} | |
def filter(f: A => Boolean): LinkedList[A] = { | |
var xs: LinkedList[A] = LNil | |
for (x <- this) | |
if (f(x)) | |
xs +:= x | |
xs.reverse | |
} | |
def reverse: LinkedList[A] = { | |
var xs: LinkedList[A] = LNil | |
for(x <- this) | |
xs +:= x | |
xs | |
} | |
def contains[B >: A](elem: B): Boolean = { | |
var xs = this | |
for (x <- this) | |
if (x == elem) | |
return true | |
false | |
} | |
def find(f: A => Boolean): Option[A] = { | |
var xs = this | |
for (x <- this) | |
if (f(x)) | |
return Some(x) | |
None | |
} | |
def exists(f: A => Boolean): Boolean = | |
find(f) != None | |
def foldLeft[B](init: B)(f: (B, A) => B): B = | |
if (this.isEmpty) throw new UOE("nil.foldLeft") | |
else { | |
var ret = init | |
for (x <- this) | |
ret = f(ret, x) | |
ret | |
} | |
def foldRight[B](init: B)(f: (A, B) => B): B = | |
this.reverse.foldLeft(init) { (a, b) => f(b, a) } | |
def reduceLeft[B >: A](f: (B, A) => B): B = | |
if (this.isEmpty) throw new UOE("nil.reduceLeft") | |
else this.tail.foldLeft[B](head) { f } | |
def sum[B >: A](implicit num: Numeric[B]): B = | |
(num.zero /: this) { num.plus } | |
def max[B >: A](implicit ord: Ordering[B]): B = | |
if (this.isEmpty) throw new UOE("nil.max") | |
else this reduceLeft { (ret, x) => if (ord.gteq(ret, x)) ret else x } | |
def min[B >: A](implicit ord: Ordering[B]): B = | |
if (this.isEmpty) throw new UOE("nil.max") | |
else this reduceLeft { (ret, x) => if (ord.lteq(ret, x)) ret else x } | |
def mkString: String | |
def mkString(start: String, sep: String, end: String): String = { | |
val sb = StringBuilder.newBuilder | |
sb append start | |
sb append head | |
if (!tail.isEmpty) { | |
sb append sep | |
sb append tail.head | |
for (x <- tail.tail) { | |
sb append sep | |
sb append x | |
} | |
} | |
sb append end | |
sb.toString | |
} | |
def sorted[B >: A](implicit ord: Ordering[B]): LinkedList[B] = { | |
import ord._ | |
def qsort(xs: LinkedList[B]): LinkedList[B] = { | |
xs match { | |
case LNil => LNil | |
case x +: xs => qsort(xs filter { _ < x }) ++: LinkedList(x) ++: qsort(xs filter { _ >= x }) | |
} | |
} | |
qsort(this) | |
} | |
def zip[B](xs: LinkedList[B]): LinkedList[(A, B)] = { | |
var ys: LinkedList[(A, B)] = LNil | |
var i1 = this.iterator | |
var i2 = xs.iterator | |
while (i1.hasNext && i2.hasNext) | |
ys +:= i1.next() -> i2.next() | |
ys.reverse | |
} | |
def iterator: Iterator[A] = new Iterator[A] { | |
var xs = self | |
def next(): A = { | |
val x = xs.head | |
xs = xs.tail | |
x | |
} | |
def hasNext = !xs.isEmpty | |
} | |
} | |
object LinkedList { | |
def apply[A](a: A*): LinkedList[A] = | |
(a :\ empty[A]) { _ +: _ } | |
def empty[A]: LinkedList[A] = LNil | |
} | |
private case class +: [A](head: A, tail: LinkedList[A]) extends LinkedList[A] { | |
def init = this take this.size-1 | |
def last = (this drop this.size-1).head | |
def isEmpty = false | |
def mkString = mkString("LinkedList(", ", ", ")") | |
override def toString = mkString | |
} | |
final case object LNil extends LinkedList[Nothing] { | |
def head = throw new UOE("nil head") | |
def tail = throw new UOE("nil tail") | |
def init = throw new UOE("nil init") | |
def last = throw new UOE("nil last") | |
def isEmpty = true | |
def mkString = "" | |
override def toString = "LNil" | |
} |
Oh, I'm sorry. I've copied the wrong version of filter. Here is the actual:
def filter(f: A => Boolean): LinkedList[A] = {
var first: LinkedList[A] = LNil
for (x <- this.reverse)
if (f(x))
first = new +: (x, first)
first
}
This does not look ugly any more. Now, I think it is the better solution than the one with the mutable state.
I don't need full performance - this code is not for production. But it is shorter and easier to read.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks for your response. I noticed this already. The problem with this solution is, that the Seq have to be reversed. I think that takes more time than appending to the last mutable element of the List. But mutable elements are not functional.
In method map, for example, I can change the behavior too:
It's more functional but slower because of the reversing. Also, in method filter without mutable state I came only to this ugly solution:
Maybe it is better, maybe not. Suggestions?