gt: 		if (isleaf(other)) {
context: package org.colomoto.mddlib.internal;
  
  import java.text.ParseException;
  import java.util.Collection;
  import java.util.List;
  import java.util.Stack;
  
  import org.colomoto.mddlib.MDDManager;
  import org.colomoto.mddlib.MDDManagerFactory;
  import org.colomoto.mddlib.MDDVariable;
  import org.colomoto.mddlib.MDDVariableFactory;
  import org.colomoto.mddlib.NodeRelation;
  import org.colomoto.mddlib.VariableEffect;
  import org.colomoto.mddlib.operators.MDDBaseOperators;
  
  /**
   * MDD factory implementation: create, store, retrieve a collection of MDDs.
   * <p>
   * The number of leaves is defined upon creation and can not be changed.
   * <p>
   * MDDs are stored in a large integer array, divided into blocs.
   * Each bloc denotes a MDD node, providing its level and list of children,
   * as well as the reference counter.
   * To avoid duplication, a hashmap allows to find existing nodes quickly.
   * New nodes are added by extending the storage array, but blocs can also
   * be freed when unused. A chained list allows to reuse these free blocs.
   * <p>
   * @see MDDManager for further details.
   * 
   * @author Aurelien Naldi
   */
  public class MDDStoreImpl implements MDDStore {
  
  	private static final int DEFAULT_CAPACITY  = 100;
  	private static final int DEFAULT_HASHITEMS = 20;
  
  	private static final int FILL_LIMIT = 80;
  	
  	private static final int INC_COUNT = 1;
  	private static final int INC_VALUES = 2;
  	
  	private static final int[] NOTFLIP = {1,0};
  	
  	/* Temporary switches to enable/disable freeing nodes */
  	private static final boolean CANFREE=true;
  	private static final boolean CANFREEHASH=CANFREE;
  	
  	
  	protected MDDVariable[] variables;
  
  	private int blocsize;
  
  	private int[] hashcodes;
  	private int[] hashitems;
  	private int[] blocs;
  	
  	// starting point for free blocs/item chained lists
  	private int freeBloc = -1;
  	private int freeItem = -1;
  
  	// first free position at the end of data/hash-items arrays
  	private int lastitem = 0;
  	private int lastbloc = 0;
  
  	private int nbnodes = 0;
  	private final int nbleaves;
  
  	/**
  	 * Create a new MDDStore using the default capacity.
  	 * Note that this constructor should be called through {@link MDDManagerFactory}, not directly.
  	 * 
  	 * @param keys		the list of variables that can be used.
  	 * @param nbleaves	the number of values that can be reached.
  	 */
  	public MDDStoreImpl(Collection<?> keys, int nbleaves) {
  		this(DEFAULT_CAPACITY, keys, nbleaves);
  	}
  
  	/**
  	 * Create a new MDDStore.
  	 * 
  	 * @param capacity		number of nodes that can be stored in the initially reserved space.
  	 * @param keys		    the list of variables that can be used.
  	 * @param nbleaves		the number of values that can be reached.
  	 */
  	private MDDStoreImpl(int capacity, Collection<?> keys, int nbleaves) {
  		if (keys instanceof MDDVariableFactory) {
  			this.variables = getVariables((MDDVariableFactory)keys);
  		} else {
  			this.variables = getBooleanVariables(keys);
  		}
  		
  		this.nbleaves = nbleaves;
  		blocsize = 2;
  		for (MDDVariable var: variables) {
  			if (var.nbval > blocsize ) {
  				blocsize  = var.nbval;
  			}
  		}
  		blocsize += INC_VALUES;  // add INC_VALUES cells in the bloc for metadata (type, usage count)
  		
  		hashcodes = new int[capacity*2];
  		hashitems = new int[DEFAULT_HASHITEMS];
  		reset_hash();
  
  		lastbloc = nbleaves;
  		blocs = new int[nbleaves + capacity*blocsize];
  		for (int i=0 ; i<nbleaves ; i++) {
  			blocs[i] = i;
  		}
  	}
  
  	@Override
  	public MDDManager getManager(List<?> order) {
  		return MDDManagerProxy.getProxy(this, order);
  	}
  
  
  	/* ********************* VARIABLES ****************************** */
  	
  	private MDDVariable[] getBooleanVariables(Collection<?> keys) {
  		
  		MDDVariable[] variables = new MDDVariable[keys.size()];
  		int i=0;
  		byte v = 2;
  		for (Object key: keys) {
  			variables[i] = new MDDVariable(this, i, key, v);
  			i++;
  		}
  		
  		return variables;
  	}
  	
  	private MDDVariable[] getVariables(MDDVariableFactory keys) {
  		
  		MDDVariable[] variables = new MDDVariable[keys.size()];
  		int i=0;
  		for (Object key: keys) {
  			byte v = keys.getNbValue(key);
  			variables[i] = new MDDVariable(this, i, key, v);
  			i++;
  		}
  		
  		return variables;
  	}
  	
  	@Override
  	public MDDVariable getNodeVariable(int n) {
  		if (isleaf(n)) {
  			return null;
  		}
  		
  		int l = getLevel(n);
  		if (l < 0) {
  			throw new RuntimeException("Invalid level found for "+n+": free/use bug?");
  		}
  		return variables[l];
  	}
  
  	@Override
  	public int getVariableIndex(MDDVariable var) {
  		return var.order;
  	}
  
  	@Override
  	public MDDVariable getVariableForKey(Object key) {
  		// TODO: make getVariableID faster if needed
  		//MDDVariable var = m_key2variable.get(o);
  		for (MDDVariable var: variables) {
  			if ( key.equals(var.key) ) {
  				return var;
  			}
  		}
  		return null;
  	}
  
  	@Override
  	public MDDVariable ensureVariable(Object key, byte nbval) {
  		MDDVariable var = getVariableForKey(key);
  		if (var == null) {
  			// create the variable
  			var = new MDDVariable(this, variables.length, key, nbval);
  			MDDVariable[] extended = new MDDVariable[variables.length+1];
  			System.arraycopy(variables, 0, extended, 0, variables.length);
  			extended[variables.length] = var;
  			variables = extended;
  		} else if (var.nbval < nbval) {
  			throw new RuntimeException("changing the number of values of a component is not supported");
  		}
  		return var;
  	}
  
  	@Override
  	public MDDVariable[] getAllVariables() {
  		// should we return a clone?
  		return variables;
  	}
  
  	@Override
  	public synchronized int getNode(int var, int lchild, int rchild) {
  		if (lchild == rchild) {
  			return use(lchild);
  		}
  		if ((!isleaf(lchild) && blocs[lchild] <= var) || (!isleaf(rchild) && blocs[rchild] <= var)) {
  			System.err.println("Invalid request");
  			return -1;
  		}
  		int hash = compute_bhash(var, lchild, rchild);
  		boolean hashexists = hashcodes[hash] != -1;
  		if (hashexists) {
  			int pos = hashcodes[hash];
  			if (is_equal(pos, var, lchild, rchild)) {
  				return use(pos);
  			}
  			int item = hashcodes[hash+1];
  			while (item != -1) {
  				pos = hashitems[item];
  				if (is_equal(pos, var, lchild, rchild)) {
  					return use(pos);
  				}
  				item = hashitems[item+1];
  			}
  		}
  		
  		// node not found, create it
  		int pos = get_free_bloc();
  		blocs[pos] = var;
  		blocs[pos+INC_COUNT] = 0; 	   // reset usage count
  		blocs[pos+INC_VALUES] = lchild;
  		blocs[pos+INC_VALUES+1] = rchild;
  		
  		// increase usage of the children
  		use(lchild);
  		use(rchild);
  		nbnodes++;
  
  		if ( (100*nbnodes)/hashcodes.length > FILL_LIMIT) {
  			extend_hash();
  		} else {
  			place_hash(pos, hash);
  		}
  		return use(pos);
  	}
  
  	private int getNodeFree(int var, int f, int t) {
  		int ret = getNode(var, f, t);
  		free(f);
  		free(t);
  		return ret;
  	}
  	
  	private int getNodeFree(int var, int[] children) {
  		int ret = getNode(var, children);
  		for (int c: children) {
  			free(c);
  		}
  		return ret;
  		
  	}
  
  	@Override
  	public int getNode(int var, int[] children) {
  		// check that the children are not all equal
  		int child = children[0];
  		for (int c:children) {
  			if (c != child) {
  				child = -1;
  				break;
  			}
  			
  			if (!isleaf(c) && blocs[c] <= var) {
  				System.err.println("Invalid node request!");
  				return -1;
  			}
  		}
  		if (child > -1) {
  			return use(child);
  		}
  		
  		int hash = compute_mhash(var, children);
  		boolean hashexists = hashcodes[hash] != -1;
  		if (hashexists) {
  			int pos = hashcodes[hash];
  			if (is_equal(pos, var, children)) {
  				return use(pos);
  			}
  			int item = hashcodes[hash+1];
  			while (item != -1) {
  				pos = hashitems[item];
  				if (is_equal(pos, var, children)) {
  					return use(pos);
  				}
  				item = hashitems[item+1];
  			}
  		}
  		
  		// node not found, create it
  		int pos = get_free_bloc();
  		blocs[pos] = var;
  		blocs[pos+INC_COUNT] = 0; 	   // reset usage count
  		System.arraycopy(children, 0, blocs, pos+INC_VALUES, children.length);
  		
  		for (int c: children) {
  			use(c);
  		}
  		
  		nbnodes++;
  		
  		if ( (100*nbnodes)/hashcodes.length > FILL_LIMIT) {
  			extend_hash();
  		} else {
  			place_hash(pos, hash);
  		}
  		return use(pos);
  	}
  
  	/* ******************** USAGE COUNT ***************************** */
  	
  	@Override
  	public synchronized int use(int node) {
  		if (!isleaf(node)) {
  			blocs[node+INC_COUNT]++;
  		}
  		return node;
  	}
  
  	@Override
  	public synchronized void free(int pos) {
  		if (!CANFREE) {
  			return;
  		}
  		if (isleaf(pos)) {
  			return;
  		}
  		
  		if (blocs[pos+INC_COUNT] > 1) {
  			blocs[pos+INC_COUNT]--;
  			return;
  		}
  
  		if (blocs[pos] < 0) {
  			System.err.println("re-free bloc: "+pos);
  			return;
  		}
  
  		int var = blocs[pos];
  		int nbval = variables[var].nbval;
  		
  		// remove it from the hash
  		freeHash(pos, var, nbval);
  
  		// clear the data and set the bloc as free
  		blocs[pos] = -1;
  		if (lastbloc == pos+blocsize) {
  			lastbloc = pos;
  		} else {
  			blocs[pos+1] = freeBloc;
  			freeBloc = pos;
  		}
  		// free the children
  		for (int i=0 ; i<nbval ; i++) {
  			free(blocs[pos+INC_VALUES+i]);
  			blocs[pos+INC_VALUES+i] = 0;
  		}
  		nbnodes--;
  	}
  	
  	/**
  	 * Internal method to remove an entry from the hashtable.
  	 * This aims to be called by <code>free(int)</code> when needed.
  	 * 
  	 * @param pos
  	 * @param var
  	 * @param nbval
  	 */
  	private void freeHash(int pos, int var, int nbval) {
  		if (!CANFREEHASH) {
  			return;
  		}
  		
  		// compute the hash
  		int hash;
  		if (nbval == 2) {
  			hash = compute_bhash(var, blocs[pos+INC_VALUES], blocs[pos+INC_VALUES+1]);
  		} else {
  			int[] children = new int[variables[var].nbval];
  			System.arraycopy(blocs, pos+INC_VALUES, children, 0, children.length);
  			hash = compute_mhash(var, children);
  		}
  
  		int hpos = hashcodes[hash];
  		int itemPos = hashcodes[hash+1];
  		if (hpos == pos) { 		// the item is in the main hashtable
  			if (itemPos == -1) {
  				hashcodes[hash] = -1;
  			} else {
  				// re-chain back this hashcode
  				hashcodes[hash] = hashitems[itemPos];
  				hashcodes[hash+1] = hashitems[itemPos+1];
  				free_hashitem(itemPos);
  			}
  			return;
  		}
  		
  		if (true) {
  			//return;
  		}
  
  		// the item is not in the main hashtable: look it up in the hashitem linktable
  		int nextItem, prevItem = -1;
  		while (itemPos != -1) {
  			hpos = hashitems[itemPos];
  			nextItem = hashitems[itemPos+1];
  			if (hpos == pos) {
  				if (prevItem == -1) {
  					// first item, link in the main hashcodes array
  					hashcodes[hash+1] = nextItem;
  				} else {
  					// update chain in the hashitems array
  					hashitems[prevItem+1] = nextItem;
  				}
  				free_hashitem(itemPos);
  				return;
  			}
  			prevItem = itemPos;
  			itemPos = nextItem;
  		}
  		System.err.println("item not found !!!!");
  	}
  	
  	/**
  	 * Internal method to destroy a hash item.
  	 * This aims to be called by <code>freeHash</code> when needed.
  	 * 
  	 * @param item
  	 */
  	private void free_hashitem(int item) {
  		if (item < 0) {
  			throw new RuntimeException("Trying to free a negative hashitem");
  		}
  		// free the hash item
  		if (item == lastitem-2) {
  			lastitem = item;
  		} else {
  			hashitems[item]   = -1;
  			hashitems[item+1] = freeItem;
  			freeItem = item;
  		}
  	}
  
  	/**
  	 * Internal method to insert a new hash.
  	 * It works like <code>get_free_bloc</code>
  	 */
  	private void place_hash(int blocPos, int hash) {
  		if (hashcodes[hash] == -1) {
  			hashcodes[hash] = blocPos;
  			hashcodes[hash+1] = -1;
  			return;
  		}
  		int pos;
  		if (freeItem >= 0) {
  			pos = freeItem;
  			freeItem = hashitems[pos+1];
  		} else {
  			pos = lastitem;
  			lastitem += 2;
  			if (lastitem > hashitems.length) {
  				hashitems = extend_array(hashitems);
  			}
  		}
  		
  		hashitems[pos] = blocPos;
  		hashitems[pos+1] = hashcodes[hash+1];
  		if (hashcodes[hash+1] == pos) {
  			System.err.println("BIG BUG with hash link list!");
  		}
  		hashcodes[hash+1] = pos;
  	}
  
  	/**
  	 * Flip the values of leaves reachable in this MDD.
  	 * 
  	 * @param node
  	 * @param newValues
  	 * 
  	 * @return the ID of a node rooting a MDD with the same structure but different leaves
  	 */
  	private int leafFlip(int node, int[] newValues) {
  		if (isleaf(node)) {
  			if (node >= newValues.length) {
  				return node;
  			}
  			return newValues[node];
  		}
  		int level = blocs[node];
  		int nbval = variables[level].nbval;
  		if (nbval == 2) {
  			int l = leafFlip(blocs[node+INC_VALUES], newValues);
  			int r = leafFlip(blocs[node+INC_VALUES+1], newValues);
  			return getNodeFree(level, l, r);
  		}
  		
  		int[] children = new int[nbval];
  		for (int i=0 ; i<children.length ; i++) {
  			children[i] = leafFlip(blocs[node+INC_VALUES+i], newValues);
  		}
  		return getNodeFree(level, children);
  	}
  
  
  	@Override
  	public synchronized int not(int node) {
  		return leafFlip(node, NOTFLIP);
  	}
  
  	@Override
  	public synchronized int mnot(int node, int v) {
  		int[] flipper = new int[v+1];
  		flipper[0] = v;
  		for (int i=1 ; i<v ; i++) {
  			flipper[i] = i;
  		}
  		flipper[v] = 0;
  		return leafFlip(node, flipper);
  	}
  
  
  	@Override
  	public NodeRelation getRelation(int first, int other) {
  		if (first == other) {
  			if (isleaf(first)) {
  				return NodeRelation.LL;
  			}
  			return NodeRelation.NN;
  		}
  		
  		if (isleaf(first)) {
  			if (isleaf(other)) {
  				return NodeRelation.LL;
  			}
  			return NodeRelation.LN;
  		}
  		
  