1 /*
   2  * Copyright (c) 2015, 2018, 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 
  24 
  25 package org.graalvm.compiler.core.common.util;
  26 
  27 import java.util.ArrayList;
  28 import java.util.List;
  29 
  30 import jdk.internal.vm.compiler.collections.EconomicMap;
  31 import jdk.internal.vm.compiler.collections.Equivalence;
  32 
  33 /**
  34  * Creates an array of T objects order by the occurrence frequency of each object. The most
  35  * frequently used object is the first one, the least frequently used the last one. If {@code null}
  36  * is added, it is always the first element.
  37  *
  38  * Either object {@link #createIdentityEncoder() identity} or object {@link #createEqualityEncoder()
  39  * equality} can be used to build the array and count the frequency.
  40  */
  41 public class FrequencyEncoder<T> {
  42 
  43     static class Entry<T> {
  44         protected final T object;
  45         protected int frequency;
  46         protected int index;
  47 
  48         protected Entry(T object) {
  49             this.object = object;
  50             this.index = -1;
  51         }
  52     }
  53 
  54     protected final EconomicMap<T, Entry<T>> map;
  55     protected boolean containsNull;
  56 
  57     /**
  58      * Creates an encoder that uses object identity.
  59      */
  60     public static <T> FrequencyEncoder<T> createIdentityEncoder() {
  61         return new FrequencyEncoder<>(EconomicMap.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE));
  62     }
  63 
  64     /**
  65      * Creates an encoder that uses {@link Object#equals(Object) object equality}.
  66      */
  67     public static <T> FrequencyEncoder<T> createEqualityEncoder() {
  68         return new FrequencyEncoder<>(EconomicMap.create(Equivalence.DEFAULT));
  69     }
  70 
  71     protected FrequencyEncoder(EconomicMap<T, Entry<T>> map) {
  72         this.map = map;
  73     }
  74 
  75     /**
  76      * Adds an object to the array.
  77      */
  78     public void addObject(T object) {
  79         if (object == null) {
  80             containsNull = true;
  81             return;
  82         }
  83 
  84         Entry<T> entry = map.get(object);
  85         if (entry == null) {
  86             entry = new Entry<>(object);
  87             map.put(object, entry);
  88         }
  89         entry.frequency++;
  90     }
  91 
  92     /**
  93      * Returns the index of an object in the array. The object must have been
  94      * {@link #addObject(Object) added} before.
  95      */
  96     public int getIndex(T object) {
  97         if (object == null) {
  98             assert containsNull;
  99             return 0;
 100         }
 101         Entry<T> entry = map.get(object);
 102         assert entry != null && entry.index >= 0;
 103         return entry.index;
 104     }
 105 
 106     /**
 107      * Returns the number of distinct objects that have been added, i.e., the length of the array.
 108      */
 109     public int getLength() {
 110         return map.size() + (containsNull ? 1 : 0);
 111     }
 112 
 113     /**
 114      * Fills the provided array with the added objects. The array must have the {@link #getLength()
 115      * correct length}.
 116      */
 117     public T[] encodeAll(T[] allObjects) {
 118         assert allObjects.length == getLength();
 119         List<Entry<T>> sortedEntries = new ArrayList<>(allObjects.length);
 120         for (Entry<T> value : map.getValues()) {
 121             sortedEntries.add(value);
 122         }
 123         sortedEntries.sort((e1, e2) -> -Integer.compare(e1.frequency, e2.frequency));
 124 
 125         int offset = 0;
 126         if (containsNull) {
 127             allObjects[0] = null;
 128             offset = 1;
 129         }
 130         for (int i = 0; i < sortedEntries.size(); i++) {
 131             Entry<T> entry = sortedEntries.get(i);
 132             int index = i + offset;
 133             entry.index = index;
 134             allObjects[index] = entry.object;
 135             assert entry.object != null;
 136         }
 137         return allObjects;
 138     }
 139 }