Package org.apache.druid.frame.processor

Class TournamentTree

java.lang.Object
org.apache.druid.frame.processor.TournamentTree
public class TournamentTree extends Object
Tree-of-losers tournament tree used for K-way merging. The tree contains a fixed set of elements, from 0 (inclusive) to numElements (exclusive). The tree represents a tournament played amongst the elements. At all times each node of the tree contains the loser of the match at that node. The winners of the matches are not explicitly stored, except for the overall winner of the tournament, which is stored in tree[0]. When used as part of k-way merge, expected usage is call getMin() to retrieve a run number, then read an element from the run. On the next call to getMin(), the tree internally calls update() to handle the case where the min needs to change. Refer to https://en.wikipedia.org/wiki/K-way_merge_algorithm#Tournament_Tree for additional details.

  • Constructor Summary

    Constructors
    Constructor
    Description
    TournamentTree(int numElements, it.unimi.dsi.fastutil.ints.IntComparator comparator)
    Creates a tree with a certain number of elements.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    getMin()
    Get the current minimum element (the overall winner, i.e., the run to pull the next element from in the K-way merge).
    String
    toString()
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • TournamentTree

      public TournamentTree(int numElements, it.unimi.dsi.fastutil.ints.IntComparator comparator)
      Creates a tree with a certain number of elements.
      Parameters:
      numElements - number of elements in the tree
      comparator - comparator for the elements. Smaller elements "win".

  • Method Details

    • getMin

      public int getMin()
      Get the current minimum element (the overall winner, i.e., the run to pull the next element from in the K-way merge).

    • toString

      public String toString()
      Overrides:
      toString in class Object