<commit_before>//! A naive implementation of left-leaning red-black trees
//! that are isomorphic to 2-3 trees. This implementation
//! borrows heavily from https://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
//! and https://github.com/rcatolino/rbtree-rust.
//! Debug assertions borrow heavily from the implementations
//! at http://algs4.cs.princeton.edu/33balanced.

// I have spent a lot of hours trying all possible ways to
// implement this data structure. Most of the attemps
// led to confusing compilation errors. The heart of the
// issue is how to represent the Option<Box<Node>>.

// I tried using the newtype pattern
// https://doc.rust-lang.org/book/structs.html#tuple-structs.
// I (and others) had difficulty writing the
// destructuring lets correctly. See
// https://www.reddit.com/r/rust/comments/2cmjfn/how_to_do_typedefsnewtypes

// I tried creating a struct with a single field
// but had trouble accessing the field correctly
// ("let", "let ref", "let mut", "let ref mut").
// In addition the dummy field obfuscated the implementation.

// I tried using a type alias but then it's not
// possible to implement Display and Debug.

// Eventually I settled on using no abstraction for
// Option<Box<Node>>. The implementation became
// much easier to write.

// Also the implementation became much easier after I
// saw from rcatolino that some methods should be defined
// on a trait that wraps Box<Node> and other method
// should be defined on a trait that wraps Option<Box<Node>>.

use std::cmp::Ordering;
use std::fmt;
use std::mem;

#[derive(PartialEq, Eq, Copy, Clone)]
enum Color {
    Red,
    Black,
}

// This instance of the newtype pattern
// https://doc.rust-lang.org/book/structs.html#tuple-structs
// is used only for fmt::Display and fmt::Debug.
struct Link<'a>(&'a Option<Box<Node>>);

pub struct LLRBTree {
    root: Option<Box<Node>>,
}

struct Node {
    key: i32,
    val: i32,
    color: Color,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl LLRBTree {
    pub fn new() -> Self {
        LLRBTree { root: None }
    }

    pub fn get(&self, key: i32) -> Option<i32> {
        self.root.get(key)
    }

    pub fn insert(&mut self, key: i32, value: i32) -> Option<i32> {
        let prev = self.root.insert(key, value);
        self.root.set_color(Color::Black);
        debug_assert!(self.check());
        prev
    }

    pub fn remove_min(&mut self) -> Option<i32> {
        if self.root.is_none() {
            None
        } else {
            if !self.root.left().is_red() && !self.root.right().is_red() {
                self.root.set_color(Color::Red);
            }
            let min = self.root.remove_min();
            if self.root.is_some() {
                self.root.set_color(Color::Black);
            }
            debug_assert!(self.check());
            min
        }
    }

    fn is_bst(&self) -> bool {
        self.root.is_bst(None, None)
    }

    fn is_23(&self) -> bool {
        self.root.is_23(true)
    }

    fn is_balanced(&self) -> bool {
        let mut black = 0;
        let mut next = &self.root;
        loop {
            match next {
                &None => break,
                &Some(ref node) => {
                    if !node.is_red() {
                        black += 1;
                    }
                    next = &node.left;
                }
            }
        }
        self.root.is_balanced(black)
    }

    fn check(&self) -> bool {
        debug_assert!(self.is_bst(), "Not a binary search tree");
        debug_assert!(self.is_23(), "Not a 2-3 tree");
        debug_assert!(self.is_balanced(), "Not balanced");
        true
    }
}

impl fmt::Display for LLRBTree {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", Link(&self.root))
    }
}

impl fmt::Debug for LLRBTree {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?}", Link(&self.root))
    }
}

impl Node {
    fn new(key: i32, val: i32) -> Self {
        Node {
            key: key,
            val: val,
            color: Color::Red,
            left: None,
            right: None,
        }
    }
}

trait BoxNode {
    fn is_red(&self) -> bool;
    fn left_rotate(&mut self);
    fn right_rotate(&mut self);
    fn flip_colors(&mut self);
    fn move_red_to_left(&mut self);
    fn move_red_to_right(&mut self);
    fn post_insert_balance(&mut self);
    fn post_remove_balance(&mut self);
}

impl BoxNode for Box<Node> {
    fn is_red(&self) -> bool {
        self.color == Color::Red
    }

    fn left_rotate(&mut self) {
        debug_assert!(self.right.is_red());
        let mut child = self.right.take().unwrap();
        mem::swap(self, &mut child);
        mem::swap(&mut child.right, &mut self.left);
        self.color = child.color;
        child.color = Color::Red;
        self.left = Some(child);
    }

    fn right_rotate(&mut self) {
        debug_assert!(self.left.is_red());
        let mut child = self.left.take().unwrap();
        mem::swap(self, &mut child);
        mem::swap(&mut child.left, &mut self.right);
        self.color = child.color;
        child.color = Color::Red;
        self.right = Some(child);
    }

    fn flip_colors(&mut self) {
        debug_assert!(self.left.is_some());<commit_msg>Remove unnecessary trait.<commit_after>//! A naive implementation of left-leaning red-black trees
//! that are isomorphic to 2-3 trees. This implementation
//! borrows heavily from https://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
//! and https://github.com/rcatolino/rbtree-rust.
//! Debug assertions borrow heavily from the implementations
//! at http://algs4.cs.princeton.edu/33balanced.

// I have spent a lot of hours trying all possible ways to
// implement this data structure. Most of the attemps
// led to confusing compilation errors. The heart of the
// issue is how to represent the Option<Box<Node>>.

// I tried using the newtype pattern
// https://doc.rust-lang.org/book/structs.html#tuple-structs.
// I (and others) had difficulty writing the
// destructuring lets correctly. See
// https://www.reddit.com/r/rust/comments/2cmjfn/how_to_do_typedefsnewtypes

// I tried creating a struct with a single field
// but had trouble accessing the field correctly
// ("let", "let ref", "let mut", "let ref mut").
// In addition the dummy field obfuscated the implementation.

// I tried using a type alias but then it's not
// possible to implement Display and Debug.

// Eventually I settled on using no abstraction for
// Option<Box<Node>>. The implementation became
// much easier to write.

// Also the implementation became much easier after I
// saw from rcatolino that some methods should be defined
// on a trait that wraps Box<Node> and other method
// should be defined on a trait that wraps Option<Box<Node>>.

use std::cmp::Ordering;
use std::fmt;
use std::mem;

#[derive(PartialEq, Eq, Copy, Clone)]
enum Color {
    Red,
    Black,
}

// This instance of the newtype pattern
// https://doc.rust-lang.org/book/structs.html#tuple-structs
// is used only for fmt::Display and fmt::Debug.
struct Link<'a>(&'a Option<Box<Node>>);

pub struct LLRBTree {
    root: Option<Box<Node>>,
}

struct Node {
    key: i32,
    val: i32,
    color: Color,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl LLRBTree {
    pub fn new() -> Self {
        LLRBTree { root: None }
    }

    pub fn get(&self, key: i32) -> Option<i32> {
        self.root.get(key)
    }

    pub fn insert(&mut self, key: i32, value: i32) -> Option<i32> {
        let prev = self.root.insert(key, value);
        self.root.set_color(Color::Black);
        debug_assert!(self.check());
        prev
    }

    pub fn remove_min(&mut self) -> Option<i32> {
        if self.root.is_none() {
            None
        } else {
            if !self.root.left().is_red() && !self.root.right().is_red() {
                self.root.set_color(Color::Red);
            }
            let min = self.root.remove_min();
            if self.root.is_some() {
                self.root.set_color(Color::Black);
            }
            debug_assert!(self.check());
            min
        }
    }

    fn is_bst(&self) -> bool {
        self.root.is_bst(None, None)
    }

    fn is_23(&self) -> bool {
        self.root.is_23(true)
    }

    fn is_balanced(&self) -> bool {
        let mut black = 0;
        let mut next = &self.root;
        loop {
            match next {
                &None => break,
                &Some(ref node) => {
                    if !node.is_red() {
                        black += 1;
                    }
                    next = &node.left;
                }
            }
        }
        self.root.is_balanced(black)
    }

    fn check(&self) -> bool {
        debug_assert!(self.is_bst(), "Not a binary search tree");
        debug_assert!(self.is_23(), "Not a 2-3 tree");
        debug_assert!(self.is_balanced(), "Not balanced");
        true
    }
}

impl fmt::Display for LLRBTree {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", Link(&self.root))
    }
}

impl fmt::Debug for LLRBTree {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?}", Link(&self.root))
    }
}

impl Node {
    fn new(key: i32, val: i32) -> Self {
        Node {
            key: key,
            val: val,
            color: Color::Red,
            left: None,
            right: None,
        }
    }
}

impl Node {
    fn is_red(&self) -> bool {
        self.color == Color::Red
    }

    fn left_rotate(&mut self) {
        debug_assert!(self.right.is_red());
        let mut child = self.right.take().unwrap();
        mem::swap(self, &mut child);
        mem::swap(&mut child.right, &mut self.left);
        self.color = child.color;
        child.color = Color::Red;
        self.left = Some(child);
    }

    fn right_rotate(&mut self) {
        debug_assert!(self.left.is_red());
        let mut child = self.left.take().unwrap();
        mem::swap(self, &mut child);
        mem::swap(&mut child.left, &mut self.right);
        self.color = child.color;
        child.color = Color::Red;
        self.right = Some(child);
    }

    fn flip_colors(&mut self) {
        debug_assert!(self.left.is_some());
{'fraction_non_alphanumeric': 0.1398309202215528, 'fraction_numerical': 0.006996404625400836, 'mean_word_length': 2.144515734799878, 'pattern_counts': {'":': 0, '<': 42, '<?xml version=': 0, '>': 71, 'https://': 10, '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': '3175957', 'n_tokens_mistral': 3305, 'n_tokens_neox': 3207, 'n_words': 897}