function [T,node_error] = prune(T,T_breakdown,node_class,position)
% PRUNE prunes the decision tree T using the pruning algorithm from C4.5 by
%	J. Ross Quinlan.
%
%	[T,error] = prune(T,T_breakdown,node_class,position) 
%
%	T: matrix representing the decision tree T, generated by MSM-T.
%	node_error: error in a node (described in C4.5). 
%	T_breakdown: matrix describing the division of the points in sets
%		A and B (decribed in msmt_tree_breakdown.m).
%	node_class: flag telling whether the current node is correctly
%		classifying set A or B.
%		If current node is a left child: correctly classifying A.
%		If current node is right child: correclty classifying B.
%		node_class = 0 : correctly classifying A
%		node_class = 1 : correctly classifying B
%	position: vector representing the order in which we are recursing
%		thru tree T.  

% coeff is a global variable accessible to prune, prune_tree.
global coeff;


% n, the dimension of the points in sets A, B is global
global n;

% begin
% index of the current node is the last entry in the position vector

node_index = size(position,2);
node_position = position(node_index);

if (node_position == -1)	% we are in a leaf node, the information
				% we want is contained at the parent_position,
				% the parent_index is the entry before
				% node_index in position vector

	parent_index = node_index - 1;
	parent_position = position(parent_index);

	% now compute the error for this leaf:

	if (node_class == 0)	% A correct, B incorrect, left child leaf
		node_error = T_breakdown(4,parent_position);
		add_errors = prune_errs((T_breakdown(3,parent_position) + T_breakdown(4,parent_position)),node_error,coeff);
	
	else	% (node_class == 1), B correct, A incorrect, right child leaf
		node_error = T_breakdown(5,parent_position);
		add_errors = prune_errs((T_breakdown(5,parent_position) + T_breakdown(6,parent_position)),node_error,coeff);
	end
	
	node_error = node_error + add_errors;
	return;

else	% we are not in a leaf node
	% compute the error here
	if (node_class == 0)	% A correct, B incorrect
		node_error = T_breakdown(2,node_position);
	else			% B correct, A incorrect
		node_error = T_breakdown(1,node_position);
	end
	
	add_errors = prune_errs((T_breakdown(1,node_position) + T_breakdown(2,node_position)),node_error,coeff);

	node_error = node_error + add_errors;

	% prune to the left of this node
	
	[T,left_tree_errors] = prune(T,T_breakdown,0,[position,T(n+2,node_position)]);
	
	% prune to the right of this node
	
	[T,right_tree_errors] = prune(T,T_breakdown,1,[position,T(n+3,node_position)]);

	subtree_error = left_tree_errors + right_tree_errors;

	if (node_error <= subtree_error + 1.0 )
		T = prune_kill_kids(T,position);
		
	else
		node_error = subtree_error;
		
	end
	return;
end
				








