FlexBuffers.java

/*
 * Copyright 2014 Google Inc. All rights reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.flatbuffers;


import static com.google.flatbuffers.FlexBuffers.Unsigned.byteToUnsignedInt;
import static com.google.flatbuffers.FlexBuffers.Unsigned.intToUnsignedLong;
import static com.google.flatbuffers.FlexBuffers.Unsigned.shortToUnsignedInt;

import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;

/// @file
/// @addtogroup flatbuffers_java_api
/// @{

/**
 * This class can be used to parse FlexBuffer messages.
 * <p>
 * For generating FlexBuffer messages, use {@link FlexBuffersBuilder}.
 * <p>
 * Example of usage:
 * <pre>
 * ReadBuf bb = ... // load message from file or network
 * FlexBuffers.Reference r = FlexBuffers.getRoot(bb); // Reads the root element
 * FlexBuffers.Map map = r.asMap(); // We assumed root object is a map
 * System.out.println(map.get("name").asString()); // prints element with key "name"
 * </pre>
 */
public class FlexBuffers {

    // These are used as the upper 6 bits of a type field to indicate the actual
    // type.
    /** Represent a null type */
    public static final int FBT_NULL = 0;
    /** Represent a signed integer type */
    public static final int FBT_INT = 1;
    /** Represent a unsigned type */
    public static final int FBT_UINT = 2;
    /** Represent a float type */
    public static final int FBT_FLOAT = 3; // Types above stored inline, types below store an offset.
    /** Represent a key to a map type */
    public static final int FBT_KEY = 4;
    /** Represent a string type */
    public static final int FBT_STRING = 5;
    /** Represent a indirect signed integer type */
    public static final int FBT_INDIRECT_INT = 6;
    /** Represent a indirect unsigned integer type */
    public static final int FBT_INDIRECT_UINT = 7;
    /** Represent a indirect float type */
    public static final int FBT_INDIRECT_FLOAT = 8;
    /** Represent a map type */
    public static final int FBT_MAP = 9;
    /** Represent a vector type */
    public static final int FBT_VECTOR = 10; // Untyped.
    /** Represent a vector of signed integers type */
    public static final int FBT_VECTOR_INT = 11;  // Typed any size  = stores no type table).
    /** Represent a vector of unsigned integers type */
    public static final int FBT_VECTOR_UINT = 12;
    /** Represent a vector of floats type */
    public static final int FBT_VECTOR_FLOAT = 13;
    /** Represent a vector of keys type */
    public static final int FBT_VECTOR_KEY = 14;
    /** Represent a vector of strings type */
    // DEPRECATED, use FBT_VECTOR or FBT_VECTOR_KEY instead.
    // more info on thttps://github.com/google/flatbuffers/issues/5627.
    public static final int FBT_VECTOR_STRING_DEPRECATED = 15;

    /// @cond FLATBUFFERS_INTERNAL
    public static final int FBT_VECTOR_INT2 = 16;  // Typed tuple  = no type table; no size field).
    public static final int FBT_VECTOR_UINT2 = 17;
    public static final int FBT_VECTOR_FLOAT2 = 18;
    public static final int FBT_VECTOR_INT3 = 19;  // Typed triple  = no type table; no size field).
    public static final int FBT_VECTOR_UINT3 = 20;
    public static final int FBT_VECTOR_FLOAT3 = 21;
    public static final int FBT_VECTOR_INT4 = 22;  // Typed quad  = no type table; no size field).
    public static final int FBT_VECTOR_UINT4 = 23;
    public static final int FBT_VECTOR_FLOAT4 = 24;
    /// @endcond FLATBUFFERS_INTERNAL

    /** Represent a blob type */
    public static final int FBT_BLOB = 25;
    /** Represent a boolean type */
    public static final int FBT_BOOL = 26;
    /** Represent a vector of booleans type */
    public static final int FBT_VECTOR_BOOL = 36;  // To Allow the same type of conversion of type to vector type

    private static final ReadBuf EMPTY_BB = new ArrayReadWriteBuf(new byte[] {0}, 1);

    /**
     * Checks where a type is a typed vector
     *
     * @param type type to be checked
     * @return true if typed vector
     */
    static boolean isTypedVector(int type) {
        return (type >= FBT_VECTOR_INT && type <= FBT_VECTOR_STRING_DEPRECATED) || type == FBT_VECTOR_BOOL;
    }

    /**
     * Check whether you can access type directly (no indirection) or not.
     *
     * @param type type to be checked
     * @return true if inline type
     */
    static boolean isTypeInline(int type) {
        return type <= FBT_FLOAT || type == FBT_BOOL;
    }

    static int toTypedVectorElementType(int original_type) {
        return original_type - FBT_VECTOR_INT + FBT_INT;
    }

    /**
     * Return a vector type our of a original element type
     *
     * @param type        element type
     * @param fixedLength size of element
     * @return typed vector type
     */
    static int toTypedVector(int type, int fixedLength) {
        assert (isTypedVectorElementType(type));
        switch (fixedLength) {
            case 0: return type - FBT_INT + FBT_VECTOR_INT;
            case 2: return type - FBT_INT + FBT_VECTOR_INT2;
            case 3: return type - FBT_INT + FBT_VECTOR_INT3;
            case 4: return type - FBT_INT + FBT_VECTOR_INT4;
            default:
                assert (false);
                return FBT_NULL;
        }
    }

    static boolean isTypedVectorElementType(int type) {
        return (type >= FBT_INT && type <= FBT_KEY) || type == FBT_BOOL;
    }

    // return position of the element that the offset is pointing to
    private static int indirect(ReadBuf bb, int offset, int byteWidth) {
        // we assume all offset fits on a int, since ReadBuf operates with that assumption
        return (int) (offset - readUInt(bb, offset, byteWidth));
    }

    // read unsigned int with size byteWidth and return as a 64-bit integer
    private static long readUInt(ReadBuf buff, int end, int byteWidth) {
        switch (byteWidth) {
            case 1: return byteToUnsignedInt(buff.get(end));
            case 2: return shortToUnsignedInt(buff.getShort(end));
            case 4: return intToUnsignedLong(buff.getInt(end));
            case 8: return buff.getLong(end); // We are passing signed long here. Losing information (user should know)
            default: return -1; // we should never reach here
        }
    }

    // read signed int of size byteWidth and return as 32-bit int
    private static int readInt(ReadBuf buff, int end, int byteWidth) {
        return (int) readLong(buff, end, byteWidth);
    }

    // read signed int of size byteWidth and return as 64-bit int
    private static long readLong(ReadBuf buff, int end, int byteWidth) {
        switch (byteWidth) {
            case 1: return buff.get(end);
            case 2: return buff.getShort(end);
            case 4: return buff.getInt(end);
            case 8: return buff.getLong(end);
            default: return -1; // we should never reach here
        }
    }

    private static double readDouble(ReadBuf buff, int end, int byteWidth) {
        switch (byteWidth) {
            case 4: return buff.getFloat(end);
            case 8: return buff.getDouble(end);
            default: return -1; // we should never reach here
        }
    }

    /**
     * Reads a FlexBuffer message in ReadBuf and returns {@link Reference} to
     * the root element.
     * @param buffer ReadBuf containing FlexBuffer message
     * @return {@link Reference} to the root object
     */
    @Deprecated
    public static Reference getRoot(ByteBuffer buffer) {
        return getRoot( buffer.hasArray() ? new ArrayReadWriteBuf(buffer.array(), buffer.limit()) : new ByteBufferReadWriteBuf(buffer));
    }

        /**
     * Reads a FlexBuffer message in ReadBuf and returns {@link Reference} to
     * the root element.
     * @param buffer ReadBuf containing FlexBuffer message
     * @return {@link Reference} to the root object
     */
    public static Reference getRoot(ReadBuf buffer) {
        // See Finish() below for the serialization counterpart of this.
        // The root ends at the end of the buffer, so we parse backwards from there.
        int end = buffer.limit();
        int byteWidth = buffer.get(--end);
        int packetType = byteToUnsignedInt(buffer.get(--end));
        end -= byteWidth;  // The root data item.
        return new Reference(buffer, end, byteWidth, packetType);
    }

    /**
     * Represents an generic element in the buffer.
     */
    public static class Reference {

        private static final Reference NULL_REFERENCE = new Reference(EMPTY_BB, 0, 1, 0);
        private ReadBuf bb;
        private int end;
        private int parentWidth;
        private int byteWidth;
        private int type;

        Reference(ReadBuf bb, int end, int parentWidth, int packedType) {
            this(bb, end, parentWidth, (1 << (packedType & 3)), packedType >> 2);
        }

        Reference(ReadBuf bb, int end, int parentWidth, int byteWidth, int type) {
            this.bb = bb;
            this.end = end;
            this.parentWidth = parentWidth;
            this.byteWidth = byteWidth;
            this.type = type;
        }

        /**
         * Return element type
         * @return element type as integer
         */
        public int getType() {
            return type;
        }

        /**
         * Checks whether the element is null type
         * @return true if null type
         */
        public boolean isNull() {
            return type == FBT_NULL;
        }

        /**
         * Checks whether the element is boolean type
         * @return true if boolean type
         */
        public boolean isBoolean() {
            return type == FBT_BOOL;
        }

        /**
         * Checks whether the element type is numeric (signed/unsigned integers and floats)
         * @return true if numeric type
         */
        public boolean isNumeric() {
            return isIntOrUInt() || isFloat();
        }

        /**
         * Checks whether the element type is signed or unsigned integers
         * @return true if an integer type
         */
        public boolean isIntOrUInt() {
            return isInt() || isUInt();
        }

        /**
         * Checks whether the element type is float
         * @return true if a float type
         */
        public boolean isFloat() {
            return type == FBT_FLOAT || type == FBT_INDIRECT_FLOAT;
        }

        /**
         * Checks whether the element type is signed integer
         * @return true if a signed integer type
         */
        public boolean isInt() {
            return type == FBT_INT || type == FBT_INDIRECT_INT;
        }

        /**
         * Checks whether the element type is signed integer
         * @return true if a signed integer type
         */
        public boolean isUInt() {
            return type == FBT_UINT || type == FBT_INDIRECT_UINT;
        }

        /**
         * Checks whether the element type is string
         * @return true if a string type
         */
        public boolean isString() {
            return type == FBT_STRING;
        }

        /**
         * Checks whether the element type is key
         * @return true if a key type
         */
        public boolean isKey() {
            return type == FBT_KEY;
        }

        /**
         * Checks whether the element type is vector
         * @return true if a vector type
         */
        public boolean isVector() {
            return type == FBT_VECTOR || type == FBT_MAP;
        }

        /**
         * Checks whether the element type is typed vector
         * @return true if a typed vector type
         */
        public boolean isTypedVector() {
            return FlexBuffers.isTypedVector(type);
        }

        /**
         * Checks whether the element type is a map
         * @return true if a map type
         */
        public boolean isMap() {
            return type == FBT_MAP;
        }

        /**
         * Checks whether the element type is a blob
         * @return true if a blob type
         */
        public boolean isBlob() {
            return type == FBT_BLOB;
        }

        /**
         * Returns element as 32-bit integer.
         * <p> For vector element, it will return size of the vector</p>
         * <p> For String element, it will type to be parsed as integer</p>
         * <p> Unsigned elements will become negative</p>
         * <p> Float elements will be casted to integer </p>
         * @return 32-bit integer or 0 if fail to convert element to integer.
         */
        public int asInt() {
            if (type == FBT_INT) {
                // A fast path for the common case.
                return readInt(bb, end, parentWidth);
            } else
                switch (type) {
                    case FBT_INDIRECT_INT: return readInt(bb, indirect(bb, end, parentWidth), byteWidth);
                    case FBT_UINT: return (int) readUInt(bb, end, parentWidth);
                    case FBT_INDIRECT_UINT: return (int) readUInt(bb, indirect(bb, end, parentWidth), parentWidth);
                    case FBT_FLOAT: return (int) readDouble(bb, end, parentWidth);
                    case FBT_INDIRECT_FLOAT: return (int) readDouble(bb, indirect(bb, end, parentWidth), byteWidth);
                    case FBT_NULL: return 0;
                    case FBT_STRING: return Integer.parseInt(asString());
                    case FBT_VECTOR: return asVector().size();
                    case FBT_BOOL: return readInt(bb, end, parentWidth);
                    default:
                        // Convert other things to int.
                        return 0;
                }
        }

        /**
         * Returns element as unsigned 64-bit integer.
         * <p> For vector element, it will return size of the vector</p>
         * <p> For String element, it will type to be parsed as integer</p>
         * <p> Negative signed elements will become unsigned counterpart</p>
         * <p> Float elements will be casted to integer </p>
         * @return 64-bit integer or 0 if fail to convert element to integer.
         */
        public long asUInt() {
            if (type == FBT_UINT) {
                // A fast path for the common case.
                return readUInt(bb, end, parentWidth);
            } else
                switch (type) {
                    case FBT_INDIRECT_UINT: return readUInt(bb, indirect(bb, end, parentWidth), byteWidth);
                    case FBT_INT: return readLong(bb, end, parentWidth);
                    case FBT_INDIRECT_INT: return readLong(bb, indirect(bb, end, parentWidth), byteWidth);
                    case FBT_FLOAT: return (long) readDouble(bb, end, parentWidth);
                    case FBT_INDIRECT_FLOAT: return (long) readDouble(bb,  indirect(bb, end, parentWidth), parentWidth);
                    case FBT_NULL: return 0;
                    case FBT_STRING: return Long.parseLong(asString());
                    case FBT_VECTOR: return asVector().size();
                    case FBT_BOOL: return readInt(bb, end, parentWidth);
                    default:
                        // Convert other things to uint.
                        return 0;
                }
        }

        /**
         * Returns element as 64-bit integer.
         * <p> For vector element, it will return size of the vector</p>
         * <p> For String element, it will type to be parsed as integer</p>
         * <p> Unsigned elements will become negative</p>
         * <p> Float elements will be casted to integer </p>
         * @return 64-bit integer or 0 if fail to convert element to long.
         */
        public long asLong() {
            if (type == FBT_INT) {
                // A fast path for the common case.
                return readLong(bb, end, parentWidth);
            } else
                switch (type) {
                    case FBT_INDIRECT_INT: return readLong(bb, indirect(bb, end, parentWidth), byteWidth);
                    case FBT_UINT: return readUInt(bb, end, parentWidth);
                    case FBT_INDIRECT_UINT: return readUInt(bb, indirect(bb, end, parentWidth), parentWidth);
                    case FBT_FLOAT: return (long) readDouble(bb, end, parentWidth);
                    case FBT_INDIRECT_FLOAT: return (long) readDouble(bb, indirect(bb, end, parentWidth), byteWidth);
                    case FBT_NULL: return 0;
                    case FBT_STRING: {
                        try {
                            return Long.parseLong(asString());
                        } catch (NumberFormatException nfe) {
                            return 0; //same as C++ implementation
                        }
                    }
                    case FBT_VECTOR: return asVector().size();
                    case FBT_BOOL: return readInt(bb, end, parentWidth);
                    default:
                        // Convert other things to int.
                        return 0;
                }
        }

        /**
         * Returns element as 64-bit integer.
         * <p> For vector element, it will return size of the vector</p>
         * <p> For String element, it will type to be parsed as integer</p>
         * @return 64-bit integer or 0 if fail to convert element to long.
         */
        public double asFloat() {
            if (type == FBT_FLOAT) {
                // A fast path for the common case.
                return readDouble(bb, end, parentWidth);
            } else
                switch (type) {
                    case FBT_INDIRECT_FLOAT: return readDouble(bb, indirect(bb, end, parentWidth), byteWidth);
                    case FBT_INT: return readInt(bb, end, parentWidth);
                    case FBT_UINT:
                    case FBT_BOOL:
                        return readUInt(bb, end, parentWidth);
                    case FBT_INDIRECT_INT: return readInt(bb, indirect(bb, end, parentWidth), byteWidth);
                    case FBT_INDIRECT_UINT: return readUInt(bb, indirect(bb, end, parentWidth), byteWidth);
                    case FBT_NULL: return 0.0;
                    case FBT_STRING: return Double.parseDouble(asString());
                    case FBT_VECTOR: return asVector().size();
                    default:
                        // Convert strings and other things to float.
                        return 0;
                }
        }

        /**
         * Returns element as a {@link Key}
         * @return key or {@link Key#empty()} if element is not a key
         */
        public Key asKey() {
            if (isKey()) {
                return new Key(bb, indirect(bb, end, parentWidth), byteWidth);
            } else {
                return Key.empty();
            }
        }

        /**
         * Returns element as a `String`
         * @return element as `String` or empty `String` if fail
         */
        public String asString() {
            if (isString()) {
                int start = indirect(bb, end, parentWidth);
                int size = (int) readUInt(bb, start - byteWidth, byteWidth);
                return bb.getString(start, size);
            }
            else if (isKey()){
                int start = indirect(bb, end, byteWidth);
                for (int i = start; ; i++) {
                    if (bb.get(i) == 0) {
                        return bb.getString(start, i - start);
                    }
                }
            } else {
                return "";
            }
        }

        /**
         * Returns element as a {@link Map}
         * @return element as {@link Map} or empty {@link Map} if fail
         */
        public Map asMap() {
            if (isMap()) {
                return new Map(bb, indirect(bb, end, parentWidth), byteWidth);
            } else {
                return Map.empty();
            }
        }

        /**
         * Returns element as a {@link Vector}
         * @return element as {@link Vector} or empty {@link Vector} if fail
         */
        public Vector asVector() {
            if (isVector()) {
                return new Vector(bb, indirect(bb, end, parentWidth), byteWidth);
            } else if(type == FlexBuffers.FBT_VECTOR_STRING_DEPRECATED) {
                // deprecated. Should be treated as key vector
                return new TypedVector(bb, indirect(bb, end, parentWidth), byteWidth, FlexBuffers.FBT_KEY);
            } else if (FlexBuffers.isTypedVector(type)) {
                return new TypedVector(bb, indirect(bb, end, parentWidth), byteWidth, FlexBuffers.toTypedVectorElementType(type));
            } else {
                return Vector.empty();
            }
        }

        /**
         * Returns element as a {@link Blob}
         * @return element as {@link Blob} or empty {@link Blob} if fail
         */
        public Blob asBlob() {
            if (isBlob() || isString()) {
                return new Blob(bb, indirect(bb, end, parentWidth), byteWidth);
            } else {
                return Blob.empty();
            }
        }

        /**
         * Returns element as a boolean
         * <p>If element type is not boolean, it will be casted to integer and compared against 0</p>
         * @return element as boolean
         */
        public boolean asBoolean() {
            if (isBoolean()) {
                return bb.get(end) != 0;
            }
            return asUInt() != 0;
        }

        /**
         * Returns text representation of the element (JSON)
         * @return String containing text representation of the element
         */
        @Override
        public String toString() {
            return toString(new StringBuilder(128)).toString();
        }

        /**
         * Appends a text(JSON) representation to a `StringBuilder`
         */
        StringBuilder toString(StringBuilder sb) {
            //TODO: Original C++ implementation escape strings.
            // probably we should do it as well.
            switch (type) {
                case FBT_NULL:
                    return sb.append("null");
                case FBT_INT:
                case FBT_INDIRECT_INT:
                    return sb.append(asLong());
                case FBT_UINT:
                case FBT_INDIRECT_UINT:
                    return sb.append(asUInt());
                case FBT_INDIRECT_FLOAT:
                case FBT_FLOAT:
                    return sb.append(asFloat());
                case FBT_KEY:
                    return asKey().toString(sb.append('"')).append('"');
                case FBT_STRING:
                    return sb.append('"').append(asString()).append('"');
                case FBT_MAP:
                    return asMap().toString(sb);
                case FBT_VECTOR:
                    return asVector().toString(sb);
                case FBT_BLOB:
                    return asBlob().toString(sb);
                case FBT_BOOL:
                    return sb.append(asBoolean());
                case FBT_VECTOR_INT:
                case FBT_VECTOR_UINT:
                case FBT_VECTOR_FLOAT:
                case FBT_VECTOR_KEY:
                case FBT_VECTOR_STRING_DEPRECATED:
                case FBT_VECTOR_BOOL:
                    return sb.append(asVector());
                case FBT_VECTOR_INT2:
                case FBT_VECTOR_UINT2:
                case FBT_VECTOR_FLOAT2:
                case FBT_VECTOR_INT3:
                case FBT_VECTOR_UINT3:
                case FBT_VECTOR_FLOAT3:
                case FBT_VECTOR_INT4:
                case FBT_VECTOR_UINT4:
                case FBT_VECTOR_FLOAT4:

                    throw new FlexBufferException("not_implemented:" + type);
                default:
                    return sb;
            }
        }
    }

    /**
     * Base class of all types below.
     * Points into the data buffer and allows access to one type.
     */
    private static abstract class Object {
        ReadBuf bb;
        int end;
        int byteWidth;

        Object(ReadBuf buff, int end, int byteWidth) {
            this.bb = buff;
            this.end = end;
            this.byteWidth = byteWidth;
        }

        @Override
        public String toString() {
            return toString(new StringBuilder(128)).toString();
        }

        public abstract StringBuilder toString(StringBuilder sb);
    }

    // Stores size in `byte_width_` bytes before end position.
    private static abstract class Sized extends Object {

        protected final int size;

        Sized(ReadBuf buff, int end, int byteWidth) {
            super(buff, end, byteWidth);
            size = (int) readUInt(bb, end - byteWidth, byteWidth);
        }

        public int size() {
            return size;
        }
    }

    /**
     * Represents a array of bytes element in the buffer
     *
     * <p>It can be converted to `ReadBuf` using {@link data()},
     * copied into a byte[] using {@link getBytes()} or
     * have individual bytes accessed individually using {@link get(int)}</p>
     */
    public static class Blob extends Sized {
        static final Blob EMPTY = new Blob(EMPTY_BB, 1, 1);

        Blob(ReadBuf buff, int end, int byteWidth) {
            super(buff, end, byteWidth);
        }

        /** Return an empty {@link Blob} */
        public static Blob empty() {
            return EMPTY;
        }

        /**
         * Return {@link Blob} as `ReadBuf`
         * @return blob as `ReadBuf`
         */
        public ByteBuffer data() {
            ByteBuffer dup = ByteBuffer.wrap(bb.data());
            dup.position(end);
            dup.limit(end + size());
            return dup.asReadOnlyBuffer().slice();
        }

        /**
         * Copy blob into a byte[]
         * @return blob as a byte[]
         */
        public byte[] getBytes() {
            int size = size();
            byte[] result = new byte[size];
            for (int i = 0; i < size; i++) {
                result[i] = bb.get(end + i);
            }
            return result;
        }

        /**
         * Return individual byte at a given position
         * @param pos position of the byte to be read
         */
        public byte get(int pos) {
            assert pos >=0 && pos <= size();
            return bb.get(end + pos);
        }

        /**
         * Returns a text(JSON) representation of the {@link Blob}
         */
        @Override
        public String toString() {
            return bb.getString(end, size());
        }

        /**
         * Append a text(JSON) representation of the {@link Blob} into a `StringBuilder`
         */
        @Override
        public StringBuilder toString(StringBuilder sb) {
            sb.append('"');
            sb.append(bb.getString(end, size()));
            return sb.append('"');
        }
    }

    /**
     * Represents a key element in the buffer. Keys are
     * used to reference objects in a {@link Map}
     */
    public static class Key extends Object {

        private static final Key EMPTY = new Key(EMPTY_BB, 0, 0);

        Key(ReadBuf buff, int end, int byteWidth) {
            super(buff, end, byteWidth);
        }

        /**
         * Return an empty {@link Key}
         * @return empty {@link Key}
         * */
        public static Key empty() {
            return Key.EMPTY;
        }

        /**
         * Appends a text(JSON) representation to a `StringBuilder`
         */
        @Override
        public StringBuilder toString(StringBuilder sb) {
            return sb.append(toString());
        }

        @Override
        public String toString() {
            int size;
            for (int i = end; ; i++) {
                if (bb.get(i) == 0) {
                    size = i - end;
                    break;
                }
            }
            return bb.getString(end, size);
        }

        int compareTo(byte[] other) {
            int ia = end;
            int io = 0;
            byte c1, c2;
            do {
                c1 = bb.get(ia);
                c2 = other[io];
                if (c1 == '\0')
                    return c1 - c2;
                ia++;
                io++;
                if (io == other.length) {
                    // in our buffer we have an additional \0 byte
                    // but this does not exist in regular Java strings, so we return now
                    int cmp = c1 - c2;
                    if (cmp != 0 || bb.get(ia) == '\0') {
                        return cmp;
                    } else {
                        return 1;
                    }
                }
            }
            while (c1 == c2);
            return c1 - c2;
        }

        /**
         *  Compare keys
         *  @param obj other key to compare
         *  @return true if keys are the same
         */
        @Override
        public boolean equals(java.lang.Object obj) {
            if (!(obj instanceof Key))
                return false;

            return ((Key) obj).end == end && ((Key) obj).byteWidth == byteWidth;
        }

        public int hashCode() {
          return end ^ byteWidth;
        }
    }

    /**
     * Map object representing a set of key-value pairs.
     */
    public static class Map extends Vector {
        private static final Map EMPTY_MAP = new Map(EMPTY_BB, 1, 1);
        // cache for converting UTF-8 codepoints into
        // Java chars. Used to speed up String comparison
        private final byte[] comparisonBuffer = new byte[4];

        Map(ReadBuf bb, int end, int byteWidth) {
            super(bb, end, byteWidth);
        }

        /**
         * Returns an empty {@link Map}
         * @return an empty {@link Map}
         */
        public static Map empty() {
            return EMPTY_MAP;
        }

        /**
         * @param key access key to element on map
         * @return reference to value in map
         */
        public Reference get(String key) {
            int index = binarySearch(key);
            if (index >= 0 && index < size) {
                return get(index);
            }
            return Reference.NULL_REFERENCE;
        }

        /**
         * @param key access key to element on map. Keys are assumed to be encoded in UTF-8
         * @return reference to value in map
         */
        public Reference get(byte[] key) {
            int index = binarySearch(key);
            if (index >= 0 && index < size) {
                return get(index);
            }
            return Reference.NULL_REFERENCE;
        }

        /**
         * Get a vector or keys in the map
         *
         * @return vector of keys
         */
        public KeyVector keys() {
            final int num_prefixed_fields = 3;
            int keysOffset = end - (byteWidth * num_prefixed_fields);
            return new KeyVector(new TypedVector(bb,
                    indirect(bb, keysOffset, byteWidth),
                    readInt(bb, keysOffset + byteWidth, byteWidth),
                    FBT_KEY));
        }

        /**
         * @return {@code Vector} of values from map
         */
        public Vector values() {
            return new Vector(bb, end, byteWidth);
        }

        /**
         * Writes text (json) representation of map in a {@code StringBuilder}.
         *
         * @param builder {@code StringBuilder} to be appended to
         * @return Same {@code StringBuilder} with appended text
         */
        public StringBuilder toString(StringBuilder builder) {
            builder.append("{ ");
            KeyVector keys = keys();
            int size = size();
            Vector vals = values();
            for (int i = 0; i < size; i++) {
                builder.append('"')
                        .append(keys.get(i).toString())
                        .append("\" : ");
                builder.append(vals.get(i).toString());
                if (i != size - 1)
                    builder.append(", ");
            }
            builder.append(" }");
            return builder;
        }

        // Performs a binary search on a key vector and return index of the key in key vector
        private int binarySearch(CharSequence searchedKey) {
            int low = 0;
            int high = size - 1;
            final int num_prefixed_fields = 3;
            int keysOffset = end - (byteWidth * num_prefixed_fields);
            int keysStart = indirect(bb, keysOffset, byteWidth);
            int keyByteWidth = readInt(bb, keysOffset + byteWidth, byteWidth);
            while (low <= high) {
                int mid = (low + high) >>> 1;
                int keyPos = indirect(bb, keysStart + mid * keyByteWidth, keyByteWidth);
                int cmp = compareCharSequence(keyPos, searchedKey);
                if (cmp < 0)
                    low = mid + 1;
                else if (cmp > 0)
                    high = mid - 1;
                else
                    return mid; // key found
            }
            return -(low + 1);  // key not found
        }

        private int binarySearch(byte[] searchedKey) {
            int low = 0;
            int high = size - 1;
            final int num_prefixed_fields = 3;
            int keysOffset = end - (byteWidth * num_prefixed_fields);
            int keysStart = indirect(bb, keysOffset, byteWidth);
            int keyByteWidth = readInt(bb, keysOffset + byteWidth, byteWidth);

            while (low <= high) {
                int mid = (low + high) >>> 1;
                int keyPos = indirect(bb, keysStart + mid * keyByteWidth, keyByteWidth);
                int cmp = compareBytes(bb, keyPos, searchedKey);
                if (cmp < 0)
                    low = mid + 1;
                else if (cmp > 0)
                    high = mid - 1;
                else
                    return mid; // key found
            }
            return -(low + 1);  // key not found
        }

        // compares a byte[] against a FBT_KEY
        private int compareBytes(ReadBuf bb, int start, byte[] other) {
            int l1 = start;
            int l2 = 0;
            byte c1, c2;
            do {
                c1 = bb.get(l1);
                c2 = other[l2];
                if (c1 == '\0')
                    return c1 - c2;
                l1++;
                l2++;
                if (l2 == other.length) {
                    // in our buffer we have an additional \0 byte
                    // but this does not exist in regular Java strings, so we return now
                    int cmp = c1 - c2;
                    if (cmp != 0 || bb.get(l1) == '\0') {
                        return cmp;
                    } else {
                        return 1;
                    }
                }
            }
            while (c1 == c2);
            return c1 - c2;
        }

        // compares a CharSequence against a FBT_KEY
        private int compareCharSequence(int start, CharSequence other) {
            int bufferPos = start;
            int otherPos = 0;
            int limit = bb.limit();
            int otherLimit = other.length();

            // special loop for ASCII characters. Most of keys should be ASCII only, so this
            // loop should be optimized for that.
            // breaks if a multi-byte character is found
            while (otherPos < otherLimit) {
                char c2 = other.charAt(otherPos);

                if (c2 >= 0x80) {
                    // not a single byte codepoint
                    break;
                }

                byte b = bb.get(bufferPos);

                if (b == 0) {
                    return -c2;
                } else if (b < 0) {
                    break;
                } else if ((char) b != c2) {
                    return b - c2;
                }
                ++bufferPos;
                ++otherPos;
            }

            while (bufferPos < limit) {

                int sizeInBuff = Utf8.encodeUtf8CodePoint(other, otherPos, comparisonBuffer);

                if (sizeInBuff == 0) {
                    // That means we finish with other and there are not more chars to
                    // compare. String in the buffer is bigger.
                    return bb.get(bufferPos);
                }

                for (int i = 0; i < sizeInBuff; i++) {
                    byte bufferByte = bb.get(bufferPos++);
                    byte otherByte = comparisonBuffer[i];
                    if (bufferByte == 0) {
                        // Our key is finished, so other is bigger
                        return -otherByte;
                    } else if (bufferByte != otherByte) {
                        return bufferByte - otherByte;
                    }
                }

                otherPos += sizeInBuff == 4 ? 2 : 1;
            }
            return 0;
        }
    }

    /**
     * Object that represents a set of elements in the buffer
     */
    public static class Vector extends Sized {

        private static final Vector EMPTY_VECTOR = new Vector(EMPTY_BB, 1, 1);

        Vector(ReadBuf bb, int end, int byteWidth) {
            super(bb, end, byteWidth);
        }

        /**
         * Returns an empty {@link Map}
         * @return an empty {@link Map}
         */
        public static Vector empty() {
            return EMPTY_VECTOR;
        }

        /**
         * Checks if the vector is empty
         * @return true if vector is empty
         */
        public boolean isEmpty() {
            return this == EMPTY_VECTOR;
        }

        /**
         * Appends a text(JSON) representation to a `StringBuilder`
         */
        @Override
        public StringBuilder toString(StringBuilder sb) {
            sb.append("[ ");
            int size = size();
            for (int i = 0; i < size; i++) {
                get(i).toString(sb);
                if (i != size - 1) {
                    sb.append(", ");
                }
            }
            sb.append(" ]");
            return sb;
        }

        /**
         * Get a element in a vector by index
         *
         * @param index position of the element
         * @return {@code Reference} to the element
         */
        public Reference get(int index) {
            long len = size();
            if (index >= len) {
                return Reference.NULL_REFERENCE;
            }
            int packedType = byteToUnsignedInt(bb.get((int) (end + (len * byteWidth) + index)));
            int obj_end = end + index * byteWidth;
            return new Reference(bb, obj_end, byteWidth, packedType);
        }
    }

    /**
     * Object that represents a set of elements with the same type
     */
    public static class TypedVector extends Vector {

        private static final TypedVector EMPTY_VECTOR = new TypedVector(EMPTY_BB, 1, 1, FBT_INT);

        private final int elemType;

        TypedVector(ReadBuf bb, int end, int byteWidth, int elemType) {
            super(bb, end, byteWidth);
            this.elemType = elemType;
        }

        public static TypedVector empty() {
            return EMPTY_VECTOR;
        }

        /**
         * Returns whether the vector is empty
         *
         * @return true if empty
         */
        public boolean isEmptyVector() {
            return this == EMPTY_VECTOR;
        }

        /**
         * Return element type for all elements in the vector
         *
         * @return element type
         */
        public int getElemType() {
            return elemType;
        }

        /**
         * Get reference to an object in the {@code Vector}
         *
         * @param pos position of the object in {@code Vector}
         * @return reference to element
         */
        @Override
        public Reference get(int pos) {
            int len = size();
            if (pos >= len) return Reference.NULL_REFERENCE;
            int childPos = end + pos * byteWidth;
            return new Reference(bb, childPos, byteWidth, 1, elemType);
        }
    }

    /**
     * Represent a vector of keys in a map
     */
    public static class KeyVector {

        private final TypedVector vec;

        KeyVector(TypedVector vec) {
            this.vec = vec;
        }

        /**
         * Return key
         *
         * @param pos position of the key in key vector
         * @return key
         */
        public Key get(int pos) {
            int len = size();
            if (pos >= len) return Key.EMPTY;
            int childPos = vec.end + pos * vec.byteWidth;
            return new Key(vec.bb, indirect(vec.bb, childPos, vec.byteWidth), 1);
        }

        /**
         * Returns size of key vector
         *
         * @return size
         */
        public int size() {
            return vec.size();
        }

        /**
         * Returns a text(JSON) representation
         */
        public String toString() {
            StringBuilder b = new StringBuilder();
            b.append('[');
            for (int i = 0; i < vec.size(); i++) {
                vec.get(i).toString(b);
                if (i != vec.size() - 1) {
                    b.append(", ");
                }
            }
            return b.append("]").toString();
        }
    }

    public static class FlexBufferException extends RuntimeException {
        FlexBufferException(String msg) {
            super(msg);
        }
    }

    static class Unsigned {

        static int byteToUnsignedInt(byte x) {
            return ((int) x) & 0xff;
        }

        static int shortToUnsignedInt(short x) {
            return ((int) x) & 0xffff;
        }

        static long intToUnsignedLong(int x) {
            return ((long) x) & 0xffffffffL;
        }
    }
}
/// @}