From: Jean Privat Date: Thu, 20 Mar 2014 21:54:55 +0000 (-0400) Subject: Merge branch 'doc_on_collection' X-Git-Tag: v0.6.5~19 X-Git-Url: http://nitlanguage.org?hp=806f5d7224c256b1cb3f757bf33e9181d929eba9 Merge branch 'doc_on_collection' --- diff --git a/lib/standard/collection/abstract_collection.nit b/lib/standard/collection/abstract_collection.nit index 18bac96..434d26f 100644 --- a/lib/standard/collection/abstract_collection.nit +++ b/lib/standard/collection/abstract_collection.nit @@ -4,13 +4,15 @@ # # This file is free software, which comes along with NIT. This software is # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; -# without even the implied warranty of MERCHANTABILITY or FITNESS FOR A +# without even the implied warranty of MERCHANTABILITY or FITNESS FOR A # PARTICULAR PURPOSE. You can modify it is you want, provided this header # is kept unaltered, and a notification of the changes is added. # You are allowed to redistribute it and sell it, alone or is a part of # another product. -# This module define several abstract collection classes. +# Abstract collection classes and services. +# +# TODO specify the behavior on iterators when collections are modified. module abstract_collection import kernel @@ -71,7 +73,6 @@ interface Collection[E] return nb end - # Is `item` in the collection ? # Comparisons are done with == # @@ -151,7 +152,11 @@ interface Iterator[E] end # A collection that contains only one item. -# Used to pass arguments by reference +# +# Used to pass arguments by reference. +# +# Also used when one want to give asingle element when a full +# collection is expected class Container[E] super Collection[E] @@ -184,7 +189,7 @@ class Container[E] end # This iterator is quite stupid since it is used for only one item. -class ContainerIterator[E] +private class ContainerIterator[E] super Iterator[E] redef fun item do return _container.item @@ -200,30 +205,57 @@ end # Items can be removed from this collection interface RemovableCollection[E] super Collection[E] + # Remove all items + # + # var a = [1,2,3] + # a.clear + # assert a.length == 0 + # + # ENSURE `is_empty` fun clear is abstract # Remove an occucence of `item` + # + # var a = [1,2,3,1,2,3] + # a.remove 2 + # assert a == [1,3,1,2,3] fun remove(item: E) is abstract # Remove all occurences of `item` + # + # var a = [1,2,3,1,2,3] + # a.remove_all 2 + # assert a == [1,3,1,3] fun remove_all(item: E) do while has(item) do remove(item) end # Items can be added to these collections. interface SimpleCollection[E] super RemovableCollection[E] + # Add an item in a collection. + # + # var a = [1,2] + # a.add 3 + # assert a.has(3) == true + # assert a.has(10) == false + # # Ensure col.has(item) fun add(item: E) is abstract # Add each item of `coll`. + # var a = [1,2] + # a.add_all [3..5] + # assert a.has(4) == true + # assert a.has(10) == false fun add_all(coll: Collection[E]) do for i in coll do add(i) end # Abstract sets. # -# Set is a collection without ducplicates (according to ==) +# Set is a collection without duplicates (according to `==`) +# # var s: Set[String] = new ArraySet[String] # var a = "Hello" # var b = "Hel" + "lo" @@ -266,7 +298,7 @@ interface Set[E: Object] return has_all(other) end - # because of the law between `==` and `hash`, hash is redefined to be the sum of the hash of the elements + # Because of the law between `==` and `hash`, `hash` is redefined to be the sum of the hash of the elements redef fun hash do var res = 0 @@ -277,7 +309,15 @@ end # MapRead are abstract associative collections: `key` -> `item`. interface MapRead[K: Object, E] - # Get the item at `key`. + # Get the item at `key` + # + # var x = new HashMap[String, Int] + # x["four"] = 4 + # assert x["four"] == 4 + # # assert x["five"] #=> abort + # + # 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 # Get the item at `key` or null if `key` is not in the map. @@ -295,6 +335,12 @@ interface MapRead[K: Object, E] end # Get the item at `key` or return `default` if not in map + # + # var x = new HashMap[String, Int] + # x["four"] = 4 + # 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 do if has_key(key) then return self[key] @@ -310,17 +356,39 @@ interface MapRead[K: Object, E] # Return the point of view of self on the values only. # Note that `self` and `values` are views on the same data; # therefore any modification of one is visible on the other. + # + # var x = new HashMap[String, Int] + # x["four"] = 4 + # assert x.values.has(4) == true + # assert x.values.has(5) == false fun values: Collection[E] is abstract # Return the point of view of self on the keys only. # Note that `self` and `keys` are views on the same data; # therefore any modification of one is visible on the other. + # + # var x = new HashMap[String, Int] + # x["four"] = 4 + # assert x.keys.has("four") == true + # assert x.keys.has("five") == false fun keys: Collection[K] is abstract # Is there no item in the collection? + # + # var x = new HashMap[String, Int] + # assert x.is_empty == true + # x["four"] = 4 + # assert x.is_empty == false fun is_empty: Bool is abstract # Number of items in the collection. + # + # var x = new HashMap[String, Int] + # assert x.length == 0 + # x["four"] = 4 + # assert x.length == 1 + # x["five"] = 5 + # assert x.length == 2 fun length: Int is abstract # Called by the underling implementation of `[]` to provide a default value when a `key` has no value @@ -357,11 +425,39 @@ end # interface Map[K: Object, E] super MapRead[K, E] - # Set the`item` at `key`. - fun []=(key: K, item: E) is abstract + + # Set the `value` at `key`. + # + # Values can then get retrieved with `[]`. + # + # var x = new HashMap[String, Int] + # x["four"] = 4 + # assert x["four"] == 4 + # + # If the key was associated with a value, this old value is discarted + # 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 # Add each (key,value) of `map` into `self`. # If a same key exists in `map` and `self`, then the value in self is discarded. + # + # It is the analogous of `SimpleCollection::add_all` + # + # var x = new HashMap[String, Int] + # x["four"] = 4 + # x["five"] = 5 + # var y = new HashMap[String, Int] + # y["four"] = 40 + # y["nine"] = 90 + # x.recover_with y + # assert x["four"] == 40 + # assert x["five"] == 5 + # assert x["nine"] == 90 fun recover_with(map: Map[K, E]) do var i = map.iterator @@ -372,6 +468,13 @@ interface Map[K: Object, E] end # Remove all items + # + # var x = new HashMap[String, Int] + # x["four"] = 4 + # x.clear + # x.keys.has("four") == false + # + # ENSURE `is_empty` fun clear is abstract redef fun values: RemovableCollection[E] is abstract @@ -424,45 +527,120 @@ end # Sequences are indexed collections. # The first item is 0. The last is `length-1`. +# +# The order is the main caracteristic of sequence +# and all concrete implementation of sequences are basically interchangeable. interface SequenceRead[E] super Collection[E] + # Get the first item. # Is equivalent with `self[0]`. + # + # var a = [1,2,3] + # assert a.first == 1 + # + # REQUIRE `not is_empty` redef fun first do assert not_empty: not is_empty return self[0] end - # Return the index=th element of the sequence. - # The first element is 0 and the last if `length-1` + # Return the index-th element of the sequence. + # The first element is 0 and the last is `length-1` # If index is invalid, the program aborts + # + # var a = [10,20,30] + # assert a[0] == 10 + # assert a[1] == 20 + # assert a[2] == 30 + # + # REQUIRE `index >= 0 and index < length` fun [](index: Int): E is abstract # Get the last item. # Is equivalent with `self[length-1]`. + # + # var a = [1,2,3] + # assert a.last == 3 + # + # REQUIRE `not is_empty` fun last: E do assert not_empty: not is_empty return self[length-1] end - # Return the index of the first occurrence of `item`. - # Return -1 if `item` is not found - # Comparison is done with == - fun index_of(item: E): Int + # The index of the first occurrence of `item`. + # Return -1 if `item` is not found. + # Comparison is done with `==`. + # + # var a = [10,20,30,10,20,30] + # assert a.index_of(20) == 1 + # assert a.index_of(40) == -1 + fun index_of(item: E): Int do return index_of_from(item, 0) + + # The index of the last occurrence of `item`. + # Return -1 if `item` is not found. + # Comparison is done with `==`. + # + # var a = [10,20,30,10,20,30] + # assert a.last_index_of(20) == 4 + # assert a.last_index_of(40) == -1 + fun last_index_of(item: E): Int do return last_index_of_from(item, length-1) + + # The index of the first occurrence of `item`, starting from pos. + # Return -1 if `item` is not found. + # Comparison is done with `==`. + # + # var a = [10,20,30,10,20,30] + # assert a.index_of_from(20, 3) == 4 + # assert a.index_of_from(20, 4) == 4 + # assert a.index_of_from(20, 5) == -1 + fun index_of_from(item: E, pos: Int): Int do + var p = 0 var i = iterator while i.is_ok do - if i.item == item then return i.index + if p>pos and i.item == item then return i.index i.next + p += 1 end return -1 end + # The index of the last occurrence of `item` starting from `pos` and decrementing. + # Return -1 if `item` is not found. + # Comparison is done with `==`. + # + # var a = [10,20,30,10,20,30] + # assert a.last_index_of_from(20, 2) == 1 + # assert a.last_index_of_from(20, 1) == 1 + # assert a.last_index_of_from(20, 0) == -1 + fun last_index_of_from(item: E, pos: Int): Int + do + var res = -1 + var p = 0 + var i = iterator + while i.is_ok do + if p>pos then break + if i.item == item then res = p + i.next + p += 1 + end + return res + end + redef fun iterator: IndexedIterator[E] is abstract # Two sequences are equals if they have the same items in the same order. + # + # var a = new List[Int] + # a.add(1) + # a.add(2) + # a.add(3) + # assert a == [1,2,3] + # assert a != [1,3,2] redef fun ==(o) do if not o isa SequenceRead[nullable Object] then return false @@ -476,7 +654,7 @@ interface SequenceRead[E] return true end - # because of the law between `==` and `hash`, hash is redefined to be the sum of the hash of the elements + # Because of the law between `==` and `hash`, `hash` is redefined to be the sum of the hash of the elements redef fun hash do var res = 0 @@ -493,13 +671,27 @@ interface Sequence[E] # Set the first item. # Is equivalent with `self[0] = item`. + # + # var a = [1,2,3] + # a.first = 10 + # assert a == [10,2,3] fun first=(item: E) do self[0] = item end # Set the last item. # Is equivalent with `self[length-1] = item`. - fun last=(item: E) - do + # + # var a = [1,2,3] + # a.last = 10 + # assert a == [1,2,10] + # + # If the sequence is empty, `last=` is equivalent with `self[0]=` (thus with `first=`) + # + # var b = new Array[Int] + # b.last = 10 + # assert b == [10] + fun last=(item: E) + do var l = length if l > 0 then self[l-1] = item @@ -511,26 +703,82 @@ interface Sequence[E] # A synonym of `push` redef fun add(e) do push(e) - # Add an item after the last. + # Add an item after the last one. + # + # var a = [1,2,3] + # a.push(10) + # a.push(20) + # assert a == [1,2,3,10,20] fun push(e: E) is abstract # Add each item of `coll` after the last. + # + # var a = [1,2,3] + # a.append([7..9]) + # assert a == [1,2,3,7,8,9] fun append(coll: Collection[E]) do for i in coll do push(i) # Remove the last item. + # + # var a = [1,2,3] + # assert a.pop == 3 + # assert a.pop == 2 + # assert a == [1] + # + # REQUIRE `not is_empty` fun pop: E is abstract - # Add an item before the last. + # Add an item before the first one. + # + # var a = [1,2,3] + # a.unshift(10) + # a.unshift(20) + # assert a == [20,10,1,2,3] fun unshift(e: E) is abstract # Remove the first item. - # The second item become the first. + # The second item thus become the first. + # + # var a = [1,2,3] + # assert a.shift == 1 + # assert a.shift == 2 + # assert a == [3] + # + # REQUIRE `not is_empty` fun shift: E is abstract # Set the `item` at `index`. + # + # var a = [10,20,30] + # a[1] = 200 + # assert a == [10,200,30] + # + # like with `[]`, index should be between `0` and `length-1` + # However, if `index==length`, `[]=` works like `push`. + # + # a[3] = 400 + # assert a == [10,200,30,400] + # + # REQUIRE `index >= 0 and index <= length` fun []=(index: Int, item: E) is abstract + # Insert an element at a given position, following elements are shifted. + # + # var a = [10, 20, 30, 40] + # a.insert(100, 2) + # assert a == [10, 20, 100, 30, 40] + # + # REQUIRE `index >= 0 and index < length` + # ENSURE `self[index] == item` + fun insert(item: E, index: Int) is abstract + # Remove the item at `index` and shift all following elements + # + # var a = [10,20,30] + # a.remove_at(1) + # assert a == [10,30] + # + # REQUIRE `index >= 0 and index < length` fun remove_at(index: Int) is abstract end @@ -542,12 +790,20 @@ interface IndexedIterator[E] 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] + # 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 + # Return a new iteralot on all couples + # Used to provide `iterator` and others + protected fun couple_iterator: Iterator[Couple[K,E]] is abstract + + redef fun iterator do return new CoupleMapIterator[K,E](couple_iterator) + redef fun [](key) do var c = couple_at(key) @@ -561,8 +817,8 @@ end # Iterator on CoupleMap # -# Actually is is a wrapper around an iterator of the internal array of the map. -class CoupleMapIterator[K: Object, E] +# 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] redef fun item do return _iter.item.second @@ -573,7 +829,7 @@ class CoupleMapIterator[K: Object, E] redef fun is_ok do return _iter.is_ok redef fun next - do + do _iter.next end diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit index 988ddbf..c664719 100644 --- a/lib/standard/collection/array.nit +++ b/lib/standard/collection/array.nit @@ -61,13 +61,9 @@ abstract class AbstractArrayRead[E] redef fun index_of(item) do return index_of_from(item, 0) - # The index of the last occurrence of an element. - # Return -1 if not found. - fun last_index_of(item: E): Int do return last_index_of_from(item, length-1) + redef fun last_index_of(item: E): Int do return last_index_of_from(item, length-1) - # The index of the first occurrence of an element starting from pos. - # Return -1 if not found. - fun index_of_from(item: E, pos: Int): Int + redef fun index_of_from(item: E, pos: Int): Int do var i = pos var len = length @@ -80,9 +76,7 @@ abstract class AbstractArrayRead[E] return -1 end - # The index of the first occurrence of an element starting from pos, by decremanting the index - # Return -1 if not found. - fun last_index_of_from(item: E, pos: Int): Int + redef fun last_index_of_from(item: E, pos: Int): Int do var i = pos while i >= 0 do @@ -176,19 +170,14 @@ abstract class AbstractArray[E] redef fun unshift(item) do var i = length - 1 - while i > 0 do + while i >= 0 do self[i+1] = self[i] i -= 1 end self[0] = item end - # Insert an element at a given position, following elements are shifted. - # - # var a= [10, 20, 30, 40] - # a.insert(100, 2) - # assert a == [10, 20, 100, 30, 40] - fun insert(item: E, pos: Int) + redef fun insert(item: E, pos: Int) do enlarge(length + 1) copy_to(pos, length-pos, self, pos + 1) @@ -354,7 +343,7 @@ class Array[E] end # An `Iterator` on `AbstractArray` -class ArrayIterator[E] +private class ArrayIterator[E] super IndexedIterator[E] redef fun item do return _array[_index] @@ -427,7 +416,7 @@ class ArraySet[E: Object] end # Iterators on sets implemented with arrays. -class ArraySetIterator[E: Object] +private class ArraySetIterator[E: Object] super Iterator[E] redef fun is_ok do return _iter.is_ok @@ -474,7 +463,7 @@ class ArrayMap[K: Object, E] # O(1) redef fun length do return _items.length - redef fun iterator: CoupleMapIterator[K, E] do return new CoupleMapIterator[K, E](_items.iterator) + redef fun couple_iterator do return _items.iterator redef fun is_empty do return _items.is_empty @@ -531,7 +520,7 @@ class ArrayMap[K: Object, E] end end -class ArrayMapKeys[K: Object, E] +private class ArrayMapKeys[K: Object, E] super RemovableCollection[K] # The original map var map: ArrayMap[K, E] @@ -551,7 +540,7 @@ class ArrayMapKeys[K: Object, E] redef fun remove_all(key) do self.remove(key) end -class ArrayMapValues[K: Object, E] +private class ArrayMapValues[K: Object, E] super RemovableCollection[E] # The original map var map: ArrayMap[K, E] diff --git a/lib/standard/collection/hash_collection.nit b/lib/standard/collection/hash_collection.nit index 2e3980d..a34fd7e 100644 --- a/lib/standard/collection/hash_collection.nit +++ b/lib/standard/collection/hash_collection.nit @@ -247,7 +247,7 @@ class HashMap[K: Object, V] end # View of the keys of a HashMap -class HashMapKeys[K: Object, V] +private class HashMapKeys[K: Object, V] super RemovableCollection[K] # The original map var map: HashMap[K, V] @@ -268,7 +268,7 @@ class HashMapKeys[K: Object, V] end # View of the values of a Map -class HashMapValues[K: Object, V] +private class HashMapValues[K: Object, V] super RemovableCollection[V] # The original map var map: HashMap[K, V] @@ -453,7 +453,7 @@ private class HashSetNode[E: Object] end end -class HashSetIterator[E: Object] +private class HashSetIterator[E: Object] super Iterator[E] redef fun is_ok do return _node != null diff --git a/lib/standard/collection/list.nit b/lib/standard/collection/list.nit index 3a59a49..c9a7155 100644 --- a/lib/standard/collection/list.nit +++ b/lib/standard/collection/list.nit @@ -116,6 +116,26 @@ class List[E] _head = node end + # O(n) + redef fun insert(e, i) + do + var node = get_node(i) + if node == null then + push(e) + return + end + var nnode = new ListNode[E](e) + var next = node.next + if next == null then + _tail = nnode + else + next.prev = nnode + end + nnode.prev = node + nnode.next = next + node.next = nnode + end + # Append `l` to `self` but clear `l`. ## # O(1) diff --git a/tests/base_iterator1.nit b/tests/base_iterator1.nit index e3113a3..ceec37d 100644 --- a/tests/base_iterator1.nit +++ b/tests/base_iterator1.nit @@ -14,12 +14,12 @@ class ColIterable var col = new Array[String] - fun iterator: Iterator[String] do return new ArrayIterator[String](col) + fun iterator: Iterator[String] do return col.iterator end class MapIterable var map = new HashMap[String, Array[Char]] - fun iterator: MapIterator[String, Array[Char]] do return new HashMapIterator[String, Array[Char]](map) + fun iterator: MapIterator[String, Array[Char]] do return map.iterator end # ok