support reverse iteration

[subes]

leveldbjni supports reverse iteration: https://github.com/fusesource/leveldbjni/blob/master/leveldbjni/src/main/java/org/fusesource/leveldbjni/internal/JniDBIterator.java

so it would be nice if ezdb would have api methods that make this functionality available aswell.

e.g. next to range(...) methods, also rangeReversed(...) or having another parameter in the range(...) method to enable reverse. Or make the iterator returned one that has seekFirst, seekLast, next, prev.

For the pure java version of leveldb there is this ticket: dain/leveldb#8
The APi method for this is available, it's just that it will throw UnsupportedOperationException for now: https://github.com/dain/leveldb/blob/master/leveldb/src/main/java/org/iq80/leveldb/impl/SeekingIteratorAdapter.java

[subes]

Here are my proposed methods for this:

public TableIterator<H, R, V> rangeReverse(final H hashKey) {
    final DBIterator iterator = db.iterator();
    final byte[] keyBytesFrom = Util.combine(hashKeySerde, rangeKeySerde, hashKey, null);
    iterator.seek(keyBytesFrom);
    Entry<byte[], byte[]> last = null;
    while (iterator.hasNext()
            && Util.compareKeys(hashKeyComparator, null, keyBytesFrom, iterator.peekNext().getKey()) == 0) {
        last = iterator.next();
    }
    //if there is no last one, there is nothing at all in the table
    if (last == null) {
        return new TableIterator<H, R, V>() {

            @Override
            public boolean hasNext() {
                return false;
            }

            @Override
            public TableRow<H, R, V> next() {
                throw new NoSuchElementException();
            }

            @Override
            public void remove() {
                throw new NoSuchElementException();
            }

            @Override
            public void close() {}
        };
    }
    //since last has been found, seek again for that one
    iterator.seek(last.getKey());

    return new TableIterator<H, R, V>() {

        private boolean fixFirst = true;;

        @Override
        public boolean hasNext() {
            if (useFixFirst()) {
                return true;
            }
            return iterator.hasPrev()
                    && Util.compareKeys(hashKeyComparator, null, keyBytesFrom, iterator.peekPrev().getKey()) == 0;
        }

        public boolean useFixFirst() {
            if (fixFirst && iterator.hasNext()) {
                fixFirst = false;
                final Entry<byte[], byte[]> peekNext = iterator.peekNext();
                if (peekNext != null) {
                    if (Util.compareKeys(hashKeyComparator, null, keyBytesFrom, peekNext.getKey()) == 0) {
                        return true;
                    } else {
                        fixFirst = false;
                    }
                }
            }
            return false;
        }

        @Override
        public TableRow<H, R, V> next() {
            if (useFixFirst()) {
                return new RawTableRow<H, R, V>(iterator.peekNext(), hashKeySerde, rangeKeySerde, valueSerde);
            }
            return new RawTableRow<H, R, V>(iterator.prev(), hashKeySerde, rangeKeySerde, valueSerde);
        }

        @Override
        public void remove() {
            if (useFixFirst()) {
                throw new UnsupportedOperationException("Not possible on first result for now...");
            }
            iterator.remove();
        }

        @Override
        public void close() {
            try {
                iterator.close();
            } catch (final Exception e) {
                throw new DbException(e);
            }
        }
    };
}

public TableIterator<H, R, V> rangeReverse(final H hashKey, final R fromRangeKey) {
    final DBIterator iterator = db.iterator();
    final byte[] keyBytesFrom = Util.combine(hashKeySerde, rangeKeySerde, hashKey, fromRangeKey);
    iterator.seek(keyBytesFrom);
    return new TableIterator<H, R, V>() {

        private boolean fixFirst = true;

         @Override
        public boolean hasNext() {
            if (useFixFirst()) {
                return true;
            }
            return iterator.hasPrev()
                    && Util.compareKeys(hashKeyComparator, null, keyBytesFrom, iterator.peekPrev().getKey()) == 0;
        }

        public boolean useFixFirst() {
            if (fixFirst && iterator.hasNext()) {
                fixFirst = false;
                final Entry<byte[], byte[]> peekNext = iterator.peekNext();
                if (peekNext != null) {
                    if (Util.compareKeys(hashKeyComparator, null, keyBytesFrom, peekNext.getKey()) == 0) {
                        return true;
                    } else {
                        fixFirst = false;
                    }
                }
            }
            return false;
        }

        @Override
        public TableRow<H, R, V> next() {
            if (useFixFirst()) {
                return new RawTableRow<H, R, V>(iterator.peekNext(), hashKeySerde, rangeKeySerde, valueSerde);
            }
            return new RawTableRow<H, R, V>(iterator.prev(), hashKeySerde, rangeKeySerde, valueSerde);
        }

        @Override
        public void remove() {
            if (useFixFirst()) {
                throw new UnsupportedOperationException("Not possible on first result for now...");
            }
            iterator.remove();
        }

        @Override
        public void close() {
            try {
                iterator.close();
            } catch (final Exception e) {
                throw new DbException(e);
            }
        }
    };
}

public TableIterator<H, R, V> rangeReverse(final H hashKey, final R fromRangeKey, final R toRangeKey) {
    final DBIterator iterator = db.iterator();
    final byte[] keyBytesFrom = Util.combine(hashKeySerde, rangeKeySerde, hashKey, fromRangeKey);
    final byte[] keyBytesTo = Util.combine(hashKeySerde, rangeKeySerde, hashKey, toRangeKey);
    iterator.seek(keyBytesFrom);
    return new TableIterator<H, R, V>() {

        private boolean fixFirst = true;

        @Override
        public boolean hasNext() {
            if (useFixFirst()) {
                return true;
            }
            return iterator.hasPrev()
                    && Util.compareKeys(hashKeyComparator, rangeKeyComparator, keyBytesTo, iterator.peekPrev()
                            .getKey()) < 0;
        }

        public boolean useFixFirst() {
            if (fixFirst && iterator.hasNext()) {
                fixFirst = false;
                final Entry<byte[], byte[]> peekNext = iterator.peekNext();
                if (peekNext != null) {
                    if (Util.compareKeys(hashKeyComparator, rangeKeyComparator, keyBytesTo, peekNext.getKey()) <= 0) {
                        return true;
                    } else {
                        fixFirst = false;
                    }
                }
            }
            return false;
        }

        @Override
        public TableRow<H, R, V> next() {
            if (useFixFirst()) {
                return new RawTableRow<H, R, V>(iterator.peekNext(), hashKeySerde, rangeKeySerde, valueSerde);
            }
            return new RawTableRow<H, R, V>(iterator.prev(), hashKeySerde, rangeKeySerde, valueSerde);
        }

        @Override
        public void remove() {
            if (useFixFirst()) {
                throw new UnsupportedOperationException("Not possible on first result for now...");
            }
            iterator.remove();
        }

        @Override
        public void close() {
            try {
                iterator.close();
            } catch (final Exception e) {
                throw new DbException(e);
            }
        }
    };
}

They are tested to work fine for me. I don't use remove, so I've just disabled it for the useFixFirst special case for the result to spare me the effort of finding out how to do that properly.

UseFixFirst works as follows:
in a set of 1,2,3 and a query starting from 3. Without the useFixFirst workaround this would iterate 2,1. With useFixFirst workaround this correctly iterates 3,2,1.

[criccomini]

Hey Subes,

This is great. The only recommendation that I have is making the useFixFirst method private. It mutates state, and shouldn't allow others to call it.

If you want to patch this, and send a pull request over, I'll merge it in. With the patch, please include:

• Tests
• Javadocs for the UseFixFirst function.

Cheers,
Chris

[subes]

Since the code has been migrated, this issue can be closed.