/* *********************************************************************

This source file is a part of the standard library of Scol
For the latest info, see http://www.scolring.org

Copyright (c) 2013 Stephane Bisaro aka Iri.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser 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 Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
Place - Suite 330, Boston, MA 02111-1307, USA, or go to

http://www.gnu.org/copyleft/lesser.txt

********************************************************************* */

/*
 * Standard functions for binary-tree.
 * See http://redmine.scolring.org/projects/tutorials/wiki/Scol_usage
 * for more informations
 */

/*! \file tree.pkg
 * \author Scol team
 * \version 0.1
 * \copyright GNU Lesser General Public License 2.0 or later
	* \brief Scol Standard Library - Binary-tree API
 *
 * \details A binary tree is a tree data structure in which each node has at most two children 
 * (referred to as the left child and the right child). This API allows to manipulate these object.
 * 
**/


var STD_TREE_LEFTISSMALLER = 0;;
var STD_TREE_RIGHTISSMALLER = 1;;


var STD_TREE_NODE_I = 0;;
var STD_TREE_NODE_F = 1;;
var STD_TREE_NODE_S = 2;;
var STD_TREE_NODE_LS = 3;;
var STD_TREE_NODE_LS2 = 4;;
var STD_TREE_NODE_TS = 5;;
var STD_TREE_NODE_U = 99;;




typedef STD_TREE_DATA = 
			STD_TREE_DATA_I I
			| STD_TREE_DATA_CONV_F F
			| STD_TREE_DATA_CONV_S S
			| STD_TREE_DATA_CONV_LS [S r1]
			| STD_TREE_DATA_CONV_LS2 [[S r1] r1]
			| STD_TREE_DATA_CONV_TS tab S
			| STD_TREE_DATA_CONV_U;;

struct STD_TREE_EASY = [
			stdtreenode : STD_TREE_DATA,
			stdtreeleft : STD_TREE_EASY,
			stdtreeright : STD_TREE_EASY,
			stdtreesmaller : I,				/*!< STD_TREE_LEFTISSMALLER or STD_TREE_RIGHTISSMALLER */
			stdtreenodeflag : I,
			stdtreecbgeti : fun [I] I,
			stdtreecbgetf : fun [F] I,
			stdtreecbgets : fun [S] I,
			stdtreecbgetls : fun [[S r1]] I,
			stdtreecbgetls2 : fun [[[S r1] r1]] I,
			stdtreecbgetts : fun [tab S] I
			] mkSTD_TREE_EASY;;
	
	
fun std_treeConvI (i) = STD_TREE_DATA_I i;;
fun std_treeConvF (f) = STD_TREE_DATA_CONV_F f;;
fun std_treeConvS (str) = STD_TREE_DATA_CONV_S str;;
fun std_treeConvLS (lStr) = STD_TREE_DATA_CONV_LS lStr;;
fun std_treeConvLS2 (lStr) = STD_TREE_DATA_CONV_LS2 lStr;;
fun std_treeConvTS (tStr) = STD_TREE_DATA_CONV_TS tStr;;
fun std_treeConvU (u) = STD_TREE_DATA_CONV_U;;

fun std_treeConv (tree)=_fooS "CONV";
	if tree == nil then
		nil
	else
		match tree.stdtreenode with
		(STD_TREE_DATA_I e ->  (exec tree.stdtreecbgeti with [e]; 0))
		| (STD_TREE_DATA_CONV_F e -> (exec tree.stdtreecbgetf with [e]; 0))
		| (STD_TREE_DATA_CONV_S e -> (exec tree.stdtreecbgets with [e]; 0))
		| (STD_TREE_DATA_CONV_LS e -> (exec tree.stdtreecbgetls with [e]; 0))
		| (STD_TREE_DATA_CONV_LS2 e -> (exec tree.stdtreecbgetls2 with [e]; 0))
		| (STD_TREE_DATA_CONV_TS e -> (exec tree.stdtreecbgetts with [e]; 0))
		| (STD_TREE_DATA_CONV_U -> 0);;

fun std_treecheckisleft (isLeft)=
	if (isLeft == STD_TREE_LEFTISSMALLER) || (isLeft == STD_TREE_RIGHTISSMALLER) then
		isLeft
	else
		STD_TREE_LEFTISSMALLER;;
		
fun std_treenewesay (data, isLeft, flag)=
	set isLeft = std_treecheckisleft isLeft;
	mkSTD_TREE_EASY [data nil nil isLeft flag nil nil nil nil nil nil];;

/*! \brief Create an easy binary tree.
*
* <b>Prototype :</b> fun [u0 I] STD_TREE_EASY
*
* \param u0 : an initial key.
* \param I : flag : STD_TREE_LEFTISSMALLER (left tree is smaller) or STD_TREE_RIGHTISSMALLER (right tree is smaller)
*
* \return STD_TREE_EASY : the new tree
**/
fun std_treeNew (data, isLeft)=
	let nil -> tree in
	match data with
	(STD_TREE_DATA_I e ->  set tree = std_treenewesay data isLeft STD_TREE_NODE_I)
	| (STD_TREE_DATA_CONV_F e -> set tree = std_treenewesay data isLeft STD_TREE_NODE_F)
	| (STD_TREE_DATA_CONV_S e -> set tree = std_treenewesay data isLeft STD_TREE_NODE_S)
	| (STD_TREE_DATA_CONV_LS e -> set tree = std_treenewesay data isLeft STD_TREE_NODE_LS)
	| (STD_TREE_DATA_CONV_LS2 e -> set tree = std_treenewesay data isLeft STD_TREE_NODE_LS2)
	| (STD_TREE_DATA_CONV_TS e -> set tree = std_treenewesay data isLeft STD_TREE_NODE_TS)
	| (STD_TREE_DATA_CONV_U -> /*set tree = std_treenewesay data isLeft STD_TREE_NODE_U*/nil);;
	
fun std_treeGetNode (tree)=
	std_treeConv (tree);;
	
proto std_treeGetCB = fun [STD_TREE_EASY fun [u0] I] STD_TREE_EASY;;
fun std_treeGetCB (tree, cbfun)=
	if tree.stdtreenodeflag == STD_TREE_NODE_I then
		(set tree.stdtreecbgeti = cbfun; tree)
	else if tree.stdtreenodeflag == STD_TREE_NODE_F then
		(set tree.stdtreecbgetf = cbfun; tree)
	else if tree.stdtreenodeflag == STD_TREE_NODE_S then
		(set tree.stdtreecbgets = cbfun; tree)
	else if tree.stdtreenodeflag == STD_TREE_NODE_LS then
		(set tree.stdtreecbgetls = cbfun; tree)
	else if tree.stdtreenodeflag == STD_TREE_NODE_LS2 then
		(set tree.stdtreecbgetls2 = cbfun; tree)
	else if tree.stdtreenodeflag == STD_TREE_NODE_TS then
		(set tree.stdtreecbgetts = cbfun; tree)
	else
		nil;;
	
/*fun std_treeAdd (tree, data, isLeft)=
	if tree == nil then
		nil
	else
		let nil -> subtree in
		(
		match data with
		(STD_TREE_DATA_I e ->  set subtree = mkSTD_TREE_EASY [data nil nil nil])
		| (STD_TREE_DATA_CONV_U -> set subtree = mkSTD_TREE_EASY [data nil nil nil]);
		set tree*/