Файл: Programming_in_Scala,_2nd_edition.pdf

scala> val buf = new StringBuilder buf: StringBuilder = StringBuilder()

scala> buf += 'a'

res43: buf.type = StringBuilder(a)

scala> buf ++= "bcdef"

res44: buf.type = StringBuilder(a, b, c, d, e, f)

scala> buf.toString res45: String = abcdef

Linked lists

Linked lists are mutable sequences that consist of nodes that are linked with next pointers. In most languages null would be picked as the empty linked list. That does not work for Scala collections, because even empty sequences must support all sequence methods. LinkedList.empty.isEmpty, in particular, should return true and not throw a NullPointerException. Empty linked lists are encoded instead in a special way: Their next field points back to the node itself.

Like their immutable cousins, linked lists are best operated on sequentially. In addition, linked lists make it easy to insert an element or linked list into another linked list.

Double linked lists

DoubleLinkedLists are like the single linked lists described in the previous subsection, except besides next, they have another mutable field, prev, that points to the element preceding the current node. The main benefit of that additional link is that it makes element removal very fast.

Mutable lists

A MutableList consists of a single linked list together with a pointer that refers to the terminal empty node of that list. This makes list append a constant time operation because it avoids having to traverse the list in search for its terminal node. MutableList is currently the standard implementation of mutable.LinearSeq in Scala.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Queues

Scala provides mutable queues in addition to immutable ones. You use a mutable queue similarly to the way you use an immutable one, but instead of enqueue, you use the += and ++= operators to append. Also, on a mutable queue, the dequeue method will just remove the head element from the queue and return it. Here’s an example:

scala> val queue = new scala.collection.mutable.Queue[String] queue: scala.collection.mutable.Queue[String] = Queue()

scala> queue += "a"

res46: queue.type = Queue(a)

scala> queue ++= List("b", "c") res47: queue.type = Queue(a, b, c)

scala> queue

res48: scala.collection.mutable.Queue[String] = Queue(a, b, c)

scala> queue.dequeue res49: String = a

scala> queue

res50: scala.collection.mutable.Queue[String] = Queue(b, c)

Array sequences

Array sequences are mutable sequences of fixed size that store their elements internally in an Array[AnyRef]. They are implemented in Scala by class

ArraySeq.

You would typically use an ArraySeq if you want an array for its performance characteristics, but you also want to create generic instances of the sequence where you do not know the type of the elements and do not have a ClassManifest to provide it at run-time. You will find out about these issues with arrays shortly, in Section 24.11.

Stacks

You saw immutable stacks earlier. There is also a mutable version. It works exactly the same as the immutable version except that modifications happen in place. Here’s an example:

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

scala> val stack = new scala.collection.mutable.Stack[Int] stack: scala.collection.mutable.Stack[Int] = Stack()

scala> stack.push(1)

res51: stack.type = Stack(1)

scala> stack

res52: scala.collection.mutable.Stack[Int] = Stack(1)

scala> stack.push(2)

res53: stack.type = Stack(2, 1)

scala> stack

res54: scala.collection.mutable.Stack[Int] = Stack(2, 1)

scala> stack.top res55: Int = 2

scala> stack

res56: scala.collection.mutable.Stack[Int] = Stack(2, 1)

scala> stack.pop res57: Int = 2

scala> stack

res58: scala.collection.mutable.Stack[Int] = Stack(1)

Array stacks

ArrayStack is an alternative implementation of a mutable stack, which is backed by an Array that gets resized as needed. It provides fast indexing and is generally slightly more efficient for most operations than a normal mutable stack.

Hash tables

A hash table stores its elements in an underlying array, placing each item at a position in the array determined by the hash code of that item. Adding an element to a hash table takes only constant time, so long as there isn’t already another element in the array that has the same hash code. Hash tables are thus very fast so long as the objects placed in them have a good distribution of hash codes. As a result, the default mutable map and set types in Scala are based on hash tables.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Hash sets and maps are used just like any other set or map. Here are some simple examples:

scala> val map = collection.mutable.HashMap.empty[Int,String] map: scala.collection.mutable.HashMap[Int,String] = Map()

scala> map += (1 -> "make a web site") res59: map.type = Map((1,make a web site))

scala> map += (3 -> "profit!")

res60: map.type = Map((1,make a web site), (3,profit!))

scala> map(1)

res61: String = make a web site

scala> map contains 2 res62: Boolean = false

Iteration over a hash table is not guaranteed to occur in any particular order. Iteration simply proceeds through the underlying array in whichever order it happens to be. To get a guaranteed iteration order, use a linked hash map or set instead of a regular one. A linked hash map or set is just like a regular hash map or set except that it also includes a linked list of the elements in the order they were added. Iteration over such a collection is always in the same order that the elements were initially added.

Weak hash maps

A weak hash map is a special kind of hash map in which the garbage collector does not follow links from the map to the keys stored in it. This means that a key and its associated value will disappear from the map if there is no other reference to that key. Weak hash maps are useful for tasks such as caching, where you want to re-use an expensive function’s result if the function is called again on the same key. If keys and function results are stored in a regular hash map, the map could grow without bounds, and no key would ever become garbage. Using a weak hash map avoids this problem. As soon as a key object becomes unreachable, it’s entry is removed from the weak hash map. Weak hash maps in Scala are implemented as a wrapper of an underlying Java implementation, java.util.WeakHashMap.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Concurrent Maps

A concurrent map can be accessed by several threads at once. In addition to the usual Map operations, it provides the following atomic operations:

Table 24.9 · Operations in trait ConcurrentMap

ConcurrentMap is a trait in the Scala collections library. Currently, its only implementation is Java’s java.util.concurrent.ConcurrentMap, which can be converted automatically into a Scala map using the standard Java/Scala collection conversions, which will be described in Section 24.18.

Mutable bit sets

A mutable bit set is just like an immutable one, except that it can be modified in place. Mutable bit sets are slightly more efficient at updating than immutable ones, because they don’t have to copy around Longs that haven’t changed. Here is an example:

scala> val bits = scala.collection.mutable.BitSet.empty bits: scala.collection.mutable.BitSet = BitSet()

scala> bits += 1

res63: bits.type = BitSet(1)

scala> bits += 3

res64: bits.type = BitSet(1, 3)

scala> bits

res65: scala.collection.mutable.BitSet = BitSet(1, 3)

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

24.11Arrays

Arrays are a special kind of collection in Scala. One the one hand, Scala arrays correspond one-to-one to Java arrays. That is, a Scala array Array[Int] is represented as a Java int[], an Array[Double] is represented as a Java double[] and an Array[String] is represented as a Java String[]. But at the same time, Scala arrays offer much more their Java analogues. First, Scala arrays can be generic. That is, you can have an Array[T], where T is a type parameter or abstract type. Second, Scala arrays are compatible with Scala sequences—you can pass an Array[T] where a Seq[T] is required. Finally, Scala arrays also support all sequence operations. Here’s an example of this in action:

scala> val a1 = Array(1, 2, 3) a1: Array[Int] = Array(1, 2, 3)

scala> val a2 = a1 map (_ * 3) a2: Array[Int] = Array(3, 6, 9)

scala> val a3 = a2 filter (_ % 2 != 0) a3: Array[Int] = Array(3, 9)

scala> a3.reverse

res1: Array[Int] = Array(9, 3)

Given that Scala arrays are represented just like Java arrays, how can these additional features be supported in Scala? In fact, the answer to this question differs between Scala 2.8 and earlier versions. Previously, the Scala compiler somewhat “magically” wrapped and unwrapped arrays to and from Seq objects, when required, in a process called boxing and unboxing. The details of this were quite complicated, in particular when you created a new array of generic type Array[T]. There were some puzzling corner cases and the performance of array operations was not all that predictable.

The Scala 2.8 design is much simpler. Almost all compiler magic is gone. Instead the Scala 2.8 array implementation makes systematic use of implicit conversions. In Scala 2.8 an array does not pretend to be a sequence. It can’t really be that because the data type representation of a native array is not a subtype of Seq. Instead there is an implicit “wrapping” conversion between arrays and instances of class scala.collection.mutable.WrappedArray, which is a subclass of Seq. Here you see it in action:

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

scala> val seq: Seq[Int] = a1

seq: Seq[Int] = WrappedArray(1, 2, 3)

scala> val a4: Array[Int] = seq.toArray a4: Array[Int] = Array(1, 2, 3)

scala> a1 eq a4 res2: Boolean = true

This interaction demonstrates that arrays are compatible with sequences, because there’s an implicit conversion from Array to WrappedArray. To go the other way, from a WrappedArray to an Array, you can use the toArray method defined in Traversable. The last interpreter line above shows that wrapping then unwrapping with toArray gives you back the same array you started with.

There is yet another implicit conversion that gets applied to arrays. This conversion simply “adds” all sequence methods to arrays but does not turn the array itself into a sequence. “Adding” means that the array is wrapped in another object of type ArrayOps, which supports all sequence methods. Typically, this ArrayOps object is short-lived; it will usually be inaccessible after the call to the sequence method and its storage can be recycled. Modern VMs often avoid creating this object entirely.

The difference between the two implicit conversions on arrays is demonstrated here:

scala> val seq: Seq[Int] = a1

seq: Seq[Int] = WrappedArray(1, 2, 3)

scala> seq.reverse

res2: Seq[Int] = WrappedArray(3, 2, 1)

scala> val ops: collection.mutable.ArrayOps[Int] = a1 ops: scala.collection.mutable.ArrayOps[Int] = [I(1, 2, 3)

scala> ops.reverse

res3: Array[Int] = Array(3, 2, 1)

You see that calling reverse on seq, which is a WrappedArray, will give again a WrappedArray. That’s logical, because wrapped arrays are Seqs, and calling reverse on any Seq will give again a Seq. On the other hand, calling reverse on the ops value of class ArrayOps will result in an Array, not a Seq.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index