public void clear(long index) {
        assert index >= 0;
        int prefix = (int) (index >>> Integer.SIZE);

        if (prefix == lastPrefix) {
            if (lastStorage.clear((int) index)) {
                lastPrefix = -1;
                lastStorage = null;
                // cleanup the empty storage
                storages.clear(prefix);
            }
        } else {
            SparseIntArray<E> storage = storages.get(prefix);
            if (storage != null) {
                if (storage.clear((int) index)) {
                    // cleanup the empty storage
                    storages.clear(prefix);
                } else {
                    lastPrefix = prefix;
                    lastStorage = storage;
                }
            }
        }
    }
@Test
    public void testClear() {
        // try to clear empty array
        actual.clear();
        verify();

        // at the beginning
        for (long i = 0; i < 1000; ++i) {
            set(i);
        }
        for (long i = 0; i < 1000 + 100; ++i) {
            clear(i);
            verify();
            // try nonexistent
            clear(i);
            verify();
        }

        // offset
        for (long i = 1000000; i < 1000000 + 1000; ++i) {
            set(i);
        }
        for (long i = 1000000 + 1000 + 100; i >= 1000000; --i) {
            clear(i);
            verify();
            // try nonexistent
            clear(i);
            verify();
        }

        // test empty again
        actual.clear();
        verify();

        // try gaps
        for (long i = 0; i < 1000; ++i) {
            set(i * i);
        }
        for (long i = 0; i < 1000; ++i) {
            clear(i * i);
            verify();
        }

        // try larger gaps
        for (long i = (long) Math.sqrt(Long.MAX_VALUE) - 1000; i < (long) Math.sqrt(Long.MAX_VALUE); ++i) {
            set(i * i);
        }
        for (long i = (long) Math.sqrt(Long.MAX_VALUE) - 1000; i < (long) Math.sqrt(Long.MAX_VALUE); ++i) {
            clear(i * i);
            verify();
        }

        // try larger 2-element gaps
        for (long i = (long) Math.sqrt(Long.MAX_VALUE) - 1000; i < (long) Math.sqrt(Long.MAX_VALUE); ++i) {
            set(i * i);
            set(i * i - 1);
        }
        for (long i = (long) Math.sqrt(Long.MAX_VALUE) - 1000; i < (long) Math.sqrt(Long.MAX_VALUE); ++i) {
            clear(i * i);
            verify();
            clear(i * i - 1);
            verify();
        }

        // try some edge cases
        for (long i = 0; i <= 2; ++i) {
            set(i);
        }
        for (long i = 0; i <= 2; ++i) {
            clear(i);
            verify();
        }
        for (long i = Short.MAX_VALUE - 2; i <= Short.MAX_VALUE + 2; ++i) {
            set(i);
        }
        for (long i = Short.MAX_VALUE - 2; i <= Short.MAX_VALUE + 2; ++i) {
            clear(i);
            verify();
        }
        for (long i = Integer.MAX_VALUE - 2; i <= (long) Integer.MAX_VALUE + 2; ++i) {
            set(i);
        }
        for (long i = Integer.MAX_VALUE - 2; i <= (long) Integer.MAX_VALUE + 2; ++i) {
            clear(i);
            verify();
        }
        for (long i = Long.MAX_VALUE; i >= Long.MAX_VALUE - 2; --i) {
            set(i);
        }
        for (long i = Long.MAX_VALUE; i >= Long.MAX_VALUE - 2; --i) {
            clear(i);
            verify();
        }
    }