/*******************************************************************************
 *  Copyright (c) 2010 Association for Decentralized Information Management in
 *  Industry THTH ry.
 *  All rights reserved. This program and the accompanying materials
 *  are made available under the terms of the Eclipse Public License v1.0
 *  which accompanies this distribution, and is available at
 *  http://www.eclipse.org/legal/epl-v10.html
 *
 *  Contributors:
 *      VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.databoard.accessor.binary;

import java.io.IOException;
import java.lang.ref.SoftReference;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.Executor;

import org.simantics.databoard.accessor.Accessor;
import org.simantics.databoard.accessor.MapAccessor;
import org.simantics.databoard.accessor.error.AccessorConstructionException;
import org.simantics.databoard.accessor.error.AccessorException;
import org.simantics.databoard.accessor.error.ReferenceException;
import org.simantics.databoard.accessor.event.Event;
import org.simantics.databoard.accessor.event.MapEntryAdded;
import org.simantics.databoard.accessor.event.MapEntryRemoved;
import org.simantics.databoard.accessor.event.ValueAssigned;
import org.simantics.databoard.accessor.file.FileMapAccessor;
import org.simantics.databoard.accessor.impl.AccessorParams;
import org.simantics.databoard.accessor.impl.ListenerEntry;
import org.simantics.databoard.accessor.interestset.InterestSet;
import org.simantics.databoard.accessor.interestset.MapInterestSet;
import org.simantics.databoard.accessor.reference.ChildReference;
import org.simantics.databoard.accessor.reference.KeyReference;
import org.simantics.databoard.accessor.reference.LabelReference;
import org.simantics.databoard.adapter.AdaptException;
import org.simantics.databoard.adapter.Adapter;
import org.simantics.databoard.adapter.AdapterConstructionException;
import org.simantics.databoard.binding.ArrayBinding;
import org.simantics.databoard.binding.Binding;
import org.simantics.databoard.binding.MapBinding;
import org.simantics.databoard.binding.error.BindingConstructionException;
import org.simantics.databoard.binding.error.BindingException;
import org.simantics.databoard.binding.mutable.MutableVariant;
import org.simantics.databoard.parser.repository.DataTypeSyntaxError;
import org.simantics.databoard.parser.repository.DataValueRepository;
import org.simantics.databoard.serialization.RuntimeSerializerConstructionException;
import org.simantics.databoard.serialization.SerializationException;
import org.simantics.databoard.serialization.Serializer;
import org.simantics.databoard.serialization.SerializerConstructionException;
import org.simantics.databoard.type.Datatype;
import org.simantics.databoard.type.MapType;
import org.simantics.databoard.util.binary.Blob;
import org.simantics.databoard.util.binary.RandomAccessBinary.ByteSide;

/**
 * BinaryMap is accessor to a map structure in a file or byte memory.
 * <p> (Fixed sized entries)
 * If the size of an entry is constant, then the implementation uses binary 
 * search for random access operations O(log(n)). 
 * 
 * <p> (Variable sized entries)
 * If the size is variable, for example the key or value is string, then the 
 * implementation does sequential search for all operations, which is very 
 * slow O(n). To improve performance, an index is built in memory as the file
 * is read. To conserve memory, the index is held with SoftReference. So, 
 * the performance remains good if lots of operations are done within a short
 * time period.
 * 
 * @author Toni Kalajainen <toni.kalajainen@vtt.fi>
 */
public class BinaryMap extends BinaryObject implements MapAccessor, FileMapAccessor {

	/** Accessors to children */
	TreeMap<Object, java.lang.ref.Reference<BinaryObject>> children;
	
	Binding kb;
	Binding vb;
	Serializer ks;
	Serializer vs;
	
	/** Entry size, constant */
	Integer constantSize;
	
	Index index;
	boolean indexing = false;
	
	public BinaryMap(BinaryObject parent, Blob blob, Datatype type, AccessorParams params) {
		super(parent, blob, type, params);
		MapType mt = (MapType) type;
		kb = params.bindingScheme.getBindingUnchecked( mt.keyType );
		vb = params.bindingScheme.getBindingUnchecked( mt.valueType );
		ks = params.serializerScheme.getSerializerUnchecked( kb );
		vs = params.serializerScheme.getSerializerUnchecked( vb );
		children = new TreeMap<Object, java.lang.ref.Reference<BinaryObject>>(kb);
		
		if (ks.getConstantSize()!=null && vs.getConstantSize()!=null)  {
			constantSize = ks.getConstantSize() + vs.getConstantSize();
			index = new Constant();
		} else {
			index = new Sequential();
		}
	} 
	
	// Get existing accessor
	BinaryObject getChild(Object key)
	{
		java.lang.ref.Reference<BinaryObject> ref = children.get(key);
		if (ref==null) return null;
		BinaryObject result = ref.get();
		if (result==null) {
			children.remove(key);
			return null;
		}
		return result;
	}		
	
	Entry floorChildEntry(Object key) throws IOException, SerializationException, BindingException {
		if (ks.getConstantSize()==null) return null;
		BinaryObject sa = getChild(key);
		// Exact match
		if (sa!=null) {
			if (ks.getConstantSize()==null) return null;
			long valuePos = sa.b.getStartPositionInSourceBinary();
			long keyPos = valuePos - ks.getConstantSize();
			return new Entry(key, keyPos, sa);
		}
		return lowerChildEntry(key);
	}

	Entry lowerChildEntry(Object key) throws IOException, SerializationException, BindingException {
		if (ks.getConstantSize()==null) return null;
		Map.Entry<Object, java.lang.ref.Reference<BinaryObject>> e = children.lowerEntry(key);
		while (e != null) {
			key = e.getKey();
			BinaryObject sa = e.getValue().get();
			if (sa!=null) {
				long valuePos = sa.b.getStartPositionInSourceBinary();
				long keyPos = valuePos - ks.getConstantSize();
				return new Entry(key, keyPos, sa);
			} else {
				children.remove(e.getKey());
			}
			e = children.lowerEntry(key);
		}
		return null;
	}

	Entry lastChildEntry() throws IOException, SerializationException, BindingException {
		if (ks.getConstantSize()==null) return null;
		Map.Entry<Object, java.lang.ref.Reference<BinaryObject>> e = children.lastEntry();
		while (e != null) {
			Object key = e.getKey();
			BinaryObject sa = e.getValue().get();
			if (sa!=null) {
				long valuePos = sa.b.getStartPositionInSourceBinary();
				long keyPos = valuePos - ks.getConstantSize();
				return new Entry(key, keyPos, sa);
			} else {
				children.remove(key);
			}
			e = children.lowerEntry(key);
		}
		return null;
	}
	
	Entry higherChildEntry(Object key) throws IOException, SerializationException, BindingException {
		if (ks.getConstantSize()==null) return null;
		Map.Entry<Object, java.lang.ref.Reference<BinaryObject>> e = children.higherEntry(key);
		while (e != null) {
			key = e.getKey();
			BinaryObject sa = e.getValue().get();
			if (sa!=null) {
				long valuePos = sa.b.getStartPositionInSourceBinary();
				long keyPos = valuePos - ks.getConstantSize();
				return new Entry(key, keyPos, sa);
			} else {
				children.remove(key);
			}
			e = children.higherEntry(key);
		}
		return null;
	}

	Entry ceilingChildEntry(Object key) throws IOException, SerializationException, BindingException {
		if (ks.getConstantSize()==null) return null;
		BinaryObject sa = getChild(key);
		// Exact match
		if (sa!=null) {
			long valuePos = sa.b.getStartPositionInSourceBinary();
			long keyPos = valuePos - ks.getConstantSize();
			return new Entry(key, keyPos, sa);
		}
		return higherChildEntry(key);
	}
	
	Entry getEntryAt(long pos) throws SerializationException, IOException, BindingException {
		Object k = getKeyAt(pos);
		if (k==null) return null;
		return new Entry(k, pos, getChild(k));
	}
	
	Object getKeyAt(long pos) throws SerializationException, IOException, BindingException {
		if (pos<4L) return null;
		if (pos>=b.length()) return null;
		b.position(pos);
		Object k = ks.deserialize(b, null);
		return k;
	}	
	
	@Override
	public MapType type() {
		return (MapType) type;
	}

	@Override
	public void clear() throws AccessorException {
		assert b.isOpen();
		writeLock();
		try {
			clearNoflush();
			b.flush();
		} catch (IOException e) {
			throw new AccessorException( e );
		} finally {
			writeUnlock();
		}
	}	

	@Override
	public int size() throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			if (constantSize != null) return (int) ((b.length()-4) / constantSize);
			b.position(0L);
			return b.readInt();
		} catch (IOException e) {
			throw new AccessorException( e );
		} finally {
			readUnlock();
		}
	}	

	@Override
	public boolean containsKey(Binding keyBinding, Object key)
			throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Object lk = adapt(key, keyBinding, kb);
			Entry e = index.getKey(lk);
			return e != null;
		} catch (AdaptException e) {
			throw new AccessorException(e);
		} catch (AdapterConstructionException e) {
			throw new AccessorException(e);
		} finally {
			readUnlock();
		}
	}

	@Override
	public boolean containsValue(Binding valueBinding, Object value)
			throws AccessorException {		
		assert b.isOpen();
		readLock();
		try {
			Serializer vs = params.serializerScheme.getSerializer( valueBinding );
			b.position(0L);
			int count = b.readInt();
			for (int i=0; i<count; i++) {
				ks.skip(b);
				Object v = vs.deserialize(b, null);
				if (valueBinding.equals(v, value)) return true;
			}
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (SerializerConstructionException e) {
			throw new AccessorException(e);
		} finally {
			readUnlock();
		}
		return false;
	}

	@Override
	public Object get(Binding keyBinding, Object key, Binding valueBinding)
			throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Object lk = adapt(key, keyBinding, kb);
			Entry e = index.getKey(lk);
			if (e==null) return null;
			b.position(e.pos);
			ks.skip(b, null);
			Object value = params.serializerScheme.getSerializer( valueBinding ).deserialize(b, null);			
			return value;
		} catch (AdaptException e1) {
			throw new AccessorException(e1);
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (RuntimeSerializerConstructionException e) {
			throw new AccessorException(e);
		} catch (AdapterConstructionException e) {
			throw new AccessorException(e);
		} catch (SerializerConstructionException e) {
			throw new AccessorException(e);
		} finally {
			readUnlock();
		}
	}

	@Override
	public void getAll(Binding keyBinding, Binding valueBinding,
			Map<Object, Object> to) throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Adapter ka = params.adapterScheme.getAdapter(kb, keyBinding, true, false);
			Adapter va = params.adapterScheme.getAdapter(vb, valueBinding, true, false);
			b.position(0L);
			int count = b.readInt();
			for (int i=0; i<count; i++) {
				Object k = ks.deserialize(b, null);
				Object v = vs.deserialize(b, null);
				k = ka.adapt(k);
				v = va.adapt(v);
				to.put(k, v);
			}			
			
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (AdapterConstructionException e) {
			throw new AccessorException(e);
		} catch (AdaptException e) {
			throw new AccessorException(e);
		} finally {
			readUnlock();
		}
		
	}

	@Override
	public void getAll(Binding keyBinding, Binding valueBinding, Object[] keys,
			Object[] values) throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Adapter ka = params.adapterScheme.getAdapter(kb, keyBinding, true, false);
			Adapter va = params.adapterScheme.getAdapter(vb, valueBinding, true, false);
			b.position(0L);
			int count = b.readInt();
			if (count>keys.length) throw new AccessorException("keys array too short");
			if (count>values.length) throw new AccessorException("values array too short");
			for (int i=0; i<count; i++) {
				Object k = ks.deserialize(b, null);
				Object v = vs.deserialize(b, null);
				k = ka.adapt(k);
				v = va.adapt(v);
				keys[i] = k;
				values[i] = v;
			}			
			
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (AdapterConstructionException e) {
			throw new AccessorException(e);
		} catch (AdaptException e) {
			throw new AccessorException(e);
		} finally {
			readUnlock();
		}
		
	}
	
	@Override
	public int count(Binding keyBinding, Object from, boolean fromInclusive,
			Object end, boolean endInclusive) throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Object lf = params.adapterScheme.adapt(from, keyBinding, kb);
			Object le = params.adapterScheme.adapt(end, keyBinding, kb);
			
			Entry fromEntry = fromInclusive ? index.ceiling(lf) : index.higher(lf);
			Entry endEntry  = endInclusive  ? index.floor(le)   : index.lower(le);
			if (endEntry==null || fromEntry == null) return 0;

			if (fromEntry.pos>endEntry.pos) return 0;
			if (fromEntry.pos==endEntry.pos) return 1;
						
			if (constantSize != null) {
				return (int) ((endEntry.pos-fromEntry.pos)/constantSize)+1;
			}
			
			int result = 1;
			b.position(fromEntry.pos);
			while (b.position()<endEntry.pos) {
				ks.skip(b);
				vs.skip(b);
				result++;
			}
			return result;			
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (AdaptException e) {
			throw new AccessorException(e);
		} finally {
			readUnlock();
		}
	}
	
	@Override
	public int getEntries(Binding keyBinding, Object from,
			boolean fromInclusive, Object end, boolean endInclusive,
			ArrayBinding keyArrayBinding, Object keysArray,
			ArrayBinding valueArrayBinding, Object valueArray, int limit)
			throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Object lf = params.adapterScheme.adapt(from, keyBinding, kb);
			Object le = params.adapterScheme.adapt(end, keyBinding, kb);
			
			Entry fromEntry = fromInclusive ? index.ceiling(lf) : index.higher(lf);
			Entry endEntry  = endInclusive  ? index.floor(le)   : index.lower(le);
			if (endEntry==null || fromEntry == null) return 0;
			
			// Requester's Key & Value Binding
			Binding rkb   = keyArrayBinding.getComponentBinding();
			Binding rvb   = valueArrayBinding.getComponentBinding();
			
			// Local Key & Value type & bindings
			Datatype lkt  = type().keyType;
			Datatype lvt  = type().valueType;
			
			boolean adaptKey   = !rkb.type().equals(lkt);
			boolean adaptValue = !rvb.type().equals(lvt);
			
			Serializer ks, vs;
			Adapter ka = null, va = null;
			
			if (adaptKey) {
				Binding lkb   = params.bindingScheme.getBinding( lkt );
				ka = params.adapterScheme.getAdapter( lkb, rkb, true, false);
				ks = params.serializerScheme.getSerializer( lkb );
			} else {
				ks = params.serializerScheme.getSerializer( rkb );				
			}
			
			if (adaptValue) {
				Binding lvb   = params.bindingScheme.getBinding( lvt );
				va = params.adapterScheme.getAdapter( lvb, rvb, true, false);
				vs = params.serializerScheme.getSerializer( lvb );
			} else {
				vs = params.serializerScheme.getSerializer( rvb );
			}			
			
			int i = 0;
			int kac = keyArrayBinding.size( keysArray );
			int vac = valueArrayBinding.size( valueArray ); 
			b.position(fromEntry.pos);
			while (b.position()<=endEntry.pos) {
				if (limit>=0 && i>=limit) break;
				Object key = ks.deserialize(b);
				if (adaptKey) key = ka.adapt(key);
				Object value = vs.deserialize(b);
				if (adaptValue) value = va.adapt(value);
				
				if (i<kac) keyArrayBinding.set(keysArray, i, key); else keyArrayBinding.add(keysArray, i, key);
 				if (i<vac) valueArrayBinding.set(valueArray, i, value); else valueArrayBinding.add(valueArray, i, value);
				
				i++;
			}
			return i;			
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (AdaptException e) {
			throw new AccessorException(e);
		} catch (SerializerConstructionException e) {
			throw new AccessorException(e);
		} catch (BindingException e) {
			throw new AccessorException(e);
		} catch (BindingConstructionException e) {
			throw new AccessorException(e);
		} catch (AdapterConstructionException e) {
			throw new AccessorException(e);
		} finally {
			readUnlock();
		}
	}	

	@Override
	public Object getCeilingKey(Binding keyBinding, Object key)
			throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Object lk = adapt(key, keyBinding, kb);
			if (ks.getConstantSize()!=null) {
				if (getChild(lk)!=null) return key;
			}
			Entry e = index.ceiling(lk);
			if (e==null) return null;
			return adapt(e.key, kb, keyBinding);
		} catch (AdaptException e1) {
			throw new AccessorException( e1 );
		} catch (AdapterConstructionException e) {
			throw new AccessorException( e );
		} finally {
			readUnlock();
		}
	}

	@Override
	public Object getFirstKey(Binding keyBinding) throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			b.position(0L);
			int count = b.readInt();
			if (count==0) return null;
			return params.serializerScheme.getSerializer( keyBinding ).deserialize(b);
		} catch (RuntimeSerializerConstructionException e) {
			throw new AccessorException(e);
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (SerializerConstructionException e) {
			throw new AccessorException(e);
		} finally {
			readUnlock();
		}
	}

	@Override
	public Object getFloorKey(Binding keyBinding, Object key)
			throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Object lk = adapt(key, keyBinding, kb);
			if (ks.getConstantSize()!=null) {
				// See if we get exact match
				if (getChild(lk)!=null) return key;
			}
			Entry e = index.floor(lk);
			if (e==null) return null;
			return adapt(e.key, kb, keyBinding);
		} catch (AdaptException e1) {
			throw new AccessorException( e1 );
		} catch (AdapterConstructionException e) {
			throw new AccessorException( e );
		} finally {
			readUnlock();
		}
	}

	@Override
	public Object getHigherKey(Binding keyBinding, Object key)
			throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Object lk = adapt(key, keyBinding, kb);
			Entry e = index.higher(lk);
			if (e==null) return null;
			return adapt(e.key, kb, keyBinding);
		} catch (AdaptException e1) {
			throw new AccessorException( e1 );
		} catch (AdapterConstructionException e) {
			throw new AccessorException( e );
		} finally {
			readUnlock();
		}
	}

	@Override
	public Object[] getKeys(Binding keyBinding) throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Adapter ka = params.adapterScheme.getAdapter(kb, keyBinding, true, false);
			b.position(0L);
			int count = b.readInt();
			Object[] result = new Object[ count ];
			for (int i=0; i<count; i++) {
				Object k = ks.deserialize(b, null);
				vs.skip(b, null);
				k = ka.adapt(k);
				result[i] = k;
			}			
			return result;			
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (AdapterConstructionException e) {
			throw new AccessorException(e);
		} catch (AdaptException e) {
			throw new AccessorException(e);
		} finally {
			readUnlock();
		}
	}

	@Override
	public Object getLastKey(Binding keyBinding) throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Entry e = index.last();
			if (e==null) return null;
			return adapt(e.key, kb, keyBinding);
		} catch (AdaptException e1) {
			throw new AccessorException( e1 );
		} catch (AdapterConstructionException e) {
			throw new AccessorException( e );
		} finally {
			readUnlock();
		}
	}

	@Override
	public Object getLowerKey(Binding keyBinding, Object key)
			throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Object lk = adapt(key, keyBinding, kb);
			Entry e = index.lower(lk);
			if (e==null) return null;
			return adapt(e.key, kb, keyBinding);
		} catch (AdaptException e1) {
			throw new AccessorException( e1 );
		} catch (AdapterConstructionException e) {
			throw new AccessorException( e );
		} finally {
			readUnlock();
		}
	}


	@SuppressWarnings("unchecked")
	@Override
	public <T extends Accessor> T getComponent(ChildReference reference)
			throws AccessorConstructionException {
		if (reference==null) return (T) this;
		
		if (reference instanceof LabelReference) {
			LabelReference lr = (LabelReference) reference;
			try {
				DataValueRepository rep = new DataValueRepository(); 
				kb.parseValue(lr.label, rep);
				Object value = rep.get( rep.getValueNames().iterator().next() );
				
				Accessor result = (T) getValueAccessor(kb, value);
				if (reference.getChildReference() != null)
					result = result.getComponent(reference.getChildReference());
				return (T) result;			
			} catch ( BindingException e1 ) {
				throw new ReferenceException(e1);				
			} catch ( DataTypeSyntaxError e2 ) {
				throw new ReferenceException(e2);				
			}			
		} else 		
		if (reference instanceof KeyReference) {
			KeyReference ref = (KeyReference) reference;
			Accessor result = getValueAccessor(ref.key.getBinding(), ref.key.getValue());
			if (reference.getChildReference() != null)
				result = result.getComponent(reference.getChildReference());
			return (T) result;			
		} throw new ReferenceException(reference.getClass().getName()+" is not a reference of a map");	
	}
	
	@SuppressWarnings("unchecked")
	@Override
	public <T extends Accessor> T getValueAccessor(Binding keyBinding,
			Object key) throws AccessorConstructionException {
		
		assert b.isOpen();
		readLock();
		try {			
			Object rk = key;
			Object lk = params.adapterScheme.getAdapter(keyBinding, kb, true, true).adapt(rk);
			
			BinaryObject sa = getChild(lk);
			if (sa!=null) return (T) sa;
			
			Entry e = index.getKey(lk);
			if (e == null) throw new AccessorConstructionException("Map doesn't contain the requested element");
			
			long valuePos;
			if (ks.getConstantSize()!=null) {
				valuePos = e.pos + ks.getConstantSize();
			} else {
				b.position(e.pos);
				ks.skip(b, null);
				valuePos = b.position();
			}
			
			long valueSize;
			if (vs.getConstantSize()!=null) {
				valueSize = vs.getConstantSize();
			} else {
				b.position(valuePos);
				vs.skip(b, null);
				valueSize = b.position() - valuePos;
			}
			
			// Instantiate correct sub accessor. 
			sa = createSubAccessor(vb.type(), valuePos, valueSize, params);
			children.put(lk, new SoftReference<BinaryObject>(sa));
				
			// Add component interest sets
			if (listeners!=null) {
				MutableVariant kv = new MutableVariant(kb, lk);
				ListenerEntry le = listeners;
				while (le!=null) {				
					MapInterestSet is = le.getInterestSet();
	
					// Generic element interest
					InterestSet gis = is.getComponentInterest(); 
					if (gis != null) {
						try {
							ChildReference childPath = ChildReference.concatenate(le.path, new KeyReference(kv) );
							sa.addListener(le.listener, gis, childPath, le.executor);
						} catch (AccessorException e1) {
							throw new AccessorConstructionException(e1);
						}
					}
						
					// Specific element interest
					InterestSet cis = is.getComponentInterest(kv); 
					if (cis != null) {
						try {
							ChildReference childPath = ChildReference.concatenate(le.path, new KeyReference(kv) );
							sa.addListener(le.listener, cis, childPath, le.executor );
						} catch (AccessorException e1) {
							throw new AccessorConstructionException(e1);
						}
					}
						
					// Next listener
					le = le.next;
				}
			}
			
			return (T) sa;
		} catch (AdaptException e) {
			throw new AccessorConstructionException(e);
		} catch (AdapterConstructionException e) {
			throw new AccessorConstructionException(e);
		} catch (IOException e) {
			throw new AccessorConstructionException(e);
		} catch (AccessorException e) {
			throw new AccessorConstructionException(e);
		} finally {
			readUnlock();
		}
	}
	
	@Override
	public Object[] getValues(Binding valueBinding) throws AccessorException {
		assert b.isOpen();
		readLock();
		try {
			Serializer rvs = params.serializerScheme.getSerializer(valueBinding);
			b.position(0L);
			int count = b.readInt();
			Object[] result = new Object[ count ];
			for (int i=0; i<result.length; i++) {
				ks.skip(b, null);
				result[i] = rvs.deserialize(b, null);
			}
			return result;
		} catch (IOException e) {
			throw new AccessorException( e );
		} catch (SerializerConstructionException e) {
			throw new AccessorException( e );
		} finally {
			readUnlock();
		}
	}

	@Override
	public void setValueNoflush(Binding binding, Object mapValue)
			throws AccessorException {		
		assert b.isOpen();
		MapBinding mb = (MapBinding) binding;
		if (children.isEmpty() && listeners==null) {
			writeLock();
			try {
				// Write
				Serializer s = params.serializerScheme.getSerializer( mb );
				int size = s.getSize(mapValue, null);
				b.setLength(size);
				b.position(0L);
				// Write all at once
				s.serialize(b, null, mapValue);			
			} catch (IOException e) {
				throw new AccessorException( e );
			} catch (SerializerConstructionException e) {
				throw new AccessorException( e );
			} finally {
				writeUnlock();
			}
		} else {

			writeLock();
			try {
				int nc = mb.size(mapValue);
				Object nks[] = new Object[nc];
				Object nvs[] = new Object[nc];
				mb.getAll(mapValue, nks, nvs);
				setAllNoflush(mb.getKeyBinding(), mb.getValueBinding(), nks, nvs);
			} catch (BindingException e) {
				throw new AccessorException(e);
			} finally {
				writeUnlock();
			}
			
		}
	}
	

	@Override
	public void clearNoflush() throws AccessorException {
		assert b.isOpen();
		writeLock();
		try {
			boolean hasListeners = listeners!=null;
			Object[] keys = hasListeners ? getKeys(kb) : null; 
			
			// Write
			b.position(0L);
			b.writeInt(0);
			b.setLength(4);
						
			// Disconnect sub-accessor
			for (java.lang.ref.Reference<BinaryObject> ref : children.values()) {
				BinaryObject sa = ref.get();
				if (sa==null) continue;
				sa.invalidatedNotification();
			}
			children.clear();
			
			// Notify Listeners
			ListenerEntry le = listeners;
			while (le!=null) {				
				MapInterestSet is = le.getInterestSet();
				for (Object key : keys) {
					MutableVariant var = new MutableVariant(kb, key);
					if (is.inNotificationsOf(var)) {
						MapEntryRemoved e = new MapEntryRemoved(var); 
						emitEvent(le, e);
					}
				}
								
				le = le.next;
			}		
			
		} catch (IOException e) {
			throw new AccessorException( e );
		} finally {
			writeUnlock();
		}
		
	}

	@Override
	public void putAllNoflush(Binding keyBinding, Binding valueBinding,
			Map<Object, Object> from) throws AccessorException {
		int nc = from.size();
		Object[] nks = new Object[ nc ];
		Object[] nvs = new Object[ nc ];		
	    int i=0;
	    for (Map.Entry<Object, Object> e : from.entrySet()) {
	    	nks[i] = e.getKey();
	    	nvs[i] = e.getValue();
	    	i++;
	    }
		putAllNoflush(keyBinding, valueBinding, nks, nvs);
	}

	@Override
	public void putAllNoflush(Binding kb, Binding vb,
			Object[] nks, Object[] nvs) throws AccessorException {
		int c = nks.length;
		int newItemsCount = 0;
		for (int i=0; i<c; i++) {
			boolean hadPreviousValue = _putNoflush(kb, nks[i], vb, nvs[i]);
			if (!hadPreviousValue) newItemsCount++;
		}

		if (newItemsCount>0) {
			assert b.isOpen();
			writeLock();
			try {
				b.position(0L);
				int oldCount = b.readInt();
				b.position(0L);
				b.writeInt( oldCount + newItemsCount);			
			} catch (IOException e) {
				throw new AccessorException(e);
			} finally {
				writeUnlock();
			}
		}
	
	}
	
	public void setAllNoflush(Binding kb, Binding vb,
			Object[] nks, Object[] nvs) throws AccessorException {
		assert b.isOpen();
		writeLock();
		try {
			Serializer ks = params.serializerScheme.getSerializer( kb );
			Serializer vs = params.serializerScheme.getSerializer( vb );
			int nc = nks.length;
			// Generate removed, assigned and added events
			if (listeners!=null) {
				
				b.position(4L);			
				int ni = 0;
				
				// New and Old map lowest Keys 
				Object nk = nks.length>0 ? nks[0] : null;
				Object ok = b.length()<=4 ? null : ks.deserialize(b, null);
				
				while (nk!=null || ok!=null) {
					int c = 0;
					if (nk==null) {
						c = -1;
					} else if (ok==null) {
						c= 1;
					} else c = kb.compare(ok, nk);
					if (c==0) {
						// old key == new key
						// Assigned new value
						MutableVariant kv = new MutableVariant(kb, kb.isImmutable() ? nk : kb.clone(nk));
						ListenerEntry le = listeners;
						while (le!=null) {				
							MapInterestSet is = le.getInterestSet();
							if (is.inNotificationsOf(kv)) {
								MutableVariant vv = null;
								if (is.inValuesOf(kv)) {
									Object nv = vb.isImmutable() ? nvs[ni] : vb.clone(nvs[ni]);
									vv = new MutableVariant(vb, nv);									
								}
								Event e = new ValueAssigned( new KeyReference( kv ), vv);
								emitEvent(le, e);
							}
							le = le.next;
						}
						// Move new pointer
						ni++;
						nk = ni<nks.length ? nks[ni] : null;
						// Move old pointer
						vs.skip(b, null);
						ok = b.position()<b.length() ? ks.deserialize(b, null) : null;  						
					} 
					
					else if (c<0) {
						// old key < new key
						MutableVariant kv = new MutableVariant(kb, kb.isImmutable() ? ok : kb.clone(ok));
						ListenerEntry le = listeners;
						while (le!=null) {				
							MapInterestSet is = le.getInterestSet();
							if (is.inNotificationsOf(kv)) {								
								MapEntryRemoved e = new MapEntryRemoved(kv);
								emitEvent(le, e);
							}
							le = le.next;
						}						
						// Move old pointer
						vs.skip(b, null);
						ok = b.position()<b.length() ? ks.deserialize(b, null) : null;  						
					}
					
					else if (c>0) {
						// new key < old key
						MutableVariant kv = new MutableVariant(kb, kb.isImmutable() ? nk : kb.clone(nk));

						if (listeners!=null) {
							Object nv = null;
							ListenerEntry le = listeners;
							while (le!=null) {				
								MapInterestSet is = le.getInterestSet();
								if (is.inNotificationsOf(kv)) {								
									MutableVariant vv = null;
									if (is.inValuesOf(kv)) {
										if (nv==null) {
											nv = vb.clone( nvs[ni] );
										}
										vv = new MutableVariant(vb, nv);
									}
									MapEntryAdded e = new MapEntryAdded(kv, vv);
									emitEvent(le, e);
								}
								le = le.next;
							}
						}
						
						// Move new pointer
						ni++;
						nk = ni<nks.length ? nks[ni] : null;
					}
				}
				
			}
			
			// Calc Size
			long size = 4;			
			if (ks.getConstantSize()!=null) {
				size += ((long)nc) * ks.getConstantSize();
			} else {
				for (int i=0; i<nc; i++) size += ks.getSize(nks[i], null);
				
			}
			if (vs.getConstantSize()!=null) {
				size += ((long)nc) * vs.getConstantSize();
			} else {
				for (int i=0; i<nc; i++) size += vs.getSize(nvs[i], null);
				
			}
			b.setLength(size);			
			
			// Write entry by entry and update positions of children
			b.position(0L);
			b.writeInt(nc);
			for (int i=0; i<nc; i++) {
				Object nk = nks[i];
				Object nv = nvs[i];
				long startPos = b.position();
				ks.serialize(b, null, nk);
				vs.serialize(b, null, nv);
				long endPos = b.position();
				long len = endPos - startPos;
				Object lk = params.adapterScheme.adapt(nk, kb, this.kb);
				BinaryObject sa = getChild(lk);
				if (sa!=null) sa.b.setPositionInSource(startPos, len);					
			}
				
			
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (AdaptException e) {
			throw new AccessorException(e);
		} catch (SerializerConstructionException e) {
			throw new AccessorException(e);
		} finally {
			writeUnlock();
		}
	}

	
	@Override
	public void putNoflush(Binding kb, Object key,
			Binding vb, Object value) throws AccessorException {
		assert b.isOpen();
		writeLock();
		try {
			boolean hadPreviousEntry = _putNoflush(kb, key, vb, value);
		
			if (!hadPreviousEntry) {
				b.position(0L);
				int oldCount = b.readInt();
				b.position(0L);
				b.writeInt( oldCount + 1);			
			}
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (RuntimeSerializerConstructionException e) {
			throw new AccessorException(e);
		} finally {
			writeUnlock();
		}
	}
	
	/**
	 * Put an entry. Does not update size.
	 * 
	 * @param kb
	 * @param key
	 * @param vb
	 * @param value
	 * @return true if previous entry existed
	 * @throws AccessorException
	 */
	private boolean _putNoflush(Binding kb, Object key,
			Binding vb, Object value) throws AccessorException {
		writeLock();
		try {
			Object lk = adapt(key, kb, this.kb);
			long insertPos = index.getInsertPos(lk);
			Serializer ks = params.serializerScheme.getSerializer( kb );
			Serializer vs = params.serializerScheme.getSerializer( vb );			
			long newSize = ks.getSize(key, null) + vs.getSize(value, null);
			
			if (insertPos<0) {				
				// Insert new entry
				// Write
				long pos = -insertPos;
				b.position(pos);
				b.insertBytes(newSize, ByteSide.Neither);
				b.position(pos);
				ks.serialize(b, null, key);
				vs.serialize(b, null, value);
				
				// Key variant
				MutableVariant kv = new MutableVariant(this.kb, lk);
				
				// Notify Listeners
				ListenerEntry le = listeners;
				while (le!=null) {				
					MapInterestSet is = le.getInterestSet();
					if (is.inNotificationsOf(kv)) {
						
						MutableVariant vv = null;
						if (is.inValuesOf(kv)) vv = new MutableVariant(vb, vb.isImmutable() ? value : vb.clone(value));
						
						// Notify about new entry
						MapEntryAdded e = new MapEntryAdded(kv, vv);
						emitEvent(le, e);
					}
					
					le = le.next;
				}
				
				// Optimization for sequential write
				// Create sub accessor for the last entry
				if (insertPos==b.length() && constantSize==null) {
					BinaryObject sa = getChild(lk);
					if (sa==null) {
						// Instantiate correct sub accessor. 
						try {
							sa = createSubAccessor(vb.type(), pos, newSize, params);
							children.put(lk, new SoftReference<BinaryObject>(sa));
						} catch (AccessorConstructionException e1) {
						}
					}
				}
				
				return false;
			}
			
			// Replace previous entry			
			// Write
			Entry e = new Entry(lk, insertPos, null);
			long pos = insertPos;
			long oldSize = index.size(e);
			
			if (oldSize<newSize) {
				b.position(pos);
				b.insertBytes(newSize - oldSize, ByteSide.Right);
			} else if (newSize<oldSize) {
				b.position(pos);
				b.removeBytes(oldSize - newSize, ByteSide.Right);
			}
			
			b.position(pos);
			ks.serialize(b, null, key);
			vs.serialize(b, null, value);
						
			// Notify Listeners
			ListenerEntry le = listeners;
			if (listeners!=null) {
				MutableVariant kv = new MutableVariant(kb, lk);
				while (le!=null) {				
					MapInterestSet is = le.getInterestSet();
					if (is.inNotificationsOf(kv)) {
						
						MutableVariant vv = null;
						if (is.inValuesOf(kv)) vv = new MutableVariant(vb, vb.isImmutable() ? value : vb.clone(value));
						
						// Notify about new entry
						Event ev = new ValueAssigned( new KeyReference(kv), vv);
						emitEvent(le, ev);
					}
					
					le = le.next;
				}
			}

			// Update child
//			BinaryObject sa = getChild(lk);				
//			if (sa!=null) {
//				sa.b.setPositionInSource(pos, newSize);
//			}
			
			return true;
			
		} catch (AdaptException e1) {
			throw new AccessorException(e1);
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (RuntimeSerializerConstructionException e) {
			throw new AccessorException(e);
		} catch (AdapterConstructionException e) {
			throw new AccessorException(e);
		} catch (SerializerConstructionException e) {
			throw new AccessorException(e);
		} finally {
			writeUnlock();
		}
		
	}

	@Override
	public void removeNoflush(Binding keyBinding, Object key)
			throws AccessorException {
		assert b.isOpen();
		writeLock();
		try {
			Object lk = params.adapterScheme.getAdapter(keyBinding, kb, true, listeners!=null).adapt(key);
			Entry e = index.getKey(lk);
			if (e==null) return;
			// Write
			int oldSize = size();
			b.position(0L);
			b.writeInt( oldSize - 1 );
			long size = index.size(e);
			b.position(e.pos);
			b.removeBytes(size, ByteSide.Right);
			
			// Disconnect sub-accessor
			BinaryObject sa = getChild(lk);
			// Notify about disconnection of sub-accessor
			if (sa!=null) {
				sa.invalidatedNotification();
				children.remove(lk);
			}				
			
			// Notify Listeners
			if (listeners!=null) {
				MutableVariant var = new MutableVariant(kb, lk);
				ListenerEntry le = listeners;
				while (le!=null) {				
					MapInterestSet is = le.getInterestSet();				
					if (is.inNotificationsOf(var)) {
						MapEntryRemoved e2 = new MapEntryRemoved(var); 
						emitEvent(le, e2);
					}
									
					le = le.next;
				}		
			}
			
		} catch (IOException e) {
			throw new AccessorException(e);
		} catch (AdaptException e) {
			throw new AccessorException(e);
		} catch (AdapterConstructionException e) {
			throw new AccessorException(e);
		} finally {
			writeUnlock();
		}
	}
	
	
	@Override
	public void addListener(Listener listener, InterestSet interestSet,
			ChildReference path, Executor executor) throws AccessorException {
		super.addListener(listener, interestSet, path, executor);
		MapInterestSet is = (MapInterestSet) interestSet;

		for (Object key : children.keySet()) {
			BinaryObject sa = getChild(key);
			if (sa==null) continue;
			
			MutableVariant vkey = new MutableVariant(kb, key);
			InterestSet cis = is.getComponentInterest();
			if (cis!=null) {
				ChildReference childPath = ChildReference.concatenate( path, new KeyReference(vkey) );
				sa.addListener(listener, cis, childPath, executor);				
			}
			cis = is.getComponentInterest( vkey );
			if (cis!=null) {
				ChildReference childPath = ChildReference.concatenate( path, new KeyReference(vkey) );
				sa.addListener(listener, cis, childPath, executor);				
			}
		}		
	}		
	
	@Override
	public void removeListener(Listener listener) throws AccessorException {
		ListenerEntry e = detachListener(listener);
		if (e==null) return;
		MapInterestSet is = (MapInterestSet) e.interestSet;
		
		for (Map.Entry<Object, java.lang.ref.Reference<BinaryObject>> entry : children.entrySet()) {
			BinaryObject sa = entry.getValue().get();
			if (sa==null) continue;
			Object key = entry.getKey();
			
			MutableVariant vkey = new MutableVariant(kb, key);
			InterestSet cis = is.getComponentInterest();
			if (cis!=null) {
				sa.removeListener(listener);				
			}
			cis = is.getComponentInterest( vkey );
			if (cis!=null) {
				sa.removeListener(listener);				
			}
		}
		
	}
	
	@Override
	Event applyLocal(Event e, boolean makeRollback) throws AccessorException {
		Event rollback = null;
		
		if (e instanceof ValueAssigned) {
			try {
				ValueAssigned va = (ValueAssigned) e;
				if (makeRollback) {
					Binding binding = params.bindingScheme.getBinding(type());
					rollback = new ValueAssigned(binding, getValue(binding));				
				}
				setValueNoflush(va.newValue.getBinding(), va.newValue.getValue());
				return rollback;
			} catch (BindingConstructionException e1) {
				throw new AccessorException( e1 );
			}
		} else if (e instanceof MapEntryAdded) {
			MapEntryAdded ea = (MapEntryAdded) e;
			if (ea.key==null) throw new AccessorException("Cannot apply entry added event because key is missing");
			if (ea.value==null) throw new AccessorException("Cannot apply entry added event because value is missing");
			boolean hadValue = containsKey(ea.key.getBinding(), ea.key.getValue());
			if (hadValue) throw new AccessorException("Could not add entry to key that already existed");
			
			if (makeRollback) {				
				rollback = new MapEntryRemoved( ea.key );
			}
			
			putNoflush(ea.key.getBinding(), ea.key.getValue(), ea.value.getBinding(), ea.value.getValue());
			return rollback;
			
		} else if (e instanceof MapEntryRemoved) {
			MapEntryRemoved er = (MapEntryRemoved) e;
			
			if (makeRollback) {
				boolean hadValue = containsKey(er.key.getBinding(), er.key.getValue());
				
				if (hadValue) {				
					Object oldValueObj = get(er.key.getBinding(), er.key.getValue(), vb);
					MutableVariant oldKey = er.key;
					MutableVariant oldValue = new MutableVariant(vb, oldValueObj);
					rollback = new MapEntryAdded(oldKey, oldValue);
				} else {
					rollback = new MapEntryRemoved( er.key.clone() );
				}
			}
			
			removeNoflush( er.key.getBinding(), er.key.getValue() );
			return rollback;
			
		} else {
			throw new AccessorException("Cannot apply "+e.getClass().getName()+" to Map Type");
		}		
	}

	
	
	@Override
	public void put(Binding keyBinding, Object key, Binding valueBinding,
			Object value) throws AccessorException {
		assert b.isOpen();
		writeLock();
		try {
			putNoflush(keyBinding, key, valueBinding, value);
			b.flush();
		} catch (IOException e) {
			throw new AccessorException(e);
		} finally {
			writeUnlock();
		}
	}

	@Override
	public void putAll(Binding keyBinding, Binding valueBinding,
			Map<Object, Object> from) throws AccessorException {
		assert b.isOpen();
		writeLock();
		try {
			putAllNoflush(keyBinding, valueBinding, from);
			b.flush();
		} catch (IOException e) {
			throw new AccessorException(e);
		} finally {
			writeUnlock();
		}
	}

	@Override
	public void putAll(Binding keyBinding, Binding valueBinding, Object[] keys,
			Object[] values) throws AccessorException {
		assert b.isOpen();
		writeLock();
		try {
			putAllNoflush(keyBinding, valueBinding, keys, values);
			b.flush();
		} catch (IOException e) {
			throw new AccessorException(e);
		} finally {
			writeUnlock();
		}
	}

	@Override
	public void remove(Binding keyBinding, Object key) throws AccessorException {
		assert b.isOpen();
		writeLock();
		try {
			removeNoflush(keyBinding, key);		
			b.flush();
		} catch (IOException e) {
			throw new AccessorException(e);
		} finally {
			writeUnlock();
		}
	}
	
	
	/** Interface for a search structure */
	abstract class Index {
		/**
		 * Get insert pos
		 * @param key
		 * @return if >0 position of existing entry of same key, <0 insertion position 
		 * @throws AccessorException 
		 */
		abstract long getInsertPos(Object key) throws AccessorException;

		abstract Entry getKey(Object key) throws AccessorException;		
		abstract Entry floor(Object key) throws AccessorException;
		abstract Entry ceiling(Object key) throws AccessorException;
		abstract Entry higher(Object key) throws AccessorException;
		abstract Entry lower(Object key) throws AccessorException;
		abstract long size(Entry e) throws AccessorException;		
		
		Entry first() throws AccessorException {
			try {
				b.position(0L);
				int count = b.readInt();
				if (count==0) return null;
				Object k = ks.deserialize(b);
				java.lang.ref.Reference<BinaryObject> ref = children.get(k);
				BinaryObject sa = ref == null ? null : ref.get();
				return new Entry(k, 4, sa);		
			} catch (IOException e) {
				throw new AccessorException(e);
			}
		}
		
		abstract Entry last() throws AccessorException;
				
	}	
	
	static class Entry {
		// Optional child accessor
		BinaryObject accessor;
		Object key;
		long pos;
		public Entry(Object key, long pos, BinaryObject accessor) {
			this.key = key; this.pos = pos; this.accessor = accessor;
		}
	}

	/** Entries are indexed a table */
//	class Table implements Index {		
//	}
	
	/** Entry size is constant, binary Search */ 
	class Constant extends Index {
		
		Entry last() throws AccessorException {
			try {
				if (b.length()<=4) return null;
				long pos = b.length() - constantSize;
				b.position( pos );
				Object key = ks.deserialize(b);
				return new Entry(key, pos, null);
			} catch (IOException e) {
				throw new AccessorException(e);
			}		
		}
		

		@Override
		long getInsertPos(Object key) throws AccessorException {
			try {
				int count = count();
				if (count==0) return -4L;			
				
				// Check if it is the last entry
				long pos = b.length() - constantSize;
				b.position( pos );
				Object lastKey = ks.deserialize(b);
				int c = kb.compare(lastKey, key);
				if (c<0) return -b.length();
				if (c==0) return pos;
				
				// We can narrow down the search to region between two existing children 
				Entry fc = floorChildEntry(key);
				Entry cc = ceilingChildEntry(key);			
				
				int fromIndex = fc == null ? 0 : indexOf(fc);
				int toIndex = cc == null ? count : indexOf(cc)+1; 
				
				// Do binary search			
				int r = binarySearch(fromIndex, toIndex, key);
				if (r>=0) return getPos(r);
				r=-(r+1);
				if (r==count) return -b.length();
				return -getPos(r);
			} catch (IOException e) {
				throw new AccessorException(e);
			} catch (BindingException e) {
				throw new AccessorException(e);
			}		
		}	
		
		int indexOf(Entry e) {
			return (int) ((e.pos - 4L) / constantSize);
		}
		int indexOf(long pos) {
			return (int) ((pos - 4L) / constantSize);
		}
		
		
		/**
		 * 
		 * @param fromIndex
		 * @param toIndex exclusive
		 * @param key
		 * @return
		 * @throws AccessorException
		 */
		int binarySearch(int fromIndex, int toIndex, Object key) throws AccessorException {
			int low = fromIndex;
			int high = toIndex - 1;
	
			while (low <= high) {
			    int mid = (low + high) >>> 1;
			    Object midVal = getKey(mid);
			    int cmp = kb.compare(midVal, key);
	
			    if (cmp < 0)
				low = mid + 1;
			    else if (cmp > 0)
				high = mid - 1;
			    else
				return mid; // key found
			}
			return -(low + 1);  // key not found.			
		}

		@Override
		public Entry getKey(Object key) throws AccessorException {
			BinaryObject sa = getChild(key);
			if (sa!=null) return new Entry(key, sa.b.getStartPositionInSourceBinary(), sa);
			long pos = getInsertPos(key);
			if (pos<0) return null;			
			return new Entry(key, pos, null);
		}

		@Override
		public long size(Entry e) {			
			return constantSize;
		}
		
		Object getKey(int index) throws AccessorException {
			try {
				long pos = 4L + ((long)index) * constantSize;
				b.position(pos);
				return ks.deserialize(b);
			} catch (IOException e) {
				throw new AccessorException(e);
			}		
		}

		Entry getEntry(int index) throws AccessorException {
			try {
				long pos = 4L + ((long)index) * constantSize;
				b.position(pos);
				Object key = ks.deserialize(b);
				return new Entry(key, pos, null);
			} catch (IOException e) {
				throw new AccessorException(e);
			}		
		}

		long getPos(int index) {
			return 4L + ((long)index) * constantSize;
		}
		
		int count() throws IOException {
			return (int) ((b.length()-4) / constantSize);
		}
		
		@Override
		Entry ceiling(Object key) throws AccessorException {
			try {
				long pos = getInsertPos(key);
				// Exact match
				if (pos>0) return new Entry(key, pos, getChild(key));
				pos = -pos;
				int index = indexOf(pos);
				if (index>=count()) return null;
				key = getKeyAt(pos);
				return new Entry(key, pos, null);
			} catch (IOException e) {
				throw new AccessorException(e);
			} catch (BindingException e) {
				throw new AccessorException(e);
			}		
		}

		@Override
		Entry higher(Object key) throws AccessorException {
			try {
				long pos = getInsertPos(key);
	
				if (pos>0) {
					// Exact match
					int index = indexOf(pos)+1;
					if (index>=count()) return null;
					pos = getPos(index);
					key = getKeyAt(pos);
					return new Entry(key, pos, null);
				} else {
					// Insert here match
					int index = indexOf(-pos);
					if (index>=count()) return null;
					pos = getPos(index);
					key = getKeyAt(pos);
					return new Entry(key, pos, null);
				}			
			} catch (IOException e) {
				throw new AccessorException(e);
			} catch (BindingException e) {
				throw new AccessorException(e);
			}		
			
		}

		@Override
		Entry lower(Object key) throws AccessorException {
			try {
				long pos = getInsertPos(key);
				// Exact match
				if (pos>0) {
					int index = indexOf(pos)-1;
					if (index<0) return null;
					pos = getPos(index);
					key = getKeyAt(pos);
					return new Entry(key, pos, null);
				} else {
					int index = indexOf(-pos)-1;
					if (index<0) return null;
					pos = getPos(index);
					key = getKeyAt(pos);
					return new Entry(key, pos, null);
				}
			} catch (IOException e) {
				throw new AccessorException(e);
			} catch (BindingException e) {
				throw new AccessorException(e);
			}		
		}

		@Override
		Entry floor(Object key) throws AccessorException {
			try {
				long pos = getInsertPos(key);
				// Exact match
				if (pos>0) return new Entry(key, pos, getChild(key));
				int index = indexOf(-pos)-1;
				if (index<0) return null;
				pos = getPos(index);		
				key = getKeyAt(pos);
				return new Entry(key, pos, null);
			} catch (IOException e) {
				throw new AccessorException(e);
			} catch (BindingException e) {
				throw new AccessorException(e);
			}		
		}

	}
	
	/** Variable size enetry, Sequential search */
	class Sequential extends Index {

		/**
		 * Get insert pos
		 * @param key
		 * @return if >0 position of existing entry of same key, <0 insertion position 
		 * @throws AccessorException 
		 */
		@Override
		long getInsertPos(Object key) throws AccessorException {
			try {
				Entry start = floorChildEntry(key);
				// Exact match
				if (start !=null && kb.equals(key, start.key)) {
					return start.pos;
				}
				
				long len = b.length();
				long pos = start==null ? 4L : start.pos;
				b.position(pos);
				while (b.position()<len) {
					pos = b.position();
					Object k = ks.deserialize(b, null);
					int c = kb.compare(key, k);
					if (c==0) return pos;
					if (c<0) return -pos;
					vs.skip(b, null);
				}
				return -len;
			} catch (IOException e) {
				throw new AccessorException(e);
			} catch (BindingException e) {
				throw new AccessorException(e);
			}		
		}
		
		@Override
		Entry getKey(Object key) throws AccessorException {
			BinaryObject sa = getChild(key);
			if (sa!=null) return new Entry(key, sa.b.getStartPositionInSourceBinary(), sa);
			
			long pos = getInsertPos(key);
			if (pos<0) return null;
			return new Entry(key, pos, null);
		}

		@Override
		Entry last() throws AccessorException {
			try {
				Entry e = lastChildEntry();	
				long startPos = e!=null ? e.pos : 4L;
				b.position(startPos);
				Entry result = e!=null ? new Entry(e.key, e.pos, e.accessor) : new Entry(null, 0, null);
				while (b.position() < b.length()) {
					result.key = ks.deserialize(b, null);
					result.pos = b.position();					
					vs.skip(b, null);
					long valueLen = b.position() - result.pos;
					result.accessor = createSubAccessor(vb.type(), result.pos, valueLen, params);
					children.put(result.key, new SoftReference<BinaryObject>( result.accessor ));
				}
				return (result.key == null) ? null : result;
			} catch (IOException e) {
				throw new AccessorException(e);
			} catch (BindingException e) {
				throw new AccessorException(e);
			} catch (AccessorConstructionException e) {
				throw new AccessorException(e);
			}
		}

		@Override
		long size(Entry e) throws AccessorException {
			try {
				long keyLen;
				if (ks.getConstantSize()!=null) {
					keyLen = ks.getConstantSize();
				} else {
					b.position(e.pos);
					ks.skip(b, null);
					keyLen = b.position() - e.pos;
				}
				
				long valueLen;				
				if (e.accessor!=null) {
					valueLen = e.accessor.b.length();
				} else if (vs.getConstantSize()!=null) {
					valueLen = vs.getConstantSize();
				} else {
					long pos = e.pos + keyLen;
					b.position(pos);
					vs.skip(b, null);
					valueLen = b.position() - pos; 
				}
				return keyLen + valueLen;
			} catch (IOException e1) {
				throw new AccessorException(e1);
			}
		}

		@Override
		Entry ceiling(Object key) throws AccessorException {
			try {
				long pos = getInsertPos(key);
				// Exact match
				if (pos>0) return new Entry(key, pos, getChild(key));
				pos = -pos;
				return getEntryAt(pos);
			} catch (IOException e) {
				throw new AccessorException(e);
			} catch (BindingException e) {
				throw new AccessorException(e);
			}
		}

		@Override
		Entry higher(Object key) throws AccessorException {
			try {
				long pos = getInsertPos(key);
				// Exact match
				if (pos>0) {
					if (pos>=b.length()) return null;
					b.position(pos);
					ks.skip(b, null);
					vs.skip(b, null);
					return getEntryAt(b.position());
				}
				pos = -pos;
				return getEntryAt(pos);
			} catch (IOException e) {
				throw new AccessorException(e);
			} catch (BindingException e) {
				throw new AccessorException(e);
			}		
		}

		@Override
		Entry lower(Object key) throws AccessorException {
			try {
				Entry start = lowerChildEntry(key);
				long len = b.length();
				long pos = start==null ? 4L : start.pos;
				long prevPos = 0;
				Object k = null;
				Object prevK = null;
				b.position(pos);
				while (b.position()<len) {
					prevPos = pos;
					pos = b.position();
					prevK = k;
					k = ks.deserialize(b, null);
					long valuePos = b.position();
					
					// Compare current key with search key
					int c = kb.compare(key, k);
					if (c<=0) {
						if (prevK==null) return null;
						return new Entry(prevK, prevPos, null);
					}
					vs.skip(b, null);
					long valueLen = b.position() - valuePos;
					assert(valueLen>=0);
					java.lang.ref.Reference<BinaryObject> ref = children.get(k);
					BinaryObject sa = ref!=null?ref.get():null;
					if (sa==null) {
						sa = createSubAccessor(vb.type(), valuePos, valueLen, params);
						children.put(k, new SoftReference<BinaryObject>(sa));
					}					
				}
				// There was no match, return the last entry
				return new Entry(k, pos, null);	
			} catch (IOException e) {
				throw new AccessorException(e);
			} catch (BindingException e) {
				throw new AccessorException(e);
			} catch (AccessorConstructionException e) {
				throw new AccessorException(e);
			}			
		}

		@Override
		Entry floor(Object key) throws AccessorException {
			try {			
				Entry start = floorChildEntry(key);
				// Exact match
				if (start !=null && kb.equals(key, start.key)) {
					return start;
				}
								
				long len = b.length();
				long pos = start==null ? 4L : start.pos;
				long prevPos = 0;
				Object k = null;
				Object prevK = null;
				BinaryObject prevAccessor = null;
				b.position(pos);
				while (b.position()<len) {
					prevPos = pos;
					pos = b.position();
					prevK = k;
					k = ks.deserialize(b, null);
					long valuePos = b.position();
					
					int c = kb.compare(key, k);
					// Went over
					if (c<0) {
						if (prevK==null) return null;
						return new Entry(prevK, prevPos, prevAccessor);
					}
					vs.skip(b, null);
					long valueLen = valuePos - pos;
					java.lang.ref.Reference<BinaryObject> ref = children.get(k);
					BinaryObject sa = ref!=null?ref.get():null;
					if (sa==null) {
						prevAccessor = createSubAccessor(vb.type(), valuePos, valueLen, params);
						children.put(k, new SoftReference<BinaryObject>(prevAccessor));
					}
					// Exact match
					if (c==0) {
						return new Entry(k, pos, prevAccessor);
					}					
				}
				return new Entry(k, pos, prevAccessor);	
			} catch (IOException e) {
				throw new AccessorException(e);
			} catch (BindingException e) {
				throw new AccessorException(e);
			} catch (AccessorConstructionException e) {
				throw new AccessorException(e);
			}
		}
	}
	
}