/***************************************************************************************/
/*                                                                                     */
/*  SCS editor Version 2                                                               */
/*  File : Tree.pkg                                                                    */
/*  Version : 26 Mai 2000                                                              */
/*  Tree enhanced functions                                                            */
/*                                                                                     */
/***************************************************************************************/

/****************************************************************************************
  
  return the list of value of a list of node
  
****************************************************************************************/
fun TREE_ListValOfList (nodeList)=
  if nodeList == nil
  then
    nil
  else
    (TREE_Val (hd nodeList))::(TREE_ListValOfList tl nodeList)
;;

/****************************************************************************************
  
  return the list of value of one node and all its brother
  
****************************************************************************************/
fun TREE_ListOfAllBrothers (node) =
  if node == nil
  then nil
  else node::(TREE_ListOfAllBrothers (TREE_NextBrother node))
;;    

/****************************************************************************************
  
  return the list of value of all children for a node
  
****************************************************************************************/
fun TREE_ListValOfAllChilds (node) =
  TREE_ListValOfList TREE_ListOfAllBrothers (TREE_FirstChild node)
;;

/****************************************************************************************
Apply a function on a node's value, its brothers and its children
NOTE: function is applied on the node value, not on the node itself
Return value: 1 (success) or 0 (failure)
WARNING : the parameter function must return true if the operation 
was successfully completed
****************************************************************************************/
fun TREE_ApplyOnTreeVal (node, function, param, order)=
  if node==nil
  then
    1
  else
    let node -> [nodeVal _ firstChild _ nextBrother] in
      if order == TREE_PRE_ORDER
      then
        (exec function with [nodeVal param]) &&
        (TREE_ApplyOnTreeVal firstChild  function param order) &&
        (TREE_ApplyOnTreeVal nextBrother function param order)
      else if order == TREE_POST_ORDER
      then
        (TREE_ApplyOnTreeVal firstChild  function param order) &&
        (TREE_ApplyOnTreeVal nextBrother function param order) &&
        (exec function with [nodeVal param])
      else if order == TREE_IN_ORDER
      then
        (TREE_ApplyOnTreeVal firstChild  function param order) &&
        (exec function with [nodeVal param]) &&
        (TREE_ApplyOnTreeVal nextBrother function param order)
      else if order == TREE_REVERSED_ORDER
      then
        (TREE_ApplyOnTreeVal nextBrother function param order) &&
        (TREE_ApplyOnTreeVal firstChild  function param order) &&
        (exec function with [nodeVal param])
      else
        0
;;

/****************************************************************************************
Apply a function on a root node's value and its children
NOTE: function is applied on the node value, not on the node itself
Return value: 1 (success) or 0 (failure)
****************************************************************************************/
fun TREE_ApplyOnSubTreeVal (node, function, param, order) =
  if node == nil
  then
    0
  else
    let node -> [nodeVal _ firstChild _ _] in
      (TREE_ApplyOnTreeVal firstChild function param order) &&
      (exec function with [nodeVal param])
;;

/****************************************************************************************
  DUPLICATE TREE FUNCTIONS
****************************************************************************************/
/****************************************************************************************
  
  return a duplication of a node tree, all its children and its next brother
  use a duplication function for the node value
  
****************************************************************************************/
fun TREE_DuplicateComplete (node, father, duplicateValueFun, param) =
  if node == nil
  then
    nil
  else
    let node -> [val _ firstChild _ nextBrother] in
      let TREE_MkNode (exec duplicateValueFun with [val param]) -> newNode in
      (
        TREE_DuplicateComplete firstChild newNode duplicateValueFun param;
        TREE_AddNodeToChildTail father newNode;
        TREE_DuplicateComplete nextBrother father duplicateValueFun param;
        newNode
      )
;;

/****************************************************************************************
  
  return a duplication of a node tree and all its children
  use a duplication function for the node value
  
****************************************************************************************/
fun TREE_Duplicate (node, duplicateValueFun, param) =
  if node == nil
  then
    nil
  else
    let node -> [val _ firstChild _ _] in
      let TREE_MkNode (exec duplicateValueFun with [val param]) -> newNode in
      (
        TREE_DuplicateComplete firstChild newNode duplicateValueFun param;
        newNode
      )
;;

/****************************************************************************************
  PATH FUNCTIONS
  Functions entirely validate by Macfly 31/05/2000
****************************************************************************************/

fun TREE_GetListOfParents (node) =
  if node == nil
  then
    nil
  else
    node::(TREE_GetListOfParents TREE_Father node)
;;

fun TREE_GetPathToParentList (listParent, node) =
  if node == nil
  then
    [nil nil 0]
  else
    let search_in_list listParent @simpleSearch node -> found in
      if found == nil
      then
        let TREE_GetPathToParentList listParent (TREE_Father node) -> [path founded result] in
          [node::path founded result]
      else
        [nil found 1]
;;

fun TREE_GetPathToParent (node, nodeParent) =
  if node == nil
  then
    [nil 0]
  else
    if node == nodeParent
    then
      [nil 1]
    else
      let TREE_GetPathToParent (TREE_Father node) nodeParent -> [path result] in
        [node::path result]
;;

fun TREE_SearchFirstParentAndPath (node1, node2) =
  if node1 == nil || node2 == nil 
  then
    [nil nil 0 nil]
  else
    if node1 == node2
    then
      [nil nil 1 (TREE_Father node1)]
    else
      let TREE_GetListOfParents node2 -> listParent2 in
        let TREE_GetPathToParentList listParent2 node1 -> [pathNode1 commonParent result] in
          if !result
          then
            [nil nil 0 nil]
          else
            let TREE_GetPathToParent node2 commonParent -> [pathNode2 result] in
              if !result
              then
                [nil nil 0 nil]
              else
                [pathNode1 pathNode2 1 commonParent]
;;


fun TREE_MoveNode (node1, node2) =
  TREE_RemoveNode node1;
  TREE_AddNodeToChildTail node2 node1
;;