lib: add `provide_default_value` in Map to allow subclasses to provide
[nit.git] / lib / standard / collection / abstract_collection.nit
1 # This file is part of NIT ( http://www.nitlanguage.org ).
2 #
3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
4 #
5 # This file is free software, which comes along with NIT. This software is
6 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
7 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
8 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
9 # is kept unaltered, and a notification of the changes is added.
10 # You are allowed to redistribute it and sell it, alone or is a part of
11 # another product.
12
13 # This module define several abstract collection classes.
14 module abstract_collection
15
16 import kernel
17
18 # The root of the collection hierarchy.
19 #
20 # Collections modelize finite groups of objects, called elements.
21 #
22 # The specific behavior and representation of collections is determined
23 # by the subclasses of the hierarchy.
24 #
25 # The main service of Collection is to provide a stable `iterator`
26 # method usable to retrieve all the elements of the collection.
27 #
28 # Additional services are provided.
29 # For an implementation point of view, Collection provide a basic
30 # implementation of these services using the `iterator` method.
31 # Subclasses often provide a more efficient implementation.
32 #
33 # Because of the `iterator` method, Collections instances can use
34 # the `for` control structure:
35 #
36 # var x: Collection[U]
37 # # ...
38 # for u in x do
39 # # u is a U
40 # # ...
41 # end
42 #
43 # that is equivalent with
44 #
45 # var x: Collection[U]
46 # # ...
47 # var i = x.iterator
48 # while i.is_ok do
49 # var u = i.item # u is a U
50 # # ...
51 # i.next
52 # end
53 interface Collection[E]
54 # Get a new iterator on the collection.
55 fun iterator: Iterator[E] is abstract
56
57 # Is there no item in the collection?
58 #
59 # assert [1,2,3].is_empty == false
60 # assert [1..1[.is_empty == true
61 fun is_empty: Bool do return length == 0
62
63 # Number of items in the collection.
64 #
65 # assert [10,20,30].length == 3
66 # assert [20..30[.length == 10
67 fun length: Int
68 do
69 var nb = 0
70 for i in self do nb += 1
71 return nb
72 end
73
74
75 # Is `item` in the collection ?
76 # Comparisons are done with ==
77 #
78 # assert [1,2,3].has(2) == true
79 # assert [1,2,3].has(9) == false
80 # assert [1..5[.has(2) == true
81 # assert [1..5[.has(9) == false
82 fun has(item: E): Bool
83 do
84 for i in self do if i == item then return true
85 return false
86 end
87
88 # Is the collection contain only `item`?
89 # Comparisons are done with ==
90 # Return true if the collection is empty.
91 #
92 # assert [1,1,1].has_only(1) == true
93 # assert [1,2,3].has_only(1) == false
94 # assert [1..1].has_only(1) == true
95 # assert [1..3].has_only(1) == false
96 # assert [3..3[.has_only(1) == true # empty collection
97 #
98 # ENSURE `is_empty implies result == true`
99 fun has_only(item: E): Bool
100 do
101 for i in self do if i != item then return false
102 return true
103 end
104
105 # How many occurrences of `item` are in the collection?
106 # Comparisons are done with ==
107 #
108 # assert [10,20,10].count(10) == 2
109 fun count(item: E): Int
110 do
111 var nb = 0
112 for i in self do if i == item then nb += 1
113 return nb
114 end
115
116 # Return the first item of the collection
117 #
118 # assert [1,2,3].first == 1
119 fun first: E
120 do
121 assert length > 0
122 return iterator.item
123 end
124
125 # Is the collection contains all the elements of `other`?
126 #
127 # assert [1,1,1].has_all([1]) == true
128 # assert [1,1,1].has_all([1,2]) == false
129 # assert [1,3,4,2].has_all([1..2]) == true
130 # assert [1,3,4,2].has_all([1..5]) == false
131 fun has_all(other: Collection[E]): Bool
132 do
133 for x in other do if not has(x) then return false
134 return true
135 end
136 end
137
138 # Instances of the Iterator class generates a series of elements, one at a time.
139 # They are mainly used with collections.
140 interface Iterator[E]
141 # The current item.
142 # Require `is_ok`.
143 fun item: E is abstract
144
145 # Jump to the next item.
146 # Require `is_ok`.
147 fun next is abstract
148
149 # Is there a current item ?
150 fun is_ok: Bool is abstract
151 end
152
153 # A collection that contains only one item.
154 # Used to pass arguments by reference
155 class Container[E]
156 super Collection[E]
157
158 redef fun first do return _item
159
160 redef fun is_empty do return false
161
162 redef fun length do return 1
163
164 redef fun has(an_item) do return _item == an_item
165
166 redef fun has_only(an_item) do return _item == an_item
167
168 redef fun count(an_item)
169 do
170 if _item == an_item then
171 return 1
172 else
173 return 0
174 end
175 end
176
177 redef fun iterator do return new ContainerIterator[E](self)
178
179 # Create a new instance with a given initial value.
180 init(e: E) do _item = e
181
182 # The stored item
183 readable writable var _item: E
184 end
185
186 # This iterator is quite stupid since it is used for only one item.
187 class ContainerIterator[E]
188 super Iterator[E]
189 redef fun item do return _container.item
190
191 redef fun next do _is_ok = false
192
193 init(c: Container[E]) do _container = c
194
195 redef readable var _is_ok: Bool = true
196
197 var _container: Container[E]
198 end
199
200 # Items can be removed from this collection
201 interface RemovableCollection[E]
202 super Collection[E]
203 # Remove all items
204 fun clear is abstract
205
206 # Remove an occucence of `item`
207 fun remove(item: E) is abstract
208
209 # Remove all occurences of `item`
210 fun remove_all(item: E) do while has(item) do remove(item)
211 end
212
213 # Items can be added to these collections.
214 interface SimpleCollection[E]
215 super RemovableCollection[E]
216 # Add an item in a collection.
217 # Ensure col.has(item)
218 fun add(item: E) is abstract
219
220 # Add each item of `coll`.
221 fun add_all(coll: Collection[E]) do for i in coll do add(i)
222 end
223
224 # Abstract sets.
225 #
226 # Set is a collection without ducplicates (according to ==)
227 # var s: Set[String] = new ArraySet[String]
228 # var a = "Hello"
229 # var b = "Hel" + "lo"
230 # # ...
231 # s.add(a)
232 # assert s.has(b) == true
233 interface Set[E: Object]
234 super SimpleCollection[E]
235
236 redef fun has_only(item)
237 do
238 var l = length
239 if l == 1 then
240 return has(item)
241 else if l == 0 then
242 return true
243 else
244 return false
245 end
246 end
247
248 # Only 0 or 1
249 redef fun count(item)
250 do
251 if has(item) then
252 return 1
253 else
254 return 0
255 end
256 end
257
258 # Synonym of remove since there is only one item
259 redef fun remove_all(item) do remove(item)
260
261 # Equality is defined on set and means that each set contains the same elements
262 redef fun ==(other)
263 do
264 if not other isa Set[Object] then return false
265 if other.length != length then return false
266 return has_all(other)
267 end
268
269 # because of the law between `==` and `hash`, hash is redefined to be the sum of the hash of the elements
270 redef fun hash
271 do
272 var res = 0
273 for e in self do res += res.hash
274 return res
275 end
276 end
277
278 # MapRead are abstract associative collections: `key` -> `item`.
279 interface MapRead[K: Object, E]
280 # Get the item at `key`.
281 fun [](key: K): E is abstract
282
283 # Get the item at `key` or null if `key` is not in the map.
284 #
285 # var x = new HashMap[String, Int]
286 # x["four"] = 4
287 # assert x.get_or_null("four") == 4
288 # assert x.get_or_null("five") == null
289 #
290 # Note: use `has_key` and `[]` if you need the distinction bewteen a key associated with null, and no key.
291 fun get_or_null(key: K): nullable E
292 do
293 if has_key(key) then return self[key]
294 return null
295 end
296
297 # Get the item at `key` or return `default` if not in map
298 fun get_or_default(key: K, default: E): E
299 do
300 if has_key(key) then return self[key]
301 return default
302 end
303
304 # Depreciated alias for `keys.has`
305 fun has_key(key: K): Bool do return self.keys.has(key)
306
307 # Get a new iterator on the map.
308 fun iterator: MapIterator[K, E] is abstract
309
310 # Return the point of view of self on the values only.
311 # Note that `self` and `values` are views on the same data;
312 # therefore any modification of one is visible on the other.
313 fun values: Collection[E] is abstract
314
315 # Return the point of view of self on the keys only.
316 # Note that `self` and `keys` are views on the same data;
317 # therefore any modification of one is visible on the other.
318 fun keys: Collection[K] is abstract
319
320 # Is there no item in the collection?
321 fun is_empty: Bool is abstract
322
323 # Number of items in the collection.
324 fun length: Int is abstract
325
326 # Called by the underling implementation of `[]` to provide a default value when a `key` has no value
327 # By default the behavior is to abort.
328 #
329 # Note: the value is returned *as is*, implementations may want to store the value in the map before returning it
330 # @toimplement
331 protected fun provide_default_value(key: K): E do abort
332 end
333
334 # Maps are associative collections: `key` -> `item`.
335 #
336 # The main operator over maps is [].
337 #
338 # var map: Map[String, Int] = new ArrayMap[String, Int]
339 # # ...
340 # map["one"] = 1 # Associate 'one' to '1'
341 # map["two"] = 2 # Associate 'two' to '2'
342 # assert map["one"] == 1
343 # assert map["two"] == 2
344 #
345 # Instances of maps can be used with the for structure
346 #
347 # for key, value in map do
348 # assert (key == "one" and value == 1) or (key == "two" and value == 2)
349 # end
350 #
351 # The keys and values in the map can also be manipulated directly with the `keys` and `values` methods.
352 #
353 # assert map.keys.has("one") == true
354 # assert map.keys.has("tree") == false
355 # assert map.values.has(1) == true
356 # assert map.values.has(3) == false
357 #
358 interface Map[K: Object, E]
359 super MapRead[K, E]
360 # Set the`item` at `key`.
361 fun []=(key: K, item: E) is abstract
362
363 # Add each (key,value) of `map` into `self`.
364 # If a same key exists in `map` and `self`, then the value in self is discarded.
365 fun recover_with(map: Map[K, E])
366 do
367 var i = map.iterator
368 while i.is_ok do
369 self[i.key] = i.item
370 i.next
371 end
372 end
373
374 # Remove all items
375 fun clear is abstract
376
377 redef fun values: RemovableCollection[E] is abstract
378
379 redef fun keys: RemovableCollection[K] is abstract
380 end
381
382 # Iterators for Map.
383 interface MapIterator[K: Object, E]
384 # The current item.
385 # Require `is_ok`.
386 fun item: E is abstract
387
388 # The key of the current item.
389 # Require `is_ok`.
390 fun key: K is abstract
391
392 # Jump to the next item.
393 # Require `is_ok`.
394 fun next is abstract
395
396 # Is there a current item ?
397 fun is_ok: Bool is abstract
398
399 # Set a new `item` at `key`.
400 #fun item=(item: E) is abstract
401 end
402
403 # Iterator on a 'keys' point of view of a map
404 class MapKeysIterator[K: Object, V]
405 super Iterator[K]
406 # The original iterator
407 var iterator: MapIterator[K, V]
408
409 redef fun is_ok do return self.iterator.is_ok
410 redef fun next do self.iterator.next
411 redef fun item do return self.iterator.key
412 end
413
414 # Iterator on a 'values' point of view of a map
415 class MapValuesIterator[K: Object, V]
416 super Iterator[V]
417 # The original iterator
418 var iterator: MapIterator[K, V]
419
420 redef fun is_ok do return self.iterator.is_ok
421 redef fun next do self.iterator.next
422 redef fun item do return self.iterator.item
423 end
424
425 # Sequences are indexed collections.
426 # The first item is 0. The last is `length-1`.
427 interface SequenceRead[E]
428 super Collection[E]
429 # Get the first item.
430 # Is equivalent with `self[0]`.
431 redef fun first
432 do
433 assert not_empty: not is_empty
434 return self[0]
435 end
436
437 # Return the index=th element of the sequence.
438 # The first element is 0 and the last if `length-1`
439 # If index is invalid, the program aborts
440 fun [](index: Int): E is abstract
441
442 # Get the last item.
443 # Is equivalent with `self[length-1]`.
444 fun last: E
445 do
446 assert not_empty: not is_empty
447 return self[length-1]
448 end
449
450 # Return the index of the first occurrence of `item`.
451 # Return -1 if `item` is not found
452 # Comparison is done with ==
453 fun index_of(item: E): Int
454 do
455 var i = iterator
456 while i.is_ok do
457 if i.item == item then return i.index
458 i.next
459 end
460 return -1
461 end
462
463 redef fun iterator: IndexedIterator[E] is abstract
464
465 # Two sequences are equals if they have the same items in the same order.
466 redef fun ==(o)
467 do
468 if not o isa SequenceRead[nullable Object] then return false
469 var l = length
470 if o.length != l then return false
471 var i = 0
472 while i < l do
473 if self[i] != o[i] then return false
474 i += 1
475 end
476 return true
477 end
478
479 # because of the law between `==` and `hash`, hash is redefined to be the sum of the hash of the elements
480 redef fun hash
481 do
482 var res = 0
483 for e in self do res += res.hash
484 return res
485 end
486 end
487
488 # Sequence are indexed collection.
489 # The first item is 0. The last is `length-1`.
490 interface Sequence[E]
491 super SequenceRead[E]
492 super SimpleCollection[E]
493
494 # Set the first item.
495 # Is equivalent with `self[0] = item`.
496 fun first=(item: E)
497 do self[0] = item end
498
499 # Set the last item.
500 # Is equivalent with `self[length-1] = item`.
501 fun last=(item: E)
502 do
503 var l = length
504 if l > 0 then
505 self[l-1] = item
506 else
507 self[0] = item
508 end
509 end
510
511 # A synonym of `push`
512 redef fun add(e) do push(e)
513
514 # Add an item after the last.
515 fun push(e: E) is abstract
516
517 # Add each item of `coll` after the last.
518 fun append(coll: Collection[E]) do for i in coll do push(i)
519
520 # Remove the last item.
521 fun pop: E is abstract
522
523 # Add an item before the last.
524 fun unshift(e: E) is abstract
525
526 # Remove the first item.
527 # The second item become the first.
528 fun shift: E is abstract
529
530 # Set the `item` at `index`.
531 fun []=(index: Int, item: E) is abstract
532
533 # Remove the item at `index` and shift all following elements
534 fun remove_at(index: Int) is abstract
535 end
536
537 # Iterators on indexed collections.
538 interface IndexedIterator[E]
539 super Iterator[E]
540 # The index of the current item.
541 fun index: Int is abstract
542 end
543
544 # Associative arrays that internally uses couples to represent each (key, value) pairs.
545 interface CoupleMap[K: Object, E]
546 super Map[K, E]
547 # Return the couple of the corresponding key
548 # Return null if the key is no associated element
549 protected fun couple_at(key: K): nullable Couple[K, E] is abstract
550
551 redef fun [](key)
552 do
553 var c = couple_at(key)
554 if c == null then
555 return provide_default_value(key)
556 else
557 return c.second
558 end
559 end
560 end
561
562 # Iterator on CoupleMap
563 #
564 # Actually is is a wrapper around an iterator of the internal array of the map.
565 class CoupleMapIterator[K: Object, E]
566 super MapIterator[K, E]
567 redef fun item do return _iter.item.second
568
569 #redef fun item=(e) do _iter.item.second = e
570
571 redef fun key do return _iter.item.first
572
573 redef fun is_ok do return _iter.is_ok
574
575 redef fun next
576 do
577 _iter.next
578 end
579
580 var _iter: Iterator[Couple[K,E]]
581
582 init(i: Iterator[Couple[K,E]]) do _iter = i
583 end
584
585 # Some tools ###################################################################
586
587 # Two objects in a simple structure.
588 class Couple[F, S]
589
590 # The first element of the couple.
591 readable writable var _first: F
592
593 # The second element of the couple.
594 readable writable var _second: S
595
596 # Create a new instance with a first and a second object.
597 init(f: F, s: S)
598 do
599 _first = f
600 _second = s
601 end
602 end