lib/counter.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 # Simple numerical statistical analysis and presentation
  16 module counter
  17
  18 import poset
  19
  20 # A counter counts occurrences of things
  21 # Use this instead of a `HashMap[E, Int]`
  22 #
  23 # ~~~
  24 # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
  25 # assert c["a"]   == 2
  26 # assert c["b"]   == 3
  27 # assert c["c"]   == 1
  28 # assert c["d"]   == 0
  29 # ~~~
  30 #
  31 # The counter class can also be used to gather statistical informations.
  32 #
  33 # ~~~~
  34 # assert c.length == 3   # because 3 distinct values
  35 # assert c.max    == "b" # because "b" has the most count (3)
  36 # assert c.avg    == 2.0 # because it is the mean of the counts
  37 # ~~~~
  38 class Counter[E]
  39         super Map[E, Int]
  40
  41         # Total number of counted occurrences
  42         #
  43         # ~~~
  44         # var c = new Counter[String]
  45         # assert c.sum == 0
  46         # c.inc_all(["a", "a", "b", "b", "b", "c"])
  47         # assert c.sum == 6
  48         # ~~~
  49         var sum: Int = 0
  50
  51         private var map = new HashMap[E, Int]
  52
  53         redef fun iterator do return map.iterator
  54
  55         # The number of counted occurrences of `e`
  56         redef fun [](e: E): Int
  57         do
  58                 var map = self.map
  59                 if map.has_key(e) then return map[e]
  60                 return 0
  61         end
  62
  63         redef fun []=(e: E, value: Int)
  64         do
  65                 sum -= self[e]
  66                 self.map[e] = value
  67                 sum += value
  68         end
  69
  70         redef fun keys do return map.keys
  71
  72         redef fun values do return map.values
  73
  74         redef fun length do return map.length
  75
  76         redef fun is_empty do return map.is_empty
  77
  78         redef fun clear do
  79                 sum = 0
  80                 map.clear
  81         end
  82
  83         # Count one more occurrence of `e`
  84         fun inc(e: E)
  85         do
  86                 self.map[e] = self[e] + 1
  87                 sum += 1
  88         end
  89
  90         # Count one more for each element of `es`
  91         fun inc_all(es: Collection[E])
  92         do
  93                 for e in es do inc(e)
  94         end
  95
  96         # Decrement the value of `e` by 1
  97         fun dec(e: E) do
  98                 if not has_key(e) then
  99                         self.map[e] = 0
 100                 else
 101                         self.map[e] = self[e] - 1
 102                         sum += - 1
 103                 end
 104         end
 105
 106         # Decrement the value for each element of `es`
 107         fun dec_all(es: Collection[E])
 108         do
 109                 for e in es do dec(e)
 110         end
 111
 112         # A new Counter initialized with `inc_all`.
 113         init from(es: Collection[E])
 114         do
 115                 inc_all(es)
 116         end
 117
 118         # Return an array of elements sorted by occurrences
 119         #
 120         # ~~~
 121         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 122         # assert c.sort == ["c", "a", "b"]
 123         # ~~~
 124         fun sort: Array[E]
 125         do
 126                 var res = map.keys.to_a
 127                 var sorter = new CounterComparator[E](self)
 128                 sorter.sort(res)
 129                 return res
 130         end
 131
 132         # The method used to display an element
 133         # @toimplement by default just call `to_s` on the element
 134         protected fun element_to_s(e: E): String
 135         do
 136                 return e.to_s
 137         end
 138
 139         # Display statistical information
 140         fun print_summary
 141         do
 142                 var list = self.sort
 143                 print " population: {list.length}"
 144                 if list.is_empty then return
 145                 print " minimum value: {self[list.first]}"
 146                 print " maximum value: {self[list.last]}"
 147                 print " total value: {self.sum}"
 148                 print " average value: {div(self.sum,list.length)}"
 149                 print " distribution:"
 150                 var count = 0
 151                 var sum = 0
 152                 var limit = self[list.first]
 153                 for t in list do
 154                         if self[t] > limit then
 155                                 print "  <={limit}: sub-population={count} ({div(count*100,list.length)}%); cumulated value={sum} ({div(sum*100,self.sum)}%)"
 156                                 count = 0
 157                                 sum = 0
 158                                 while self[t] > limit do
 159                                         limit = limit * 2
 160                                         if limit == 0 then limit = 1
 161                                 end
 162                         end
 163                         count += 1
 164                         sum += self[t]
 165                 end
 166                 print "  <={limit}: sub-population={count} ({div(count*100,list.length)}%); cumulated value={sum} ({div(sum*100,self.sum)}%)"
 167         end
 168
 169         # Display up to `count` most used elements and `count` least used elements
 170         # Use `element_to_s` to display the element
 171         fun print_elements(count: Int)
 172         do
 173                 print " list:"
 174                 var list = self.sort
 175                 var min = count
 176                 if list.length <= count*2 then min = list.length
 177                 for i in [0..min[ do
 178                         var t = list[list.length-i-1]
 179                         print "  {element_to_s(t)}: {self[t]} ({div(self[t]*100,self.sum)}%)"
 180                 end
 181                 if list.length <= count*2 then return
 182                 print "  ..."
 183                 for i in [0..min[ do
 184                         var t = list[min-i-1]
 185                         print "  {element_to_s(t)}: {self[t]} ({div(self[t]*100,self.sum)}%)"
 186                 end
 187         end
 188
 189         # Return the element with the highest value (aka. the mode)
 190         #
 191         # ~~~
 192         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 193         # assert c.max == "b"
 194         # ~~~
 195         #
 196         # If more than one max exists, the first one is returned.
 197         fun max: nullable E do
 198                 var max: nullable Int = null
 199                 var elem: nullable E = null
 200                 for e in map.keys do
 201                         var v = map[e]
 202                         if max == null or v > max then
 203                                 max = v
 204                                 elem = e
 205                         end
 206                 end
 207                 return elem
 208         end
 209
 210         # Return the couple with the lowest value
 211         #
 212         # ~~~
 213         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 214         # assert c.min == "c"
 215         # ~~~
 216         #
 217         # If more than one min exists, the first one is returned.
 218         fun min: nullable E do
 219                 var min: nullable Int = null
 220                 var elem: nullable E = null
 221                 for e in map.keys do
 222                         var v = map[e]
 223                         if min == null or v < min then
 224                                 min = v
 225                                 elem = e
 226                         end
 227                 end
 228                 return elem
 229         end
 230
 231         # Values average (aka. arithmetic mean)
 232         #
 233         # ~~~
 234         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 235         # assert c.avg == 2.0
 236         # ~~~
 237         fun avg: Float do
 238                 if values.is_empty then return 0.0
 239                 return (sum / values.length).to_f
 240         end
 241
 242         # The standard derivation of the counter values
 243         #
 244         # ~~~
 245         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 246         # assert c.std_dev > 0.81
 247         # assert c.std_dev < 0.82
 248         # ~~~
 249         fun std_dev: Float do
 250                 var avg = self.avg
 251                 var sum = 0.0
 252                 for value in map.values do
 253                         sum += (value.to_f - avg).pow(2.0)
 254                 end
 255                 return (sum / map.length.to_f).sqrt
 256         end
 257 end
 258
 259 private class CounterComparator[E]
 260         super Comparator
 261         redef type COMPARED: E
 262         var counter: Counter[E]
 263         redef fun compare(a,b) do return self.counter.map[a] <=> self.counter.map[b]
 264 end
 265
 266 redef class POSet[E]
 267         private fun show_counter(c: Counter[Int])
 268         do
 269                 var list = c.sort
 270                 default_comparator.sort(list)
 271                 for e in list do
 272                         print " {e} -> {c[e]} times ({div(c[e]*100, c.sum)}%)"
 273                 end
 274         end
 275
 276         # Display exhaustive metrics about the poset
 277         fun print_metrics
 278         do
 279                 var nb_greaters = new Counter[E]
 280                 var nb_direct_greaters = new Counter[E]
 281                 var nb_smallers = new Counter[E]
 282                 var nb_direct_smallers = new Counter[E]
 283                 var nb_direct_edges = 0
 284                 var nb_edges = 0
 285                 for n in self do
 286                         var ne = self[n]
 287                         nb_edges += ne.greaters.length
 288                         nb_direct_edges += ne.direct_greaters.length
 289                         nb_greaters[n] = ne.greaters.length
 290                         nb_direct_greaters[n] = ne.direct_greaters.length
 291                         nb_smallers[n] = ne.smallers.length
 292                         nb_direct_smallers[n] = ne.direct_smallers.length
 293                 end
 294                 print "Number of nodes: {self.length}"
 295                 print "Number of edges: {nb_edges} ({div(nb_edges,self.length)} per node)"
 296                 print "Number of direct edges: {nb_direct_edges} ({div(nb_direct_edges,self.length)} per node)"
 297                 print "Distribution of greaters"
 298                 nb_greaters.print_summary
 299                 print "Distribution of direct greaters"
 300                 nb_direct_greaters.print_summary
 301                 print "Distribution of smallers"
 302                 nb_smallers.print_summary
 303                 print "Distribution of direct smallers"
 304                 nb_direct_smallers.print_summary
 305         end
 306 end
 307
 308 # Helper function to display `n/d` and handle division by 0
 309 fun div(n: Int, d: Int): String
 310 do
 311         if d == 0 then return "na"
 312         return ((100*n/d).to_f/100.0).to_precision(2)
 313 end