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 class Counter[E: Object]
  23         super Map[E, Int]
  24
  25         # Total number of counted occurrences
  26         var sum: Int = 0
  27
  28         private var map = new HashMap[E, Int]
  29
  30         redef fun iterator do return map.iterator
  31
  32         # The number of counted occurrences of `e`
  33         redef fun [](e: E): Int
  34         do
  35                 var map = self.map
  36                 if map.has_key(e) then return map[e]
  37                 return 0
  38         end
  39
  40         redef fun []=(e: E, value: Int)
  41         do
  42                 sum -= self[e]
  43                 self.map[e] = value
  44                 sum += value
  45         end
  46
  47         redef fun keys do return map.keys
  48
  49         redef fun values do return map.values
  50
  51         redef fun length do return map.length
  52
  53         redef fun is_empty do return map.is_empty
  54
  55         redef fun clear do
  56                 sum = 0
  57                 map.clear
  58         end
  59
  60         # Count one more occurrence of `e`
  61         fun inc(e: E)
  62         do
  63                 self.map[e] = self[e] + 1
  64                 sum += 1
  65         end
  66
  67         # Return an array of elements sorted by occurrences
  68         fun sort: Array[E]
  69         do
  70                 var res = map.keys.to_a
  71                 var sorter = new CounterComparator[E](self)
  72                 sorter.sort(res)
  73                 return res
  74         end
  75
  76         # The method used to display an element
  77         # @toimplement by default just call `to_s` on the element
  78         protected fun element_to_s(e: E): String
  79         do
  80                 do return e.to_s
  81         end
  82
  83         # Display statistical information
  84         fun print_summary
  85         do
  86                 var list = self.sort
  87                 print " population: {list.length}"
  88                 if list.is_empty then return
  89                 print " minimum value: {self[list.first]}"
  90                 print " maximum value: {self[list.last]}"
  91                 print " total value: {self.sum}"
  92                 print " average value: {div(self.sum,list.length)}"
  93                 print " distribution:"
  94                 var count = 0
  95                 var sum = 0
  96                 var limit = self[list.first]
  97                 for t in list do
  98                         if self[t] > limit then
  99                                 print "  <={limit}: sub-population={count} ({div(count*100,list.length)}%); cumulated value={sum} ({div(sum*100,self.sum)}%)"
 100                                 count = 0
 101                                 sum = 0
 102                                 while self[t] > limit do
 103                                         limit = limit * 2
 104                                         if limit == 0 then limit = 1
 105                                 end
 106                         end
 107                         count += 1
 108                         sum += self[t]
 109                 end
 110                 print "  <={limit}: sub-population={count} ({div(count*100,list.length)}%); cumulated value={sum} ({div(sum*100,self.sum)}%)"
 111         end
 112
 113         # Display up to `count` most used elements and `count` least used elements
 114         # Use `element_to_s` to display the element
 115         fun print_elements(count: Int)
 116         do
 117                 print " list:"
 118                 var list = self.sort
 119                 var min = count
 120                 if list.length <= count*2 then min = list.length
 121                 for i in [0..min[ do
 122                         var t = list[list.length-i-1]
 123                         print "  {element_to_s(t)}: {self[t]} ({div(self[t]*100,self.sum)}%)"
 124                 end
 125                 if list.length <= count*2 then return
 126                 print "  ..."
 127                 for i in [0..min[ do
 128                         var t = list[min-i-1]
 129                         print "  {element_to_s(t)}: {self[t]} ({div(self[t]*100,self.sum)}%)"
 130                 end
 131         end
 132
 133         # Return the element with the highest value
 134         fun max: nullable E do
 135                 var max: nullable Int = null
 136                 var elem: nullable E = null
 137                 for e, v in map do
 138                         if max == null or v > max then
 139                                 max = v
 140                                 elem = e
 141                         end
 142                 end
 143                 return elem
 144         end
 145
 146         # Return the couple with the lowest value
 147         fun min: nullable E do
 148                 var min: nullable Int = null
 149                 var elem: nullable E = null
 150                 for e, v in map do
 151                         if min == null or v < min then
 152                                 min = v
 153                                 elem = e
 154                         end
 155                 end
 156                 return elem
 157         end
 158
 159         # Values average
 160         fun avg: Float do
 161                 if values.is_empty then return 0.0
 162                 return (sum / values.length).to_f
 163         end
 164
 165         # The standard derivation of the counter values
 166         fun std_dev: Float do
 167                 var avg = self.avg
 168                 var sum = 0.0
 169                 for value in map.values do
 170                         sum += (value.to_f - avg).pow(2.0)
 171                 end
 172                 return (sum / map.length.to_f).sqrt
 173         end
 174 end
 175
 176 private class CounterComparator[E: Object]
 177         super Comparator[E]
 178         var counter: Counter[E]
 179         redef fun compare(a,b) do return self.counter.map[a] <=> self.counter.map[b]
 180 end
 181
 182 redef class POSet[E]
 183         private fun show_counter(c: Counter[Int])
 184         do
 185                 var list = c.sort
 186                 default_comparator.sort(list)
 187                 for e in list do
 188                         print " {e} -> {c[e]} times ({div(c[e]*100, c.sum)}%)"
 189                 end
 190         end
 191
 192         # Display exhaustive metrics about the poset
 193         fun print_metrics
 194         do
 195                 var nb_greaters = new Counter[E]
 196                 var nb_direct_greaters = new Counter[E]
 197                 var nb_smallers = new Counter[E]
 198                 var nb_direct_smallers = new Counter[E]
 199                 var nb_direct_edges = 0
 200                 var nb_edges = 0
 201                 for n in self do
 202                         var ne = self[n]
 203                         nb_edges += ne.greaters.length
 204                         nb_direct_edges += ne.direct_greaters.length
 205                         nb_greaters[n] = ne.greaters.length
 206                         nb_direct_greaters[n] = ne.direct_greaters.length
 207                         nb_smallers[n] = ne.smallers.length
 208                         nb_direct_smallers[n] = ne.direct_smallers.length
 209                 end
 210                 print "Number of nodes: {self.length}"
 211                 print "Number of edges: {nb_edges} ({div(nb_edges,self.length)} per node)"
 212                 print "Number of direct edges: {nb_direct_edges} ({div(nb_direct_edges,self.length)} per node)"
 213                 print "Distribution of greaters"
 214                 nb_greaters.print_summary
 215                 print "Distribution of direct greaters"
 216                 nb_direct_greaters.print_summary
 217                 print "Distribution of smallers"
 218                 nb_smallers.print_summary
 219                 print "Distribution of direct smallers"
 220                 nb_direct_smallers.print_summary
 221         end
 222 end
 223
 224 # Helper function to display `n/d` and handle division by 0
 225 fun div(n: Int, d: Int): String
 226 do
 227         if d == 0 then return "na"
 228         return ((100*n/d).to_f/100.0).to_precision(2)
 229 end