Hash/boje-i-automobili/StatSet.java

   1 import java.util.AbstractSet;
   2 import java.util.Collection;
   3 import java.util.Collections;
   4 import java.util.HashMap;
   5 import java.util.HashSet;
   6 import java.util.Iterator;
   7
   8 /**
   9  * StatSet je primer standardnog Java skupa (interfejs `Set`) sa dodatnim
  10  * vodjenjem računa o tome kako se podaci smeštaju u okviru skupa, što može
  11  * pomoći da se bolje oceni kvalitet funkcije `hashCode` za konkretne objekte u
  12  * skupu.
  13  *
  14  * http://perun.dmi.rs
  15  *
  16  * @param <E>
  17  *            Tip objekata koji će biti čuvani u skupu
  18  */
  19 public class StatSet<E> extends AbstractSet<E> {
  20
  21         private final HashSet<E> set = new HashSet<E>();
  22         private final HashMap<Integer, Integer> count = new HashMap<>();
  23
  24         @Override
  25         public int size() {
  26                 return set.size();
  27         }
  28
  29         @Override
  30         public boolean isEmpty() {
  31                 return set.isEmpty();
  32         }
  33
  34         @Override
  35         public boolean contains(Object o) {
  36                 return set.contains(o);
  37         }
  38
  39         @Override
  40         public Iterator<E> iterator() {
  41                 // posto elementi mogu da se uklone preko iteratora
  42                 // moramo paziti da se brojaci odrzavaju ispravno
  43                 return new CountUpdateIterator<E>(set.iterator());
  44         }
  45
  46         @Override
  47         public Object[] toArray() {
  48                 return set.toArray();
  49         }
  50
  51         @Override
  52         public <T> T[] toArray(T[] a) {
  53                 return set.toArray(a);
  54         }
  55
  56         @Override
  57         public boolean add(E e) {
  58                 boolean b = set.add(e);
  59                 if (b) {
  60                         incCount(e.hashCode());
  61                 }
  62                 return b;
  63         }
  64
  65         @Override
  66         public boolean remove(Object o) {
  67                 boolean b = set.remove(o);
  68                 if (b) {
  69                         decCount(o.hashCode());
  70                 }
  71                 return b;
  72         }
  73
  74         @Override
  75         public boolean containsAll(Collection<?> c) {
  76                 return set.containsAll(c);
  77         }
  78
  79         @Override
  80         public boolean addAll(Collection<? extends E> c) {
  81                 boolean b = set.addAll(c);
  82                 recalculateCount();
  83                 return b;
  84         }
  85
  86         @Override
  87         public boolean retainAll(Collection<?> c) {
  88                 boolean b = set.retainAll(c);
  89                 recalculateCount();
  90                 return b;
  91         }
  92
  93         @Override
  94         public boolean removeAll(Collection<?> c) {
  95                 boolean b = set.removeAll(c);
  96                 recalculateCount();
  97                 return b;
  98         }
  99
 100         @Override
 101         public void clear() {
 102                 count.clear();
 103                 set.clear();
 104         }
 105
 106         private void incCount(int h) {
 107                 Integer i = count.get(h);
 108                 if (i == null)
 109                         i = new Integer(0);
 110                 count.put(h, i + 1);
 111         }
 112
 113         private void decCount(int h) {
 114                 Integer i = count.get(h);
 115                 if (i == null)
 116                         i = 0;
 117                 count.put(h, i - 1);
 118         }
 119
 120         public int getNumberOfValues() {
 121                 return count.size();
 122         }
 123
 124         public double getAverageChainLength() {
 125                 double avg = 0.0;
 126                 if (set.size() > 0) {
 127                         for (Integer i : count.values()) {
 128                                 avg += i;
 129                         }
 130                         avg = avg / count.size();
 131                 }
 132                 return avg;
 133         }
 134
 135         public double getStdDevChainLength() {
 136                 return stDevFromAvg(getAverageChainLength());
 137         }
 138
 139         private double stDevFromAvg(double avg) {
 140                 double std = 0.0;
 141                 if (set.size() > 0) {
 142                         for (Integer i : count.values()) {
 143                                 std += (i - avg) * (i - avg);
 144                         }
 145                         std = std / count.size();
 146                 }
 147                 return Math.sqrt(std);
 148         }
 149
 150         public int getLongestChain() {
 151                 return Collections.max(count.values());
 152         }
 153
 154         public double getChiSquare(long range) {
 155                 double chi = 0.0;
 156                 if (set.size() > 0) {
 157                         double avg = ((double) set.size()) / (double) range;
 158                         for (Integer i : count.values()) {
 159                                 chi += (i - avg) * (i - avg) / avg;
 160                         }
 161                 }
 162                 return chi;
 163         }
 164
 165         public void printStats() {
 166                 System.out.printf("Number of elements:\t%6d\n", set.size());
 167                 int numv = getNumberOfValues();
 168                 System.out.printf("Different values:\t%6d\t(%.2f %%)\n", numv, numv*100.0/set.size());
 169                 double avg = getAverageChainLength();
 170                 System.out.printf("Avg. search chain len.:\t%5.2f +- %5.2f\n", avg, stDevFromAvg(avg));
 171                 System.out.printf("Longest search chain:\t%5d\n", getLongestChain());
 172                 System.out.printf("Chi square (no. of el):\t%,14.2f\n" , getChiSquare(set.size()));
 173                 System.out.printf("Chi square (diff el.):\t%,14.2f\n", getChiSquare(count.size()));
 174         }
 175
 176         public double getChiSquare() {
 177                 // vraca za ceo moguc opseg vrednosti
 178                 return getChiSquare(2L * Integer.MAX_VALUE + 2);
 179         }
 180
 181         public E someElement() {
 182                 if (!set.isEmpty()) {
 183                         return set.iterator().next();
 184                 } else {
 185                         return null;
 186                 }
 187         }
 188
 189         private void recalculateCount() {
 190                 count.clear();
 191                 for (E el : set) {
 192                         incCount(el.hashCode());
 193                 }
 194         }
 195
 196         /**
 197          * Dodatna pomocna klasa koja brine o odrzavanju brojaca u slucaju da se
 198          * objekti uklanjaju preko iteratora.
 199          *
 200          */
 201         private class CountUpdateIterator<F> implements Iterator<F> {
 202
 203                 private final Iterator<F> iterator;
 204
 205                 private F trenutni = null;
 206
 207                 public CountUpdateIterator(Iterator<F> it) {
 208                         iterator = it;
 209                 }
 210
 211                 @Override
 212                 public boolean hasNext() {
 213                         return iterator.hasNext();
 214                 }
 215
 216                 @Override
 217                 public F next() {
 218                         trenutni = iterator.next();
 219                         return trenutni;
 220                 }
 221
 222                 @Override
 223                 public void remove() {
 224                         iterator.remove();
 225                         if (trenutni != null) {
 226                                 decCount(trenutni.hashCode());
 227                         }
 228                 }
 229         }
 230 }