package ru.ifmo.nds.util;

import java.util.Arrays;

public final class FenwickRankQueryStructure extends RankQueryStructure {
    private final double[] keys;
    private final int[] values;

    public FenwickRankQueryStructure(int maximumSize) {
        keys = new double[maximumSize];
        values = new int[maximumSize];
    }

    @Override
    public RangeHandle createHandle(int storageStart, int from, int until, int[] indices, double[] keys) {
        return new RangeHandleImpl(storageStart, from, until, indices, keys);
    }

    private class RangeHandleImpl extends RankQueryStructure.RangeHandle {
        private final int size;
        private final int offset;

        private RangeHandleImpl(int storageStart, int from, int until, int[] indices, double[] k) {
            this.offset = storageStart;
            for (int i = from, j = offset; i < until; ++i, ++j) {
                keys[j] = k[indices[i]];
            }
            int storageEnd = storageStart + until - from;
            Arrays.sort(keys, storageStart, storageEnd);
            int realSize = 1;
            for (int i = storageStart + 1; i < storageEnd; ++i) {
                if (keys[i] != keys[i - 1]) {
                    keys[offset + realSize++] = keys[i];
                }
            }
            size = realSize;
            Arrays.fill(values, offset, offset + size, -1);
        }

        private int indexFor(double key) {
            int left = -1, right = size;
            while (right - left > 1) {
                int mid = (left + right) >>> 1;
                if (keys[offset + mid] <= key) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            return left;

        }

        @Override
        public void put(double key, int value) {
            int fwi = indexFor(key);
            while (fwi < size) {
                values[offset + fwi] = Math.max(values[offset + fwi], value);
                fwi |= fwi + 1;
            }
        }

        @Override
        public int getMaximumWithKeyAtMost(double key, int minimumMeaningfulAnswer) {
            int fwi = indexFor(key);
            if (fwi >= size || fwi < 0) {
                return -1;
            } else {
                int rv = -1;
                while (fwi >= 0) {
                    rv = Math.max(rv, values[offset + fwi]);
                    fwi = (fwi & (fwi + 1)) - 1;
                }
                return rv;
            }
        }
    }
}

@@ -1072,20 +1072,70 @@
 int 
-realSize = 1
+uniqueEnd = offset + 1;%0A            double prev = keys%5Boffset%5D
 ;%0A  
@@ -1218,113 +1218,155 @@
     
-if (keys%5Bi%5D != keys%5Bi - 1%5D) %7B%0A                    keys%5Boffset + realSize++%5D = keys%5Bi%5D;%0A                %7D%0A
+double curr = keys%5Bi%5D;%0A                if (curr != prev) %7B%0A                    keys%5BuniqueEnd%5D = prev = curr;%0A                    ++uniqueEnd;%0A    
     
@@ -1391,24 +1391,9 @@
     
-size = realSize;
+%7D
 %0A   
@@ -1433,26 +1433,61 @@
 et, 
-offset + size, -1)
+uniqueEnd, -1);%0A            size = uniqueEnd - offset
 ;%0A  
@@ -1561,17 +1561,25 @@
  left = 
--
+offset - 
 1, right
@@ -1580,16 +1580,25 @@
  right =
+ offset +
  size;%0A 
@@ -1708,25 +1708,16 @@
 f (keys%5B
-offset + 
 mid%5D %3C= 
@@ -1868,18 +1868,26 @@
 urn left
+ - offset
 ;
-%0A
 %0A       
@@ -2043,23 +2043,26 @@
         
-values%5B
+int idx = 
 offset +
@@ -2065,16 +2065,44 @@
 et + fwi
+;%0A                values%5Bidx
 %5D = Math
@@ -2113,28 +2113,19 @@
 (values%5B
-offset + fwi
+idx
 %5D, value
@@ -2329,102 +2329,8 @@
 y);%0A
-            if (fwi %3E= size %7C%7C fwi %3C 0) %7B%0A                return -1;%0A            %7D else %7B%0A    
     
@@ -2354,36 +2354,32 @@
 -1;%0A            
-  
-  
 while (fwi %3E= 0)
@@ -2377,28 +2377,24 @@
 fwi %3E= 0) %7B%0A
-    
             
@@ -2450,28 +2450,24 @@
             
-  
-  
 fwi = (fwi &
@@ -2491,32 +2491,26 @@
             
-    %7D%0A  
+%7D%0A
             
@@ -2505,26 +2505,24 @@
             
-  
 return rv;%0A 
@@ -2520,30 +2520,16 @@
 urn rv;%0A
-            %7D%0A
         

Improve FenwickRQS.