-
-
Save kiritsuku/1126402 to your computer and use it in GitHub Desktop.
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" | |
} |
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:
def map[B](f: A => B): LinkedList[B] = {
var xs: LinkedList[B] = LNil
for (x <- this.reverse)
xs = new +: (f(x), xs)
xs
}
It's more functional but slower because of the reversing. Also, in method filter without mutable state I came only to this ugly solution:
def filter(f: A => Boolean): LinkedList[A] = {
var xs = this
var first: LinkedList[A] = LNil
var last: +:[A] = null
while (!xs.isEmpty) {
if (f(xs.head)) {
val cur = new +: (xs.head, LNil)
if (first.isEmpty) first = cur
else last.t = cur
last = cur
}
xs = xs.tail
}
first
}
Maybe it is better, maybe not. Suggestions?
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.
Don't give +: a mutable tail, it seem the only reason to do so is to make constructing it a left to right traversal of the A array in LinkedList.apply. You can avoid that by: