From a55f14b464e6738545ac954ba4e8bc86a217acf9 Mon Sep 17 00:00:00 2001 From: Matthias Zenger Date: Tue, 10 Jun 2003 12:02:29 +0000 Subject: Renamed some functions in the collection classes. --- sources/scala/HashMap.scala | 34 +++++----- sources/scala/HashSet.scala | 24 +++---- sources/scala/HashTable.scala | 96 +++++++++++++-------------- sources/scala/Iterable.scala | 2 +- sources/scala/LinkedList.scala | 58 +++++++++++++--- sources/scala/ListBuffer.scala | 146 +++++++++++++++++++++++++++++++++++++++++ sources/scala/ListSet.scala | 2 +- sources/scala/Map.scala | 122 +++++++++++++++++----------------- sources/scala/MutableMap.scala | 70 ++++++++++---------- sources/scala/Seq.scala | 22 ++++--- sources/scala/Set.scala | 136 +++++++++++++++++++------------------- 11 files changed, 451 insertions(+), 261 deletions(-) create mode 100644 sources/scala/ListBuffer.scala diff --git a/sources/scala/HashMap.scala b/sources/scala/HashMap.scala index ed6519a383..4aa4bc7ab5 100644 --- a/sources/scala/HashMap.scala +++ b/sources/scala/HashMap.scala @@ -14,33 +14,33 @@ package scala; class HashMap[A, B] extends MutableMap[A, B] with HashTable[A] { def get(key: A) = findEntry(key) match { - case None => None - case Some(e) => Some(e.value); + case None => None + case Some(e) => Some(e.value); } def update(key: A, value: B) = findEntry(key) match { - case None => addEntry(new Entry(key, value)); - case Some(e) => e.value = value; + case None => addEntry(new Entry(key, value)); + case Some(e) => e.value = value; } def remove(key: A) = { - val old = apply(key); - removeEntry(key); - old; + val old = apply(key); + removeEntry(key); + old; } - def iterator = new Iterator[Pair[A, B]] { - val iter = entries; - def hasNext = iter.hasNext; - def next = iter.next.toPair; - } + def elements = new Iterator[Pair[A, B]] { + val iter = entries; + def hasNext = iter.hasNext; + def next = iter.next.toPair; + } protected class Entry(k: A, v: B) { - def key = k; - var value = v; - def toPair = Pair(k, value); - override def toString() = k.toString() + " -> " + value; + def key = k; + var value = v; + def toPair = Pair(k, value); + override def toString() = k.toString() + " -> " + value; } - protected def entryKey(e: Entry) = e.key; + protected def entryKey(e: Entry) = e.key; } diff --git a/sources/scala/HashSet.scala b/sources/scala/HashSet.scala index 08d4b95d5b..763222b526 100644 --- a/sources/scala/HashSet.scala +++ b/sources/scala/HashSet.scala @@ -13,21 +13,21 @@ package scala; */ class HashSet[A] extends Set[A] with HashTable[A] { - def contains(elem: A): Boolean = findEntry(elem) match { - case None => false - case Some(_) => true - } + def contains(elem: A): Boolean = findEntry(elem) match { + case None => false + case Some(_) => true + } - def add(elem: A): Unit = findEntry(elem) match { - case None => addEntry(elem); - case Some(_) => - } + def add(elem: A): Unit = findEntry(elem) match { + case None => addEntry(elem); + case Some(_) => + } - def remove(elem: A): Unit = removeEntry(elem); + def remove(elem: A): Unit = removeEntry(elem); - def iterator = entries; + def elements = entries; - protected type Entry = A; + protected type Entry = A; - protected def entryKey(e: Entry) = e; + protected def entryKey(e: Entry) = e; } diff --git a/sources/scala/HashTable.scala b/sources/scala/HashTable.scala index 8d551a1c52..c57b1b59a6 100644 --- a/sources/scala/HashTable.scala +++ b/sources/scala/HashTable.scala @@ -19,16 +19,16 @@ abstract class HashTable[A] { /** The initial size of the hash table. */ - protected val initialSize: Int = 16; + protected val initialSize: Int = 16; - /** The initial threshold - */ - protected val initialThreshold: Int = ((initialSize as Float) * loadFactor) as Int; + /** The initial threshold + */ + protected val initialThreshold: Int = ((initialSize as Float) * loadFactor) as Int; /** The actual hash table. */ - protected var table: Array[List[Entry]] = new Array(initialSize); - initTable(initialSize - 1); + protected var table: Array[List[Entry]] = new Array(initialSize); + initTable(initialSize - 1); /** The number of mappings contained in this hash table. */ @@ -43,55 +43,55 @@ abstract class HashTable[A] { def size = tableSize; protected def findEntry(key: A): Option[Entry] = - table(index(elemHashCode(key))).find(entryFor(key)); + table(index(elemHashCode(key))).find(entryFor(key)); protected def addEntry(e: Entry): Unit = { - val h = index(elemHashCode(entryKey(e))); - table(h) = e :: table(h); - tableSize = tableSize + 1; - if (tableSize > threshold) - resize(2 * table.length); + val h = index(elemHashCode(entryKey(e))); + table(h) = e :: table(h); + tableSize = tableSize + 1; + if (tableSize > threshold) + resize(2 * table.length); } protected def removeEntry(key: A): Unit = { - val old = findEntry(key); - old match { - case None => - case Some(e) => { - val idx = index(elemHashCode(key)); - table(idx) = table(idx).filter(e => !elemEquals(entryKey(e), key)); - tableSize = tableSize - 1; - } - } + val old = findEntry(key); + old match { + case None => + case Some(e) => { + val idx = index(elemHashCode(key)); + table(idx) = table(idx).filter(e => !elemEquals(entryKey(e), key)); + tableSize = tableSize - 1; + } + } } def clear = { - initTable(table.length - 1); - tableSize = 0; + initTable(table.length - 1); + tableSize = 0; } - protected type Entry; - - protected def entryKey(e: Entry): A; - - protected def entries = new Iterator[Entry] { - val iterTable = table; - var idx = table.length - 1; - var xs = iterTable(idx); - scan(); - def hasNext = !xs.isEmpty; - def next = { - val res = xs.head; - xs = xs.tail; - scan(); - res; - } - def scan(): Unit = if (xs.isEmpty && (idx > 0)) { - idx = idx - 1; - xs = iterTable(idx); - scan(); - } - } + protected type Entry; + + protected def entryKey(e: Entry): A; + + protected def entries = new Iterator[Entry] { + val iterTable = table; + var idx = table.length - 1; + var xs = iterTable(idx); + scan(); + def hasNext = !xs.isEmpty; + def next = { + val res = xs.head; + xs = xs.tail; + scan(); + res; + } + def scan(): Unit = if (xs.isEmpty && (idx > 0)) { + idx = idx - 1; + xs = iterTable(idx); + scan(); + } + } private def entryFor(key: A) = (e: Entry => elemEquals(entryKey(e), key)); @@ -104,8 +104,8 @@ abstract class HashTable[A] { val newTable: Array[List[Entry]] = new Array(newSize); initTable(newSize - 1); def rehash(i: Int) = { - if (i >= 0) - rehashList(table(i)); + if (i >= 0) + rehashList(table(i)); } def rehashList(xs: List[Entry]): Unit = xs.match { case Nil => () @@ -125,7 +125,7 @@ abstract class HashTable[A] { protected def elemHashCode(key: A) = key.hashCode(); protected final def improve(hcode: Int) = { - var h: Int = hcode + ~(hcode << 9); + var h: Int = hcode + ~(hcode << 9); h = h ^ (h >>> 14); h = h + (h << 4); h ^ (h >>> 10); diff --git a/sources/scala/Iterable.scala b/sources/scala/Iterable.scala index a0edf1a7f3..47d7715987 100644 --- a/sources/scala/Iterable.scala +++ b/sources/scala/Iterable.scala @@ -10,5 +10,5 @@ package scala; trait Iterable[+A] { - def iterator: Iterator[A]; + def elements: Iterator[A]; } diff --git a/sources/scala/LinkedList.scala b/sources/scala/LinkedList.scala index 064fe011c2..bd500e13e2 100644 --- a/sources/scala/LinkedList.scala +++ b/sources/scala/LinkedList.scala @@ -1,13 +1,51 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + package scala; -class LinkedList[a]() { - var elem: a = _; - var next: LinkedList[a] = null; - def append(x: a): LinkedList[a] = { - val l = new LinkedList[a](); - l.elem = x; - this.next = l; - l - } -} +class LinkedList[A] with Seq[A] { + var elem: A = _; + var next: LinkedList[A] = null; + + def append(x: A): LinkedList[A] = { + val l = new LinkedList[A](); + l.elem = x; + this.next = l; + l + } + + def length: Int = 1 + (if (next == null) 0 else next.length); + + def apply(n: Int): A = { + if (n == 0) elem + else if (next == null) null + else next.apply(n - 1); + } + def at(n: Int): A = apply(n); + + def get(n: Int): Option[A] = { + if (n == 0) Some(elem) + else if (next == null) None + else next.get(n - 1); + } + + def elements: Iterator[A] = new Iterator[A] { + var elems = LinkedList.this; + def hasNext = (elems != null); + def next = { + val res = elems.elem; + elems = elems.next; + res; + } + } + + def toList: List[A] = + if (next == null) (elem :: Nil) else (elem :: next.toList); +} diff --git a/sources/scala/ListBuffer.scala b/sources/scala/ListBuffer.scala new file mode 100644 index 0000000000..f861df0606 --- /dev/null +++ b/sources/scala/ListBuffer.scala @@ -0,0 +1,146 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala; + +class ListBuffer[A] with Seq[A] with PartialFunction[Int, A] { + + protected var first: LinkedList[A] = null; + protected var last: LinkedList[A] = null; + protected var len: Int = 0; + + def size: Int = len; + + def length: Int = len; + + def isDefinedAt(n: Int) = (n >= 0) && (n < len); + + def apply(n: Int): A = get(n) match { + case None => null + case Some(value) => value + } + + def get(n: Int): Option[A] = first.get(n); + + def at(n: Int): A = apply(n); + + def remove(n: Int): A = { + val old = apply(n); + if (n >= len) + error("cannot remove element " + n + " in ListBuffer"); + if ((n == 0) && (len == 1)) { + first = null; + last = null; + } else if (n == 0) { + first = first.next; + } else { + var elem = first; + var i = n; + while (i > 1) { + elem = elem.next; + i = i - 1; + } + elem.next = elem.next.next; + if (n == (len - 1)) { + last = elem.next; + } + } + len = len - 1; + old; + } + + def clear: Unit = { + first = null; + last = null; + len = 0; + } + + def update(n: Int, newelem: A): Unit = { + var elem = first; + var i = n; + while (i > 0) { + elem = elem.next; + if (elem == null) + error("cannot update element " + n + " in ListBuffer"); + i = i - 1; + } + elem.elem = newelem; + } + + def insert(n: Int, newelem: A): Unit = { + if (n == 0) + prepend(newelem); + else if (n >= len) + append(newelem); + else { + var elem = first; + var i = n; + while (i > 1) { + elem = elem.next; + if (elem == null) + error("cannot insert element " + n + " in ListBuffer"); + i = i - 1; + } + val old = elem.next; + elem.next = new LinkedList[A]; + elem.next.elem = newelem; + elem.next.next = old; + } + } + + def prepend(elem: A) = { + if (len == 0) { + first = new LinkedList[A]; + first.elem = elem; + last = first; + } else { + val old = first; + first = new LinkedList[A]; + first.elem = elem; + first.next = old; + } + len = len + 1; + } + + def prependAll(elem: A*) = + (elem as List[A]).reverse.foreach(e => prepend(e)); + + def prependSeq(iter: Iterable[A]) = prependIterator(iter.elements); + + protected def prependIterator(iter: Iterator[A]): Unit = if (iter.hasNext) { + val cur = iter.next; + prependIterator(iter); + prepend(cur); + } + + def +=(elem: A) = append(elem); + + def +=(elems: Iterable[A]) = appendSeq(elems); + + def append(elem: A) = { + if (len == 0) + prepend(elem); + else { + last.next = new LinkedList[A]; + last.next.elem = elem; + last = last.next; + len = len + 1; + } + } + + def appendAll(elem: A*) = (elem as List[A]).foreach(e => append(e)); + + def appendSeq(iter: Iterable[A]) = iter.elements.foreach(e => append(e)); + + def elements: Iterator[A] = first.elements; + + def toList: List[A] = first.toList; + + override def toString() = toList.toString(); +} diff --git a/sources/scala/ListSet.scala b/sources/scala/ListSet.scala index d5abe5406a..0ee60b1943 100644 --- a/sources/scala/ListSet.scala +++ b/sources/scala/ListSet.scala @@ -24,7 +24,7 @@ class ListSet[A] extends Set[A] { def clear: Unit = { elems = Nil; } - def iterator: Iterator[A] = elems.iterator; + def elements: Iterator[A] = elems.elements; override def toList: List[A] = elems; } diff --git a/sources/scala/Map.scala b/sources/scala/Map.scala index fb1c235486..0a42a7fccd 100644 --- a/sources/scala/Map.scala +++ b/sources/scala/Map.scala @@ -15,71 +15,71 @@ trait Map[A, +B] with Function1[A, B] with PartialFunction[A, B] with Iterable[Pair[A, B]] { - def size: Int; + def size: Int; def isEmpty: Boolean = (size == 0); def apply(key: A): B = get(key) match { - case None => null - case Some(value) => value + case None => null + case Some(value) => value } - def get(key: A): Option[B]; - - def remove(key: A): B; - - def contains(key: A): Boolean = get(key) match { - case None => false - case Some(_) => true - } - - def isDefinedAt(key: A) = contains(key); - - def clear: Unit; - - def keys: Iterator[A] = new Iterator[A] { - val iter = iterator; - def hasNext = iter.hasNext; - def next = iter.next._1; - } - - def values: Iterator[B] = new Iterator[B] { - val iter = iterator; - def hasNext = iter.hasNext; - def next = iter.next._2; - } - - def foreach(f: (A, B) => Unit) = { - val iter = iterator; - while (iter.hasNext) { - val Pair(key, value) = iter.next; - f(key, value); - } - } - - def filter(p: (A, B) => Boolean): Unit = toList foreach { - case Pair(key, value) => if (p(key, value)) { val old = remove(key); } - } - - def toList: List[Pair[A, B]] = { - var res: List[Pair[A, B]] = Nil; - val iter = iterator; - while (iter.hasNext) { - res = iter.next :: res; - } - res; - } - - override def toString() = - if (size == 0) - "{}" - else - "{" + { - val iter = iterator; - var res = iter.next.toString(); - while (iter.hasNext) { - res = res + ", " + iter.next; - } - res; - } + "}"; + def get(key: A): Option[B]; + + def remove(key: A): B; + + def contains(key: A): Boolean = get(key) match { + case None => false + case Some(_) => true + } + + def isDefinedAt(key: A) = contains(key); + + def clear: Unit; + + def keys: Iterator[A] = new Iterator[A] { + val iter = elements; + def hasNext = iter.hasNext; + def next = iter.next._1; + } + + def values: Iterator[B] = new Iterator[B] { + val iter = elements; + def hasNext = iter.hasNext; + def next = iter.next._2; + } + + def foreach(f: (A, B) => Unit) = { + val iter = elements; + while (iter.hasNext) { + val Pair(key, value) = iter.next; + f(key, value); + } + } + + def filter(p: (A, B) => Boolean): Unit = toList foreach { + case Pair(key, value) => if (p(key, value)) { val old = remove(key); } + } + + def toList: List[Pair[A, B]] = { + var res: List[Pair[A, B]] = Nil; + val iter = elements; + while (iter.hasNext) { + res = iter.next :: res; + } + res; + } + + override def toString() = + if (size == 0) + "{}" + else + "{" + { + val iter = elements; + var res = iter.next.toString(); + while (iter.hasNext) { + res = res + ", " + iter.next; + } + res; + } + "}"; } diff --git a/sources/scala/MutableMap.scala b/sources/scala/MutableMap.scala index 861a9f6b60..1d7c3d6931 100644 --- a/sources/scala/MutableMap.scala +++ b/sources/scala/MutableMap.scala @@ -13,39 +13,39 @@ package scala; */ trait MutableMap[A, B] with Map[A, B] { - def update(key: A, value: B): Unit; - - def put(key: A, value: B): B = { - val old = apply(key); - update(key, value); - old; - } - - def putAll(mappings: Pair[A, B]*) = { - val ys = mappings as List[Pair[A, B]]; - ys foreach { case Pair(key, value) => update(key, value); }; - } - - def putMap(map: Iterable[Pair[A, B]]): Unit = map.iterator foreach { - case Pair(key, value) => update(key, value); - } - - def map(f: (A, B) => B): Unit = iterator foreach { - case Pair(key, value) => update(key, f(key, value)); - } - - override def toString() = - if (size == 0) - "{}" - else - "{" + { - val iter = iterator; - var res = mappingToString(iter.next); - while (iter.hasNext) { - res = res + ", " + mappingToString(iter.next); - } - res; - } + "}"; - - def mappingToString(p: Pair[A, B]) = p._1.toString() + " -> " + p._2; + def update(key: A, value: B): Unit; + + def put(key: A, value: B): B = { + val old = apply(key); + update(key, value); + old; + } + + def putAll(mappings: Pair[A, B]*) = { + val ys = mappings as List[Pair[A, B]]; + ys foreach { case Pair(key, value) => update(key, value); }; + } + + def putMap(map: Iterable[Pair[A, B]]): Unit = map.elements foreach { + case Pair(key, value) => update(key, value); + } + + def map(f: (A, B) => B): Unit = elements foreach { + case Pair(key, value) => update(key, f(key, value)); + } + + override def toString() = + if (size == 0) + "{}" + else + "{" + { + val iter = elements; + var res = mappingToString(iter.next); + while (iter.hasNext) { + res = res + ", " + mappingToString(iter.next); + } + res; + } + "}"; + + def mappingToString(p: Pair[A, B]) = p._1.toString() + " -> " + p._2; } diff --git a/sources/scala/Seq.scala b/sources/scala/Seq.scala index bdda1b5503..2612e56e55 100644 --- a/sources/scala/Seq.scala +++ b/sources/scala/Seq.scala @@ -1,12 +1,18 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + package scala; -trait Seq[+a] with Function1[Int, a] with Iterable[a] { - def length: Int; - def elements: Iterator[a]; - def iterator: Iterator[a] = elements; - def apply(index: Int): a; +trait Seq[+A] with Function1[Int, A] with Iterable[A] { + def length: Int; - /** @deprecated - */ - def at(index: Int): a; + /** @deprecated + */ + def at(index: Int): A; } diff --git a/sources/scala/Set.scala b/sources/scala/Set.scala index 17ca20015f..6f6074247e 100644 --- a/sources/scala/Set.scala +++ b/sources/scala/Set.scala @@ -13,75 +13,75 @@ package scala; */ trait Set[A] with Iterable[A] { - def size: Int; + def size: Int; def isEmpty: Boolean = (size == 0); - def contains(elem: A): Boolean; - - def add(elem: A): Unit; - - def addAll(elems: A*): Unit = { - val ys = elems as List[A]; - ys foreach { y => add(y); }; - } - - def addSet(that: Iterable[A]): Unit = - that.iterator.foreach(elem => add(elem)); - - def remove(elem: A): Unit; - - def removeAll(elems: A*): Unit = { - val ys = elems as List[A]; - ys foreach { y => remove(y); }; - } - - def removeSet(that: Iterable[A]): Unit = - that.iterator.foreach(elem => remove(elem)); - - def intersect(that: Set[A]): Unit = filter(that.contains); - - def clear: Unit; - - def subsetOf(that: Set[A]): Boolean = { - val iter = iterator; - var res = true; - while (res && iter.hasNext) { - res = that.contains(iter.next); - } - res - } - - def foreach(f: A => Unit) = { - val iter = iterator; - while (iter.hasNext) { - f(iter.next); - } - } - - def filter(p: A => Boolean): Unit = toList foreach { - elem => if (p(elem)) remove(elem); - } - - def toList: List[A] = { - var res: List[A] = Nil; - val iter = iterator; - while (iter.hasNext) { - res = iter.next :: res; - } - res; - } - - override def toString() = - if (size == 0) - "{}" - else - "{" + { - val iter = iterator; - var res = iter.next.toString(); - while (iter.hasNext) { - res = res + ", " + iter.next; - } - res; - } + "}"; + def contains(elem: A): Boolean; + + def add(elem: A): Unit; + + def addAll(elems: A*): Unit = { + val ys = elems as List[A]; + ys foreach { y => add(y); }; + } + + def addSet(that: Iterable[A]): Unit = + that.elements.foreach(elem => add(elem)); + + def remove(elem: A): Unit; + + def removeAll(elems: A*): Unit = { + val ys = elems as List[A]; + ys foreach { y => remove(y); }; + } + + def removeSet(that: Iterable[A]): Unit = + that.elements.foreach(elem => remove(elem)); + + def intersect(that: Set[A]): Unit = filter(that.contains); + + def clear: Unit; + + def subsetOf(that: Set[A]): Boolean = { + val iter = elements; + var res = true; + while (res && iter.hasNext) { + res = that.contains(iter.next); + } + res + } + + def foreach(f: A => Unit) = { + val iter = elements; + while (iter.hasNext) { + f(iter.next); + } + } + + def filter(p: A => Boolean): Unit = toList foreach { + elem => if (p(elem)) remove(elem); + } + + def toList: List[A] = { + var res: List[A] = Nil; + val iter = elements; + while (iter.hasNext) { + res = iter.next :: res; + } + res; + } + + override def toString() = + if (size == 0) + "{}" + else + "{" + { + val iter = elements; + var res = iter.next.toString(); + while (iter.hasNext) { + res = res + ", " + iter.next; + } + res; + } + "}"; } -- cgit v1.2.3