<commit_before>// Many of my decisions were based off the following document
// https://web.archive.org/web/20140727185616/http://algs4.cs.princeton.edu/33balanced/


// TODO:
// Collection trait
// convert this to Key/Value K/V

use std::cmp::Ord;
use std::option::{None, Option, Some};


/// Four
enum Four<V: Ord> {
    InternalFour(V, V, V, Box<Node<V>>, Box<Node<V>>, Box<Node<V>>, Box<Node<V>>),
    LeafFour(V, V, V),
}

impl <V: Ord> Four<V> {
    fn to_two(self) -> Two<V> {
        match self {
            LeafFour(v1, v2, v3) =>
                Two(v2,
                    box LeafTwoNode(LeafTwo(v1)),
                    box LeafTwoNode(LeafTwo(v3))),
            InternalFour(v1, v2, v3, n1, n2, n3, n4) =>
                Two(v2,
                    box TwoNode(Two(v1, n1, n2)),
                    box TwoNode(Two(v3, n3, n4))),
        }
    }
}


/// InsertResult
enum InsertResult<V: Ord> {
    Fit(Node<V>),
    Split(Four<V>),
}


/// Direction
enum Direction {
    Left,
    Middle,
    Right,
    Leaf,
}


/// Two
pub struct Two<V: Ord>(pub V, pub Box<Node<V>>, pub Box<Node<V>>);

impl <V: Ord> Two<V> {
    fn to_node(self) -> Node<V> { TwoNode(self) }

    fn to_three(self, other_value: V, other_node: Box<Node<V>>) -> Three<V> {
        let Two(self_value, self_left, self_middle) = self;
        if self_value > other_value {
            Three(other_value, self_value, other_node, self_left, self_middle)
        } else {
            Three(self_value, other_value, self_left, self_middle, other_node)
        }
    }
}


/// Three
pub struct Three<V: Ord>(pub V, pub V, pub Box<Node<V>>, pub Box<Node<V>>, pub Box<Node<V>>);

impl <V: Ord> Three<V> {
    fn to_node(self) -> Node<V> { ThreeNode(self) }

    fn to_four(self, other_value: V, other_node: Box<Node<V>>) -> Four<V> {
        let Three(self_value1, self_value2, self_left, self_middle, self_right) = self;
        if other_value < self_value1 {
            InternalFour(other_value, self_value1, self_value2, other_node, self_left, self_middle, self_right)
        } else {
            InternalFour(self_value1, self_value2, other_value, self_left, self_middle, self_right, other_node)
        }
    }
}


/// LeafTwo
pub struct LeafTwo<V: Ord>(pub V);


/// LeafThree
pub struct LeafThree<V: Ord>(pub V, pub V);

impl <V: Ord> LeafThree<V> {
    fn to_four(self, value: V) -> Four<V> {
        let LeafThree(value1, value2) = self;
        if value > value2      { LeafFour(value1, value2, value) }
        else if value < value1 { LeafFour(value, value1, value2) }
        else                   { LeafFour(value1, value, value2) }
    }
}


/// Node
pub enum Node<V: Ord> {
    LeafTwoNode(LeafTwo<V>),
    LeafThreeNode(LeafThree<V>),
    TwoNode(Two<V>),
    ThreeNode(Three<V>),
}


impl <V: Ord> Node<V> {
    fn next_direction(&self, to_insert: &V) -> Direction {
        match self {
            &TwoNode(Two(ref value, _, _)) =>
                if to_insert < value { Left }
                else                 { Middle },
            &ThreeNode(Three(ref value1, ref value2, _, _, _)) =>
                if      to_insert < value1 { Left }
                else if to_insert > value2 { Right }
                else                       { Middle },
            _ => Leaf,
        }
    }

    fn contains_node(&self, to_check: &V) -> bool {
        match self {
            &TwoNode(Two(ref v, _, _)) |
                &LeafTwoNode(LeafTwo(ref v)) if to_check == v => true,

            &ThreeNode(Three(ref v1, ref v2, _, _, _)) |
                &LeafThreeNode(LeafThree(ref v1, ref v2)) if to_check == v1 || to_check == v2 => true,

            _ => false
        }
    }

    fn insert(self, to_insert: V) -> InsertResult<V> {
        // If value is already in this node, we're done (prevent duplicates)
        if self.contains_node(&to_insert) { return Fit(self); }

        let next_direction = self.next_direction(&to_insert);

        match self {
            // Insert if leaf TwoNode
            LeafTwoNode(LeafTwo(value)) => {
                let (smaller, larger) =
                    if value < to_insert { (value, to_insert) }
                    else                 { (to_insert, value) };
                let new_node = LeafThreeNode(LeafThree(smaller, larger));
                Fit(new_node)
            },

            // Split if leaf ThreeNode
            LeafThreeNode(leaf_three) => {
                let four_node = leaf_three.to_four(to_insert);
                Split(four_node)
            },

            // Recurse down if internal Node and handle results
            TwoNode(Two(value, box left, box middle)) => {

                // Determine which node we'll recurse next
                let (next_node, other_node) = match next_direction {
                    Left => (left, middle),
                    Middle => (middle, left),
                    _ => panic!(""),
                };

                // Recurse, save the result of the insert
                let insert_result = next_node.insert(to_insert);

                // Handle the result of the insert
                let new_node = match insert_result {
                    Fit(returned_node) =>
                        match next_direction {
                            Left =>   Two(value, box returned_node, box other_node),
                            Middle => Two(value, box other_node, box returned_node),
                            _ => panic!(""),<commit_msg>Move more logic to struct methods<commit_after>// Many of my decisions were based off the following document
// https://web.archive.org/web/20140727185616/http://algs4.cs.princeton.edu/33balanced/


// TODO:
// Collection trait
// convert this to Key/Value K/V

use std::cmp::Ord;
use std::option::{None, Option, Some};


/// Four
enum Four<V: Ord> {
    InternalFour(V, V, V, Box<Node<V>>, Box<Node<V>>, Box<Node<V>>, Box<Node<V>>),
    LeafFour(V, V, V),
}

impl <V: Ord> Four<V> {
    fn to_two(self) -> Two<V> {
        match self {
            LeafFour(v1, v2, v3) =>
                Two(v2,
                    box LeafTwoNode(LeafTwo(v1)),
                    box LeafTwoNode(LeafTwo(v3))),
            InternalFour(v1, v2, v3, n1, n2, n3, n4) =>
                Two(v2,
                    box TwoNode(Two(v1, n1, n2)),
                    box TwoNode(Two(v3, n3, n4))),
        }
    }
}


/// InsertResult
enum InsertResult<V: Ord> {
    Fit(Node<V>),
    Split(Four<V>),
}


/// Direction
enum Direction {
    Left,
    Middle,
    Right,
    Leaf,
}


/// Two
pub struct Two<V: Ord>(pub V, pub Box<Node<V>>, pub Box<Node<V>>);

impl <V: Ord> Two<V> {
    fn to_node(self) -> Node<V> { TwoNode(self) }

    fn to_three(self, other_value: V, other_node: Box<Node<V>>) -> Three<V> {
        let Two(self_value, self_left, self_middle) = self;
        if self_value > other_value {
            Three(other_value, self_value, other_node, self_left, self_middle)
        } else {
            Three(self_value, other_value, self_left, self_middle, other_node)
        }
    }
}


/// Three
pub struct Three<V: Ord>(pub V, pub V, pub Box<Node<V>>, pub Box<Node<V>>, pub Box<Node<V>>);

impl <V: Ord> Three<V> {
    fn to_node(self) -> Node<V> { ThreeNode(self) }

    fn to_four(self, other_value: V, other_node: Box<Node<V>>) -> Four<V> {
        let Three(self_value1, self_value2, self_left, self_middle, self_right) = self;
        if other_value < self_value1 {
            InternalFour(other_value, self_value1, self_value2, other_node, self_left, self_middle, self_right)
        } else {
            InternalFour(self_value1, self_value2, other_value, self_left, self_middle, self_right, other_node)
        }
    }
}


/// LeafTwo
pub struct LeafTwo<V: Ord>(pub V);

impl <V: Ord> LeafTwo<V> {
    fn to_three(self, other_value: V) -> LeafThree<V> {
        let LeafTwo(self_value) = self;
        if self_value > other_value {
            LeafThree(other_value, self_value)
        } else {
            LeafThree(self_value, other_value)
        }
    }
}


/// LeafThree
pub struct LeafThree<V: Ord>(pub V, pub V);

impl <V: Ord> LeafThree<V> {
    fn to_node(self) -> Node<V> { LeafThreeNode(self) }

    fn to_four(self, value: V) -> Four<V> {
        let LeafThree(value1, value2) = self;
        if value > value2      { LeafFour(value1, value2, value) }
        else if value < value1 { LeafFour(value, value1, value2) }
        else                   { LeafFour(value1, value, value2) }
    }
}


/// Node
pub enum Node<V: Ord> {
    LeafTwoNode(LeafTwo<V>),
    LeafThreeNode(LeafThree<V>),
    TwoNode(Two<V>),
    ThreeNode(Three<V>),
}


impl <V: Ord> Node<V> {
    fn next_direction(&self, to_insert: &V) -> Direction {
        match self {
            &TwoNode(Two(ref value, _, _)) =>
                if to_insert < value { Left }
                else                 { Middle },
            &ThreeNode(Three(ref value1, ref value2, _, _, _)) =>
                if      to_insert < value1 { Left }
                else if to_insert > value2 { Right }
                else                       { Middle },
            _ => Leaf,
        }
    }

    fn contains_node(&self, to_check: &V) -> bool {
        match self {
            &TwoNode(Two(ref v, _, _)) |
                &LeafTwoNode(LeafTwo(ref v)) if to_check == v => true,

            &ThreeNode(Three(ref v1, ref v2, _, _, _)) |
                &LeafThreeNode(LeafThree(ref v1, ref v2)) if to_check == v1 || to_check == v2 => true,

            _ => false
        }
    }

    fn insert(self, to_insert: V) -> InsertResult<V> {
        // If value is already in this node, we're done (prevent duplicates)
        if self.contains_node(&to_insert) { return Fit(self); }

        let next_direction = self.next_direction(&to_insert);

        match self {
            // Insert if leaf TwoNode
            LeafTwoNode(leaf_two) => {
                let three_node = leaf_two.to_three(to_insert);
                Fit(three_node.to_node())
            },

            // Split if leaf ThreeNode
            LeafThreeNode(leaf_three) => {
                let four_node = leaf_three.to_four(to_insert);
                Split(four_node)
            },

            // Recurse down if internal Node and handle results
            TwoNode(Two(value, box left, box middle)) => {

                // Determine which node we'll recurse next
                let (next_node, other_node) = match next_direction {
                    Left => (left, middle),
                    Middle => (middle, left),
                    _ => panic!(""),
                };

                // Recurse, save the result of the insert
                let insert_result = next_node.insert(to_insert);

                // Handle the result of the insert
                let new_node = match insert_result {
                    Fit(returned_node) =>
                        match next_direction {
                            Left =>   Two(value, box returned_node, box other_node),
                            Middle => Two(value, box other_node, box returned_node),
                            _ => panic!(""),
{'fraction_non_alphanumeric': 0.1281659780851446, 'fraction_numerical': 0.011496317585773307, 'mean_word_length': 1.8290142276422765, 'pattern_counts': {'":': 0, '<': 120, '<?xml version=': 0, '>': 174, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2034177', 'n_tokens_mistral': 3739, 'n_tokens_neox': 3535, 'n_words': 864}