package ru.ifmo.nds.util.veb;

final class IntIntBitSet extends VanEmdeBoasSet {
    private static final int limit = 1 << 10;
    private final int[] clusters;
    private int summary;
    private int min, max;

    IntIntBitSet(int scale) {
        min = limit;
        max = -1;
        clusters = new int[1 << (scale - 5)];
        summary = 0;
    }

    @Override
    public boolean isEmpty() {
        return max == -1;
    }

    @Override
    public int min() {
        return min;
    }

    @Override
    public int max() {
        return max;
    }

    @Override
    public int prev(int index) {
        if (index <= min) {
            return -1;
        }
        if (index > max) {
            return max;
        }
        int h = hi(index);
        int chs = (clusters[h] << ~index) << 1;
        if (chs == 0) {
            h = VanEmdeBoasSet.prev(summary, h);
            return h < 0 ? min : join(h, VanEmdeBoasSet.max(clusters[h]));
        } else {
            return index - 1 - Integer.numberOfLeadingZeros(chs);
        }
    }

    @Override
    public int prevInclusively(int index) {
        if (index <= min) {
            // same as "index == min ? min : -1"
            return min | ((index - min) >> 31);
        }
        if (index >= max) {
            return max;
        }
        int h = hi(index);
        int chs = clusters[h] << ~index;
        if (chs == 0) {
            h = VanEmdeBoasSet.prev(summary, h);
            return h < 0 ? min : join(h, VanEmdeBoasSet.max(clusters[h]));
        } else {
            return index - Integer.numberOfLeadingZeros(chs);
        }
    }

    @Override
    public int next(int index) {
        if (index >= max) {
            return limit;
        }
        if (index < min) {
            return min;
        }
        int h = hi(index);
        int chs = (clusters[h] >>> index) >>> 1;
        if (chs == 0) {
            h = VanEmdeBoasSet.next(summary, h);
            return h >= clusters.length ? max : join(h, VanEmdeBoasSet.min(clusters[h]));
        } else {
            return index + 1 + Integer.numberOfTrailingZeros(chs);
        }
    }

    @Override
    public void add(int index) {
        if (max < 0) {
            min = max = index;
        } else if (min == max && index != min) {
            if (index < min) {
                min = index;
            } else {
                max = index;
            }
        } else if (index != min && index != max) {
            if (index < min) {
                int tmp = min;
                min = index;
                index = tmp;
            }
            if (index > max) {
                int tmp = max;
                max = index;
                index = tmp;
            }
            int h = hi(index);
            if (clusters[h] == 0) {
                summary |= 1 << h;
            }
            clusters[h] |= 1 << index;
        }
    }

    @Override
    public void remove(int index) {
        if (index == min) {
            if (index == max) {
                min = limit;
                max = -1;
            } else {
                int newMin = next(min);
                if (newMin != max) {
                    remove(newMin);
                }
                min = newMin;
            }
        } else if (index == max) {
            int newMax = prev(max);
            if (newMax != min) {
                remove(newMax);
            }
            max = newMax;
        } else if (min < index && index < max) {
            int h = hi(index);
            clusters[h] &= ~(1 << index);
            if (clusters[h] == 0) {
                summary &= ~(1 << h);
            }
        }
    }

    @Override
    public void clear() {
        min = limit;
        max = -1;
        for (int i = VanEmdeBoasSet.min(summary); i < clusters.length; i = VanEmdeBoasSet.next(summary, i)) {
            clusters[i] = 0;
        }
        summary = 0;
    }

    private boolean cleanupMidMax(int from, int offset, int value, int[] values) {
        if (summary != 0) {
            for (int i = from == -1 ? VanEmdeBoasSet.min(summary) : VanEmdeBoasSet.next(summary, from);
                     i < clusters.length;
                     i = VanEmdeBoasSet.next(summary, i)) {
                clusters[i] = VanEmdeBoasSet.cleanupUpwards(clusters[i], offset + (i << 5), value, values);
                if (clusters[i] == 0) {
                    summary ^= 1 << i;
                } else {
                    return false;
                }
            }
        }
        return values[offset + max] <= value;
    }

    @Override
    public void setEnsuringMonotonicity(int index, int offset, int value, int[] values) {
        if (min == max) {
            // Only one element is stored. Consider where we fall...
            if (index < min) {
                values[offset + index] = value;
                min = index;
                if (values[offset + max] <= value) {
                    max = index;
                }
            } else if (index == min) {
                int oi = offset + index;
                if (values[oi] < value) {
                    values[oi] = value;
                }
            } else {
                if (values[offset + min] < value) {
                    values[offset + index] = value;
                    max = index;
                }
            }
        } else if (max == -1) {
            // The set was empty. Just set the value.
            min = index;
            max = index;
            values[offset + index] = value;
        } else {
            if (index < min) {
                // First of all, insert ourselves.
                values[offset + index] = value;
                int oldMin = min;
                min = index;

                if (values[offset + oldMin] > value) {
                    // Add the old minimum and break out.
                    int h = hi(oldMin);
                    clusters[h] |= 1 << oldMin;
                    summary |= 1 << h;
                } else {
                    // Do not add the old minimum, as it is dominated.
                    if (cleanupMidMax(-1, offset, value, values)) {
                        max = min;
                    }
                }
            } else if (index == min) {
                int idx = offset + index;
                if (values[idx] < value) {
                    // Replace the value at the minimum, clean up the tail.
                    values[idx] = value;
                    if (cleanupMidMax(-1, offset, value, values)) {
                        max = min;
                    }
                }
            } else if (max <= index) {
                // We either replace max or add a new index after max
                if (values[offset + max] < value) {
                    values[offset + index] = value;
                    if (max != index) {
                        int oldMax = max;
                        max = index;
                        add(oldMax);
                    }
                }
            } else if (summary == 0) {
                if (values[offset + min] < value) {
                    values[offset + index] = value;
                    if (values[offset + max] > value) {
                        // Normal insertion
                        int h = hi(index);
                        clusters[h] |= 1 << index;
                        summary |= 1 << h;
                    } else {
                        // Replacement of max
                        max = index;
                    }
                }
            } else {
                int h = hi(index);
                int ch = clusters[h];
                int greaterThanCurrentMask = (-1 << index) << 1;
                int upTo = ch & ~greaterThanCurrentMask;
                if (upTo == 0) {
                    int hPrev = VanEmdeBoasSet.prev(summary, h);
                    int iPrev = hPrev == -1 ? min : join(hPrev, VanEmdeBoasSet.max(clusters[hPrev]));
                    if (values[offset + iPrev] >= value) {
                        return;
                    }
                } else {
                    int lPrev = 31 - Integer.numberOfLeadingZeros(upTo);
                    if (values[offset + (h << 5) + lPrev] >= value) {
                        return;
                    }
                }
                summary |= 1 << h;
                ch = VanEmdeBoasSet.setEnsuringMonotonicity(ch, index & 31, offset + (h << 5), value, values);
                values[offset + index] = value;
                if ((ch & greaterThanCurrentMask) == 0) {
                    if (cleanupMidMax(h, offset, value, values)) {
                        max = index;
                        ch ^= 1 << index;
                        if (ch == 0) {
                            summary ^= 1 << h;
                        }
                    }
                }
                clusters[h] = ch;
            }
        }
    }

    @Override
    void cleanupUpwards(int offset, int value, int[] values) {
        if (values[offset + max] <= value) {
            clear();
        } else if (values[offset + min] <= value) {
            if (summary != 0) {
                // need to cleanup at least something
                for (int i = VanEmdeBoasSet.min(summary); i < clusters.length; i = VanEmdeBoasSet.next(summary, i)) {
                    int ci = clusters[i];
                    ci = VanEmdeBoasSet.cleanupUpwards(ci, offset + (i << 5), value, values);
                    if (ci != 0) {
                        int min = VanEmdeBoasSet.min(ci);
                        this.min = min + (i << 5);
                        ci ^= 1 << min;
                        if (ci == 0) {
                            summary ^= 1 << i;
                        }
                        return;
                    }
                    clusters[i] = ci;
                    summary ^= 1 << i;
                }
            }
            // summary == 0 here
            min = max;
        }
    }

    private static int hi(int index) {
        return index >>> 5;
    }
    private static int join(int hi, int lo) {
        return (hi << 5) ^ lo;
    }
}
