/*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
* 
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.
* 
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

/*
* ADNode.java
* Copyright (C) 2002 University of Waikato, Hamilton, New Zealand
* 
*/
package dataset.adtree;

import java.util.BitSet;
import java.util.Map;

import dataset.Dataset;



/**
 * The ADNode class implements the ADTree data structure which increases the
 * speed with which sub-contingency tables can be constructed from a data set in
 * an Instances object. For details, see:
 * <p/>
 * 
 * <!-- technical-plaintext-start --> Andrew W. Moore, Mary S. Lee (1998).
 * Cached Sufficient Statistics for Efficient Machine Learning with Large
 * Datasets. Journal of Artificial Intelligence Research. 8:67-91. <!--
 * technical-plaintext-end -->
 * <p/>
 */
public class ADNode implements java.io.Serializable {

	private static final long serialVersionUID = -1538774929394037264L;

	/* Size used by Adree W. Moore, Mary S. Lee (pag. 79, section
	   7 Experimental Results) */
	public static int MIN_RECORD_SIZE = 16;

	/** list of VaryNode children **/
	public VaryNode[] m_VaryNodes;
	/**
	 * list of Instance children (either m_Instances or m_VaryNodes is
	 * instantiated)
	 **/
	public BitSet m_Instances;

	/** count **/
	public int m_nCount;

	/** first node in VaryNode array **/
	public int m_nStartNode;

	/** Creates new ADNode */
	public ADNode() {
	}

	/**
	 * create sub tree
	 * 
	 * @param iNode
	 *            index of the lowest node in the tree
	 * @param nRecords
	 *            set of records in instances to be considered
	 * @param instances
	 *            data set
	 * @return VaryNode representing part of an ADTree
	 **/
	public static VaryNode makeVaryNode(int iNode, BitSet nRecords,
			Dataset dataset) {
		VaryNode _VaryNode = new VaryNode(iNode);

		int nValues = dataset.getCardinalities(iNode);

		// reserve memory and initialize
		BitSet[] nChildRecords = new BitSet[nValues];
		for (int iChild = 0; iChild < nValues; iChild++)
			nChildRecords[iChild] = new BitSet();

		// divide the records among children
		for (int iInstance = nRecords.nextSetBit(0); iInstance >= 0; iInstance = nRecords
				.nextSetBit(iInstance + 1))
			nChildRecords[(int) dataset.getList().get(iInstance).getVal(iNode)]
					.set(iInstance);

		// find most common value
		int nCount = nChildRecords[0].cardinality();
		int nMCV = 0;
		for (int iChild = 1; iChild < nValues; iChild++)
			if (nChildRecords[iChild].cardinality() > nCount) {
				nCount = nChildRecords[iChild].cardinality();
				nMCV = iChild;
			}

		_VaryNode.m_nMCV = nMCV;
		// free memory
		nChildRecords[nMCV] = null;

		// determine child nodes
		_VaryNode.m_ADNodes = new ADNode[nValues];
		for (int iChild = 0; iChild < nValues; iChild++)
			if (iChild == nMCV || nChildRecords[iChild].cardinality() == 0)
				_VaryNode.m_ADNodes[iChild] = null;
			else
				_VaryNode.m_ADNodes[iChild] = makeADNode(iNode + 1,
						nChildRecords[iChild], dataset);

		return _VaryNode;
	} // MakeVaryNode

	private static int computeCount(BitSet nRecords, Dataset dataset) {
		int count = 0;

		for (int i = nRecords.nextSetBit(0); i >= 0; i = nRecords
				.nextSetBit(i + 1))
			count += dataset.getCountFromIndex(i);

		return count;
	}

	public static ADNode makeADNode(int iNode, BitSet nRecords, Dataset dataset) {
		ADNode _ADNode = new ADNode();
		_ADNode.m_nStartNode = iNode;
		_ADNode.m_nCount = computeCount(nRecords, dataset);
		_ADNode.m_Instances = (BitSet) nRecords.clone();

		return _ADNode;
	}

	public static ADNode makeADNode(Dataset dataset) {
		BitSet nRecords = new BitSet(dataset.getList().size());

		for (int i = 0; i < dataset.getList().size(); i++)
			nRecords.set(i, true);

		return makeADNode(0, nRecords, dataset);
	}
	/**
	 * Construct a contingency table
	 * @param vars A bitset with the variables used
	 * @param node A node to start from
	 * @param context A HashMap with a specific context to construct the contingency table. If no specific context is needed it can be an empty HashMap
	 * @param cards The cardinalities of the variables
	 * @param dataset The dataset used
	 * @return A contingency table
	 */
	public int[] makeContab(BitSet vars, ADNode node,
			Map<Integer, Integer> context, int[] cards, Dataset dataset) {
		// The base case
		// An ADNode is null if this is a MCV
		if (vars.cardinality() == 0)
			return (node == null) ? new int[] { 0 }
					: new int[] { node.m_nCount };

		final int var = vars.nextSetBit(0);
		final Integer val = context.get(var);

		// An ADNode is null if this is a MCV. In such case, the
		// counts are computed by using an upper subtree
		if (node == null)
			return (val == null) ? new int[cards[var]] : new int[] { 0 };

		BitSet rvars = (BitSet) vars.clone();
		rvars.set(var, false);

		// not expanding subtree because counter is below to the
		// threshold. counters are obtained from dataset instead of
		// the adtree
		if (node.m_Instances.cardinality() < MIN_RECORD_SIZE)
			return dataset.computeSufficientStatisticsFromDataset(vars,
					context, node.m_Instances);

		// If varyNodes is null, then creates it
		if (node.m_VaryNodes == null)
			node.m_VaryNodes = new VaryNode[dataset.getNumberOfVariables()
					- node.m_nStartNode];

		// Obtain the vary node of the variable var. If the previous
		// line was performed, then this vn is null
		VaryNode vn = node.m_VaryNodes[var - node.m_nStartNode];

		// Create dinamically this vary node
		if (vn == null) {
			vn = makeVaryNode(var, node.m_Instances, dataset);
			node.m_VaryNodes[var - node.m_nStartNode] = vn;
		}

		int mcv = vn.m_nMCV;

		// The following lines computes the counts by using recursion

		int[][] ct_k;
		ADNode adnK;

		ct_k = new int[cards[var]][];

		// Compute length of counter arrays
		int numberEl = 1;
		for (int i = rvars.nextSetBit(0); i >= 0; i = rvars.nextSetBit(i + 1))
			if (!context.containsKey(i))
				numberEl *= 2;

		int[] counts;

		// This conditional saves memory consumption. If val != null,
		// then it is only required to create a single ct_k, one that
		// corresponds with val
		if (val == null) {
			for (int k = 0; k < cards[var]; k++) {
				if (k != mcv)
					adnK = vn.m_ADNodes[k];
				else
					adnK = node;

				counts = makeContab(rvars, adnK, context, cards, dataset);

				if (k != mcv)
					ct_k[k] = new int[numberEl];
				if (ct_k[mcv] == null)
					ct_k[mcv] = new int[numberEl];

				for (int i = 0; i < counts.length; i++) {
					ct_k[k][i] += counts[i];

					if (k != mcv)
						ct_k[mcv][i] -= counts[i];
				}

				// clean
				counts = null;
			}
		} else {
			ct_k[val] = new int[numberEl];

			if (val != mcv)
				return makeContab(rvars, vn.m_ADNodes[val], context, cards,
						dataset);

			for (int k = 0; k < cards[var]; k++) {
				if (k != mcv)
					adnK = vn.m_ADNodes[k];
				else
					adnK = node;

				counts = makeContab(rvars, adnK, context, cards, dataset);

				for (int i = 0; i < counts.length; i++) {
					if (ct_k[k] != null)
						ct_k[k][i] += counts[i];

					if (k != mcv && ct_k[mcv] != null)
						ct_k[mcv][i] -= counts[i];
				}

				// clean
				counts = null;
			}

			return ct_k[val];
		}

		int[] contingencyTable = new int[numberEl * ct_k.length];
		int offset = 0;

		for (int k = 0; k < ct_k.length; k++) {
			for (int i = 0; i < ct_k[k].length; i++)
				contingencyTable[offset + i] = ct_k[k][i];

			offset += ct_k[k].length;
		}

		ct_k = null;

		return contingencyTable;
	}

	/**
	 * Construct a contingency table
	 * @param vars A bitset with the variables used
	 * @param context A HashMap with a specific context to construct the contingency table. If no specific context is needed it can be an empty HashMap
	 * @param cards The cardinalities of the variables
	 * @param dataset The dataset used
	 * @return A contingency table
	 */
	public int[] makeContab(BitSet vars, Map<Integer, Integer> context,
			int[] cards, Dataset dataset) {
		return makeContab(vars, this, context, cards, dataset);
	}

	/**
	 * print is used for debugging only and shows the ADTree in ASCII graphics
	 */
	public void print() {
		String sTab = new String();
		for (int i = 0; i < m_nStartNode; i++) {
			sTab = sTab + "  ";
		}
		System.out.println(sTab + "Count = " + m_nCount);
		if (m_VaryNodes != null) {
			for (int iNode = 0; iNode < m_VaryNodes.length; iNode++) {
				System.out.println(sTab + "Node " + (iNode + m_nStartNode));
				m_VaryNodes[iNode].print(sTab);
			}
		} else {
			System.out.println(m_Instances);
		}
	}
} // class ADNode