1 /*
   2  * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.graalvm.compiler.core.common.util;
  24 
  25 import java.util.ArrayList;
  26 import java.util.HashMap;
  27 import java.util.IdentityHashMap;
  28 import java.util.List;
  29 import java.util.Map;
  30 
  31 /**
  32  * Creates an array of T objects order by the occurrence frequency of each object. The most
  33  * frequently used object is the first one, the least frequently used the last one. If {@code null}
  34  * is added, it is always the first element.
  35  *
  36  * Either object {@link #createIdentityEncoder() identity} or object {@link #createEqualityEncoder()
  37  * equality} can be used to build the array and count the frequency.
  38  */
  39 public class FrequencyEncoder<T> {
  40 
  41     static class Entry<T> {
  42         protected final T object;
  43         protected int frequency;
  44         protected int index;
  45 
  46         protected Entry(T object) {
  47             this.object = object;
  48             this.index = -1;
  49         }
  50     }
  51 
  52     protected final Map<T, Entry<T>> map;
  53     protected boolean containsNull;
  54 
  55     /**
  56      * Creates an encoder that uses object identity.
  57      */
  58     public static <T> FrequencyEncoder<T> createIdentityEncoder() {
  59         return new FrequencyEncoder<>(new IdentityHashMap<>());
  60     }
  61 
  62     /**
  63      * Creates an encoder that uses {@link Object#equals(Object) object equality}.
  64      */
  65     public static <T> FrequencyEncoder<T> createEqualityEncoder() {
  66         return new FrequencyEncoder<>(new HashMap<>());
  67     }
  68 
  69     protected FrequencyEncoder(Map<T, Entry<T>> map) {
  70         this.map = map;
  71     }
  72 
  73     /**
  74      * Adds an object to the array.
  75      */
  76     public void addObject(T object) {
  77         if (object == null) {
  78             containsNull = true;
  79             return;
  80         }
  81 
  82         Entry<T> entry = map.get(object);
  83         if (entry == null) {
  84             entry = new Entry<>(object);
  85             map.put(object, entry);
  86         }
  87         entry.frequency++;
  88     }
  89 
  90     /**
  91      * Returns the index of an object in the array. The object must have been
  92      * {@link #addObject(Object) added} before.
  93      */
  94     public int getIndex(Object object) {
  95         if (object == null) {
  96             assert containsNull;
  97             return 0;
  98         }
  99         Entry<T> entry = map.get(object);
 100         assert entry != null && entry.index >= 0;
 101         return entry.index;
 102     }
 103 
 104     /**
 105      * Returns the number of distinct objects that have been added, i.e., the length of the array.
 106      */
 107     public int getLength() {
 108         return map.size() + (containsNull ? 1 : 0);
 109     }
 110 
 111     /**
 112      * Fills the provided array with the added objects. The array must have the {@link #getLength()
 113      * correct length}.
 114      */
 115     public T[] encodeAll(T[] allObjects) {
 116         assert allObjects.length == getLength();
 117         List<Entry<T>> sortedEntries = new ArrayList<>(map.values());
 118         sortedEntries.sort((e1, e2) -> -Integer.compare(e1.frequency, e2.frequency));
 119 
 120         int offset = 0;
 121         if (containsNull) {
 122             allObjects[0] = null;
 123             offset = 1;
 124         }
 125         for (int i = 0; i < sortedEntries.size(); i++) {
 126             Entry<T> entry = sortedEntries.get(i);
 127             int index = i + offset;
 128             entry.index = index;
 129             allObjects[index] = entry.object;
 130             assert entry.object != null;
 131         }
 132         return allObjects;
 133     }
 134 }