Defining a package to handle binary trees

• definition of subroutines (function, procedure)
• data structures 'list' and 'record'
• type definitions

(!*******************************************************
   Mosel Example Problems
   ======================

   file bintree.mos
   ````````````````
   a package that provides the functionality for
   handling binary trees

   (c) 2008 Fair Isaac Corporation
       author: Y. Colombani, 2006
  *******************************************************!)
package bintree

declarations
 public btree_R:range
 public btree_node=record
       value:real
       left,right:integer
      end-record
 public tree=record
       lastnode:integer
       nodes:dynamic array(btree_R) of btree_node
      end-record
end-declarations

forward procedure show(t:tree,n:integer)
forward procedure makelist(t:tree,n:integer,l:list of real)

!**************************************************************
!* Public declarations
!**************************************************************
!**************
! Reset a tree
!**************
public procedure reset(t:tree)
 delcell(t.nodes)
 t.lastnode:=0
end-procedure

!************************
! Get the size of a tree
!************************
public function getsize(t:tree):integer
 returned:=t.lastnode
end-function

!**************************
! Insert a value in a tree
!**************************
public procedure insert(t:tree,v:real)
 if t.lastnode  > 0 then
  j:=1
  repeat
   p_j:=j
   j:=if(t.nodes(j).value > v , t.nodes(j).left,t.nodes(j).right)
  until (j=0)
  if t.nodes(p_j).value <> v then
   t.lastnode+=1
   t.nodes(t.lastnode).value:=v
   if t.nodes(p_j).value > v then
    t.nodes(p_j).left:=t.lastnode
   else
    t.nodes(p_j).right:=t.lastnode
   end-if
  end-if
 else
  t.lastnode+=1
  t.nodes(t.lastnode).value:=v
 end-if
end-procedure

!***************************************************
! Check whether a value is already stored in a tree
!***************************************************
public function find(t:tree,v:real):boolean
 if t.lastnode > 0 then
  j:=1
  repeat
   if t.nodes(j).value > v then
    j:=t.nodes(j).left
   elif t.nodes(j).value < v then
    j:=t.nodes(j).right
   else
    break
   end-if
  until (j=0)
  returned:= j<>0
 else
  returned:=false
 end-if
end-function

!*****************
!* Display a tree
!*****************
public procedure show(t:tree)
 write("<")
  if t.lastnode > 0 then
   show(t,1)
  end-if
 writeln(" >")
end-procedure

!*************************************************
!* Return the sorted list of all values of a tree
!*************************************************
public function tolist(t:tree):list of real
  if t.lastnode > 0 then
   makelist(t,1,returned)
  end-if
end-function

!**************************************************************
!* Private declarations
!**************************************************************
!********************
!* Display a subtree
!********************
procedure show(t:tree,n:integer)
 if n > 0 then
  show(t,t.nodes(n).left)
  write(" ",t.nodes(n).value)
  show(t,t.nodes(n).right)
 end-if
end-procedure

!*****************************
!* Append a subtree to a list
!*****************************
procedure makelist(t:tree,n:integer,l:list of real)
 if n > 0 then
  makelist(t,t.nodes(n).left,l)
  l+=[t.nodes(n).value]
  makelist(t,t.nodes(n).right,l)
 end-if
end-procedure

end-package

(!*******************************************************
   Mosel Example Problems
   ======================

   file exbtree.mos
   ````````````````
   Example of use lists and of the 'bintree' package

   -- Note: The package 'bintree' (file bintree.mos)  
      needs to be compiled before executing this model --

   (c) 2008 Fair Isaac Corporation
       author: Y. Colombani, 2006
  *******************************************************!)
model exbtree
uses ':bintree.bim'

declarations
 arbre:tree
 allvals:list of real
end-declarations

repeat
 insert(arbre,round(random*100))
until arbre.size = 10

write("Values in the binary tree:"); show(arbre)

allvals:=tolist(arbre)
writeln("The smallest value:",allvals.first)
writeln("The biggest value:",allvals.last)
writeln("The 5 first entries:",splithead(allvals,5))
writeln("Remaining after split:",allvals)

end-model