1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
|
package scala;
/* An abstract class representing an ordered collection of elements
* of type <code>a</code>.
* This class comes with two implementing case classes {link scala.Nil/} and
* {@link scala.::_class/} that implement the abstract members <code>isEmpty</code>,
* <code>head</code> and <code>tail</code>. But instead of this
*
* @arg a the type of the elements contained in the list.
*/
trait List[a] extends Seq[a] {
/** Tests if this list is empty.
* @return True iff the list contains no element.
*/
def isEmpty: Boolean;
/** Returns this first element of the list.
* @return the first element of this list.
* @throws java.lang.RuntimeException if the list is empty.
*/
def head: a;
/** Returns this list without its first element.
* @return this list without its first element.
* @throws java.lang.RuntimeException if the list is empty.
*/
def tail: List[a];
/** Add an element <code>x</code> at the beginning of this list.
* <p>
* Ex:<br>
* <code>1 :: [2, 3] = [2, 3].::(1) = [1, 2, 3]</code>.
* @param x the element to append.
* @return the list with <code>x</code> appended at the beginning.
*/
def ::(x: a): List[a] =
new scala.::[a](x, this);
/** Returns a list resulting from the concatenation of the given
* list <code>prefix</code> and this list.
* <p>
* Ex:<br>
* <code>[1, 2] ::: [3, 4] = [3, 4].:::([1, 2]) = [1, 2, 3, 4]</code>.
* @param prefix the list to concatenate at the beginning of this list.
* @return the concatenation of the two lists.
*/
def :::(prefix: List[a]): List[a] =
if (prefix.isEmpty) this
else prefix.head :: (prefix.tail ::: this);
/** Returns the number of elements in the list.
* @return the number of elements in the list.
*/
def length: Int = this match {
case Nil => 0
case _ :: xs => xs.length + 1
}
/** Returns the elements in the list as an iterator
*/
def elements: Iterator[a] = new Iterator[a] {
var current = List.this;
def hasNext: Boolean = !current.isEmpty;
def next: a = { val result = current.head; current = current.tail; result }
}
/** Returns the list without its last element.
* @return the list without its last element.
* @throws java.lang.RuntimeException if the list is empty.
*/
def init: List[a] =
if (isEmpty) error("Nil.init")
else if (tail.isEmpty) Nil
else head :: tail.init;
/** Returns the last element of this list.
* @return the last element of the list.
* @throws java.lang.RuntimeException if the list is empty.
*/
def last: a =
if (isEmpty) error("Nil.last")
else if (tail.isEmpty) head
else tail.last;
/** Returns the <code>n</code> first elements of this list.
* @param n the number of elements to take.
* @return the <code>n</code> first elements of this list.
* @throws java.lang.RuntimeException if the list is too short.
*/
def take(n: Int): List[a] =
if (n == 0) Nil
else head :: tail.take(n-1);
/** Returns the list without its <code>n</code> first elements.
* @param n the number of elements to drop.
* @return the list without its <code>n</code> first elements.
* @throws java.lang.RuntimeException if the list is too short.
*/
def drop(n: Int): List[a] =
if (n == 0) this
else tail.drop(n-1);
/** Returns the longest prefix of this list whose elements satisfy
* the predicate <code>p</code>.
* @param p the test predicate.
* @return the longest prefix of this list whose elements satisfy
* the predicate <code>p</code>.
*/
def takeWhile(p: a => Boolean): List[a] =
if (isEmpty || !p(head)) Nil
else head :: tail.takeWhile(p);
/** Returns the longest suffix of this list whose first element does not satisfy
* the predicate <code>p</code>.
* @param p the test predicate.
* @return the longest suffix of the list whose first element does not satisfy
* the predicate <code>p</code>.
*/
def dropWhile(p: a => Boolean): List[a] =
if (isEmpty || !p(head)) this
else tail.dropWhile(p);
/** Returns the <code>n</code>-th element of this list. The first element
* (head of the list) is at position 0.
* @param n index of the element to return
* @return the element at position <code>n</code> in this list.
* @throws java.lang.RuntimeException if the list is too short.
*/
def apply(n: Int) = drop(n).head;
def at(n: Int) = drop(n).head;
/** Returns the list resulting from applying the given function <code>f</code> to each
* element of this list.
* @param f function to apply to each element.
* @return <code>[f(a0), ..., f(an)]</code> if this list is <code>[a0, ..., an]</code>.
*/
def map[b](f: a => b): List[b] =
if (isEmpty) Nil
else f(head) :: tail.map(f);
/** Apply the given function <code>f</code> to each element of this list (while respecting
* the order of the elements).
* @param f the treatment to apply to each element.
*/
def foreach(f: a => Unit): Unit =
if (isEmpty) {} else { f(head); tail.foreach(f) };
/** Returns all the elements of this list that satisfy the
* predicate <code>p</code>. The order of the elements is preserved.
* @param p the redicate used to filter the list.
* @return the elements of this list satisfying <code>p</code>.
*/
def filter(p: a => Boolean): List[a] =
if (isEmpty) this
else if (p(head)) head :: tail.filter(p)
else tail.filter(p);
/** Tests if the predicate <code>p</code> is satisfied by all elements in this
* list.
* @param p the test predicate.
* @return True iff all elements of this list satisfy the predicate <code>p</code>.
*/
def forall(p: a => Boolean): Boolean = isEmpty || (p(head) &&
tail.forall(p));
/** Tests the existence in this list of an element that satisfies the predicate
* <code>p</code>.
* @param p the test predicate.
* @return True iff there exists an element in this list that satisfies
* the predicate <code>p</code>.
*/
def exists(p: a => Boolean): Boolean =
!isEmpty && (p(head) || tail.exists(p));
/** Combines the elements of this list together using the binary
* operator <code>op</code>, from left to right, and starting with
* the value <code>z</code>. Similar to <code>fold</code> but with
* a different order of the arguments, allowing to use nice constructions like
* <code>(z foldLeft l) { ... }</code>.
* @return <code>op(... (op(op(z,a0),a1) ...), an)</code> if the list
* is <code>[a0, a1, ..., an]</code>.
*/
def foldLeft[b](z: b)(f: (b, a) => b): b = match {
case Nil => z
case x :: xs => xs.foldLeft[b](f(z, x))(f)
}
def foldLeft_:[b](z: b)(f: (b, a) => b): b = foldLeft(z)(f);
def foldRight[b](z: b)(f: (a, b) => b): b = match {
case Nil => z
case x :: xs => f(x, xs.foldRight(z)(f))
}
def reduceLeft(f: (a, a) => a): a = this match {
case Nil => error("Nil.reduceLeft")
case x :: xs => (xs foldLeft x)(f)
}
def reduceRight(f: (a, a) => a): a = match {
case Nil => error("Nil.reduceRight")
case x :: Nil => x
case x :: xs => f(x, xs.reduceRight(f))
}
/**
* Applies the given function <code>f</code> to each element of
* this list, then concatenates the results.
* @param f the function to apply on each element.
* @return <code>f(a0) ::: ... ::: f(an)</code> if this list is
* <code>[a0, ..., an]</code>.
*/
def flatMap[b](f: a => List[b]): List[b] =
if (isEmpty) Nil
else f(head) ::: tail.flatMap(f);
/** Reverses the elements of this list.
* <p>
* Ex: <br>
* <code>[1, 2, 3] reverse = [3, 2, 1]</code>.
* @return the elements of this list in reverse order.
*/
def reverse: List[a] = {
foldLeft(Nil: List[a])((xs, x) => x :: xs)
}
/** Prints on standard output a raw textual representation of this list.
* <p>
* Ex: <br>
* <code>[1, 2, 3] print</code> will display <code>1 :: 2 :: 3 :: []</code>.
*/
def print: Unit =
if (isEmpty) java.lang.System.out.println("Nil")
else {
java.lang.System.out.print(head as java.lang.Object);
java.lang.System.out.print(" :: ");
tail.print
}
/*
def toArray: Array[a] = {
val xs = new Array[a](length);
copyToArray(xs, 0);
xs
}
*/
/** Fills the given array <code>xs</code> with the elements of
* this list starting at position <code>start</code>. Does not
* work with empty lists.
* @param xs the array to fill.
* @param start starting index.
* @return the given array <code>xs</code> filled with this list.
* @throws error if the list is empty.
*/
def copyToArray(xs: Array[a], start: Int): Array[a] = match {
case Nil => xs
case y :: ys => xs(start) = y; ys.copyToArray(xs, start + 1)
}
/** Returns a string representation of this list. The resulting string
* begins with the string <code>start</code> and is finished by the string
* <code>end</code>. Inside, the string representations of elements (w.r.t.
* the method <code>toString()</code>) are separated by the string
* <code>sep</code>.
* <p>
* Ex: <br>
* <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code>
* @param start starting string.
* @param sep separator string.
* @param end ending string.
* @return a string representation of this list.
*/
def mkString(start: String, sep: String, end: String): String =
start +
(if (isEmpty) end
else if (tail.isEmpty) head.toString() + end
else head.toString().concat(sep).concat(tail.mkString("", sep, end)));
override def toString() = mkString("List(", ",", ")");
/** Return a list formed from this list and the specified list
* <code>that</code> by associating each element of the former with
* the element at the same position in the latter.
* @param that must have the same length as the self list.
* @return <code>[(a0,b0), ..., (an,bn)]</code> when
* <code>[a0, ..., an] zip [b0, ..., bn]</code> is invoked.
* @throws java.lang.RuntimeException if lists have different lengths.
*/
def zip[b](that: List[b]): List[Tuple2[a,b]] =
if (this.isEmpty || that.isEmpty) Nil
else Tuple2(this.head, that.head) :: this.tail.zip(that.tail);
/** Tests if the given value <code>elem</code> is a member of
* this list.
* @param elem element whose membership has to be tested.
* @return True iff there is an element of this list which is
* equal (w.r.t. <code>==</code>) to <code>elem</code>.
*/
def contains(elem: a) = exists(
new Object with Function1[a, Boolean] {
def apply(x: a): Boolean = x == elem;
});
/** Computes the union of this list and the given list
* <code>that</code>.
* @param that the list of elements to add to the list.
* @return a list without doubles containing the elements of this
* list and those of the given list <code>that</code>.
*/
def union(that: List[a]): List[a] =
if (this.isEmpty) that
else {
val result = this.tail union that;
if (that contains this.head) result else this.head :: result;
}
/** Computes the difference between this list and the given list
* <code>that</code>.
* @param that the list of elements to remove from this list.
* @return this list without the elements of the given list <code>that</code>.
*/
def diff(that: List[a]): List[a] =
if (this.isEmpty || that.isEmpty) this
else {
val result = this.tail diff that;
if (that contains this.head) result else this.head :: result;
}
/** Computes the intersection between this list and the given list
* <code>that</code>.
* @param that the list to intersect.
* @return the list of elements contained both in this list and
* in the given list <code>that</code>.
*/
def intersect(that: List[a]): List[a] = filter(x => that contains x);
/** Removes redundant elements from the list. Uses the method <code>==</code>
* to decide if two elements are identical.
* @return the list without doubles.
*/
def removeDuplicates: List[a] =
if (isEmpty) this
else {
val rest = tail.removeDuplicates;
if (rest contains head) rest else head :: rest
}
}
object List {
def range(from: Int, end: Int): List[Int] =
if (from >= end) scala.Predef.List()
else from :: range(from + 1, end);
}
|