class LocalPage extends Page {

    /**
     * The last result of a find operation is cached.
     */
    protected int cachedCompare;

    /**
     * The estimated memory used.
     */
    protected int memory;

    /**
     * The keys.
     * <p>
     * The array might be larger than needed, to avoid frequent re-sizing.
     */
    protected Object[] keys;

    protected LocalPage(BTreeMap<?, ?> map) {
        super(map);
    }

    @Override
    public Object getKey(int index) {
        return keys[index];
    }

    @Override
    public int getKeyCount() {
        return keys.length;
    }

    /**
     * Search the key in this page using a binary search. Instead of always
     * starting the search in the middle, the last found index is cached.
     * <p>
     * If the key was found, the returned value is the index in the key array.
     * If not found, the returned value is negative, where -1 means the provided
     * key is smaller than any keys in this page. See also Arrays.binarySearch.
     * 
     * @param key the key
     * @return the value or null
     */
    @Override
    public int binarySearch(Object key) {<FILL_FUNCTION_BODY>}

    @Override
    boolean needSplit() {
        return memory > map.getBTreeStorage().getPageSize() && keys.length > 1;
    }

    @Override
    public void remove(int index) {
        int keyLength = keys.length;
        int keyIndex = index >= keyLength ? index - 1 : index;
        Object old = keys[keyIndex];
        addMemory(-map.getKeyType().getMemory(old));
        Object[] newKeys = new Object[keyLength - 1];
        DataUtils.copyExcept(keys, newKeys, keyLength, keyIndex);
        keys = newKeys;
    }

    protected abstract void recalculateMemory();

    protected int recalculateKeysMemory() {
        int mem = PageUtils.PAGE_MEMORY;
        StorageDataType keyType = map.getKeyType();
        for (int i = 0, len = keys.length; i < len; i++) {
            mem += keyType.getMemory(keys[i]);
        }
        return mem;
    }

    @Override
    public int getMemory() {
        return memory;
    }

    protected void addMemory(int mem) {
        addMemory(mem, true);
    }

    protected void addMemory(int mem, boolean addToUsedMemory) {
        memory += mem;
        if (addToUsedMemory)
            map.getBTreeStorage().getBTreeGC().addUsedMemory(mem);
    }

    protected void copy(LocalPage newPage) {
        newPage.cachedCompare = cachedCompare;
        newPage.setRef(getRef());
    }

    @Override
    public boolean equals(Object other) {
        if (other == this) {
            return true;
        }
        if (other instanceof LocalPage) {
            long pos = getPos();
            if (pos != 0 && ((LocalPage) other).getPos() == pos) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int hashCode() {
        return super.hashCode();
        // long pos = getPos();
        // return pos != 0 ? (int) (pos | (pos >>> 32)) : super.hashCode();
    }

    @Override
    public String toString() {
        return PrettyPagePrinter.getPrettyPageInfo(this, false);
    }
}

        int low = 0, high = keys.length - 1;
        // the cached index minus one, so that
        // for the first time (when cachedCompare is 0),
        // the default value is used
        int x = cachedCompare - 1;
        if (x < 0 || x > high) {
            x = high >>> 1;
        }
        Object[] k = keys;
        StorageDataType keyType = map.getKeyType();
        while (low <= high) {
            int compare = keyType.compare(key, k[x]);
            if (compare > 0) {
                low = x + 1;
            } else if (compare < 0) {
                high = x - 1;
            } else {
                cachedCompare = x + 1;
                return x;
            }
            x = (low + high) >>> 1;
        }
        cachedCompare = low;
        return -(low + 1);
    
<methods>public int binarySearch(java.lang.Object) ,public com.lealone.storage.aose.btree.page.Page copy() ,public com.lealone.storage.aose.btree.page.Page copyAndInsertLeaf(int, java.lang.Object, java.lang.Object) ,public static com.lealone.storage.aose.btree.page.Page create(BTreeMap<?,?>, int) ,public com.lealone.storage.aose.btree.page.Page getChildPage(int) ,public com.lealone.storage.aose.btree.page.PageReference getChildPageReference(int) ,public com.lealone.storage.aose.btree.page.PageReference[] getChildren() ,public java.lang.Object getKey(int) ,public int getKeyCount() ,public int getMemory() ,public int getPageIndex(java.lang.Object) ,public long getPos() ,public int getRawChildPageCount() ,public com.lealone.storage.aose.btree.page.PageReference getRef() ,public java.lang.Object getValue(int) ,public java.lang.Object getValue(int, int[]) ,public java.lang.Object getValue(int, boolean) ,public com.lealone.storage.aose.btree.page.Page gotoLeafPage(java.lang.Object) ,public boolean isEmpty() ,public boolean isLeaf() ,public boolean isNode() ,public void markDirty() ,public void markDirtyBottomUp() ,public void read(java.nio.ByteBuffer, int, int, int) ,public void remove(int) ,public void setRef(com.lealone.storage.aose.btree.page.PageReference) ,public java.lang.Object setValue(int, java.lang.Object) ,public long writeUnsavedRecursive(com.lealone.storage.aose.btree.page.PageInfo, com.lealone.storage.aose.btree.chunk.Chunk, com.lealone.db.DataBuffer) <variables>public static final boolean ASSERT,protected final non-sealed BTreeMap<?,?> map,private com.lealone.storage.aose.btree.page.PageReference ref