src/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 total: Int = 0
  27
  28         private var map = new HashMap[E, Int]
  29
  30         # The number of counted occurrences of `e`
  31         redef fun [](e: E): Int
  32         do
  33                 var map = self.map
  34                 if map.has_key(e) then return map[e]
  35                 return 0
  36         end
  37
  38         redef fun []=(e: E, value: Int)
  39         do
  40                 total -= self[e]
  41                 self.map[e] = value
  42                 total += value
  43         end
  44
  45         redef fun keys do return map.keys
  46
  47         redef fun values do return map.values
  48
  49         # Count one more occurrence of `e`
  50         fun inc(e: E)
  51         do
  52                 self.map[e] = self[e] + 1
  53                 total += 1
  54         end
  55
  56         # Return an array of elements sorted by occurrences
  57         fun sort: Array[E]
  58         do
  59                 var res = map.keys.to_a
  60                 var sorter = new CounterSorter[E](self)
  61                 sorter.sort(res)
  62                 #res.sort !cmp a, b = map[a] <=> map[b]
  63                 return res
  64         end
  65
  66         # The method used to display an element
  67         # @toimplement by default just call `to_s` on the element
  68         protected fun element_to_s(e: E): String
  69         do
  70                 do return e.to_s
  71         end
  72
  73         # Display statistical information
  74         fun print_summary
  75         do
  76                 var list = self.sort
  77                 print " population: {list.length}"
  78                 if list.is_empty then return
  79                 print " minimum value: {self[list.first]}"
  80                 print " maximum value: {self[list.last]}"
  81                 print " total value: {self.total}"
  82                 print " average value: {div(self.total,list.length)}"
  83                 print " distribution:"
  84                 var count = 0
  85                 var sum = 0
  86                 var limit = self[list.first]
  87                 for t in list do
  88                         if self[t] > limit then
  89                                 print "  <={limit}: sub-population={count} ({div(count*100,list.length)}%); cumulated value={sum} ({div(sum*100,self.total)}%)"
  90                                 count = 0
  91                                 sum = 0
  92                                 while self[t] > limit do
  93                                         limit = limit * 2
  94                                         if limit == 0 then limit = 1
  95                                 end
  96                         end
  97                         count += 1
  98                         sum += self[t]
  99                 end
 100                 print "  <={limit}: sub-population={count} ({div(count*100,list.length)}%); cumulated value={sum} ({div(sum*100,self.total)}%)"
 101         end
 102
 103         # Display up to `count` most used elements and `count` least used elements
 104         # Use `element_to_s` to display the element
 105         fun print_elements(count: Int)
 106         do
 107                 print " list:"
 108                 var list = self.sort
 109                 var min = count
 110                 if list.length <= count*2 then min = list.length
 111                 for i in [0..min[ do
 112                         var t = list[list.length-i-1]
 113                         print "  {element_to_s(t)}: {self[t]} ({div(self[t]*100,self.total)}%)"
 114                 end
 115                 if list.length <= count*2 then return
 116                 print "  ..."
 117                 for i in [0..min[ do
 118                         var t = list[min-i-1]
 119                         print "  {element_to_s(t)}: {self[t]} ({div(self[t]*100,self.total)}%)"
 120                 end
 121         end
 122 end
 123
 124 private class CounterSorter[E: Object]
 125         super AbstractSorter[E]
 126         var counter: Counter[E]
 127         redef fun compare(a,b) do return self.counter.map[a] <=> self.counter.map[b]
 128 end
 129
 130 redef class POSet[E]
 131         private fun show_counter(c: Counter[Int])
 132         do
 133                 var list = c.sort
 134                 (new ComparableSorter[Int]).sort(list)
 135                 for e in list do
 136                         print " {e} -> {c[e]} times ({div(c[e]*100, c.total)}%)"
 137                 end
 138         end
 139
 140         # Display exhaustive metrics about the poset
 141         fun print_metrics
 142         do
 143                 var nb_greaters = new Counter[E]
 144                 var nb_direct_greaters = new Counter[E]
 145                 var nb_smallers = new Counter[E]
 146                 var nb_direct_smallers = new Counter[E]
 147                 var nb_direct_edges = 0
 148                 var nb_edges = 0
 149                 for n in self do
 150                         var ne = self[n]
 151                         nb_edges += ne.greaters.length
 152                         nb_direct_edges += ne.direct_greaters.length
 153                         nb_greaters[n] = ne.greaters.length
 154                         nb_direct_greaters[n] = ne.direct_greaters.length
 155                         nb_smallers[n] = ne.smallers.length
 156                         nb_direct_smallers[n] = ne.direct_smallers.length
 157                 end
 158                 print "Number of nodes: {self.length}"
 159                 print "Number of edges: {nb_edges} ({div(nb_edges,self.length)} per node)"
 160                 print "Number of direct edges: {nb_direct_edges} ({div(nb_direct_edges,self.length)} per node)"
 161                 print "Distribution of greaters"
 162                 nb_greaters.print_summary
 163                 print "Distribution of direct greaters"
 164                 nb_direct_greaters.print_summary
 165                 print "Distribution of smallers"
 166                 nb_smallers.print_summary
 167                 print "Distribution of direct smallers"
 168                 nb_direct_smallers.print_summary
 169         end
 170 end
 171
 172 # Helper function to display `n/d` and handle division by 0
 173 fun div(n: Int, d: Int): String
 174 do
 175         if d == 0 then return "na"
 176         return ((100*n/d).to_f/100.0).to_precision(2)
 177 end