<commit_before>package ru.ifmo.util;

/**
 * This is an implementation of the rank query structure using a tailored version of the Red-Black Tree
 * from the Scala collection library.
 *
 * @author <NAME>
 * @author <NAME>
 */
public class RedBlackRankQueryStructure extends RankQueryStructure {
    private boolean initialized = false;
    private final Node[] allNodes;
    private Node root;
    private int size;

    public RedBlackRankQueryStructure(int maximumPoints) {
        allNodes = new Node[maximumPoints];
        root = null;
        size = 0;
    }

    @Override
    public void addPossibleKey(double key) {}

    @Override
    public void init() {
        initialized = true;
    }

    @Override
    public void put(double key, int value) {
        Node place = maxNodeBeforeExact(root, key);
        if (place == null || place.value < value) {
            if (place == null) {
                if (root != null) {
                    place = minNodeNonNull(root);
                }
            } else if (place.key != key) {
                place = successor(place);
            }
            while (place != null && place.value <= value) {
                Node next = successor(place);
                delete(place);
                place = next;
            }
            insert(key, value);
        }
    }

    @Override
    public int getMaximumWithKeyAtMost(double key) {
        Node q = maxNodeBeforeExact(root, key);<commit_msg>Slightly improve RedBlackRQS.put: may speed up if many equal Ys.<commit_after>package ru.ifmo.util;

/**
 * This is an implementation of the rank query structure using a tailored version of the Red-Black Tree
 * from the Scala collection library.
 *
 * @author <NAME>
 * @author <NAME>
 */
public class RedBlackRankQueryStructure extends RankQueryStructure {
    private boolean initialized = false;
    private final Node[] allNodes;
    private Node root;
    private int size;

    public RedBlackRankQueryStructure(int maximumPoints) {
        allNodes = new Node[maximumPoints];
        root = null;
        size = 0;
    }

    @Override
    public void addPossibleKey(double key) {}

    @Override
    public void init() {
        initialized = true;
    }

    @Override
    public void put(double key, int value) {
        Node place = maxNodeBeforeExact(root, key);
        if (place == null || place.value < value) {
            Node insertionHint = null;
            if (place == null) {
                if (root != null) {
                    place = minNodeNonNull(root);
                }
            } else {
                if (place.key == key) {
                    insertionHint = place;
                }
                place = successor(place);
            }
            while (place != null && place.value <= value) {
                Node next = successor(place);
                delete(place);
                place = next;
            }
            if (insertionHint == null) {
                insert(key, value);
            } else {
                insertionHint.value = Math.max(insertionHint.value, value);
            }
        }
    }

    @Override
    public int getMaximumWithKeyAtMost(double key) {
        Node q = maxNodeBeforeExact(root, key);
{'fraction_non_alphanumeric': 0.09231244211176289, 'fraction_numerical': 0.0006174745291756715, 'mean_word_length': 1.7906976744186047, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, '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': '6963075', 'n_tokens_mistral': 875, 'n_tokens_neox': 832, 'n_words': 260}