
/*
 * Copyright (C) 2014 Archie L. Cobbs. All rights reserved.
 *
 * $Id$
 */

package org.jsimpledb.kv.util;

import com.google.common.base.Preconditions;

import java.io.EOFException;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;

import org.jsimpledb.util.LongEncoder;
import org.jsimpledb.util.UnsignedIntEncoder;

/**
 * Serializes a sequence of {@code byte[]} arrays, compressing common prefixes.
 *
 * <p>
 * Keys are encoded in one of two forms:
 *  <ul>
 *  <li>{@code total-length bytes...}
 *  <li>{@code -prefix-length suffix-length suffix-bytes ...}
 *  </ul>
 * The first length ({@code total-length} or negative {@code prefix-length}) is encoded using {@link LongEncoder}.
 * The {@code suffix-length}, if present, is encoded using {@link UnsignedIntEncoder}.
 */
public final class KeyListEncoder {

    private KeyListEncoder() {
    }

    /**
     * Write the next key, compressing its common prefix with the previous key (if any).
     *
     * @param out output stream
     * @param key key to write
     * @param prev previous key, or null for none
     * @throws IOException if an I/O error occurs
     * @throws IllegalArgumentException if {@code out} or {@code key} is null
     */
    public static void write(OutputStream out, byte[] key, byte[] prev) throws IOException {
        Preconditions.checkArgument(out != null, "null out");
        Preconditions.checkArgument(key != null, "null key");
        int prefixLength = 0;
        if (prev != null) {
            while (prefixLength < key.length && prefixLength < prev.length && key[prefixLength] == prev[prefixLength])
                prefixLength++;
        }
        if (prefixLength > 1) {
            final int suffixLength = key.length - prefixLength;
            LongEncoder.write(out, -prefixLength);
            UnsignedIntEncoder.write(out, suffixLength);
            out.write(key, prefixLength, suffixLength);
        } else {
            LongEncoder.write(out, key.length);
            out.write(key);
        }
    }

    /**
     * Calculate the number of bytes that would be required to write the next key via {@link #write write()}.
     *
     * @param key key to write
     * @param prev previous key, or null for none
     * @return number of bytes to be written by {@link #write write(out, key, prev)}
     * @throws IllegalArgumentException if {@code key} is null
     */
    public static int writeLength(byte[] key, byte[] prev) {
        Preconditions.checkArgument(key != null, "null key");
        int prefixLength = 0;
        if (prev != null) {
            while (prefixLength < key.length && prefixLength < prev.length && key[prefixLength] == prev[prefixLength])
                prefixLength++;
        }
        if (prefixLength > 1) {
            final int suffixLength = key.length - prefixLength;
            return LongEncoder.encodeLength(-prefixLength) + UnsignedIntEncoder.encodeLength(suffixLength) + suffixLength;
        } else
            return LongEncoder.encodeLength(key.length) + key.length;
    }

    /**
     * Read the next key.
     *
     * @param input input stream
     * @param prev previous key, or null for none
     * @return next key
     * @throws IOException if an I/O error occurs
     * @throws EOFException if an unexpected EOF is encountered
     * @throws IllegalArgumentException if {@code input} is null
     * @throws IllegalArgumentException if {@code input} contains invalid data
     */
    public static byte[] read(InputStream input, byte[] prev) throws IOException {
        Preconditions.checkArgument(input != null, "null input");
        int keyLength = KeyListEncoder.readSignedInt(input);
        final byte[] key;
        if (keyLength < 0) {
            if (prev == null)
                throw new IllegalArgumentException("null `prev' given but next key has " + -keyLength + " byte shared prefix");
            final int prefixLength = -keyLength;
            final int suffixLength = UnsignedIntEncoder.read(input);
            keyLength = prefixLength + suffixLength;
            if (keyLength < 0)
                throw new IllegalArgumentException("invalid prefix length " + prefixLength + " plus suffix length " + suffixLength);
            key = new byte[keyLength];
            System.arraycopy(prev, 0, key, 0, prefixLength);
            final int num = input.read(key, prefixLength, suffixLength);
            if (num < suffixLength)
                throw new EOFException();
        } else {
            key = new byte[keyLength];
            final int num = input.read(key);
            if (num < key.length)
                throw new EOFException();
        }
        return key;
    }

    private static int readSignedInt(InputStream input) throws IOException {
        final long longValue = LongEncoder.read(input);
        final int intValue = (int)longValue;
        Preconditions.checkArgument(intValue == (int)longValue, "read out-of-range encoded int value %s", longValue);
        return intValue;
    }
}


@@ -1807,17 +1807,18 @@
 te(out, 
--
+~(
 prefixLe
@@ -1813,32 +1813,37 @@
 , ~(prefixLength
+ - 2)
 );%0A            U
@@ -2896,17 +2896,18 @@
 eLength(
--
+~(
 prefixLe
@@ -2906,24 +2906,29 @@
 prefixLength
+ - 2)
 ) + Unsigned
@@ -3631,24 +3631,65 @@
 ull input%22);
+%0A%0A        // Get encoded length of prefix
 %0A        int
@@ -3760,24 +3760,107 @@
 byte%5B%5D key;%0A
+        int prefixLength;%0A%0A        // Decode prefix length and read prefix, if any%0A
         if (
@@ -4046,26 +4046,16 @@
         
-final int 
 prefixLe
@@ -4061,17 +4061,17 @@
 ength = 
--
+~
 keyLengt
@@ -4067,24 +4067,28 @@
 = ~keyLength
+ + 2
 ;%0A          
@@ -4475,71 +4475,54 @@
     
-    final int num = input.read(key, prefixLength, suffixLength)
+%7D else %7B%0A            key = new byte%5BkeyLength%5D
 ;%0A  
@@ -4535,21 +4535,11 @@
     
-if (num %3C suf
+pre
 fixL
@@ -4539,25 +4539,29 @@
 prefixLength
-)
+ = 0;
 %0A           
@@ -4553,32 +4553,35 @@
  0;%0A        
+%7D%0A%0A
         
 throw new EO
@@ -4572,89 +4572,66 @@
     
-throw new EOFException();%0A        %7D else %7B%0A            key = new byte%5BkeyL
+// Read suffix%0A        while (prefixLength %3C key.l
 ength
-%5D;
+) %7B
 %0A   
@@ -4665,24 +4665,65 @@
 put.read(key
+, prefixLength, key.length - prefixLength
 );%0A         
@@ -4733,28 +4733,21 @@
 if (num 
-%3C key.length
+== -1
 )%0A      
@@ -4782,33 +4782,83 @@
 tion();%0A        
-%7D
+    prefixLength += num;%0A        %7D%0A%0A        // Done
 %0A        return 

Tweak encoding; fix bugs.