iotdb-core/datanode/src/main/java/org/apache/iotdb/db/utils/datastructure/TimSort.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you 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.apache.iotdb.db.utils.datastructure;

/**
 * The interface refers to TimSort.java, and is used for sort the TVList Functions for tim_sort like
 * merge, sort, binary_sort is implemented here as default, reuse code whenever possible.
 */
public interface TimSort {
  /** when array size <= 32, it's better to use binarysort. */
  int SMALL_ARRAY_LENGTH = 32;

  /** the same as the 'set' function in TVList, the reason is to avoid two equal functions. */
  void tim_set(int src, int dest);

  void setFromSorted(int src, int dest);

  void setToSorted(int src, int dest);

  void setPivotTo(int pos);

  void saveAsPivot(int pos);

  /**
   * The arrays for sorting are not including in write memory now, the memory usage is considered as
   * temporary memory.
   */
  void clearSortedTime();

  void clearSortedValue();

  /** compare the timestamps in idx1 and idx2 */
  int compare(int idx1, int idx2);

  /** From TimSort.java */
  void reverseRange(int lo, int hi);

  /**
   * the entrance of tim_sort; 1. array_size <= 32, use binary sort. 2. recursively invoke merge
   * sort.
   */
  default void sort(int lo, int hi) {
    if (lo == hi) {
      return;
    }
    if (hi - lo <= SMALL_ARRAY_LENGTH) {
      int initRunLen = countRunAndMakeAscending(lo, hi);
      binarySort(lo, hi, lo + initRunLen);
      return;
    }
    int mid = (lo + hi) >>> 1;
    sort(lo, mid);
    sort(mid, hi);
    merge(lo, mid, hi);
  }

  default int countRunAndMakeAscending(int lo, int hi) {
    assert lo < hi;
    int runHi = lo + 1;
    if (runHi == hi) {
      return 1;
    }
    // Find end of run, and reverse range if descending
    if (compare(runHi++, lo) == -1) { // Descending
      while (runHi < hi && compare(runHi, runHi - 1) == -1) {
        runHi++;
      }
      reverseRange(lo, runHi);
    } else { // Ascending
      while (runHi < hi && compare(runHi, runHi - 1) >= 0) {
        runHi++;
      }
    }

    return runHi - lo;
  }

  default void binarySort(int lo, int hi, int start) {
    assert lo <= start && start <= hi;
    if (start == lo) {
      start++;
    }
    for (; start < hi; start++) {

      saveAsPivot(start);
      // Set left (and right) to the index where a[start] (pivot) belongs
      int left = lo;
      int right = start;
      assert left <= right;
      /*
       * Invariants:
       *   pivot >= all in [lo, left).
       *   pivot <  all in [right, start).
       */
      while (left < right) {
        int mid = (left + right) >>> 1;
        if (compare(start, mid) < 0) {
          right = mid;
        } else {
          left = mid + 1;
        }
      }
      assert left == right;

      /*
       * The invariants still hold: pivot >= all in [lo, left) and
       * pivot < all in [left, start), so pivot belongs at left.  Note
       * that if there are elements equal to pivot, left points to the
       * first slot after them -- that's why this sort is stable.
       * Slide elements over to make room for pivot.
       */
      int n = start - left; // The number of elements to move
      for (int i = n; i >= 1; i--) {
        tim_set(left + i - 1, left + i);
      }
      setPivotTo(left);
    }
    for (int i = lo; i < hi; i++) {
      setToSorted(i, i);
    }
  }

  /** merge arrays [lo, mid) [mid, hi] */
  default void merge(int lo, int mid, int hi) {
    // end of sorting buffer
    int tmpIdx = 0;

    // start of unmerged parts of each sequence
    int leftIdx = lo;
    int rightIdx = mid;

    // copy the minimum elements to sorting buffer until one sequence is exhausted
    int endSide = 0;
    while (endSide == 0) {
      if (compare(leftIdx, rightIdx) <= 0) {
        setToSorted(leftIdx, lo + tmpIdx);
        tmpIdx++;
        leftIdx++;
        if (leftIdx == mid) {
          endSide = 1;
        }
      } else {
        setToSorted(rightIdx, lo + tmpIdx);
        tmpIdx++;
        rightIdx++;
        if (rightIdx == hi) {
          endSide = 2;
        }
      }
    }

    // copy the remaining elements of another sequence
    int start;
    int end;
    if (endSide == 1) {
      start = rightIdx;
      end = hi;
    } else {
      start = leftIdx;
      end = mid;
    }
    for (; start < end; start++) {
      setToSorted(start, lo + tmpIdx);
      tmpIdx++;
    }

    // copy from sorting buffer to the original arrays so that they can be further sorted
    // potential speed up: change the place of sorting buffer and origin data between merge
    // iterations
    for (int i = lo; i < hi; i++) {
      setFromSorted(i, i);
    }
  }
}