FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Defining a package to handle binary trees

Description
  • definition of subroutines (function, procedure)
  • data structures 'list' and 'record'
  • type definitions
The package 'bintree' defines the new types 'tree' (to represent a binary tree data structure) and 'node' (a tree node, building blocks of trees storing the actual data) for the Mosel language and also a set of subroutines for working with trees, such as inserting a value into a tree, locating a value, getting the tree size, printing out a tree, and converting a tree to a list.

The model file 'exbtree.mos' shows how to create a tree and work with it using the functionality of this package. To run this example, you first need to compile the package (resulting in the BIM file 'bintree.bim'). You may then execute the example in the same directory that contains this BIM file.


Source Files





bintree.mos

(!*******************************************************
   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

Back to examples browserPrevious exampleNext example