X-Git-Url: http://nitlanguage.org diff --git a/lib/standard/collection/abstract_collection.nit b/lib/standard/collection/abstract_collection.nit index 93d882a..2f7e454 100644 --- a/lib/standard/collection/abstract_collection.nit +++ b/lib/standard/collection/abstract_collection.nit @@ -33,25 +33,29 @@ import kernel # Subclasses often provide a more efficient implementation. # # Because of the `iterator` method, Collections instances can use -# the `for` control structure: +# the `for` control structure. # -# var x: Collection[U] -# # ... -# for u in x do -# # u is a U -# # ... -# end +# ~~~nitish +# var x: Collection[U] +# # ... +# for u in x do +# # u is a U +# # ... +# end +# ~~~ # -# that is equivalent with +# that is equivalent with the following: # -# var x: Collection[U] -# # ... -# var i = x.iterator -# while i.is_ok do -# var u = i.item # u is a U -# # ... -# i.next -# end +# ~~~nitish +# var x: Collection[U] +# # ... +# var i = x.iterator +# while i.is_ok do +# var u = i.item # u is a U +# # ... +# i.next +# end +# ~~~ interface Collection[E] # Get a new iterator on the collection. fun iterator: Iterator[E] is abstract @@ -62,6 +66,14 @@ interface Collection[E] # assert [1..1[.is_empty == true fun is_empty: Bool do return length == 0 + # Alias for `not is_empty`. + # + # Some people prefer to have conditions grammatically easier to read. + # + # assert [1,2,3].not_empty == true + # assert [1..1[.not_empty == false + fun not_empty: Bool do return not self.is_empty + # Number of items in the collection. # # assert [10,20,30].length == 3 @@ -106,7 +118,7 @@ interface Collection[E] # How many occurrences of `item` are in the collection? # Comparisons are done with == # - # assert [10,20,10].count(10) == 2 + # assert [10,20,10].count(10) == 2 fun count(item: E): Int do var nb = 0 @@ -116,28 +128,60 @@ interface Collection[E] # Return the first item of the collection # - # assert [1,2,3].first == 1 + # assert [1,2,3].first == 1 fun first: E do assert length > 0 return iterator.item end - # Is the collection contains all the elements of `other`? + # Does the collection contain at least each element of `other`? + # + # assert [1,3,4,2].has_all([1..2]) == true + # assert [1,3,4,2].has_all([1..5]) == false # - # assert [1,1,1].has_all([1]) == true - # assert [1,1,1].has_all([1,2]) == false - # assert [1,3,4,2].has_all([1..2]) == true - # assert [1,3,4,2].has_all([1..5]) == false + # Repeated elements in the collections are not considered. + # + # assert [1,1,1].has_all([1]) == true + # assert [1..5].has_all([1,1,1]) == true + # + # Note that the default implementation is general and correct for any lawful Collections. + # It is memory-efficient but relies on `has` so may be CPU-inefficient for some kind of collections. fun has_all(other: Collection[E]): Bool do for x in other do if not has(x) then return false return true end + + # Does the collection contain exactly all the elements of `other`? + # + # The same elements must be present in both `self` and `other`, + # but the order of the elements in the collections are not considered. + # + # assert [1..3].has_exactly([3,1,2]) == true # the same elements + # assert [1..3].has_exactly([3,1]) == false # 2 is not in the array + # assert [1..2].has_exactly([3,1,2]) == false # 3 is not in the range + # + # Repeated elements must be present in both collections in the same amount. + # So basically it is a multi-set comparison. + # + # assert [1,2,3,2].has_exactly([1,2,2,3]) == true # the same elements + # assert [1,2,3,2].has_exactly([1,2,3]) == false # more 2 in the first array + # assert [1,2,3].has_exactly([1,2,2,3]) == false # more 2 in the second array + # + # Note that the default implementation is general and correct for any lawful Collections. + # It is memory-efficient but relies on `count` so may be CPU-inefficient for some kind of collections. + fun has_exactly(other: Collection[E]): Bool + do + if length != other.length then return false + for e in self do if self.count(e) != other.count(e) then return false + return true + end end -# Instances of the Iterator class generates a series of elements, one at a time. -# They are mainly used with collections. +# Iterators generate a series of elements, one at a time. +# +# They are mainly used with collections and obtained from `Collection::iterator`. interface Iterator[E] # The current item. # Require `is_ok`. @@ -152,13 +196,23 @@ interface Iterator[E] # Iterate over `self` fun iterator: Iterator[E] do return self + + # Post-iteration hook. + # + # Used to inform `self` that the iteration is over. + # Specific iterators can use this to free some resources. + # + # Is automatically invoked at the end of `for` structures. + # + # Do nothing by default. + fun finish do end end # A collection that contains only one item. # # Used to pass arguments by reference. # -# Also used when one want to give asingle element when a full +# Also used when one want to give a single element when a full # collection is expected class Container[E] super Collection[E] @@ -184,11 +238,8 @@ class Container[E] redef fun iterator do return new ContainerIterator[E](self) - # Create a new instance with a given initial value. - init(e: E) do item = e - # The stored item - var item: E writable + var item: E is writable end # This iterator is quite stupid since it is used for only one item. @@ -198,11 +249,9 @@ private class ContainerIterator[E] redef fun next do is_ok = false - init(c: Container[E]) do _container = c - redef var is_ok: Bool = true - var _container: Container[E] + var container: Container[E] end # Items can be removed from this collection @@ -265,7 +314,7 @@ end # # ... # s.add(a) # assert s.has(b) == true -interface Set[E: Object] +interface Set[E] super SimpleCollection[E] redef fun has_only(item) @@ -329,11 +378,15 @@ interface Set[E: Object] return nhs end + # Returns a new instance of `Set`. + # + # Depends on the subclass, mainly used for copy services + # like `union` or `intersection`. protected fun new_set: Set[E] is abstract end # MapRead are abstract associative collections: `key` -> `item`. -interface MapRead[K: Object, E] +interface MapRead[K, V] # Get the item at `key` # # var x = new HashMap[String, Int] @@ -343,7 +396,7 @@ interface MapRead[K: Object, E] # # If the key is not in the map, `provide_default_value` is called (that aborts by default) # See `get_or_null` and `get_or_default` for safe variations. - fun [](key: K): E is abstract + fun [](key: K): V is abstract # Get the item at `key` or null if `key` is not in the map. # @@ -352,8 +405,8 @@ interface MapRead[K: Object, E] # assert x.get_or_null("four") == 4 # assert x.get_or_null("five") == null # - # Note: use `has_key` and `[]` if you need the distinction bewteen a key associated with null, and no key. - fun get_or_null(key: K): nullable E + # Note: use `has_key` and `[]` if you need the distinction between a key associated with null, and no key. + fun get_or_null(key: K): nullable V do if has_key(key) then return self[key] return null @@ -366,17 +419,24 @@ interface MapRead[K: Object, E] # assert x.get_or_default("four", 40) == 4 # assert x.get_or_default("five", 50) == 50 # - fun get_or_default(key: K, default: E): E + fun get_or_default(key: K, default: V): V do if has_key(key) then return self[key] return default end - # Depreciated alias for `keys.has` + # Is there an item associated with `key`? + # + # var x = new HashMap[String, Int] + # x["four"] = 4 + # assert x.has_key("four") == true + # assert x.has_key("five") == false + # + # By default it is a synonymous to `keys.has` but could be redefined with a direct implementation. fun has_key(key: K): Bool do return self.keys.has(key) # Get a new iterator on the map. - fun iterator: MapIterator[K, E] is abstract + fun iterator: MapIterator[K, V] is abstract # Return the point of view of self on the values only. # Note that `self` and `values` are views on the same data; @@ -386,7 +446,7 @@ interface MapRead[K: Object, E] # x["four"] = 4 # assert x.values.has(4) == true # assert x.values.has(5) == false - fun values: Collection[E] is abstract + fun values: Collection[V] is abstract # Return the point of view of self on the keys only. # Note that `self` and `keys` are views on the same data; @@ -421,7 +481,50 @@ interface MapRead[K: Object, E] # # Note: the value is returned *as is*, implementations may want to store the value in the map before returning it # @toimplement - protected fun provide_default_value(key: K): E do abort + protected fun provide_default_value(key: K): V do abort + + # Does `self` and `other` have the same keys associated with the same values? + # + # ~~~ + # var a = new HashMap[String, Int] + # var b = new ArrayMap[Object, Numeric] + # assert a == b + # a["one"] = 1 + # assert a != b + # b["one"] = 1 + # assert a == b + # b["one"] = 2 + # assert a != b + # ~~~ + redef fun ==(other) + do + if not other isa MapRead[nullable Object, nullable Object] then return false + if other.length != self.length then return false + for k, v in self do + if not other.has_key(k) then return false + if other[k] != v then return false + end + return true + end + + # A hashcode based on the hashcode of the keys and the values. + # + # ~~~ + # var a = new HashMap[String, Int] + # var b = new ArrayMap[Object, Numeric] + # a["one"] = 1 + # b["one"] = 1 + # assert a.hash == b.hash + # ~~~ + redef fun hash + do + var res = length + for k, v in self do + if k != null then res += k.hash * 7 + if v != null then res += v.hash * 11 + end + return res + end end # Maps are associative collections: `key` -> `item`. @@ -448,8 +551,8 @@ end # assert map.values.has(1) == true # assert map.values.has(3) == false # -interface Map[K: Object, E] - super MapRead[K, E] +interface Map[K, V] + super MapRead[K, V] # Set the `value` at `key`. # @@ -459,14 +562,14 @@ interface Map[K: Object, E] # x["four"] = 4 # assert x["four"] == 4 # - # If the key was associated with a value, this old value is discarted + # If the key was associated with a value, this old value is discarded # and replaced with the new one. # # x["four"] = 40 # assert x["four"] == 40 # assert x.values.has(4) == false # - fun []=(key: K, value: E) is abstract + fun []=(key: K, value: V) is abstract # Add each (key,value) of `map` into `self`. # If a same key exists in `map` and `self`, then the value in self is discarded. @@ -483,7 +586,7 @@ interface Map[K: Object, E] # assert x["four"] == 40 # assert x["five"] == 5 # assert x["nine"] == 90 - fun recover_with(map: Map[K, E]) + fun recover_with(map: MapRead[K, V]) do var i = map.iterator while i.is_ok do @@ -502,16 +605,16 @@ interface Map[K: Object, E] # ENSURE `is_empty` fun clear is abstract - redef fun values: RemovableCollection[E] is abstract + redef fun values: RemovableCollection[V] is abstract redef fun keys: RemovableCollection[K] is abstract end # Iterators for Map. -interface MapIterator[K: Object, E] +interface MapIterator[K, V] # The current item. # Require `is_ok`. - fun item: E is abstract + fun item: V is abstract # The key of the current item. # Require `is_ok`. @@ -526,10 +629,20 @@ interface MapIterator[K: Object, E] # Set a new `item` at `key`. #fun item=(item: E) is abstract + + # Post-iteration hook. + # + # Used to inform `self` that the iteration is over. + # Specific iterators can use this to free some resources. + # + # Is automatically invoked at the end of `for` structures. + # + # Do nothing by default. + fun finish do end end # Iterator on a 'keys' point of view of a map -class MapKeysIterator[K: Object, V] +class MapKeysIterator[K, V] super Iterator[K] # The original iterator var original_iterator: MapIterator[K, V] @@ -540,7 +653,7 @@ class MapKeysIterator[K: Object, V] end # Iterator on a 'values' point of view of a map -class MapValuesIterator[K: Object, V] +class MapValuesIterator[K, V] super Iterator[V] # The original iterator var original_iterator: MapIterator[K, V] @@ -803,6 +916,15 @@ interface Sequence[E] # assert a == [20,10,1,2,3] fun unshift(e: E) is abstract + # Add all items of `coll` before the first one. + # + # var a = [1,2,3] + # a.prepend([7..9]) + # assert a == [7,8,9,1,2,3] + # + # Alias of `insert_at(coll, 0)` + fun prepend(coll: Collection[E]) do insert_all(coll, 0) + # Remove the first item. # The second item thus become the first. # @@ -835,10 +957,30 @@ interface Sequence[E] # a.insert(100, 2) # assert a == [10, 20, 100, 30, 40] # - # REQUIRE `index >= 0 and index < length` + # REQUIRE `index >= 0 and index <= length` # ENSURE `self[index] == item` fun insert(item: E, index: Int) is abstract + # Insert all elements at a given position, following elements are shifted. + # + # var a = [10, 20, 30, 40] + # a.insert_all([100..102], 2) + # assert a == [10, 20, 100, 101, 102, 30, 40] + # + # REQUIRE `index >= 0 and index <= length` + # ENSURE `self[index] == coll.first` + fun insert_all(coll: Collection[E], index: Int) + do + assert index >= 0 and index < length + if index == length then + add_all(coll) + end + for c in coll do + insert(c, index) + index += 1 + end + end + # Remove the item at `index` and shift all following elements # # var a = [10,20,30] @@ -858,18 +1000,18 @@ end # Associative arrays that internally uses couples to represent each (key, value) pairs. # This is an helper class that some specific implementation of Map may implements. -interface CoupleMap[K: Object, E] - super Map[K, E] +interface CoupleMap[K, V] + super Map[K, V] # Return the couple of the corresponding key # Return null if the key is no associated element - protected fun couple_at(key: K): nullable Couple[K, E] is abstract + protected fun couple_at(key: K): nullable Couple[K, V] is abstract # Return a new iteralot on all couples # Used to provide `iterator` and others - protected fun couple_iterator: Iterator[Couple[K,E]] is abstract + protected fun couple_iterator: Iterator[Couple[K,V]] is abstract - redef fun iterator do return new CoupleMapIterator[K,E](couple_iterator) + redef fun iterator do return new CoupleMapIterator[K,V](couple_iterator) redef fun [](key) do @@ -880,13 +1022,15 @@ interface CoupleMap[K: Object, E] return c.second end end + + redef fun has_key(key) do return couple_at(key) != null end # Iterator on CoupleMap # # Actually it is a wrapper around an iterator of the internal array of the map. -private class CoupleMapIterator[K: Object, E] - super MapIterator[K, E] +private class CoupleMapIterator[K, V] + super MapIterator[K, V] redef fun item do return _iter.item.second #redef fun item=(e) do _iter.item.second = e @@ -900,9 +1044,7 @@ private class CoupleMapIterator[K: Object, E] _iter.next end - var _iter: Iterator[Couple[K,E]] - - init(i: Iterator[Couple[K,E]]) do _iter = i + var iter: Iterator[Couple[K,V]] end # Some tools ################################################################### @@ -911,15 +1053,8 @@ end class Couple[F, S] # The first element of the couple. - var first: F writable + var first: F is writable # The second element of the couple. - var second: S writable - - # Create a new instance with a first and a second object. - init(f: F, s: S) - do - first = f - second = s - end + var second: S is writable end