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
  90         # Remove the item at `k1` and `k2`
  91         fun remove_at(k1: K1, k2: K2)
  92         do
  93                 var level1 = self.level1
  94
  95                 if not level1.has_key(k1) then return
  96
  97                 var level2 = level1[k1]
  98                 level2.keys.remove(k2)
  99         end
 100 end
 101
 102 # Simple way to store an `HashMap[K1, HashMap[K2, HashMap[K3, V]]]`
 103 #
 104 # ~~~~
 105 # var hm3 = new HashMap3[Int, String, Int, Float]
 106 # hm3[1, "one", 11] = 1.0
 107 # hm3[2, "two", 22] = 2.0
 108 # assert hm3[1, "one", 11] == 1.0
 109 # assert hm3[2, "not-two", 22] == null
 110 # ~~~~
 111 class HashMap3[K1, K2, K3, V]
 112         private var level1 = new HashMap[K1, HashMap2[K2, K3, V]]
 113
 114         # Return the value associated to the keys `k1`, `k2`, and `k3`.
 115         # Return `null` if no such a value.
 116         fun [](k1: K1, k2: K2, k3: K3): nullable V
 117         do
 118                 var level1 = self.level1
 119                 if not level1.has_key(k1) then return null
 120                 var level2 = level1[k1]
 121                 return level2[k2, k3]
 122         end
 123
 124         # Set `v` the value associated to the keys `k1`, `k2`, and `k3`.
 125         fun []=(k1: K1, k2: K2, k3: K3, v: V)
 126         do
 127                 var level1 = self.level1
 128                 var level2: HashMap2[K2, K3, V]
 129                 if not level1.has_key(k1) then
 130                         level2 = new HashMap2[K2, K3, V]
 131                         level1[k1] = level2
 132                 else
 133                         level2 = level1[k1]
 134                 end
 135                 level2[k2, k3] = v
 136         end
 137
 138         # Remove the item at `k1`, `k2` and `k3`
 139         fun remove_at(k1: K1, k2: K2, k3: K3)
 140         do
 141                 var level1 = self.level1
 142
 143                 if not level1.has_key(k1) then return
 144
 145                 var level2 = level1[k1]
 146                 level2.remove_at(k2, k3)
 147         end
 148 end
 149
 150 # A map with a default value.
 151 #
 152 # ~~~~
 153 # var dm = new DefaultMap[String, Int](10)
 154 # assert dm["a"] == 10
 155 # ~~~~
 156 #
 157 # The default value is used when the key is not present.
 158 # And getting a default value does not register the key.
 159 #
 160 # ~~~~
 161 # assert dm["a"] == 10
 162 # assert dm.length == 0
 163 # assert dm.has_key("a") == false
 164 # ~~~~
 165 #
 166 # It also means that removed key retrieve the default value.
 167 #
 168 # ~~~~
 169 # dm["a"] = 2
 170 # assert dm["a"] == 2
 171 # dm.keys.remove("a")
 172 # assert dm["a"] == 10
 173 # ~~~~
 174 #
 175 # Warning: the default value is used as is, so using mutable object might
 176 # cause side-effects.
 177 #
 178 # ~~~~
 179 # var dma = new DefaultMap[String, Array[Int]](new Array[Int])
 180 #
 181 # dma["a"].add(65)
 182 # assert dma["a"] == [65]
 183 # assert dma.default == [65]
 184 # assert dma["c"] == [65]
 185 #
 186 # dma["b"] += [66]
 187 # assert dma["b"] == [65, 66]
 188 # assert dma.default == [65]
 189 # ~~~~
 190 class DefaultMap[K, V]
 191         super HashMap[K, V]
 192
 193         # The default value.
 194         var default: V
 195
 196         redef fun provide_default_value(key) do return default
 197 end