From 0c66a8f19033a1c71fc718629ff6c8490a4061e3 Mon Sep 17 00:00:00 2001 From: Jean Privat Date: Fri, 10 Feb 2012 11:24:45 -0500 Subject: [PATCH] lib: add 'keys' and 'values' methods in Map Make a bunch of method in Map depreciated and implement them by using a delegation trough keys or values. Signed-off-by: Jean Privat --- lib/standard/collection/abstract_collection.nit | 54 ++++++++---- lib/standard/collection/array.nit | 75 +++++++++++------ lib/standard/collection/hash_collection.nit | 100 ++++++++++++++--------- tests/test_iterate.nit | 4 +- tests/test_map.nit | 4 +- 5 files changed, 152 insertions(+), 85 deletions(-) diff --git a/lib/standard/collection/abstract_collection.nit b/lib/standard/collection/abstract_collection.nit index cd6c734..12a5598 100644 --- a/lib/standard/collection/abstract_collection.nit +++ b/lib/standard/collection/abstract_collection.nit @@ -242,8 +242,8 @@ interface MapRead[K: Object, E] # Get the item at `key'. fun [](key: K): E is abstract - # Is there an item at `key'. - fun has_key(key: K): Bool is abstract + # Depreciated alias for `keys.has' + 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 @@ -259,27 +259,29 @@ interface MapRead[K: Object, E] end end + # Return the point of view of self on the values only + fun values: Collection[E] is abstract + + # Return the point of view of self on the keys only + fun keys: Collection[E] is abstract + # Is there no item in the collection ? fun is_empty: Bool is abstract # Number of items in the collection. fun length: Int is abstract - # Is `item' in the collection ? - # Comparaisons are done with == - fun has(item: E): Bool is abstract + # Depreciated alias for `values.has' + fun has(item: E): Bool do return self.values.has(item) - # Is the collection contain only `item' ? - # Comparaisons are done with == - # Return true if the collection is empty. - fun has_only(item: E): Bool is abstract + # Depreciated alias for `values.has_only' + fun has_only(item: E): Bool do return self.values.has_only(item) - # How many occurences of `item' are in the collection ? - # Comparaisons are done with == - fun count(item: E): Int is abstract + # Depreciated alias for `values.count' + fun count(item: E): Int do return self.values.count(item) - # Return one the item of the collection - fun first: E is abstract + # Depreciated alias for `values.first' + fun first: E do return self.values.first end # Maps are associative collections: `key' -> `item'. @@ -344,6 +346,28 @@ interface MapIterator[K: Object, E] #fun item=(item: E) is abstract end +# Iterator on a 'keys' point of view of a map +class MapKeysIterator[K: Object, V] + super Iterator[K] + # The original iterator + var iterator: MapIterator[K, V] + + redef fun is_ok do return self.iterator.is_ok + redef fun next do self.iterator.next + redef fun item do return self.iterator.key +end + +# Iterator on a 'values' point of view of a map +class MapValuesIterator[K: Object, V] + super Iterator[K] + # The original iterator + var iterator: MapIterator[K, V] + + redef fun is_ok do return self.iterator.is_ok + redef fun next do self.iterator.next + redef fun item do return self.iterator.item +end + # Indexed collection are ordoned collections. # The first item is 0. The last is `length'-1. interface SequenceRead[E] @@ -452,8 +476,6 @@ 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 diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit index 1f96dd4..8a11c88 100644 --- a/lib/standard/collection/array.nit +++ b/lib/standard/collection/array.nit @@ -500,36 +500,12 @@ class ArrayMap[K: Object, E] end end - # O(n) - redef fun has_key(key) do return index(key) >= 0 - - # O(n) - redef fun has(item) - do - for i in _items do if i.second == item then return true - return false - end - - # O(n) - redef fun has_only(item) - do - for i in _items do if i.second != item then return false - return true - end + redef var keys: ArrayMapKeys[K, E] = new ArrayMapKeys[K, E](self) + redef var values: ArrayMapValues[K, E] = new ArrayMapValues[K, E](self) # O(1) redef fun length do return _items.length - redef fun first do return _items.first.second - - # O(n) - redef fun count(item) - do - var nb = 0 - for i in _items do if i.second == item then nb += 1 - return nb - end - redef fun iterator: CoupleMapIterator[K, E] do return new CoupleMapIterator[K, E](_items.iterator) redef fun is_empty do return _items.is_empty @@ -616,6 +592,53 @@ class ArrayMap[K: Object, E] end end +class ArrayMapKeys[K: Object, E] + super Collection[K] + # The original map + var map: ArrayMap[K, E] + redef fun count(k) do if self.has(k) then return 1 else return 0 + redef fun first do return self.map._items.first.first + redef fun has(k) do return self.map.index(k) >= 0 + redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty + redef fun is_empty do return self.map.is_empty + redef fun length do return self.map.length + redef fun iterator do return new MapKeysIterator[K, E](self.map.iterator) +end + +class ArrayMapValues[K: Object, E] + super Collection[K] + # The original map + var map: ArrayMap[K, E] + redef fun first do return self.map._items.first.first + redef fun is_empty do return self.map.is_empty + redef fun length do return self.map.length + redef fun iterator do return new MapValuesIterator[K, E](self.map.iterator) + + # O(n) + redef fun has(item) + do + for i in self.map._items do if i.second == item then return true + return false + end + + # O(n) + redef fun has_only(item) + do + for i in self.map._items do if i.second != item then return false + return true + end + + # O(n) + redef fun count(item) + do + var nb = 0 + for i in self.map._items do if i.second == item then nb += 1 + return nb + end + +end + + # Others tools ################################################################ redef class Iterator[E] diff --git a/lib/standard/collection/hash_collection.nit b/lib/standard/collection/hash_collection.nit index 4110677..d1b4bb7 100644 --- a/lib/standard/collection/hash_collection.nit +++ b/lib/standard/collection/hash_collection.nit @@ -210,8 +210,6 @@ class HashMap[K: Object, V] end end - redef fun has_key(key) do return node_at(key) != null - redef fun iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self) redef fun iterate @@ -224,47 +222,10 @@ class HashMap[K: Object, V] end end - redef fun first - do - assert _length > 0 - return _first_item._value - end - redef fun length do return _length redef fun is_empty do return _length == 0 - redef fun count(item) - do - var nb = 0 - var c = _first_item - while c != null do - if c._value == item then nb += 1 - c = c._next_item - end - return nb - end - - redef fun has(item) - do - var c = _first_item - while c != null do - if c._value == item then return true - c = c._next_item - end - return false - end - - redef fun has_only(item) - do - var c = _first_item - while c != null do - if c._value != item then return false - c = c._next_item - end - return true - end - redef fun []=(key, v) do var i = index_at(key) @@ -299,6 +260,67 @@ class HashMap[K: Object, V] _length = 0 enlarge(0) end + + redef var keys: HashMapKeys[K, V] = new HashMapKeys[K, V](self) + redef var values: HashMapValues[K, V] = new HashMapValues[K, V](self) +end + +class HashMapKeys[K: Object, V] + super NaiveCollection[K] + # The original map + var map: HashMap[K, V] + + redef fun count(k) do if self.has(k) then return 1 else return 0 + redef fun first do return self.map._first_item._key + redef fun has(k) do return self.map.node_at(k) != null + redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty + redef fun is_empty do return self.map.is_empty + redef fun length do return self.map.length + + redef fun iterator do return new MapKeysIterator[K, V](self.map.iterator) +end + +class HashMapValues[K: Object, V] + super NaiveCollection[V] + # The original map + var map: HashMap[K, V] + + redef fun count(item) + do + var nb = 0 + var c = self.map._first_item + while c != null do + if c._value == item then nb += 1 + c = c._next_item + end + return nb + end + redef fun first do return self.map._first_item._value + + redef fun has(item) + do + var c = self.map._first_item + while c != null do + if c._value == item then return true + c = c._next_item + end + return false + end + + redef fun has_only(item) + do + var c = self.map._first_item + while c != null do + if c._value != item then return false + c = c._next_item + end + return true + end + + redef fun is_empty do return self.map.is_empty + redef fun length do return self.map.length + + redef fun iterator do return new MapValuesIterator[K, V](self.map.iterator) end class HashMapNode[K: Object, V] diff --git a/tests/test_iterate.nit b/tests/test_iterate.nit index b2d95c5..9cfc2d8 100644 --- a/tests/test_iterate.nit +++ b/tests/test_iterate.nit @@ -77,6 +77,6 @@ test_coll(init_seq(new ArraySet[Int]), "ArraySet") test_coll(init_seq(new HashSet[Int]), "HashSet") test_coll([0..5[, "ORange") test_coll([0..4], "CRange") -test_coll(init_map(new ArrayMap[Int, Int]), "ArrayMap") -test_coll(init_map(new HashMap[Int, Int]), "HashMap") +test_coll(init_map(new ArrayMap[Int, Int]).values, "ArrayMap") +test_coll(init_map(new HashMap[Int, Int]).values, "HashMap") diff --git a/tests/test_map.nit b/tests/test_map.nit index 01b5ee6..58e8ea0 100644 --- a/tests/test_map.nit +++ b/tests/test_map.nit @@ -118,7 +118,7 @@ do print(m.has_key("blue")) print(not m.has_key("green")) print(not m.has_key("vert")) - print(m.join(", ")) + print(m.values.join(", ")) print("* remove:") print(m.count("rose") == 1) @@ -131,7 +131,7 @@ do m.remove_at("blue") print(m.length == 5) print(m.count("bleu") == 0) - print(m.join(", ")) + print(m.values.join(", ")) m.clear print(m.is_empty) end -- 1.7.9.5