src/main/java/org/luaj/vm3/LuaTable.java

/*******************************************************************************
 * Copyright (c) 2009 Luaj.org. All rights reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 ******************************************************************************/
package org.luaj.vm3;

import java.lang.ref.WeakReference;
import java.util.Vector;

/**
 * Subclass of {@link LuaValue} for representing lua tables. 
 * <p>
 * Almost all API's implemented in {@link LuaTable} are defined and documented in {@link LuaValue}.
 * <p>
 * If a table is needed, the one of the type-checking functions can be used such as
 * {@link #istable()}, 
 * {@link #checktable()}, or
 * {@link #opttable(LuaTable)} 
 * <p>
 * The main table operations are defined on {@link LuaValue} 
 * for getting and setting values with and without metatag processing:
 * <ul>
 * <li>{@link #get(LuaValue)}</li>  
 * <li>{@link #set(LuaValue,LuaValue)}</li>  
 * <li>{@link #rawget(LuaValue)}</li>  
 * <li>{@link #rawset(LuaValue,LuaValue)}</li>
 * <li>plus overloads such as {@link #get(String)}, {@link #get(int)}, and so on</li>  
 * </ul>
 * <p>
 * To iterate over key-value pairs from Java, use
 * <pre> {@code
 * LuaValue k = LuaValue.NIL;
 * while ( true ) {
 *    Varargs n = table.next(k);
 *    if ( (k = n.arg1()).isnil() )
 *       break;
 *    LuaValue v = n.arg(2)
 *    process( k, v )
 * }}</pre>
 * 
 * <p>
 * As with other types, {@link LuaTable} instances should be constructed via one of the table constructor 
 * methods on {@link LuaValue}:
 * <ul>
 * <li>{@link LuaValue#tableOf()} empty table</li>
 * <li>{@link LuaValue#tableOf(int, int)} table with capacity</li>
 * <li>{@link LuaValue#listOf(LuaValue[])} initialize array part</li>
 * <li>{@link LuaValue#listOf(LuaValue[], Varargs)} initialize array part</li>
 * <li>{@link LuaValue#tableOf(LuaValue[])} initialize named hash part</li>
 * <li>{@link LuaValue#tableOf(Varargs, int)} initialize named hash part</li>
 * <li>{@link LuaValue#tableOf(LuaValue[], LuaValue[])} initialize array and named parts</li>
 * <li>{@link LuaValue#tableOf(LuaValue[], LuaValue[], Varargs)} initialize array and named parts</li>
 * </ul>
 * @see LuaValue
 */
public class LuaTable extends LuaValue implements Metatable {
	private static final int MIN_HASH_CAPACITY = 2;
	private static final LuaString N = valueOf("n");

	/** the array values */
	protected LuaValue[] array;

	/** the hash part */
	protected Slot[] hash;

	/** the number of hash entries */
	protected int hashEntries;

	/** metatable for this table, or null */
	protected Metatable m_metatable;

	/** Construct empty table */
	public LuaTable() {
		array = NOVALS;
		hash = NOBUCKETS;
	}

	/** 
	 * Construct table with preset capacity.
	 * @param narray capacity of array part
	 * @param nhash capacity of hash part
	 */
	public LuaTable(int narray, int nhash) {
		presize(narray, nhash);
	}

	/**
	 * Construct table with named and unnamed parts. 
	 * @param named Named elements in order {@code key-a, value-a, key-b, value-b, ... }
	 * @param unnamed Unnamed elements in order {@code value-1, value-2, ... } 
	 * @param lastarg Additional unnamed values beyond {@code unnamed.length}
	 */
	public LuaTable(LuaValue[] named, LuaValue[] unnamed, Varargs lastarg) {
		int nn = (named != null ? named.length : 0);
		int nu = (unnamed != null ? unnamed.length : 0);
		int nl = (lastarg != null ? lastarg.narg() : 0);
		presize(nu + nl, nn >> 1);
		for (int i = 0; i < nu; i++)
			rawset(i + 1, unnamed[i]);
		if (lastarg != null)
			for (int i = 1, n = lastarg.narg(); i <= n; ++i)
				rawset(nu + i, lastarg.arg(i));
		for (int i = 0; i < nn; i += 2)
			if (!named[i + 1].isnil())
				rawset(named[i], named[i + 1]);
	}

	/**
	 * Construct table of unnamed elements. 
	 * @param varargs Unnamed elements in order {@code value-1, value-2, ... } 
	 */
	public LuaTable(Varargs varargs) {
		this(varargs, 1);
	}

	/**
	 * Construct table of unnamed elements. 
	 * @param varargs Unnamed elements in order {@code value-1, value-2, ... }
	 * @param firstarg the index in varargs of the first argument to include in the table 
	 */
	public LuaTable(Varargs varargs, int firstarg) {
		int nskip = firstarg - 1;
		int n = Math.max(varargs.narg() - nskip, 0);
		presize(n, 1);
		set(N, valueOf(n));
		for (int i = 1; i <= n; i++)
			set(i, varargs.arg(i + nskip));
	}

	public int type() {
		return LuaValue.TTABLE;
	}

	public String typename() {
		return "table";
	}

	public boolean istable() {
		return true;
	}

	public LuaTable checktable() {
		return this;
	}

	public LuaTable opttable(LuaTable defval) {
		return this;
	}

	public void presize(int narray) {
		if (narray > array.length)
			array = resize(array, 1 << log2(narray));
	}

	public void presize(int narray, int nhash) {
		if (nhash > 0 && nhash < MIN_HASH_CAPACITY)
			nhash = MIN_HASH_CAPACITY;
		// Size of both parts must be a power of two.
		array = (narray > 0 ? new LuaValue[1 << log2(narray)] : NOVALS);
		hash = (nhash > 0 ? new Slot[1 << log2(nhash)] : NOBUCKETS);
		hashEntries = 0;
	}

	/** Resize the table */
	private static LuaValue[] resize(LuaValue[] old, int n) {
		LuaValue[] v = new LuaValue[n];
		System.arraycopy(old, 0, v, 0, old.length);
		return v;
	}

	/** 
	 * Get the length of the array part of the table. 
	 * @return length of the array part, does not relate to count of objects in the table. 
	 */
	protected int getArrayLength() {
		return array.length;
	}

	/** 
	 * Get the length of the hash part of the table. 
	 * @return length of the hash part, does not relate to count of objects in the table. 
	 */
	protected int getHashLength() {
		return hash.length;
	}

	public LuaValue getmetatable() {
		return (m_metatable != null) ? m_metatable.toLuaValue() : null;
	}

	public LuaValue setmetatable(LuaValue metatable) {
		boolean hadWeakKeys = m_metatable != null && m_metatable.useWeakKeys();
		boolean hadWeakValues = m_metatable != null && m_metatable.useWeakValues();
		m_metatable = metatableOf(metatable);
		if ((hadWeakKeys != (m_metatable != null && m_metatable.useWeakKeys())) || (hadWeakValues != (m_metatable != null && m_metatable.useWeakValues()))) {
			// force a rehash
			rehash(0);
		}
		return this;
	}

	public LuaValue get(int key) {
		LuaValue v = rawget(key);
		return v.isnil() && m_metatable != null ? gettable(this, valueOf(key)) : v;
	}

	public LuaValue get(LuaValue key) {
		LuaValue v = rawget(key);
		return v.isnil() && m_metatable != null ? gettable(this, key) : v;
	}

	public LuaValue rawget(int key) {
		if (key > 0 && key <= array.length) {
			LuaValue v = m_metatable == null ? array[key - 1] : m_metatable.arrayget(array, key - 1);
			return v != null ? v : NIL;
		}
		return hashget(LuaInteger.valueOf(key));
	}

	public LuaValue rawget(LuaValue key) {
		if (key.isinttype()) {
			int ikey = key.toint();
			if (ikey > 0 && ikey <= array.length) {
				LuaValue v = m_metatable == null ? array[ikey - 1] : m_metatable.arrayget(array, ikey - 1);
				return v != null ? v : NIL;
			}
		}
		return hashget(key);
	}

	protected LuaValue hashget(LuaValue key) {
		if (hashEntries > 0) {
			for (Slot slot = hash[hashSlot(key)]; slot != null; slot = slot.rest()) {
				StrongSlot foundSlot;
				if ((foundSlot = slot.find(key)) != null) {
					return foundSlot.value();
				}
			}
		}
		return NIL;
	}

	public void set(int key, LuaValue value) {
		if (m_metatable == null || !rawget(key).isnil() || !settable(this, LuaInteger.valueOf(key), value))
			rawset(key, value);
	}

	/** caller must ensure key is not nil */
	public void set(LuaValue key, LuaValue value) {
		if (!key.isvalidkey() && !metatag(NEWINDEX).isfunction())
			typerror("table index");
		if (m_metatable == null || !rawget(key).isnil() || !settable(this, key, value))
			rawset(key, value);
	}

	public void rawset(int key, LuaValue value) {
		if (!arrayset(key, value))
			hashset(LuaInteger.valueOf(key), value);
	}

	/** caller must ensure key is not nil */
	public void rawset(LuaValue key, LuaValue value) {
		if (!key.isinttype() || !arrayset(key.toint(), value))
			hashset(key, value);
	}

	/** Set an array element */
	private boolean arrayset(int key, LuaValue value) {
		if (key > 0 && key <= array.length) {
			array[key - 1] = value.isnil() ? null : (m_metatable != null ? m_metatable.wrap(value) : value);
			return true;
		}
		return false;
	}

	/** Remove the element at a position in a list-table
	 *  
	 * @param pos the position to remove
	 * @return The removed item, or {@link #NONE} if not removed
	 */
	public LuaValue remove(int pos) {
		int n = length();
		if (pos == 0)
			pos = n;
		else if (pos > n)
			return NONE;
		LuaValue v = rawget(pos);
		for (LuaValue r = v; !r.isnil();) {
			r = rawget(pos + 1);
			rawset(pos++, r);
		}
		return v.isnil() ? NONE : v;
	}

	/** Insert an element at a position in a list-table
	 *  
	 * @param pos the position to remove
	 * @param value The value to insert
	 */
	public void insert(int pos, LuaValue value) {
		if (pos == 0)
			pos = length() + 1;
		while (!value.isnil()) {
			LuaValue v = rawget(pos);
			rawset(pos++, value);
			value = v;
		}
	}

	/** Concatenate the contents of a table efficiently, using {@link Buffer}
	 * 
	 * @param sep {@link LuaString} separater to apply between elements
	 * @param i the first element index
	 * @param j the last element index, inclusive
	 * @return {@link LuaString} value of the concatenation
	 */
	public LuaValue concat(LuaString sep, int i, int j) {
		Buffer sb = new Buffer();
		if (i <= j) {
			sb.append(get(i).checkstring());
			while (++i <= j) {
				sb.append(sep);
				sb.append(get(i).checkstring());
			}
		}
		return sb.tostring();
	}

	public int length() {
		int a = getArrayLength();
		int n = a + 1, m = 0;
		while (!rawget(n).isnil()) {
			m = n;
			n += a + getHashLength() + 1;
		}
		while (n > m + 1) {
			int k = (n + m) / 2;
			if (!rawget(k).isnil())
				m = k;
			else
				n = k;
		}
		return m;
	}

	public LuaValue len() {
		return LuaInteger.valueOf(length());
	}

	public int rawlen() {
		return length();
	}

	/**
	 * Get the next element after a particular key in the table 
	 * @return key,value or nil
	 */
	public Varargs next(LuaValue key) {
		int i = 0;
		do {
			// find current key index
			if (!key.isnil()) {
				if (key.isinttype()) {
					i = key.toint();
					if (i > 0 && i <= array.length) {
						break;
					}
				}
				if (hash.length == 0)
					error("invalid key to 'next'");
				i = hashSlot(key);
				boolean found = false;
				for (Slot slot = hash[i]; slot != null; slot = slot.rest()) {
					if (found) {
						StrongSlot nextEntry = slot.first();
						if (nextEntry != null) {
							return nextEntry.toVarargs();
						}
					} else if (slot.keyeq(key)) {
						found = true;
					}
				}
				if (!found) {
					error("invalid key to 'next'");
				}
				i += 1 + array.length;
			}
		} while (false);

		// check array part
		for (; i < array.length; ++i) {
			if (array[i] != null) {
				LuaValue value = m_metatable == null ? array[i] : m_metatable.arrayget(array, i);
				if (value != null) {
					return varargsOf(LuaInteger.valueOf(i + 1), value);
				}
			}
		}

		// check hash part
		for (i -= array.length; i < hash.length; ++i) {
			Slot slot = hash[i];
			while (slot != null) {
				StrongSlot first = slot.first();
				if (first != null)
					return first.toVarargs();
				slot = slot.rest();
			}
		}

		// nothing found, push nil, return nil.
		return NIL;
	}

	/**
	 * Get the next element after a particular key in the 
	 * contiguous array part of a table 
	 * @return key,value or none
	 */
	public Varargs inext(LuaValue key) {
		int k = key.checkint() + 1;
		LuaValue v = rawget(k);
		return v.isnil() ? NONE : varargsOf(LuaInteger.valueOf(k), v);
	}

	/**
	 * Set a hashtable value
	 * @param key key to set
	 * @param value value to set
	 */
	public void hashset(LuaValue key, LuaValue value) {
		if (value.isnil())
			hashRemove(key);
		else {
			int index = 0;
			if (hash.length > 0) {
				index = hashSlot(key);
				for (Slot slot = hash[index]; slot != null; slot = slot.rest()) {
					StrongSlot foundSlot;
					if ((foundSlot = slot.find(key)) != null) {
						hash[index] = hash[index].set(foundSlot, value);
						return;
					}
				}
			}
			if (checkLoadFactor()) {
				if (key.isinttype() && key.toint() > 0) {
					// a rehash might make room in the array portion for this key.
					rehash(key.toint());
					if (arrayset(key.toint(), value))
						return;
				} else {
					rehash(-1);
				}
				index = hashSlot(key);
			}
			Slot entry = (m_metatable != null) ? m_metatable.entry(key, value) : defaultEntry(key, value);
			hash[index] = (hash[index] != null) ? hash[index].add(entry) : entry;
			++hashEntries;
		}
	}

	public static int hashpow2(int hashCode, int mask) {
		return hashCode & mask;
	}

	public static int hashmod(int hashCode, int mask) {
		return (hashCode & 0x7FFFFFFF) % mask;
	}

	/**
	 * Find the hashtable slot index to use.
	 * @param key the key to look for
	 * @param hashMask N-1 where N is the number of hash slots (must be power of 2)
	 * @return the slot index
	 */
	public static int hashSlot(LuaValue key, int hashMask) {
		switch (key.type()) {
		case TNUMBER:
		case TTABLE:
		case TTHREAD:
		case TLIGHTUSERDATA:
		case TUSERDATA:
			return hashmod(key.hashCode(), hashMask);
		default:
			return hashpow2(key.hashCode(), hashMask);
		}
	}

	/** 
	 * Find the hashtable slot to use
	 * @param key key to look for
	 * @return slot to use
	 */
	private int hashSlot(LuaValue key) {
		return hashSlot(key, hash.length - 1);
	}

	private void hashRemove(LuaValue key) {
		if (hash.length > 0) {
			int index = hashSlot(key);
			for (Slot slot = hash[index]; slot != null; slot = slot.rest()) {
				StrongSlot foundSlot;
				if ((foundSlot = slot.find(key)) != null) {
					hash[index] = hash[index].remove(foundSlot);
					--hashEntries;
					return;
				}
			}
		}
	}

	private boolean checkLoadFactor() {
		return hashEntries >= hash.length;
	}

	private int countHashKeys() {
		int keys = 0;
		for (int i = 0; i < hash.length; ++i) {
			for (Slot slot = hash[i]; slot != null; slot = slot.rest()) {
				if (slot.first() != null)
					keys++;
			}
		}
		return keys;
	}

	private void dropWeakArrayValues() {
		for (int i = 0; i < array.length; ++i) {
			m_metatable.arrayget(array, i);
		}
	}

	private int countIntKeys(int[] nums) {
		int total = 0;
		int i = 1;

		// Count integer keys in array part
		for (int bit = 0; bit < 31; ++bit) {
			if (i > array.length)
				break;
			int j = Math.min(array.length, 1 << bit);
			int c = 0;
			while (i <= j) {
				if (array[i++ - 1] != null)
					c++;
			}
			nums[bit] = c;
			total += c;
		}

		// Count integer keys in hash part
		for (i = 0; i < hash.length; ++i) {
			for (Slot s = hash[i]; s != null; s = s.rest()) {
				int k;
				if ((k = s.arraykey(Integer.MAX_VALUE)) > 0) {
					nums[log2(k)]++;
					total++;
				}
			}
		}

		return total;
	}

	// Compute ceil(log2(x))
	static int log2(int x) {
		int lg = 0;
		x -= 1;
		if (x < 0)
			// 2^(-(2^31)) is approximately 0
			return Integer.MIN_VALUE;
		if ((x & 0xFFFF0000) != 0) {
			lg = 16;
			x >>>= 16;
		}
		if ((x & 0xFF00) != 0) {
			lg += 8;
			x >>>= 8;
		}
		if ((x & 0xF0) != 0) {
			lg += 4;
			x >>>= 4;
		}
		switch (x) {
		case 0x0:
			return 0;
		case 0x1:
			lg += 1;
			break;
		case 0x2:
			lg += 2;
			break;
		case 0x3:
			lg += 2;
			break;
		case 0x4:
			lg += 3;
			break;
		case 0x5:
			lg += 3;
			break;
		case 0x6:
			lg += 3;
			break;
		case 0x7:
			lg += 3;
			break;
		case 0x8:
			lg += 4;
			break;
		case 0x9:
			lg += 4;
			break;
		case 0xA:
			lg += 4;
			break;
		case 0xB:
			lg += 4;
			break;
		case 0xC:
			lg += 4;
			break;
		case 0xD:
			lg += 4;
			break;
		case 0xE:
			lg += 4;
			break;
		case 0xF:
			lg += 4;
			break;
		}
		return lg;
	}

	/*
	 * newKey > 0 is next key to insert
	 * newKey == 0 means number of keys not changing (__mode changed)
	 * newKey < 0 next key will go in hash part
	 */
	private void rehash(int newKey) {
		if (m_metatable != null && (m_metatable.useWeakKeys() || m_metatable.useWeakValues())) {
			// If this table has weak entries, hashEntries is just an upper bound.
			hashEntries = countHashKeys();
			if (m_metatable.useWeakValues()) {
				dropWeakArrayValues();
			}
		}
		int[] nums = new int[32];
		int total = countIntKeys(nums);
		if (newKey > 0) {
			total++;
			nums[log2(newKey)]++;
		}

		// Choose N such that N <= sum(nums[0..log(N)]) < 2N
		int keys = nums[0];
		int newArraySize = 0;
		for (int log = 1; log < 32; ++log) {
			keys += nums[log];
			if (total * 2 < 1 << log) {
				// Not enough integer keys.
				break;
			} else if (keys >= (1 << (log - 1))) {
				newArraySize = 1 << log;
			}
		}

		final LuaValue[] oldArray = array;
		final Slot[] oldHash = hash;
		final LuaValue[] newArray;
		final Slot[] newHash;

		// Copy existing array entries and compute number of moving entries.
		int movingToArray = 0;
		if (newKey > 0 && newKey <= newArraySize) {
			movingToArray--;
		}
		if (newArraySize != oldArray.length) {
			newArray = new LuaValue[newArraySize];
			if (newArraySize > oldArray.length) {
				for (int i = log2(oldArray.length + 1), j = log2(newArraySize) + 1; i < j; ++i) {
					movingToArray += nums[i];
				}
			} else if (oldArray.length > newArraySize) {
				for (int i = log2(newArraySize + 1), j = log2(oldArray.length) + 1; i < j; ++i) {
					movingToArray -= nums[i];
				}
			}
			System.arraycopy(oldArray, 0, newArray, 0, Math.min(oldArray.length, newArraySize));
		} else {
			newArray = array;
		}

		final int newHashSize = hashEntries - movingToArray + ((newKey < 0 || newKey > newArraySize) ? 1 : 0); // Make room for the new entry
		final int oldCapacity = oldHash.length;
		final int newCapacity;
		final int newHashMask;

		if (newHashSize > 0) {
			// round up to next power of 2.
			newCapacity = (newHashSize < MIN_HASH_CAPACITY) ? MIN_HASH_CAPACITY : 1 << log2(newHashSize);
			newHashMask = newCapacity - 1;
			newHash = new Slot[newCapacity];
		} else {
			newCapacity = 0;
			newHashMask = 0;
			newHash = NOBUCKETS;
		}

		// Move hash buckets
		for (int i = 0; i < oldCapacity; ++i) {
			for (Slot slot = oldHash[i]; slot != null; slot = slot.rest()) {
				int k;
				if ((k = slot.arraykey(newArraySize)) > 0) {
					StrongSlot entry = slot.first();
					if (entry != null)
						newArray[k - 1] = entry.value();
				} else {
					int j = slot.keyindex(newHashMask);
					newHash[j] = slot.relink(newHash[j]);
				}
			}
		}

		// Move array values into hash portion
		for (int i = newArraySize; i < oldArray.length;) {
			LuaValue v;
			if ((v = oldArray[i++]) != null) {
				int slot = hashmod(LuaInteger.hashCode(i), newHashMask);
				Slot newEntry;
				if (m_metatable != null) {
					newEntry = m_metatable.entry(valueOf(i), v);
					if (newEntry == null)
						continue;
				} else {
					newEntry = defaultEntry(valueOf(i), v);
				}
				newHash[slot] = (newHash[slot] != null) ? newHash[slot].add(newEntry) : newEntry;
			}
		}

		hash = newHash;
		array = newArray;
		hashEntries -= movingToArray;
	}

	public Slot entry(LuaValue key, LuaValue value) {
		return defaultEntry(key, value);
	}

	protected static boolean isLargeKey(LuaValue key) {
		switch (key.type()) {
		case TSTRING:
			return key.rawlen() > LuaString.RECENT_STRINGS_MAX_LENGTH;
		case TNUMBER:
		case TBOOLEAN:
			return false;
		default:
			return true;
		}
	}

	protected static Entry defaultEntry(LuaValue key, LuaValue value) {
		if (key.isinttype()) {
			return new IntKeyEntry(key.toint(), value);
		} else if (value.type() == TNUMBER) {
			return new NumberValueEntry(key, value.todouble());
		} else {
			return new NormalEntry(key, value);
		}
	}

	// ----------------- sort support -----------------------------
	//
	// implemented heap sort from wikipedia
	//
	// Only sorts the contiguous array part. 
	//
	/** Sort the table using a comparator.
	 * @param comparator {@link LuaValue} to be called to compare elements.
	 */
	public void sort(LuaValue comparator) {
		if (m_metatable != null && m_metatable.useWeakValues()) {
			dropWeakArrayValues();
		}
		int n = array.length;
		while (n > 0 && array[n - 1] == null)
			--n;
		if (n > 1)
			heapSort(n, comparator);
	}

	private void heapSort(int count, LuaValue cmpfunc) {
		heapify(count, cmpfunc);
		for (int end = count - 1; end > 0;) {
			swap(end, 0);
			siftDown(0, --end, cmpfunc);
		}
	}

	private void heapify(int count, LuaValue cmpfunc) {
		for (int start = count / 2 - 1; start >= 0; --start)
			siftDown(start, count - 1, cmpfunc);
	}

	private void siftDown(int start, int end, LuaValue cmpfunc) {
		for (int root = start; root * 2 + 1 <= end;) {
			int child = root * 2 + 1;
			if (child < end && compare(child, child + 1, cmpfunc))
				++child;
			if (compare(root, child, cmpfunc)) {
				swap(root, child);
				root = child;
			} else
				return;
		}
	}

	private boolean compare(int i, int j, LuaValue cmpfunc) {
		LuaValue a, b;
		if (m_metatable == null) {
			a = array[i];
			b = array[j];
		} else {
			a = m_metatable.arrayget(array, i);
			b = m_metatable.arrayget(array, j);
		}
		if (a == null || b == null)
			return false;
		if (!cmpfunc.isnil()) {
			return cmpfunc.call(a, b).toboolean();
		} else {
			return a.lt_b(b);
		}
	}

	private void swap(int i, int j) {
		LuaValue a = array[i];
		array[i] = array[j];
		array[j] = a;
	}

	/** This may be deprecated in a future release.  
	 * It is recommended to count via iteration over next() instead
	 * @return count of keys in the table 
	 * */
	public int keyCount() {
		LuaValue k = LuaValue.NIL;
		for (int i = 0; true; i++) {
			Varargs n = next(k);
			if ((k = n.arg1()).isnil())
				return i;
		}
	}

	/** This may be deprecated in a future release.  
	 * It is recommended to use next() instead 
	 * @return array of keys in the table 
	 * */
	public LuaValue[] keys() {
		Vector l = new Vector();
		LuaValue k = LuaValue.NIL;
		while (true) {
			Varargs n = next(k);
			if ((k = n.arg1()).isnil())
				break;
			l.addElement(k);
		}
		LuaValue[] a = new LuaValue[l.size()];
		l.copyInto(a);
		return a;
	}

	// equality w/ metatable processing
	public LuaValue eq(LuaValue val) {
		return eq_b(val) ? TRUE : FALSE;
	}

	public boolean eq_b(LuaValue val) {
		if (this == val)
			return true;
		if (m_metatable == null || !val.istable())
			return false;
		LuaValue valmt = val.getmetatable();
		return valmt != null && LuaValue.eqmtcall(this, m_metatable.toLuaValue(), val, valmt);
	}

	/** Unpack all the elements of this table */
	public Varargs unpack() {
		return unpack(1, this.length());
	}

	/** Unpack all the elements of this table from element i */
	public Varargs unpack(int i) {
		return unpack(i, this.length());
	}

	/** Unpack the elements from i to j inclusive */
	public Varargs unpack(int i, int j) {
		int n = j + 1 - i;
		switch (n) {
		case 0:
			return NONE;
		case 1:
			return get(i);
		case 2:
			return varargsOf(get(i), get(i + 1));
		default:
			if (n < 0)
				return NONE;
			LuaValue[] v = new LuaValue[n];
			while (--n >= 0)
				v[n] = get(i + n);
			return varargsOf(v);
		}
	}

	/**
	 * Represents a slot in the hash table.
	 */
	interface Slot {

		/** Return hash{pow2,mod}( first().key().hashCode(), sizeMask ) */
		int keyindex(int hashMask);

		/** Return first Entry, if still present, or null. */
		StrongSlot first();

		/** Compare given key with first()'s key; return first() if equal. */
		StrongSlot find(LuaValue key);

		/**
		 * Compare given key with first()'s key; return true if equal. May
		 * return true for keys no longer present in the table.
		 */
		boolean keyeq(LuaValue key);

		/** Return rest of elements */
		Slot rest();

		/**
		 * Return first entry's key, iff it is an integer between 1 and max,
		 * inclusive, or zero otherwise.
		 */
		int arraykey(int max);

		/**
		 * Set the value of this Slot's first Entry, if possible, or return a
		 * new Slot whose first entry has the given value.
		 */
		Slot set(StrongSlot target, LuaValue value);

		/**
		 * Link the given new entry to this slot.
		 */
		Slot add(Slot newEntry);

		/**
		 * Return a Slot with the given value set to nil; must not return null
		 * for next() to behave correctly.
		 */
		Slot remove(StrongSlot target);

		/**
		 * Return a Slot with the same first key and value (if still present)
		 * and rest() equal to rest.
		 */
		Slot relink(Slot rest);
	}

	/**
	 * Subclass of Slot guaranteed to have a strongly-referenced key and value,
	 * to support weak tables.
	 */
	interface StrongSlot extends Slot {
		/** Return first entry's key */
		LuaValue key();

		/** Return first entry's value */
		LuaValue value();

		/** Return varargsOf(key(), value()) or equivalent */
		Varargs toVarargs();
	}

	private static class LinkSlot implements StrongSlot {
		private Entry entry;
		private Slot next;

		LinkSlot(Entry entry, Slot next) {
			this.entry = entry;
			this.next = next;
		}

		public LuaValue key() {
			return entry.key();
		}

		public int keyindex(int hashMask) {
			return entry.keyindex(hashMask);
		}

		public LuaValue value() {
			return entry.value();
		}

		public Varargs toVarargs() {
			return entry.toVarargs();
		}

		public StrongSlot first() {
			return entry;
		}

		public StrongSlot find(LuaValue key) {
			return entry.keyeq(key) ? this : null;
		}

		public boolean keyeq(LuaValue key) {
			return entry.keyeq(key);
		}

		public Slot rest() {
			return next;
		}

		public int arraykey(int max) {
			return entry.arraykey(max);
		}

		public Slot set(StrongSlot target, LuaValue value) {
			if (target == this) {
				entry = entry.set(value);
				return this;
			} else {
				return setnext(next.set(target, value));
			}
		}

		public Slot add(Slot entry) {
			return setnext(next.add(entry));
		}

		public Slot remove(StrongSlot target) {
			if (this == target) {
				return new DeadSlot(key(), next);
			} else {
				this.next = next.remove(target);
			}
			return this;
		}

		public Slot relink(Slot rest) {
			// This method is (only) called during rehash, so it must not change this.next.
			return (rest != null) ? new LinkSlot(entry, rest) : (Slot) entry;
		}

		// this method ensures that this.next is never set to null.
		private Slot setnext(Slot next) {
			if (next != null) {
				this.next = next;
				return this;
			} else {
				return entry;
			}
		}

		public String toString() {
			return entry + "; " + next;
		}
	}

	/**
	 * Base class for regular entries.
	 * 
	 * <p>
	 * If the key may be an integer, the {@link #arraykey(int)} method must be
	 * overridden to handle that case.
	 */
	static abstract class Entry extends Varargs implements StrongSlot {
		public abstract LuaValue key();

		public abstract LuaValue value();

		abstract Entry set(LuaValue value);

		public int arraykey(int max) {
			return 0;
		}

		public LuaValue arg(int i) {
			switch (i) {
			case 1:
				return key();
			case 2:
				return value();
			}
			return NIL;
		}

		public int narg() {
			return 2;
		}

		/**
		 * Subclasses should redefine as "return this;" whenever possible.
		 */
		public Varargs toVarargs() {
			return varargsOf(key(), value());
		}

		public LuaValue arg1() {
			return key();
		}

		public Varargs subargs(int start) {
			switch (start) {
			case 1:
				return this;
			case 2:
				return value();
			}
			return NONE;
		}

		public StrongSlot first() {
			return this;
		}

		public Slot rest() {
			return null;
		}

		public StrongSlot find(LuaValue key) {
			return keyeq(key) ? this : null;
		}

		public Slot set(StrongSlot target, LuaValue value) {
			return set(value);
		}

		public Slot add(Slot entry) {
			return new LinkSlot(this, entry);
		}

		public Slot remove(StrongSlot target) {
			return new DeadSlot(key(), null);
		}

		public Slot relink(Slot rest) {
			return (rest != null) ? new LinkSlot(this, rest) : (Slot) this;
		}
	}

	static class NormalEntry extends Entry {
		private final LuaValue key;
		private LuaValue value;

		NormalEntry(LuaValue key, LuaValue value) {
			this.key = key;
			this.value = value;
		}

		public LuaValue key() {
			return key;
		}

		public LuaValue value() {
			return value;
		}

		public Entry set(LuaValue value) {
			this.value = value;
			return this;
		}

		public Varargs toVarargs() {
			return this;
		}

		public int keyindex(int hashMask) {
			return hashSlot(key, hashMask);
		}

		public boolean keyeq(LuaValue key) {
			return key.raweq(this.key);
		}
	}

	private static class IntKeyEntry extends Entry {
		private final int key;
		private LuaValue value;

		IntKeyEntry(int key, LuaValue value) {
			this.key = key;
			this.value = value;
		}

		public LuaValue key() {
			return valueOf(key);
		}

		public int arraykey(int max) {
			return (key >= 1 && key <= max) ? key : 0;
		}

		public LuaValue value() {
			return value;
		}

		public Entry set(LuaValue value) {
			this.value = value;
			return this;
		}

		public int keyindex(int mask) {
			return hashmod(LuaInteger.hashCode(key), mask);
		}

		public boolean keyeq(LuaValue key) {
			return key.raweq(this.key);
		}
	}

	/**
	 * Entry class used with numeric values, but only when the key is not an integer.
	 */
	private static class NumberValueEntry extends Entry {
		private double value;
		private final LuaValue key;

		NumberValueEntry(LuaValue key, double value) {
			this.key = key;
			this.value = value;
		}

		public LuaValue key() {
			return key;
		}

		public LuaValue value() {
			return valueOf(value);
		}

		public Entry set(LuaValue value) {
			LuaValue n = value.tonumber();
			if (!n.isnil()) {
				this.value = n.todouble();
				return this;
			} else {
				return new NormalEntry(this.key, value);
			}
		}

		public int keyindex(int mask) {
			return hashSlot(key, mask);
		}

		public boolean keyeq(LuaValue key) {
			return key.raweq(this.key);
		}
	}

	/**
	 * A Slot whose value has been set to nil. The key is kept in a weak reference so that
	 * it can be found by next().
	 */
	private static class DeadSlot implements Slot {

		private final Object key;
		private Slot next;

		private DeadSlot(LuaValue key, Slot next) {
			this.key = isLargeKey(key) ? new WeakReference(key) : (Object) key;
			this.next = next;
		}

		private LuaValue key() {
			return (LuaValue) (key instanceof WeakReference ? ((WeakReference) key).get() : key);
		}

		public int keyindex(int hashMask) {
			// Not needed: this entry will be dropped during rehash.
			return 0;
		}

		public StrongSlot first() {
			return null;
		}

		public StrongSlot find(LuaValue key) {
			return null;
		}

		public boolean keyeq(LuaValue key) {
			LuaValue k = key();
			return k != null && key.raweq(k);
		}

		public Slot rest() {
			return next;
		}

		public int arraykey(int max) {
			return -1;
		}

		public Slot set(StrongSlot target, LuaValue value) {
			Slot next = (this.next != null) ? this.next.set(target, value) : null;
			if (key() != null) {
				// if key hasn't been garbage collected, it is still potentially a valid argument
				// to next(), so we can't drop this entry yet.
				this.next = next;
				return this;
			} else {
				return next;
			}
		}

		public Slot add(Slot newEntry) {
			return (next != null) ? next.add(newEntry) : newEntry;
		}

		public Slot remove(StrongSlot target) {
			if (key() != null) {
				next = next.remove(target);
				return this;
			} else {
				return next;
			}
		}

		public Slot relink(Slot rest) {
			return rest;
		}

		public String toString() {
			StringBuffer buf = new StringBuffer();
			buf.append("<dead");
			LuaValue k = key();
			if (k != null) {
				buf.append(": ");
				buf.append(k.toString());
			}
			buf.append('>');
			if (next != null) {
				buf.append("; ");
				buf.append(next.toString());
			}
			return buf.toString();
		}
	};

	private static final Slot[] NOBUCKETS = {};

	// Metatable operations

	public boolean useWeakKeys() {
		return false;
	}

	public boolean useWeakValues() {
		return false;
	}

	public LuaValue toLuaValue() {
		return this;
	}

	public LuaValue wrap(LuaValue value) {
		return value;
	}

	public LuaValue arrayget(LuaValue[] array, int index) {
		return array[index];
	}
}