<commit_before>/**
 * This file contains an implementation of an AVL tree. An AVL tree
 * is a special type of binary tree which self balances itself to keep
 * operations logarithmic.
 *
 * @author <NAME>, <EMAIL>
 **/

public class RedBlackTree <T extends Comparable<T>> {

  class Node implements TreePrinter.PrintableNode {
    
    // 'bf' is short for Balance Factor
    int bf;

    // The value/data contained within the node.
    T value;

    // The height of this node in the tree.
    int height;

    // The left and the right children of this node.    
    Node left, right;

    public Node(T value, Node left, Node right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }

    @Override 
    public Node getLeft() {
      return left;
    }

    @Override
    public Node getRight() {
      return right;
    }

    @Override
    public String getText() {
      return String.valueOf(value);
    }

  }

  // The root node of the AVL tree.
  Node root;

  // Tracks the number of nodes inside the tree.
  private int nodeCount = 0;

  // Special token value used as an alternative to returning 'null'.
  // The TOKEN is used to indicate special return value signals. For example, 
  // we can return the TOKEN instead of null when we're inserting a new item
  // and discover the value we were inserting already exists in the tree.
  private Node TOKEN = new Node(null, null, null);

  // The height of a rooted tree is the number of edges between the tree's
  // root and its furthest leaf. This means that a tree containing a single 
  // node has a height of 0.
  public int height() {
    if (root == null) return 0;
    return root.height;
  }

  // Returns the number of nodes in the tree.
  public int size() {
    return nodeCount;
  }

  // Returns whether or not the tree is empty.
  public boolean isEmpty() {
    return size() == 0;
  }

  // Prints a visual representation of the tree to the console.
  // public void display() {
  //   TreePrinter.print(root);
  // }

  // Return true/false depending on whether a value exists in the tree.
  public boolean contains(T value) {
    return contains(root, value);
  }

  // Recursive contains helper method.
  private boolean contains(Node node, T value) {
    
    if (node == null) return false;

    // Compare current value to the value in the node.
    int cmp = value.compareTo(node.value);

    // Dig into left subtree.
    if (cmp < 0) return contains(node.left, value);

    // Dig into right subtree.
    if (cmp > 0) return contains(node.right, value);

    // Found value in tree.
    return true;

  }

  // Helper method to find the leftmost node (which has the smallest value)
  // private Node findMin(Node node) {
  //   while(node.left != null) 
  //     node = node.left;
  //   return node;
  // }

  // Helper method to find the rightmost node (which has the largest value)
  // private Node findMax(Node node) {
  //   while(node.right != null) 
  //     node = node.right;
  //   return node;
  // }

  // Returns as iterator to traverse the tree in order.
  // public java.util.Iterator<T> iterator () {

  //   final int expectedNodeCount = nodeCount;
  //   final java.util.Stack<Node> stack = new java.util.Stack<>();
  //   stack.push(root);

  //   return new java.util.Iterator<T> () {
  //     Node trav = root;
  //     @Override 
  //     public boolean hasNext() {
  //       if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();        
  //       return root != null && !stack.isEmpty();
  //     }
  //     @Override 
  //     public T next () {
        
  //       if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();

  //       while(trav != null && trav.left != null) {
  //         stack.push(trav.left);
  //         trav = trav.left;
  //       }
        
  //       Node node = stack.pop();
        
  //       if (node.right != null) {
  //         stack.push(node.right);
  //         trav = node.right;
  //       }
        
  //       return node.value;
  //     }
  //     @Override 
  //     public void remove() {
  //       throw new UnsupportedOperationException();
  //     }      
  //   };
  // }

  // Make sure all left child nodes are smaller in value than their parent and
  // make sure all right child nodes are greater in value than their parent.
  // (Used only for testing)
  // boolean validateBSTInvarient(Node node) {
  //   if (node == null) return true;
  //   T val = node.value;
  //   boolean isValid = true;
  //   if (node.left  != null) isValid = isValid && node.left.value.compareTo(val)  < 0;
  //   if (node.right != null) isValid = isValid && node.right.value.compareTo(val) > 0;
  //   return isValid && validateBSTInvarient(node.left) && validateBSTInvarient(node.right);
  // }

  public static void main(String[] args) {
    
  }

}












<commit_msg>Worked on insertion method for RB tree<commit_after>/**
 * This file contains an implementation of a Red-Black tree. A RB tree
 * is a special type of binary tree which self balances itself to keep
 * operations logarithmic.
 *
 * @author <NAME>, <EMAIL>
 **/

public class RedBlackTree <T extends Comparable<T>> {

  static final boolean RED = true;
  static final boolean BLACK = false;

  class Node implements TreePrinter.PrintableNode {
    
    // The color of the node. By default all nodes start red.
    boolean color = RED;

    // The value/data contained within the node.
    T value;

    // The left, right and parent references for this node.    
    Node left, right, parent;

    public Node(T value, Node parent) {
      this.value = value;
      this.parent = parent;
    }

    @Override 
    public Node getLeft() {
      return left;
    }

    @Override
    public Node getRight() {
      return right;
    }

    @Override
    public String getText() {
      return String.valueOf(value);
    }

  }

  // The root node of the AVL tree.
  Node root;

  // Tracks the number of nodes inside the tree.
  private int nodeCount = 0;

  // Returns the number of nodes in the tree.
  public int size() {
    return nodeCount;
  }

  // Returns whether or not the tree is empty.
  public boolean isEmpty() {
    return size() == 0;
  }

  // Prints a visual representation of the tree to the console.
  public void display() {
    TreePrinter.print(root);
  }

  // Return true/false depending on whether a value exists in the tree.
  public boolean contains(T value) {
    return contains(root, value);
  }

  // Recursive contains helper method.
  private boolean contains(Node node, T value) {
    
    if (node == null) return false;

    // Compare current value to the value in the node.
    int cmp = value.compareTo(node.value);

    // Dig into left subtree.
    if (cmp < 0) return contains(node.left, value);

    // Dig into right subtree.
    if (cmp > 0) return contains(node.right, value);

    // Found value in tree.
    return true;

  }

  public boolean insert(T value) {

    if (value == null) throw new IllegalArgumentException();

    // No root node.
    if (root == null) {
      root = new Node(value, null);
      return true;      
    }

    for(Node node = root;;) {

      int cmp = node.value.compareTo(value);

      if (cmp < 0) {
        if (node.left == null) {
          node.left = new Node(value, node);
          // balance
          return true;
        }
        node = node.left;

      } else if (cmp > 0) {
        if (node.right == null) {
          node.right = new Node(value, node);
          // balance
          return true;
        }
        node = node.right;

      // Duplicate value.
      } else return false;

    }

  }

  // Helper method to find the leftmost node (which has the smallest value)
  private Node findMin(Node node) {
    while(node.left != null) 
      node = node.left;
    return node;
  }

  // Helper method to find the rightmost node (which has the largest value)
  private Node findMax(Node node) {
    while(node.right != null) 
      node = node.right;
    return node;
  }

  // Returns as iterator to traverse the tree in order.
  public java.util.Iterator<T> iterator () {

    final int expectedNodeCount = nodeCount;
    final java.util.Stack<Node> stack = new java.util.Stack<>();
    stack.push(root);

    return new java.util.Iterator<T> () {
      Node trav = root;
      @Override 
      public boolean hasNext() {
        if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();        
        return root != null && !stack.isEmpty();
      }
      @Override 
      public T next () {
        
        if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();

        while(trav != null && trav.left != null) {
          stack.push(trav.left);
          trav = trav.left;
        }
        
        Node node = stack.pop();
        
        if (node.right != null) {
          stack.push(node.right);
          trav = node.right;
        }
        
        return node.value;
      }
      @Override 
      public void remove() {
        throw new UnsupportedOperationException();
      }      
    };
  }

  // Make sure all left child nodes are smaller in value than their parent and
  // make sure all right child nodes are greater in value than their parent.
  // (Used only for testing)
  // boolean validateBSTInvarient(Node node) {
  //   if (node == null) return true;
  //   T val = node.value;
  //   boolean isValid = true;
  //   if (node.left  != null) isValid = isValid && node.left.value.compareTo(val)  < 0;
  //   if (node.right != null) isValid = isValid && node.right.value.compareTo(val) > 0;
  //   return isValid && validateBSTInvarient(node.left) && validateBSTInvarient(node.right);
  // }

  public static void main(String[] args) {
    
  }

}













{'fraction_non_alphanumeric': 0.1095613503133212, 'fraction_numerical': 0.0016171417020416413, 'mean_word_length': 2.094121325828643, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 24, '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': '1981394', 'n_tokens_mistral': 2991, 'n_tokens_neox': 2869, 'n_words': 1035}