<commit_before>using NUnit.Framework;

namespace ImTools.Experimental2.UnitTests
{
    [TestFixture]
    public class ImMapTests
    {
        [Test]
        public void Test_that_all_added_values_are_accessible()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(1, 11)
                .AddOrUpdate(2, 22)
                .AddOrUpdate(3, 33);

            Assert.AreEqual(11, t.GetValueOrDefault(1));
            Assert.AreEqual(22, t.GetValueOrDefault(2));
            Assert.AreEqual(33, t.GetValueOrDefault(3));
        }

        [Test]
        public void Test_balance_ensured_for_left_left_tree()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(5, 1)
                .AddOrUpdate(4, 2)
                .AddOrUpdate(3, 3) 
                .To<ImMapTree<int>>();

            //     5   =>    4
            //   4         3   5
            // 3
            Assert.AreEqual(4, t.Data.Key);
            Assert.AreEqual(3, t.Left.To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t.Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_balance_preserved_when_add_to_balanced_tree()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(5, 1)
                .AddOrUpdate(4, 2)
                .AddOrUpdate(3, 3)
                // add to that
                .AddOrUpdate(2, 4)
                .AddOrUpdate(1, 5)
                .To<ImMapTree<int>>();

            //       4    =>     4
            //     3   5      2     5
            //   2          1   3
            // 1
            Assert.AreEqual(4, t.Data.Key);
            Assert.AreEqual(2, t.Left.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(1, t.Left.To<ImMapTree<int>>().Left.To<ImMapData<int>>().Key);
            Assert.AreEqual(3, t.Left.To<ImMapTree<int>>().Right.To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t.Right.To<ImMapData<int>>().Key);

            // parent node balancing
            var t1 = t.AddOrUpdate(-1, 6);

            //         4                 2
            //      2     5   =>     -1     4
            //    1   3                1   3   5
            // -1

            Assert.AreEqual(2,  t1.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(-1, t1.To<ImMapTree<int>>().Left.To<ImMapBranch<int>>().Data.Key);
            Assert.AreEqual(1, t1.To<ImMapTree<int>>().Left.To<ImMapBranch<int>>().RightData.Key);

            Assert.AreEqual(4, t1.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(3, t1.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Left.To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t1.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_balance_ensured_for_left_right_tree()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(5, 1)
                .AddOrUpdate(3, 2)
                .AddOrUpdate(4, 3)
                .To<ImMapTree<int>>();

            //     5  =>    5   =>   4 
            //  3         4        3   5
            //    4     3  
            Assert.AreEqual(4, t.Data.Key);
            Assert.AreEqual(3, t.Left .To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t.Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_balance_ensured_for_right_right_tree()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(3, 1)
                .AddOrUpdate(4, 2)
                .AddOrUpdate(5, 3)
                .To<ImMapTree<int>>();

            // 3      =>     4
            //   4         3   5
            //     5
            Assert.AreEqual(4, t.Data.Key);
            Assert.AreEqual(3, t.Left.To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t.Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_balance_ensured_for_right_left_tree()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(3, 1)
                .AddOrUpdate(5, 2)
                .AddOrUpdate(4, 3)
                .To<ImMapTree<int>>();

            // 3      =>   3     =>    4
            //    5          4       3   5
            //  4              5
            Assert.AreEqual(4, t.Data.Key);
            Assert.AreEqual(3, t.Left.To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t.Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_double_rotation_in_tree_when_adding_to_the_right()
        {
            //            10                            10                            10
            //      5           15                5           15                5            20
            //   3     7    12      20     =>  3     7    12       23    =>  3     7    12       23
            //                          25                      20    25                  15   21   25
            //                        23                          21                            
            var t = ImMap<int>.Empty
                .AddOrUpdate(10, 10)

                .AddOrUpdate(15, 15)
                .AddOrUpdate(5,  5)
                .AddOrUpdate(7,  7)

                .AddOrUpdate(3,  3)
                .AddOrUpdate(20, 20)
                .AddOrUpdate(12, 12)
                .AddOrUpdate(25, 25)

                .AddOrUpdate(23, 23)
                .AddOrUpdate(21, 21) // here ?

                .To<ImMapTree<int>>();

            Assert.AreEqual(10, t.To<ImMapTree<int>>().Data.Key);
            
            Assert.AreEqual(5,  t.To<ImMapTree<int>>().Left .To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(3,  t.To<ImMapTree<int>>().Left .To<ImMapTree<int>>().Left .To<ImMapData<int>>().Key);
            Assert.AreEqual(7,  t.To<ImMapTree<int>>().Left .To<ImMapTree<int>>().Right.To<ImMapData<int>>().Key);

            Assert.AreEqual(20, t.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(12, t.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Left .To<ImMapBranch<int>>().Data.Key);
            Assert.AreEqual(15, t.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Left .To<ImMapBranch<int>>().RightData.Key);
            
            Assert.AreEqual(23, t.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(21, t.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Left .To<ImMapData<int>>().Key);
            Assert.AreEqual(25, t.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_balance_when_adding_10_items_to_the_right()
        {
            var t = ImMap<int>.Empty;
            for (var i = 1; i <= 10; i++)
                t = t.AddOrUpdate(i, i);

            // 1     =>   2     =>    2     =>    2      =>       4       =>        4        =>        4           =>         4           =>         4           =>          4       
            //    2     1   3       1   3      1     4        2       5        2         6        2         6            2         6            2         6            2           8
            //                            4        3   5    1   3       6    1   3     5   7   1     3   5     7      1     3   5     8      1     3   5     8      1     3     6     9
            //                                                                                                   8                  7   9                  7   9              5   7     10
            Assert.AreEqual(4, t.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(2, t.To<ImMapTree<int>>().Left.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(1, t.To<ImMapTree<int>>().Left.To<ImMapTree<int>>().Left .To<ImMapData<int>>().Key);
            Assert.AreEqual(3, t.To<ImMapTree<int>>().Left.To<ImMapTree<int>>().Right.To<ImMapData<int>>().Key);<commit_msg>rotation of the tree found<commit_after>using NUnit.Framework;

namespace ImTools.Experimental2.UnitTests
{
    [TestFixture]
    public class ImMapTests
    {
        [Test]
        public void Test_that_all_added_values_are_accessible()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(1, 11)
                .AddOrUpdate(2, 22)
                .AddOrUpdate(3, 33);

            Assert.AreEqual(11, t.GetValueOrDefault(1));
            Assert.AreEqual(22, t.GetValueOrDefault(2));
            Assert.AreEqual(33, t.GetValueOrDefault(3));
        }

        [Test]
        public void Test_balance_ensured_for_left_left_tree()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(5, 1)
                .AddOrUpdate(4, 2)
                .AddOrUpdate(3, 3) 
                .To<ImMapTree<int>>();

            //     5   =>    4
            //   4         3   5
            // 3
            Assert.AreEqual(4, t.Data.Key);
            Assert.AreEqual(3, t.Left.To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t.Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_balance_preserved_when_add_to_balanced_tree()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(5, 1)
                .AddOrUpdate(4, 2)
                .AddOrUpdate(3, 3)
                // add to that
                .AddOrUpdate(2, 4)
                .AddOrUpdate(1, 5)
                .To<ImMapTree<int>>();

            //       4    =>     4
            //     3   5      2     5
            //   2          1   3
            // 1
            Assert.AreEqual(4, t.Data.Key);
            Assert.AreEqual(2, t.Left.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(1, t.Left.To<ImMapTree<int>>().Left.To<ImMapData<int>>().Key);
            Assert.AreEqual(3, t.Left.To<ImMapTree<int>>().Right.To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t.Right.To<ImMapData<int>>().Key);

            // parent node balancing
            var t1 = t.AddOrUpdate(-1, 6);

            //         4                 2
            //      2     5   =>     -1     4
            //    1   3                1   3   5
            // -1

            Assert.AreEqual(2,  t1.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(-1, t1.To<ImMapTree<int>>().Left.To<ImMapBranch<int>>().Data.Key);
            Assert.AreEqual(1, t1.To<ImMapTree<int>>().Left.To<ImMapBranch<int>>().RightData.Key);

            Assert.AreEqual(4, t1.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(3, t1.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Left.To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t1.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_balance_ensured_for_left_right_tree()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(5, 1)
                .AddOrUpdate(3, 2)
                .AddOrUpdate(4, 3)
                .To<ImMapTree<int>>();

            //     5  =>    5   =>   4 
            //  3         4        3   5
            //    4     3  
            Assert.AreEqual(4, t.Data.Key);
            Assert.AreEqual(3, t.Left .To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t.Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_balance_ensured_for_right_right_tree()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(3, 1)
                .AddOrUpdate(4, 2)
                .AddOrUpdate(5, 3)
                .To<ImMapTree<int>>();

            // 3      =>     4
            //   4         3   5
            //     5
            Assert.AreEqual(4, t.Data.Key);
            Assert.AreEqual(3, t.Left.To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t.Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_balance_ensured_for_right_left_tree()
        {
            var t = ImMap<int>.Empty
                .AddOrUpdate(3, 1)
                .AddOrUpdate(5, 2)
                .AddOrUpdate(4, 3)
                .To<ImMapTree<int>>();

            // 3      =>   3     =>    4
            //    5          4       3   5
            //  4              5
            Assert.AreEqual(4, t.Data.Key);
            Assert.AreEqual(3, t.Left.To<ImMapData<int>>().Key);
            Assert.AreEqual(5, t.Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_double_rotation_in_tree_when_adding_to_the_right()
        {
            //            10                            10                            10                            10                                     12
            //      5           15                5           15                5            20               5                20                    10             20
            //   3     7    12      20     =>  3     7    12       23    =>  3     7    12       23    =>  3     7       12          23     =>    5      11    15        23
            //                          25                      20    25                  15   21   25                 11   15      21   25     3   7            17    21   25
            //                        23!                         21!                                                        17!                                   
            var t = ImMap<int>.Empty
                .AddOrUpdate(10, 10)

                .AddOrUpdate(15, 15)
                .AddOrUpdate(5,  5)
                .AddOrUpdate(7,  7)

                .AddOrUpdate(3,  3)
                .AddOrUpdate(20, 20)
                .AddOrUpdate(12, 12)
                .AddOrUpdate(25, 25)

                .AddOrUpdate(23, 23)
                .AddOrUpdate(21, 21) // here it goes double rotate!
                
                .AddOrUpdate(11, 11)
                .AddOrUpdate(17, 17) // boom again - on the global scale!
                .To<ImMapTree<int>>();

            Assert.AreEqual(12, t.Data.Key);
            
            Assert.AreEqual(10, t.Left .To<ImMapTree<int>>().Data.Key);
            
            Assert.AreEqual(5,  t.Left .To<ImMapTree<int>>().Left .To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(3,  t.Left .To<ImMapTree<int>>().Left .To<ImMapTree<int>>().Left .To<ImMapData<int>>().Key);
            Assert.AreEqual(7,  t.Left .To<ImMapTree<int>>().Left .To<ImMapTree<int>>().Right.To<ImMapData<int>>().Key);

            Assert.AreEqual(11,  t.Left .To<ImMapTree<int>>().Right.To<ImMapData<int>>().Key);

            Assert.AreEqual(20, t.Right.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(15, t.Right.To<ImMapTree<int>>().Left .To<ImMapBranch<int>>().Data.Key);
            Assert.AreEqual(17, t.Right.To<ImMapTree<int>>().Left .To<ImMapBranch<int>>().RightData.Key);

            Assert.AreEqual(23, t.Right.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(21, t.Right.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Left .To<ImMapData<int>>().Key);
            Assert.AreEqual(25, t.Right.To<ImMapTree<int>>().Right.To<ImMapTree<int>>().Right.To<ImMapData<int>>().Key);
        }

        [Test]
        public void Test_balance_when_adding_10_items_to_the_right()
        {
            var t = ImMap<int>.Empty;
            for (var i = 1; i <= 10; i++)
                t = t.AddOrUpdate(i, i);

            // 1     =>   2     =>    2     =>    2      =>       4       =>        4        =>        4           =>         4           =>         4           =>          4       
            //    2     1   3       1   3      1     4        2       5        2         6        2         6            2         6            2         6            2           8
            //                            4        3   5    1   3       6    1   3     5   7   1     3   5     7      1     3   5     8      1     3   5     8      1     3     6     9
            //                                                                                                   8                  7   9                  7   9              5   7     10
            Assert.AreEqual(4, t.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(2, t.To<ImMapTree<int>>().Left.To<ImMapTree<int>>().Data.Key);
            Assert.AreEqual(1, t.To<ImMapTree<int>>().Left.To<ImMapTree<int>>().Left .To<ImMapData<int>>().Key);
            Assert.AreEqual(3, t.To<ImMapTree<int>>().Left.To<ImMapTree<int>>().Right.To<ImMapData<int>>().Key);
{'fraction_non_alphanumeric': 0.13831708197905382, 'fraction_numerical': 0.04056819549777296, 'mean_word_length': 1.0920423067237472, 'pattern_counts': {'":': 0, '<': 293, '<?xml version=': 0, '>': 331, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 108, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3865966', 'n_tokens_mistral': 5483, 'n_tokens_neox': 5133, 'n_words': 818}