poerhfsdhfnc_h's blog

By poerhfsdhfnc_h, history, 4 years ago, In English

Could anyone please tell is there any alternative for pbds in java. I searched in the net but could find nothing. So is it that java users implement BIT or segment tree when c++ users use pbds or do they have some shortcuts ?

  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If you're looking or an equivalent to the pbds ordered set/map, TreeSet and TreeMap might offer what you're looking for. You can simulate find_by_order with toArray and order_of_key by getting the size of the headMap. I don't know what sort of efficiency these would come with though, you would have to benchmark them.

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I see the community is so much toxic that users are forced to ask genuine questions using new account. It makes me sad.

»
2 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

//PBDS JAVA CODE private static class AVLTreePBDS { private Node root; private boolean multi;

     AVLTreePBDS(boolean multi) {
         this.root = null;
         this.multi = multi;
     }

     int size() {
         return size(root);
     }

     boolean isEmpty() {
         return size(root) == 0;
     }

     boolean contains(int key) {
         return contains(root, key);
     }

     void add(int key) {
         root = add(root, key);
     }

     void remove(int key) {
         root = remove(root, key);
     }

     Integer first() {
         Node min = findMin(root);
         return min != null ? min.key : null;
     }

     Integer last() {
         Node max = findMax(root);
         return max != null ? max.key : null;
     }

     Integer poolFirst() {
         Node min = findMin(root);
         if (min != null) {
             remove(min.key);
             return min.key;
         }
         return null;
     }

     Integer poolLast() {
         Node max = findMax(root);
         if (max != null) {
             remove(max.key);
             return max.key;
         }
         return null;
     }

     // min >= key
     Integer ceiling(int key) {
         return contains(key) ? key : higher(key);
     }

     // max <= key
     Integer floor(int key) {
         return contains(key) ? key : lower(key);
     }

     // min > key
     Integer higher(int key) {
         Node min = higher(root, key);
         return min == null ? null : min.key;
     }

     private Node higher(Node cur, int key) {
         if (cur == null)
             return null;

         if (cur.key <= key)
             return higher(cur.right, key);

         // cur.key > key
         Node left = higher(cur.left, key);
         return left == null ? cur : left;
     }

     // max < key
     Integer lower(int key) {
         Node max = lower(root, key);
         return max == null ? null : max.key;
     }

     private Node lower(Node cur, int key) {
         if (cur == null)
             return null;

         if (cur.key >= key)
             return lower(cur.left, key);

         // cur.key < key
         Node right = lower(cur.right, key);
         return right == null ? cur : right;
     }

     private class Node {
         int key, height, size;
         Node left, right;

         Node(int key) {
             this.key = key;
             height = size = 1;
             left = right = null;
         }
         private void preOrder(Node root , StringBuilder ans) {
           if(root == null) return;
           if(root.left != null) preOrder(root.left,ans );
           ans.append(root.key+",");
           if(root.right!=null) preOrder(root.right, ans);
         }
         public String toString() {
           StringBuilder res = new StringBuilder();
           preOrder(root, res);
           return "[" + String.valueOf(res.substring(0 , res.length()-1)) +"]" ;
         }
     }

     private int height(Node cur) {
         return cur == null ? 0 : cur.height;
     }

     private int balanceFactor(Node cur) {
         return height(cur.right) - height(cur.left);
     }

     private int size(Node cur) {
         return cur == null ? 0 : cur.size;
     }

     // fixVertex
     private void fixHeightAndSize(Node cur) {
         cur.height = Math.max(height(cur.left), height(cur.right)) + 1;
         cur.size = size(cur.left) + size(cur.right) + 1;
     }

     private Node rotateRight(Node cur) {
         Node prevLeft = cur.left;
         cur.left = prevLeft.right;
         prevLeft.right = cur;
         fixHeightAndSize(cur);
         fixHeightAndSize(prevLeft);
         return prevLeft;
     }

     private Node rotateLeft(Node cur) {
         Node prevRight = cur.right;
         cur.right = prevRight.left;
         prevRight.left = cur;
         fixHeightAndSize(cur);
         fixHeightAndSize(prevRight);
         return prevRight;
     }

     private Node balance(Node cur) {
         fixHeightAndSize(cur);
         if (balanceFactor(cur) == 2) {
             if (balanceFactor(cur.right) < 0)
                 cur.right = rotateRight(cur.right);
             return rotateLeft(cur);
         }
         if (balanceFactor(cur) == -2) {
             if (balanceFactor(cur.left) > 0)
                 cur.left = rotateLeft(cur.left);
             return rotateRight(cur);
         }
         return cur;
     }

     private boolean contains(Node cur, int key) {
         if (cur == null)
             return false;
         else if (key < cur.key)
             return contains(cur.left, key);
         else if (key > cur.key)
             return contains(cur.right, key);
         else
             return true;
     }

     private Node add(Node cur, int key) {
         if (cur == null)
             return new Node(key);

         if (key < cur.key)
             cur.left = add(cur.left, key);
         else if (key > cur.key || multi)
             cur.right = add(cur.right, key);

         return balance(cur);
     }

     private Node findMin(Node cur) {
         return cur.left != null ? findMin(cur.left) : cur;
     }

     private Node findMax(Node cur) {
         return cur.right != null ? findMax(cur.right) : cur;
     }

     private Node removeMin(Node cur) {
         if (cur.left == null)
             return cur.right;

         cur.left = removeMin(cur.left);
         return balance(cur);
     }

     private Node removeMax(Node cur) {
         if (cur.right == null)
             return cur.left;

         cur.right = removeMax(cur.right);
         return balance(cur);
     }

     private Node remove(Node cur, int key) {
         if (cur == null)
             return null;

         if (key < cur.key)
             cur.left = remove(cur.left, key);
         else if (key > cur.key)
             cur.right = remove(cur.right, key);
         else { //  k == cur.key
             Node prevLeft = cur.left;
             Node prevRight = cur.right;

             if (prevRight == null)
                 return prevLeft;

             Node min = findMin(prevRight);
             min.right = removeMin(prevRight);
             min.left = prevLeft;

             return balance(min);
         }

         return balance(cur);
     }

     int orderOfKey(int key) {
         return orderOfKey(root, key);
     }

     // count < key
     private int orderOfKey(Node cur, int key) {
         if (cur == null)
             return 0;

         if (cur.key < key)
             return size(cur.left) + 1 + orderOfKey(cur.right, key);

         if(cur.key > key || (multi && cur.left!=null && cur.left.key == key))
         return orderOfKey(cur.left, key);

// cur.key == key return size(cur.left);

     }

     Integer findByOrder(int pos) {
         return size(root) > pos ? findByOrder(root, pos) : null;
     }

     // get i-th
     private int findByOrder(Node cur, int pos) {
         if (size(cur.left) > pos)
             return findByOrder(cur.left, pos);

         if (size(cur.left) == pos)
             return cur.key;

         // size(cur.left) < pos
         return findByOrder(cur.right, pos - 1 - size(cur.left));
     }
     public String toString() {
       return String.valueOf(this.root) ;
     }
    }
  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it -7 Vote: I do not like it

    I guess the function order_of_key method in C++ does the job in O(logn) time. But in java taking headSet(element).size() takes O(n) time. Isn't there any other method in java which does the same in O(logn) time?