lib/more_collections.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Highly specific, but useful, collections-related classes.
  16 module more_collections
  17
  18 # Simple way to store an `HashMap[K, Array[V]]`
  19 #
  20 # Unlike standard HashMap, MultiHashMap provides a new
  21 # empty array on the first access on a unknown key.
  22 #
  23 #     var m = new MultiHashMap[String, Char]
  24 #     assert not m.has_key("four")
  25 #     m["four"].add('i')
  26 #     m["four"].add('i')
  27 #     m["four"].add('i')
  28 #     m["four"].add('i')
  29 #     assert m.has_key("four")
  30 #     assert m["four"] == ['i', 'i', 'i', 'i']
  31 #     assert m["zzz"] == new Array[Char]
  32 class MultiHashMap[K, V]
  33         super HashMap[K, Array[V]]
  34
  35         # Add `v` to the array associated with `k`.
  36         # If there is no array associated, then create it.
  37         fun add_one(k: K, v: V)
  38         do
  39                 if self.has_key(k) then
  40                         self[k].add(v)
  41                 else
  42                         self[k] = [v]
  43                 end
  44         end
  45
  46         redef fun provide_default_value(key) do
  47                 var res = new Array[V]
  48                 self[key] = res
  49                 return res
  50         end
  51 end
  52
  53 # Simple way to store an `HashMap[K1, HashMap[K2, V]]`
  54 #
  55 # ~~~~
  56 # var hm2 = new HashMap2[Int, String, Float]
  57 # hm2[1, "one"] = 1.0
  58 # hm2[2, "two"] = 2.0
  59 # assert hm2[1, "one"] == 1.0
  60 # assert hm2[2, "not-two"] == null
  61 # ~~~~
  62 class HashMap2[K1, K2, V]
  63         private var level1 = new HashMap[K1, HashMap[K2, V]]
  64
  65         # Return the value associated to the keys `k1` and `k2`.
  66         # Return `null` if no such a value.
  67         fun [](k1: K1, k2: K2): nullable V
  68         do
  69                 var level1 = self.level1
  70                 if not level1.has_key(k1) then return null
  71                 var level2 = level1[k1]
  72                 if not level2.has_key(k2) then return null
  73                 return level2[k2]
  74         end
  75
  76         # Set `v` the value associated to the keys `k1` and `k2`.
  77         fun []=(k1: K1, k2: K2, v: V)
  78         do
  79                 var level1 = self.level1
  80                 var level2: HashMap[K2, V]
  81                 if not level1.has_key(k1) then
  82                         level2 = new HashMap[K2, V]
  83                         level1[k1] = level2
  84                 else
  85                         level2 = level1[k1]
  86                 end
  87                 level2[k2] = v
  88         end
  89 end
  90
  91 # Simple way to store an `HashMap[K1, HashMap[K2, HashMap[K3, V]]]`
  92 #
  93 # ~~~~
  94 # var hm3 = new HashMap3[Int, String, Int, Float]
  95 # hm3[1, "one", 11] = 1.0
  96 # hm3[2, "two", 22] = 2.0
  97 # assert hm3[1, "one", 11] == 1.0
  98 # assert hm3[2, "not-two", 22] == null
  99 # ~~~~
 100 class HashMap3[K1, K2, K3, V]
 101         private var level1 = new HashMap[K1, HashMap2[K2, K3, V]]
 102
 103         # Return the value associated to the keys `k1`, `k2`, and `k3`.
 104         # Return `null` if no such a value.
 105         fun [](k1: K1, k2: K2, k3: K3): nullable V
 106         do
 107                 var level1 = self.level1
 108                 if not level1.has_key(k1) then return null
 109                 var level2 = level1[k1]
 110                 return level2[k2, k3]
 111         end
 112
 113         # Set `v` the value associated to the keys `k1`, `k2`, and `k3`.
 114         fun []=(k1: K1, k2: K2, k3: K3, v: V)
 115         do
 116                 var level1 = self.level1
 117                 var level2: HashMap2[K2, K3, V]
 118                 if not level1.has_key(k1) then
 119                         level2 = new HashMap2[K2, K3, V]
 120                         level1[k1] = level2
 121                 else
 122                         level2 = level1[k1]
 123                 end
 124                 level2[k2, k3] = v
 125         end
 126 end
 127
 128 # A map with a default value.
 129 #
 130 # ~~~~
 131 # var dm = new DefaultMap[String, Int](10)
 132 # assert dm["a"] == 10
 133 # ~~~~
 134 #
 135 # The default value is used when the key is not present.
 136 # And getting a default value does not register the key.
 137 #
 138 # ~~~~
 139 # assert dm["a"] == 10
 140 # assert dm.length == 0
 141 # assert dm.has_key("a") == false
 142 # ~~~~
 143 #
 144 # It also means that removed key retrieve the default value.
 145 #
 146 # ~~~~
 147 # dm["a"] = 2
 148 # assert dm["a"] == 2
 149 # dm.keys.remove("a")
 150 # assert dm["a"] == 10
 151 # ~~~~
 152 #
 153 # Warning: the default value is used as is, so using mutable object might
 154 # cause side-effects.
 155 #
 156 # ~~~~
 157 # var dma = new DefaultMap[String, Array[Int]](new Array[Int])
 158 #
 159 # dma["a"].add(65)
 160 # assert dma["a"] == [65]
 161 # assert dma.default == [65]
 162 # assert dma["c"] == [65]
 163 #
 164 # dma["b"] += [66]
 165 # assert dma["b"] == [65, 66]
 166 # assert dma.default == [65]
 167 # ~~~~
 168 class DefaultMap[K, V]
 169         super HashMap[K, V]
 170
 171         # The default value.
 172         var default: V
 173
 174         redef fun provide_default_value(key) do return default
 175 end