content: package com.test.prizesystem.util;
  
  import java.io.Serializable;
  import java.util.ArrayList;
  import java.util.List;
  
  import static com.test.prizesystem.util.RedBlackTree.Color.BLACK;
  import static com.test.prizesystem.util.RedBlackTree.Color.RED;
  
  /**
   * <h3>红黑树</h3>
   * <p>
   * 红黑树实现，用于高效存储和检索数据。该实现支持以下特性：
   * <ul>
   *   <li>添加、删除和查找操作</li>
   *   <li>基于时间戳的查询</li>
   *   <li>自动平衡以保持O(log n)性能</li>
   * </ul>
   * <p>
   * 此数据结构主要用于系统中需要高效索引的场景，比如令牌管理。
   * 红黑树保证了在最坏情况下也能提供对数级别的性能。
   * 
   * @author wu
   * @version 1.0
   */
  public class RedBlackTree implements Serializable {
  
      private static final long serialVersionUID = 1L;
  
      enum Color {
          RED, BLACK;
      }
  
      Node root;
  
      static class Node implements Serializable {
          private static final long serialVersionUID = 1L;
          long key;
          Object value;
          Node left;
          Node right;
          Node parent;        // 父节点
          Color color = RED;  // 颜色
  
          public Node(long key, Object value) {
              this.key = key;
              this.value = value;
          }
  
          public Node(long key) {
              this.key = key;
          }
  
          public Node(long key, Color color) {
              this.key = key;
              this.color = color;
          }
  
          public Node(long key, Color color, Node left, Node right) {
              this.key = key;
              this.color = color;
              this.left = left;
              this.right = right;
              if (left != null) {
                  left.parent = this;
              }
              if (right != null) {
                  right.parent = this;
              }
          }
  
          // 是否是左孩子
          boolean isLeftChild() {
              return parent != null && parent.left == this;
          }
  
          // 叔叔
          Node uncle() {
              if (parent == null || parent.parent == null) {
                  return null;
              }
              if (parent.isLeftChild()) {
                  return parent.parent.right;
              } else {
                  return parent.parent.left;
              }
          }
  
          // 兄弟
          Node sibling() {
              if (parent == null) {
                  return null;
              }
              if (this.isLeftChild()) {
                  return parent.right;
              } else {
                  return parent.left;
              }
          }
      }
  
      // 判断红
      boolean isRed(Node node) {
          return node != null && node.color == RED;
      }
  
      // 判断黑
      boolean isBlack(Node node) {
  //        return !isRed(node);
          return node == null || node.color == BLACK;
      }
  
      // 右旋 1. parent 的处理 2. 旋转后新根的父子关系
      private void rightRotate(Node pink) {
          Node parent = pink.parent;
          Node yellow = pink.left;
          Node green = yellow.right;
          if (green != null) {
              green.parent = pink;
          }
          yellow.right = pink;
          yellow.parent = parent;
          pink.left = green;
          pink.parent = yellow;
          if (parent == null) {
              root = yellow;
          } else if (parent.left == pink) {
              parent.left = yellow;
          } else {
              parent.right = yellow;
          }
      }
  
      // 左旋
      private void leftRotate(Node pink) {
          Node parent = pink.parent;
          Node yellow = pink.right;
          Node green = yellow.left;
          if (green != null) {
              green.parent = pink;
          }
          yellow.left = pink;
          yellow.parent = parent;
          pink.right = green;
          pink.parent = yellow;
          if (parent == null) {
              root = yellow;
          } else if (parent.left == pink) {
              parent.left = yellow;
          } else {
              parent.right = yellow;
          }
      }
  
      /**
       * 新增或更新
       * <br>
       * 正常增、遇到红红不平衡进行调整
       *
       * @param key   键
       * @param value 值
       */
      public void put(long key, Object value) {
          Node p = root;
          Node parent = null;
          while (p != null) {
              parent = p;
              if (key < p.key) {
                  p = p.left;
              } else if (p.key < key) {
                  p = p.right;
              } else {
                  p.value = value; // 更新
                  return;
              }
          }
          Node inserted = new Node(key, value);
          if (parent == null) {
              root = inserted;
          } else if (key < parent.key) {
              parent.left = inserted;
              inserted.parent = parent;
          } else {
              parent.right = inserted;
              inserted.parent = parent;
          }
          fixRedRed(inserted);
      }
  
      void fixRedRed(Node x) {
          // case 1 插入节点是根节点，变黑即可
          if (x == root) {
              x.color = BLACK;
              return;
          }
          // case 2 插入节点父亲是黑色，无需调整
          if (isBlack(x.parent)) {
              return;
          }
          /* case 3 当红红相邻，叔叔为红时
              需要将父亲、叔叔变黑、祖父变红，然后对祖父做递归处理
          */
          Node parent = x.parent;
          Node uncle = x.uncle();
          Node grandparent = parent.parent;
          if (isRed(uncle)) {
              parent.color = BLACK;
              uncle.color = BLACK;
              grandparent.color = RED;
              fixRedRed(grandparent);
              return;
          }
  
          // case 4 当红红相邻，叔叔为黑时
          if (parent.isLeftChild() && x.isLeftChild()) { // LL
              parent.color = BLACK;
              grandparent.color = RED;
              rightRotate(grandparent);
          } else if (parent.isLeftChild()) { // LR
              leftRotate(parent);
              x.color = BLACK;
              grandparent.color = RED;
              rightRotate(grandparent);
          } else if (!x.isLeftChild()) { // RR
              parent.color = BLACK;
              grandparent.color = RED;
              leftRotate(grandparent);
          } else { // RL
              rightRotate(parent);
              x.color = BLACK;
              grandparent.color = RED;
              leftRotate(grandparent);
          }
      }
  
      /**
       * 删除
       * <br>
       * 正常删、会用到李代桃僵技巧、遇到黑黑不平衡进行调整
       *
       * @param key 键
       */
      public void remove(long key) {
          Node deleted = find(key);
          if (deleted == null) {
              return;
          }
          doRemove(deleted);
      }
  
      public boolean contains(long key) {
          return find(key) != null;
      }
  
      // 查找删除节点
      private Node find(long key) {
          Node p = root;
          while (p != null) {
              if (key < p.key) {
                  p = p.left;
              } else if (p.key < key) {
                  p = p.right;
              } else {
                  return p;
              }
          }
          return null;
      }
  
      // 查找剩余节点
      private Node findReplaced(Node deleted) {
          if (deleted.left == null && deleted.right == null) {
              return null;
          }
          if (deleted.left == null) {
              return deleted.right;
          }
          if (deleted.right == null) {
              return deleted.left;
          }
          Node s = deleted.right;
          while (s.left != null) {
              s = s.left;
          }
          return s;
      }
  
      // 处理双黑 (case3、case4、case5)
      private void fixDoubleBlack(Node x) {
          if (x == root) {
              return;
          }
          Node parent = x.parent;
          Node sibling = x.sibling();
          // case 3 兄弟节点是红色
          if (isRed(sibling)) {
              if (x.isLeftChild()) {
                  leftRotate(parent);
              } else {
                  rightRotate(parent);
              }
              parent.color = RED;
              sibling.color = BLACK;
              fixDoubleBlack(x);
              return;
          }
          if (sibling != null) {
              // case 4 兄弟是黑色, 两个侄子也是黑色
              if (isBlack(sibling.left) && isBlack(sibling.right)) {
                  sibling.color = RED;
                  if (isRed(parent)) {
                      parent.color = BLACK;
                  } else {
                      fixDoubleBlack(parent);
                  }
              }
              // case 5 兄弟是黑色, 侄子有红色
              else {
                  // LL
                  if (sibling.isLeftChild() && isRed(sibling.left)) {
                      rightRotate(parent);
                      sibling.left.color = BLACK;
                      sibling.color = parent.color;
                  }
                  // LR
                  else if (sibling.isLeftChild() && isRed(sibling.right)) {
                      sibling.right.color = parent.color;
                      leftRotate(sibling);
                      rightRotate(parent);
                  }
                  // RL
                  else if (!sibling.isLeftChild() && isRed(sibling.left)) {
                      sibling.left.color = parent.color;
                      rightRotate(sibling);
                      leftRotate(parent);
                  }
                  // RR
                  else {
                      leftRotate(parent);
                      sibling.right.color = BLACK;
                      sibling.color = parent.color;
                  }
                  parent.color = BLACK;
              }
          } else {
              // @TODO 实际也不会出现，触发双黑后，兄弟节点不会为 null
              fixDoubleBlack(parent);
          }
      }
  
      private void doRemove(Node deleted) {
          Node replaced = findReplaced(deleted);
          Node parent = deleted.parent;
          // 没有孩子
          if (replaced == null) {
              // case 1 删除的是根节点
              if (deleted == root) {
                  root = null;
              } else {
                  if (isBlack(deleted)) {
                      // 复杂调整
                      fixDoubleBlack(deleted);
                  } else {
                      // 红色叶子, 无需任何处理
                  }
                  if (deleted.isLeftChild()) {
                      parent.left = null;
                  } else {
                      parent.right = null;
                  }
                  deleted.parent = null;
              }
              return;
          }
          // 有一个孩子
          if (deleted.left == null || deleted.right == null) {
              // case 1 删除的是根节点
              if (deleted == root) {
                  root.key = replaced.key;
                  root.value = replaced.value;
                  root.left = root.right = null;
              } else {
                  if (deleted.isLeftChild()) {
                      parent.left = replaced;
                  } else {
                      parent.right = replaced;
                  }
                  replaced.parent = parent;
                  deleted.left = deleted.right = deleted.parent = null;
                  if (isBlack(deleted) && isBlack(replaced)) {
                      // 复杂处理 @TODO 实际不会有这种情况 因为只有一个孩子时 被删除节点是黑色 那么剩余节点只能是红色不会触发双黑
                      fixDoubleBlack(replaced);
                  } else {
                      // case 2 删除是黑，剩下是红
                      replaced.color = BLACK;
                  }
              }
              return;
          }
          // case 0 有两个孩子 => 有一个孩子 或 没有孩子
          long t = deleted.key;
          deleted.key = replaced.key;
          replaced.key = t;
  
          Object v = deleted.value;
          deleted.value = replaced.value;
          replaced.value = v;
          doRemove(replaced);
      }
  
      /**
       * 查找不大于指定key的最大节点
       */
      public Object findTokenBefore(long timestamp) {
          Node current = root;
          Node result = null;
  
          while (current != null) {
              if (current.key <= timestamp) {
                  result = current;
                  current = current.right;
              } else {
                  current = current.left;
              }
          }
  
          return result != null ? result.value : null;
      }
  
      /**
       * 查找第一个(最小)节点
       */
      public Object findFirstToken() {
          Node current = root;
          if (current == null) {
              return null;
          }
  
          while (current.left != null) {
              current = current.left;
          }
  
          return current.value;
      }
      
      /**
       * 根据key获取值
       */
      public Object get(long key) {
          Node node = find(key);
          return node != null ? node.value : null;
      }
  
      /**
       * 判断树是否为空
       */
      public boolean isEmpty() {
          return root == null;
      }
  
      /**
       * 获取红黑树中节点的数量
       * @return 节点数量
       */
      public int size() {
          return countNodes(root);
      }
  
      /**
       * 递归计算节点数量
       */
      private int countNodes(Node node) {
          if (node == null) {
              return 0;
          }
          return 1 + countNodes(node.left) + countNodes(node.right);
      }
  
      /**
       * 获取树中所有的键
       * @return 树中所有键的列表
       */
      public List<Long> keySet() {
          List<Long> keys = new ArrayList<>();
          collectKeys(root, keys);
          return keys;
      }
  
      /**
       * 递归收集树中所有的键
       * @param node 当前节点
       * @param keys 收集键的列表
       */
      private void collectKeys(Node node, List<Long> keys) {
          if (node == null) {
              return;
          }
          collectKeys(node.left, keys);
          keys.add(node.key);
          collectKeys(node.right, keys);
      }
  
  
  }