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 import serialization
  19
  20 # Simple way to store an `HashMap[K, Array[V]]`
  21 #
  22 # Unlike standard HashMap, MultiHashMap provides a new
  23 # empty array on the first access on a unknown key.
  24 #
  25 #     var m = new MultiHashMap[String, Char]
  26 #     assert not m.has_key("four")
  27 #     m["four"].add('i')
  28 #     m["four"].add('i')
  29 #     m["four"].add('i')
  30 #     m["four"].add('i')
  31 #     assert m.has_key("four")
  32 #     assert m["four"] == ['i', 'i', 'i', 'i']
  33 #     assert m["zzz"] == new Array[Char]
  34 class MultiHashMap[K, V]
  35         auto_serializable
  36         super HashMap[K, Array[V]]
  37
  38         # Add `v` to the array associated with `k`.
  39         # If there is no array associated, then create it.
  40         fun add_one(k: K, v: V)
  41         do
  42                 var x = self.get_or_null(k)
  43                 if x != null then
  44                         x.add(v)
  45                 else
  46                         self[k] = [v]
  47                 end
  48         end
  49
  50         redef fun provide_default_value(key) do
  51                 var res = new Array[V]
  52                 self[key] = res
  53                 return res
  54         end
  55 end
  56
  57 # Simple way to store an `HashMap[K1, HashMap[K2, V]]`
  58 #
  59 # ~~~~
  60 # var hm2 = new HashMap2[Int, String, Float]
  61 # hm2[1, "one"] = 1.0
  62 # hm2[2, "two"] = 2.0
  63 # assert hm2[1, "one"] == 1.0
  64 # assert hm2[2, "not-two"] == null
  65 # ~~~~
  66 class HashMap2[K1, K2, V]
  67         auto_serializable
  68
  69         private var level1 = new HashMap[K1, HashMap[K2, V]]
  70
  71         # Return the value associated to the keys `k1` and `k2`.
  72         # Return `null` if no such a value.
  73         fun [](k1: K1, k2: K2): nullable V
  74         do
  75                 var level1 = self.level1
  76                 var level2 = level1.get_or_null(k1)
  77                 if level2 == null then return null
  78                 return level2.get_or_null(k2)
  79         end
  80
  81         # Set `v` the value associated to the keys `k1` and `k2`.
  82         fun []=(k1: K1, k2: K2, v: V)
  83         do
  84                 var level1 = self.level1
  85                 var level2 = level1.get_or_null(k1)
  86                 if level2 == null then
  87                         level2 = new HashMap[K2, V]
  88                         level1[k1] = level2
  89                 end
  90                 level2[k2] = v
  91         end
  92
  93         # Remove the item at `k1` and `k2`
  94         fun remove_at(k1: K1, k2: K2)
  95         do
  96                 var level1 = self.level1
  97                 var level2 = level1.get_or_null(k1)
  98                 if level2 == null then return
  99                 level2.keys.remove(k2)
 100         end
 101
 102         # Remove all items
 103         fun clear do level1.clear
 104 end
 105
 106 # Simple way to store an `HashMap[K1, HashMap[K2, HashMap[K3, V]]]`
 107 #
 108 # ~~~~
 109 # var hm3 = new HashMap3[Int, String, Int, Float]
 110 # hm3[1, "one", 11] = 1.0
 111 # hm3[2, "two", 22] = 2.0
 112 # assert hm3[1, "one", 11] == 1.0
 113 # assert hm3[2, "not-two", 22] == null
 114 # ~~~~
 115 class HashMap3[K1, K2, K3, V]
 116         auto_serializable
 117
 118         private var level1 = new HashMap[K1, HashMap2[K2, K3, V]]
 119
 120         # Return the value associated to the keys `k1`, `k2`, and `k3`.
 121         # Return `null` if no such a value.
 122         fun [](k1: K1, k2: K2, k3: K3): nullable V
 123         do
 124                 var level1 = self.level1
 125                 var level2 = level1.get_or_null(k1)
 126                 if level2 == null then return null
 127                 return level2[k2, k3]
 128         end
 129
 130         # Set `v` the value associated to the keys `k1`, `k2`, and `k3`.
 131         fun []=(k1: K1, k2: K2, k3: K3, v: V)
 132         do
 133                 var level1 = self.level1
 134                 var level2 = level1.get_or_null(k1)
 135                 if level2 == null then
 136                         level2 = new HashMap2[K2, K3, V]
 137                         level1[k1] = level2
 138                 end
 139                 level2[k2, k3] = v
 140         end
 141
 142         # Remove the item at `k1`, `k2` and `k3`
 143         fun remove_at(k1: K1, k2: K2, k3: K3)
 144         do
 145                 var level1 = self.level1
 146                 var level2 = level1.get_or_null(k1)
 147                 if level2 == null then return
 148                 level2.remove_at(k2, k3)
 149         end
 150
 151         # Remove all items
 152         fun clear do level1.clear
 153 end
 154
 155 # A map with a default value.
 156 #
 157 # ~~~~
 158 # var dm = new DefaultMap[String, Int](10)
 159 # assert dm["a"] == 10
 160 # ~~~~
 161 #
 162 # The default value is used when the key is not present.
 163 # And getting a default value does not register the key.
 164 #
 165 # ~~~~
 166 # assert dm["a"] == 10
 167 # assert dm.length == 0
 168 # assert dm.has_key("a") == false
 169 # ~~~~
 170 #
 171 # It also means that removed key retrieve the default value.
 172 #
 173 # ~~~~
 174 # dm["a"] = 2
 175 # assert dm["a"] == 2
 176 # dm.keys.remove("a")
 177 # assert dm["a"] == 10
 178 # ~~~~
 179 #
 180 # Warning: the default value is used as is, so using mutable object might
 181 # cause side-effects.
 182 #
 183 # ~~~~
 184 # var dma = new DefaultMap[String, Array[Int]](new Array[Int])
 185 #
 186 # dma["a"].add(65)
 187 # assert dma["a"] == [65]
 188 # assert dma.default == [65]
 189 # assert dma["c"] == [65]
 190 #
 191 # dma["b"] += [66]
 192 # assert dma["b"] == [65, 66]
 193 # assert dma.default == [65]
 194 # ~~~~
 195 class DefaultMap[K, V]
 196         auto_serializable
 197         super HashMap[K, V]
 198
 199         # The default value.
 200         var default: V
 201
 202         redef fun provide_default_value(key) do return default
 203 end