<commit_before>/*
Copyright 2013 Twitter, 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 com.twitter.algebird

/**
 * A QTree provides an approximate Map[Double,A:Monoid] suitable for range queries, quantile queries,
 * and combinations of these (for example, if you use a numeric A, you can derive the inter-quartile mean).
 *
 * It is loosely related to the Q-Digest data structure from http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf,
 * but using an immutable tree structure, and carrying a generalized sum (of type A) at each node instead of just a count.
 *
 * The basic idea is to keep a binary tree, where the root represents the entire range of the input keys,
 * and each child node represents either the lower or upper half of its parent's range. Ranges are constrained to be
 * dyadic intervals (https://en.wikipedia.org/wiki/Interval_(mathematics)#Dyadic_intervals) for ease of merging.
 *
 * To keep the size bounded, the total count carried by any sub-tree must be at least 1/(2^k) of the total
 * count at the root. Any sub-trees that do not meet this criteria have their children pruned and become leaves.
 * (It's important that they not be pruned away entirely, but that we keep a fringe of low-count leaves that can
 * gain weight over time and ultimately split again when warranted).
 *
 * Quantile and range queries both give hard upper and lower bounds; the true result will be somewhere in the range given.
 *
 * Keys must be >= 0.
 */

object QTree {
  val DefaultLevel: Int = -16
  /**
   * level gives a bin size of 2^level. By default the bin size is 1/65536 (level = -16)
   */
  def apply[A](kv: (Double, A), level: Int = DefaultLevel): QTree[A] =
    QTree(math.floor(kv._1 / math.pow(2.0, level)).toLong,
      level,
      1,
      kv._2,
      None,
      None)

  def apply[A](kv: (Long, A)): QTree[A] =
    QTree(kv._1,
      0,
      1,
      kv._2,
      None,
      None)

  /**
   * The common case of wanting an offset and sum for the same value
   * This is useful if you want to query the mean inside a range later.<commit_msg>Small changes for clarity<commit_after>/*
Copyright 2013 Twitter, 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 com.twitter.algebird

/**
 * A QTree provides an approximate Map[Double,A:Monoid] suitable for range queries, quantile queries,
 * and combinations of these (for example, if you use a numeric A, you can derive the inter-quartile mean).
 *
 * It is loosely related to the Q-Digest data structure from http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf,
 * but using an immutable tree structure, and carrying a generalized sum (of type A) at each node instead of just a count.
 *
 * The basic idea is to keep a binary tree, where the root represents the entire range of the input keys,
 * and each child node represents either the lower or upper half of its parent's range. Ranges are constrained to be
 * dyadic intervals (https://en.wikipedia.org/wiki/Interval_(mathematics)#Dyadic_intervals) for ease of merging.
 *
 * To keep the size bounded, the total count carried by any sub-tree must be at least 1/(2^k) of the total
 * count at the root. Any sub-trees that do not meet this criteria have their children pruned and become leaves.
 * (It's important that they not be pruned away entirely, but that we keep a fringe of low-count leaves that can
 * gain weight over time and ultimately split again when warranted).
 *
 * Quantile and range queries both give hard upper and lower bounds; the true result will be somewhere in the range given.
 *
 * Keys must be >= 0.
 */

object QTree {
  val DefaultLevel: Int = -16
  /**
   * level gives a bin size of 2^level. By default the bin size is 1/65536 (level = -16)
   */
  def apply[A](kv: (Double, A), level: Int = DefaultLevel): QTree[A] =
    QTree(offset = math.floor(kv._1 / math.pow(2.0, level)).toLong,
      level = level,
      count = 1,
      sum = kv._2,
      lowerChild = None,
      upperChild = None)

  def apply[A](kv: (Long, A)): QTree[A] =
    QTree(offset = kv._1,
      level = 0,
      count = 1,
      sum = kv._2,
      lowerChild = None,
      upperChild = None)

  /**
   * The common case of wanting an offset and sum for the same value
   * This is useful if you want to query the mean inside a range later.
{'fraction_non_alphanumeric': 0.07957559681697612, 'fraction_numerical': 0.013641530882910194, 'mean_word_length': 3.4138795986622075, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 2, 'lorem ipsum': 0, 'www.': 4, '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': '6438427', 'n_tokens_mistral': 1556, 'n_tokens_neox': 1464, 'n_words': 744}