<commit_before>jest.autoMockOff();
const IM = require('immutable');
const BSTree = require('../../../src/binary_trees/BSTree');
const BSTNode = require('../../../src/binary_trees/BSTNode');


describe('BSTree', () => {

  describe('Instantiation', () => {
    let bst = new BSTree(),
        _node = new BSTNode(0, 'first node value', null, null, 1),
        bstWithNode = new BSTree(null, _node);

    it('instantiates empty, checks size', () => {
      expect(bst.size).toBe(0);
    });

    it('instantiates with a root node, checks size', () => {
      expect(bstWithNode.size).toBe(1);
    });

    it('instantiates with a default comparator', () => {
      expect(bst.comparator).toBeDefined();
      expect(typeof bst.comparator).toBe('function');
    });

    it('instantiates with a custom comparator', () => {
      let comp = () => 0, compBST = new BSTree(comp);
      expect(compBST.comparator).toBe(comp);
      expect(typeof compBST.comparator).toBe('function');
    });

  });

  describe('Instance Methods', () => {

    describe('#insert', () => {

      describe('empty trees', () => {
        let bst = new BSTree();

        it('returns current tree when no args', () => {
          expect(bst.insert()).toBe(bst);
        });

        it('returns new tree for simple insert into empty tree', () => {
          expect(bst.insert(2, 'val')).toEqual(jasmine.any(BSTree));
        });

        it('returns a tree with the correct root node', () => {
          let _node = bst.insert(2, 'val').root;
          expect(_node.key).toBe(2);
          expect(_node.value).toBe('val');
        });

      })

      describe('nonempty trees', () => {
        let rootNode = new BSTNode(1, 'hi', null, null, 1),
            bst = new BSTree(null, rootNode);

        it('returns a new tree', () => {
          expect(bst.insert(2, 'a')).toEqual(jasmine.any(BSTree));
        });

        describe('root node', () => {
          let newTree1 = bst.insert(8, 'string');

          it('has correct id', () => {
            expect(newTree1.root.id).toBe(1);
          });

          it('has correct key', () => {
            expect(newTree1.root.key).toBe(1);
          });

          it('has correct value', () => {
            expect(newTree1.root.value).toBe('hi');
          });

          it('has correct right child', () => {
            expect(newTree1.root.right).toEqual(new BSTNode(8, 'string', null, null, 2));
          });

          it('has correct left child', () => {
            expect(newTree1.root.left).toBeNull();
          });

        });

      });

      describe('chained insertion', () => {
        let rootNode = new BSTNode(50, 'hi', null, null, 1),
            bst = new BSTree(undefined, rootNode),
            chainedResult = bst.insert(25, 'a').insert(75, 'b').insert(95, 'c');

        describe('resulting tree', () => {

          it('returns a new tree', () => {
            expect(chainedResult).toEqual(jasmine.any(BSTree));
          });

          it('has correct max node', () => {
            expect(chainedResult.max.key).toBe(95);
          });

          it('has correct min node', () => {
            expect(chainedResult.min.key).toBe(25);
          });

        });

        describe('root node of chained tree', () => {

          it('has the correct id', () => {
            expect(chainedResult.root.id).toBe(1);
          });

          it('has the correct key', () => {
            expect(chainedResult.root.key).toBe(50);
          });

          it('has the correct value', () => {
            expect(chainedResult.root.value).toBe('hi');
          });

          it('has the correct left and right nodes', () => {
            expect(chainedResult.root.left.key).toBe(25);
            expect(chainedResult.root.right.key).toBe(75);
          });

        });

      });

      describe('insertion operation immutability', () => {

        it('does not mutate tree', () => {
          let bst = new BSTree();
          bst.insert(1, 'a');
          expect(bst.size).toBe(0);
        });

        it('does not mutate nodes', () => {
          let node = new BSTNode(1, 'a', null, null, 1),
              bst = new BSTree(node);
          bst.insert(2, 'b');
          expect(node.right).toBeNull();
        });

      });

    });

    xdescribe('#remove', () => {

    });

    describe('#find', () => {

      describe('key not present in tree', () => {
<commit_msg>Add partial pending specs for BSTree #remove method<commit_after>jest.autoMockOff();
const IM = require('immutable');
const BSTree = require('../../../src/binary_trees/BSTree');
const BSTNode = require('../../../src/binary_trees/BSTNode');


describe('BSTree', () => {

  describe('Instantiation', () => {
    let bst = new BSTree(),
        _node = new BSTNode(0, 'first node value', null, null, 1),
        bstWithNode = new BSTree(null, _node);

    it('instantiates empty, checks size', () => {
      expect(bst.size).toBe(0);
    });

    it('instantiates with a root node, checks size', () => {
      expect(bstWithNode.size).toBe(1);
    });

    it('instantiates with a default comparator', () => {
      expect(bst.comparator).toBeDefined();
      expect(typeof bst.comparator).toBe('function');
    });

    it('instantiates with a custom comparator', () => {
      let comp = () => 0, compBST = new BSTree(comp);
      expect(compBST.comparator).toBe(comp);
      expect(typeof compBST.comparator).toBe('function');
    });

  });

  describe('Instance Methods', () => {

    describe('#insert', () => {

      describe('empty trees', () => {
        let bst = new BSTree();

        it('returns current tree when no args', () => {
          expect(bst.insert()).toBe(bst);
        });

        it('returns new tree for simple insert into empty tree', () => {
          expect(bst.insert(2, 'val')).toEqual(jasmine.any(BSTree));
        });

        it('returns a tree with the correct root node', () => {
          let _node = bst.insert(2, 'val').root;
          expect(_node.key).toBe(2);
          expect(_node.value).toBe('val');
        });

      })

      describe('nonempty trees', () => {
        let rootNode = new BSTNode(1, 'hi', null, null, 1),
            bst = new BSTree(null, rootNode);

        it('returns a new tree', () => {
          expect(bst.insert(2, 'a')).toEqual(jasmine.any(BSTree));
        });

        describe('root node', () => {
          let newTree1 = bst.insert(8, 'string');

          it('has correct id', () => {
            expect(newTree1.root.id).toBe(1);
          });

          it('has correct key', () => {
            expect(newTree1.root.key).toBe(1);
          });

          it('has correct value', () => {
            expect(newTree1.root.value).toBe('hi');
          });

          it('has correct right child', () => {
            expect(newTree1.root.right).toEqual(new BSTNode(8, 'string', null, null, 2));
          });

          it('has correct left child', () => {
            expect(newTree1.root.left).toBeNull();
          });

        });

      });

      describe('chained insertion', () => {
        let rootNode = new BSTNode(50, 'hi', null, null, 1),
            bst = new BSTree(undefined, rootNode),
            chainedResult = bst.insert(25, 'a').insert(75, 'b').insert(95, 'c');

        describe('resulting tree', () => {

          it('returns a new tree', () => {
            expect(chainedResult).toEqual(jasmine.any(BSTree));
          });

          it('has correct max node', () => {
            expect(chainedResult.max.key).toBe(95);
          });

          it('has correct min node', () => {
            expect(chainedResult.min.key).toBe(25);
          });

        });

        describe('root node of chained tree', () => {

          it('has the correct id', () => {
            expect(chainedResult.root.id).toBe(1);
          });

          it('has the correct key', () => {
            expect(chainedResult.root.key).toBe(50);
          });

          it('has the correct value', () => {
            expect(chainedResult.root.value).toBe('hi');
          });

          it('has the correct left and right nodes', () => {
            expect(chainedResult.root.left.key).toBe(25);
            expect(chainedResult.root.right.key).toBe(75);
          });

        });

      });

      describe('insertion operation immutability', () => {

        it('does not mutate tree', () => {
          let bst = new BSTree();
          bst.insert(1, 'a');
          expect(bst.size).toBe(0);
        });

        it('does not mutate nodes', () => {
          let node = new BSTNode(1, 'a', null, null, 1),
              bst = new BSTree(node);
          bst.insert(2, 'b');
          expect(node.right).toBeNull();
        });

      });

    });

    xdescribe('#remove', () => {

      xdescribe('empty trees', () => {
        let bst = new BSTree();

        it('returns current tree when no args', () => {
          expect(bst.remove()).toEqual(bst);
        });

        it('returns current tree when args', () => {
          expect(bst.remove(2)).toEqual(bst);
        });

      })

      xdescribe('nonempty trees', () => {

        it('returns a new tree', () => {
          let rootNode = new BSTNode(1, 'hi', null, null, 1),
              bst = new BSTree(null, rootNode);
          expect(bst.remove(1)).toEqual(jasmine.any(BSTree));
        });

        xdescribe('root node', () => {
          let minNode = new BSTNode(0, 'min', null, null, 4),
              rootRight = new BSTNode(75, 'max', null, null, 2),
              rootLeft = new BSTNode(25, 'c', minNode, null, 3),
              rootNode = new BSTNode(50, 'a', rootLeft, rootRight, 1),
              bst = new BSTree(null, rootNode),
              newTreeRoot = bst.remove(25).root;

          it('has correct left child', () => {
            expect(newTreeRoot.left).toBe(minNode);
          });

        });

      });

      xdescribe('target node with no children', () => {
        let target = new BSTNode(1, 'remove me', null, null, 1),
            parent = new BSTNode(99, 'reset my children', target, null, 2),
            bst = new BSTree(null, parent);

        it('sets parent node side to null', () => {
          expect(bst.remove(1).root.left).toBeNull();
        });

      });

      xdescribe('target node with one child', () => {
        let child = new BSTNode(99, 'reset my position to root', null, null, 1),
            targetLeft = new BSTNode(1, 'remove me', child, null, 2),
            targetRight = new BSTNode(1, 'remove me', null, child, 2),
            bstLeft = new BSTree(null, targetLeft),
            bstRight = new BSTree(null, targetRight);

        it('left child', () => {
          expect(bstLeft.remove(1).root).toEqual(child);
        });

        it('right child', () => {
          expect(bstRight.remove(1).root).toEqual(child);
        });

      });

      xdescribe('target node with two children', () => {
        let childLeft = new BSTNode(1, 'reset my position', null, null, 2),
            childRight = new BSTNode(9, 'reset my position', null, null, 3),
            target = new BSTNode(5, 'remove me', childLeft, childRight, 1),
            bst = new BSTree(null, target);

        // no right children of left child case
        // > 0 right children of left child case
      });

    });

    describe('#find', () => {

      describe('key not present in tree', () => {

{'fraction_non_alphanumeric': 0.18158724597056763, 'fraction_numerical': 0.01165031534688157, 'mean_word_length': 1.9755016940317958, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 91, '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': '6192684', 'n_tokens_mistral': 3577, 'n_tokens_neox': 3384, 'n_words': 742}