<commit_before>/*
 * Copyright 2015 Terracotta, Inc..
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.terracotta.statistics.derived.histogram;

import static java.lang.Long.MIN_VALUE;
import static java.lang.Long.numberOfLeadingZeros;
import static java.lang.Math.max;
import static java.lang.System.arraycopy;
import static java.util.Arrays.copyOf;
import static java.util.Arrays.fill;

public class ExponentialHistogram {
  
  /*
   * TODO: The original paper on this data structure doesn't (by my reading) say
   * anything about different merge thresholds for the 1-size boxes.  Need to
   * figure out if this is an error in the BASH/BSBH paper, or is an important
   * correction from the EH one.
   */
  private static final long[] EMPTY_LONG_ARRAY = new long[0];
  
  private final int mergeThreshold;
  private final long window;
  
  private long[] boxes;
  private int[] insert;
  
  private long total;
  private long last;

  public ExponentialHistogram(float epsilon, long window) {
    this((int) (Math.ceil(Math.ceil(1 / epsilon) / 2) + 1), window, 0);
  }
  
  private ExponentialHistogram(int mergeThreshold, long window, int initialSize) {
    this.mergeThreshold = mergeThreshold;
    this.window = window;
    initializeArrays(initialSize);
  }
  
  public void merge(ExponentialHistogram b) {
    long[] aBoxes = this.boxes;
    long[] bBoxes = b.boxes;

    int logLast = (Long.SIZE - 1) - numberOfLeadingZeros(last | b.last);
    initializeArrays(logLast);
    this.total += b.total;
    
    long[] overflow = EMPTY_LONG_ARRAY;
    for (int logSize = 0; logSize <= logLast; logSize++) {
      overflow = insert(logSize, aBoxes, bBoxes, overflow);
    }
    int logSize = logLast + 1;
    while (overflow.length > 0) {
      ensureCapacity(logSize);
      overflow = insert(logSize, overflow);
      logSize++;
    }
    last = 1L << (logSize - 1);
  }

  private long[] insert(int logSize, long[] values) {
    int min = min_l(logSize);
    int max = max_l(logSize);
    int width = max - min;
    int overflowSize = max(0, ((values.length - width) + 1) & -2);
    int savedSize = values.length - overflowSize;

    arraycopy(values, 0, boxes, max - savedSize, savedSize);
    insert[logSize] = max - ((savedSize % width) + 1);

    if (overflowSize == 0) {
      return EMPTY_LONG_ARRAY;
    } else {
      long[] overflow = new long[overflowSize >>> 1];
      for (int j = 0; j < overflow.length; j++) {
        overflow[j] = values[savedSize + (2 * j)];
      }
      return overflow;
    }
  }

  private long[] insert(int logSize, long[] a, long[] b, long[] carry) {
    int min = min_l(logSize);
    int max = max_l(logSize);
    long[] merged = reverseSort(merge(a, b, min, max, carry));
    int mergedEnd = usedLength(merged);
    int width = max - min;
    int overflowSize = max(0, ((mergedEnd - width) + 1) & -2);
    int savedSize = mergedEnd - overflowSize;
    
    arraycopy(merged, 0, boxes, max - savedSize, savedSize);
    insert[logSize] = max - ((savedSize % width) + 1);

    if (overflowSize == 0) {
      return EMPTY_LONG_ARRAY;
    } else {
      long[] overflow = new long[overflowSize >>> 1];
      for (int j = 0; j < overflow.length; j++) {
        overflow[j] = merged[savedSize + (2 * j)];
      }

      return overflow;
    }
  }

  private static long[] merge(long[] a, long[] b, int min, int max, long[] c) {
    if (max <= a.length) {
      if (max <= b.length) {
    	int width = max - min;
        long[] merged = copyOf(c, c.length + 2 * width);
        arraycopy(a, min, merged, c.length, width);
        arraycopy(b, min, merged, c.length + width, width);
        return merged;
      } else {
        return merge(a, min, max, c);
      }
    } else {
      return merge(b, min, max, c);
    }
  }

  private static long[] merge(long[] a, int min, int max, long[] c) {
    int width = max - min;
    long[] merged = copyOf(c, c.length + width);
    arraycopy(a, min, merged, c.length, width);
    return merged;
  }
  
  public void insert(long time) {
    insert_l(0, time);
  }

  private void insert_l(int initialLogSize, long time) {
    long threshold = time - window;
    total += (1 << initialLogSize);
    for (int logSize = initialLogSize; ; logSize++) {
      ensureCapacity(logSize);
      
      int insertIndex = insert[logSize];
      long previous = boxes[insertIndex];
      boxes[insertIndex--] = time;
      if (insertIndex < min_l(logSize)) {
        insertIndex = max_l(logSize) - 1;
      }
      insert[logSize] = insertIndex;
      
      if (previous <= threshold) {
        if (previous == MIN_VALUE) {
          long finalSize = 1L << logSize;
          if (finalSize > last) {
            last = finalSize;
          }
        } else {
          total -= 1 << logSize;
        }
        return;
      } else {
        //no space available - time to merge
        time = boxes[insertIndex];
        boxes[insertIndex] = MIN_VALUE;
      }
    }
  }
  <commit_msg>reshuffle insert conditionals to optimize common paths<commit_after>/*
 * Copyright 2015 Terracotta, Inc..
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.terracotta.statistics.derived.histogram;

import static java.lang.Long.MIN_VALUE;
import static java.lang.Long.numberOfLeadingZeros;
import static java.lang.Math.max;
import static java.lang.System.arraycopy;
import static java.util.Arrays.copyOf;
import static java.util.Arrays.fill;

public class ExponentialHistogram {
  
  /*
   * TODO: The original paper on this data structure doesn't (by my reading) say
   * anything about different merge thresholds for the 1-size boxes.  Need to
   * figure out if this is an error in the BASH/BSBH paper, or is an important
   * correction from the EH one.
   */
  private static final long[] EMPTY_LONG_ARRAY = new long[0];
  
  private final int mergeThreshold;
  private final long window;
  
  private long[] boxes;
  private int[] insert;
  
  private long total;
  private long last;

  public ExponentialHistogram(float epsilon, long window) {
    this((int) (Math.ceil(Math.ceil(1 / epsilon) / 2) + 1), window, 0);
  }
  
  private ExponentialHistogram(int mergeThreshold, long window, int initialSize) {
    this.mergeThreshold = mergeThreshold;
    this.window = window;
    initializeArrays(initialSize);
  }
  
  public void merge(ExponentialHistogram b) {
    long[] aBoxes = this.boxes;
    long[] bBoxes = b.boxes;

    int logLast = (Long.SIZE - 1) - numberOfLeadingZeros(last | b.last);
    initializeArrays(logLast);
    this.total += b.total;
    
    long[] overflow = EMPTY_LONG_ARRAY;
    for (int logSize = 0; logSize <= logLast; logSize++) {
      overflow = insert(logSize, aBoxes, bBoxes, overflow);
    }
    int logSize = logLast + 1;
    while (overflow.length > 0) {
      ensureCapacity(logSize);
      overflow = insert(logSize, overflow);
      logSize++;
    }
    last = 1L << (logSize - 1);
  }

  private long[] insert(int logSize, long[] values) {
    int min = min_l(logSize);
    int max = max_l(logSize);
    int width = max - min;
    int overflowSize = max(0, ((values.length - width) + 1) & -2);
    int savedSize = values.length - overflowSize;

    arraycopy(values, 0, boxes, max - savedSize, savedSize);
    insert[logSize] = max - ((savedSize % width) + 1);

    if (overflowSize == 0) {
      return EMPTY_LONG_ARRAY;
    } else {
      long[] overflow = new long[overflowSize >>> 1];
      for (int j = 0; j < overflow.length; j++) {
        overflow[j] = values[savedSize + (2 * j)];
      }
      return overflow;
    }
  }

  private long[] insert(int logSize, long[] a, long[] b, long[] carry) {
    int min = min_l(logSize);
    int max = max_l(logSize);
    long[] merged = reverseSort(merge(a, b, min, max, carry));
    int mergedEnd = usedLength(merged);
    int width = max - min;
    int overflowSize = max(0, ((mergedEnd - width) + 1) & -2);
    int savedSize = mergedEnd - overflowSize;
    
    arraycopy(merged, 0, boxes, max - savedSize, savedSize);
    insert[logSize] = max - ((savedSize % width) + 1);

    if (overflowSize == 0) {
      return EMPTY_LONG_ARRAY;
    } else {
      long[] overflow = new long[overflowSize >>> 1];
      for (int j = 0; j < overflow.length; j++) {
        overflow[j] = merged[savedSize + (2 * j)];
      }

      return overflow;
    }
  }

  private static long[] merge(long[] a, long[] b, int min, int max, long[] c) {
    if (max <= a.length) {
      if (max <= b.length) {
    	int width = max - min;
        long[] merged = copyOf(c, c.length + 2 * width);
        arraycopy(a, min, merged, c.length, width);
        arraycopy(b, min, merged, c.length + width, width);
        return merged;
      } else {
        return merge(a, min, max, c);
      }
    } else {
      return merge(b, min, max, c);
    }
  }

  private static long[] merge(long[] a, int min, int max, long[] c) {
    int width = max - min;
    long[] merged = copyOf(c, c.length + width);
    arraycopy(a, min, merged, c.length, width);
    return merged;
  }
  
  public void insert(long time) {
    insert_l(0, time);
  }

  private void insert_l(int initialLogSize, long time) {
    long threshold = time - window;
    total += (1 << initialLogSize);
    for (int logSize = initialLogSize; ; logSize++) {
      ensureCapacity(logSize);
      
      int insertIndex = insert[logSize];
      long previous = boxes[insertIndex];
      boxes[insertIndex--] = time;
      if (insertIndex < min_l(logSize)) {
        insertIndex = max_l(logSize) - 1;
      }
      insert[logSize] = insertIndex;
      
      if (previous > threshold) {
        //no space available - time to merge
        time = boxes[insertIndex];
        boxes[insertIndex] = MIN_VALUE;
      } else if (previous == MIN_VALUE) {
        //previous unoccupied
        long finalSize = 1L << logSize;
        if (finalSize > last) {
          last = finalSize;
        }
        return;
      } else {
        //previous aged out - decrement size
        total -= 1 << logSize;
        return;
      }
    }
  }
  
{'fraction_non_alphanumeric': 0.12028920018075011, 'fraction_numerical': 0.007953004970628107, 'mean_word_length': 2.6413293846660086, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 20, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6544896', 'n_tokens_mistral': 3523, 'n_tokens_neox': 3424, 'n_words': 1098}