DosTips.com

A Forum all about DOS Batch
It is currently 24 Feb 2017 22:34

All times are UTC-06:00




Post new topic  Reply to topic  [ 5 posts ] 
Author Message
PostPosted: 07 Jan 2017 15:52 
Offline

Joined: 24 Jun 2013 17:10
Posts: 421
Location: Bulgaria
I think I saw somewhere here some data structures implemented by Aacini in pure batch(?)

Here's an attempt to create a binary tree (with holding only numbers and without safety checks).
Only insert and find method (now I'm wondering how to implement delete)

Code: Select all
@echo off
setlocal enableDelayedExpansion

:::--- some tests -----
call ::insert test_tree6 1
call ::insert test_tree6 5
call ::insert test_tree6 8
call ::insert test_tree6 9999

color
echo searching for value 8
call ::find test_tree6 8
echo %errorlevel% - if 0 element is found
echo searching for value 123
call ::find test_tree6 123
echo %errorlevel% - if 1 element is not found
set test_tree6
::::::::::::::::::::::::::::::

exit /b 0


:find three_name value
setlocal enableDelayedExpansion
set /a value=%~2
set node=%1

if %value% equ !%1! (
   endlocal & (
      echo %1
      exit /b 0
   )
)


if %value% GTR !%1! (
   if defined %1r (
      endlocal & (
         call ::find %1r %value%
      )
   ) else (
      endlocal & exit /b 1
   )
)

if %value% LSS !%1! (
   if defined %1l (
      endlocal & (
         call ::find %1l %value%
      )
   ) else (
      endlocal & exit /b 1
   )
)


exit /b



:insert three_name value
setlocal
::set "three_name=%~1"
set /a value=%~2

if not defined %~1 (
   endlocal & (
      set "%~1=%value%"
      exit /b 0
   )
)

if %value% GEQ %~1r (
 if not defined  %~1r (
   endlocal & (
      set %~1r=%value%
      exit /b 0
   )
  ) else (
   endlocal & (
      call ::insert %~1r %value%
      rem exit /b 0
   )
  )
)

if %value% LSS %~1l (
  if not defined  %~1l (
   endlocal & (
      set %~1l=%value%
      exit /b 0
   )
   ) else (
   endlocal & (
      call ::insert %~1r %value%
      rem exit /b 0
   )
   )
)

exit /b 0

:delete




As batch files does not support things like objects or structures I'm just using the tree name as the root variable name (e.g. test_tree). The less elements go to 'left' and test_treel variable is created for the bigger elements test_treer and so on. And these variable names are used as root elements in the next recursion calls.

Some things like calculating the tree depth will be pretty easy in this case as you'll need the length of the name biggest variable associated with this tree.
Or number of the nodes will require to count all variables associated with the tree.

At the moment balancing a tree looks like mission impossible...

As for delete a node - it should be fairly easy (I think). If I want to delete test_treelrrl element in theory I'll have delete the last L for all elements under that node.


Top
   
PostPosted: 07 Jan 2017 17:17 
Offline
Expert

Joined: 06 Dec 2011 22:15
Posts: 1290
Location: México City, México
Take a look at this thread, below 2- STRUCTURES AND LINKED LISTS IN BATCH FILES

Antonio


Top
   
PostPosted: 07 Jan 2017 21:00 
Offline
Expert

Joined: 06 Dec 2011 22:15
Posts: 1290
Location: México City, México
Ok. Here it is my own example of an ordered binary tree:

Code: Select all
@echo off
setlocal EnableDelayedExpansion

set "letter=ABCDEFGHIJKLMNOPQRSTUVWXYZ"

< NUL (for /L %%i in (1,1,10) do (
   set /A num=!random!%%10
   for %%n in (!num!) do set "char=!letter:~%%n,1!"
   set /P "=Insert !char!: "
   call :insert !char!
   if errorlevel 1 (echo Duplicated data) else echo Data inserted
))

echo/
set node[
echo/

< NUL (for /L %%i in (1,1,10) do (
   set /A num=!random!%%12
   for %%n in (!num!) do set "char=!letter:~%%n,1!"
   set /P "=Search !char!: "
   call :find !char!
   if errorlevel 1 (echo Not found) else echo Found
))

goto :EOF


:insert value
set "value=%1"
set "node=0"
:insertLoop
if not defined node[%node%].data (
   set "node[%node%].data=%value%"
   set "heap=%node%"
   exit /B 0
)
if %value% equ !node[%node%].data! exit /B 1
if %value% lss !node[%node%].data! (
   if defined node[%node%].left (
      set /A "node=node[%node%].left"
   ) else (
      set /A "node=heap+1, node[%node%].left=node"
   )
) else (
   if defined node[%node%].right (
      set /A "node=node[%node%].right"
   ) else (
      set /A "node=heap+1, node[%node%].right=node"
   )
)
goto :insertLoop


:find value
set "value=%1"
set "node=0"
:findLoop
if not defined node[%node%].data exit /B 1
if %value% equ !node[%node%].data! exit /B 0
if %value% lss !node[%node%].data! (
   if defined node[%node%].left (
      set /A "node=node[%node%].left"
      goto :findLoop
   )
) else (
   if defined node[%node%].right (
      set /A "node=node[%node%].right"
      goto :findLoop
   )
)
exit /B 1

Output example:

Code: Select all
Insert G: Data inserted
Insert J: Data inserted
Insert C: Data inserted
Insert H: Data inserted
Insert C: Duplicated data
Insert E: Data inserted
Insert A: Data inserted
Insert F: Data inserted
Insert A: Duplicated data
Insert A: Duplicated data

node[0].data=G
node[0].left=2
node[0].right=1
node[1].data=J
node[1].left=3
node[2].data=C
node[2].left=5
node[2].right=4
node[3].data=H
node[4].data=E
node[4].right=6
node[5].data=A
node[6].data=F

Search A: Found
Search H: Found
Search A: Found
Search D: Not found
Search K: Not found
Search G: Found
Search E: Found
Search J: Found
Search E: Found
Search J: Found

Antonio


Top
   
PostPosted: 08 Jan 2017 20:15 
Offline
Expert

Joined: 06 Dec 2011 22:15
Posts: 1290
Location: México City, México
I implemented the display of the binary tree in a pleasant, aligned way! :D

Code: Select all
@echo off
setlocal EnableDelayedExpansion

set "letter=ABCDEFGHIJKLMNOPQRSTUVWXYZ"

cls
< NUL (for /L %%i in (1,1,26) do (
   set /A num=!random!%%26
   for %%n in (!num!) do set "char=!letter:~%%n,1!"
   set /P "=Insert !char!: "
   call :insert !char!
   if errorlevel 1 (echo Duplicate data) else echo Data inserted
))

echo/
set node[
echo/

< NUL (for /L %%i in (1,1,10) do (
   set /A num=!random!%%26
   for %%n in (!num!) do set "char=!letter:~%%n,1!"
   set /P "=Search !char!: "
   call :find !char!
   if errorlevel 1 (echo Not found) else echo Found
))

echo/
call :showTree
goto :EOF


:insert value
set "value=%1"
set "node=0"
:insertLoop
if not defined node[%node%].data (
   set "node[%node%].data=%value%"
   set "heap=%node%"
   exit /B 0
)
if %value% equ !node[%node%].data! exit /B 1
if %value% lss !node[%node%].data! (
   if defined node[%node%].left (
      set /A "node=node[%node%].left"
   ) else (
      set /A "node=heap+1, node[%node%].left=node"
   )
) else (
   if defined node[%node%].right (
      set /A "node=node[%node%].right"
   ) else (
      set /A "node=heap+1, node[%node%].right=node"
   )
)
goto :insertLoop


:find value
set "value=%1"
set "node=0"
:findLoop
if not defined node[%node%].data exit /B 1
if %value% equ !node[%node%].data! exit /B 0
if %value% lss !node[%node%].data! (
   if defined node[%node%].left (
      set /A "node=node[%node%].left"
      goto :findLoop
   )
) else (
   if defined node[%node%].right (
      set /A "node=node[%node%].right"
      goto :findLoop
   )
)
exit /B 1


:showTree
for /F "delims==" %%a in ('set leve 2^>NUL') do set "%%a="
setlocal EnableDelayedExpansion
set /A "node=0, thisLevel=-1, level=-1"
call :getLevel
set /A "node=0, thisLevel=-1"
set /P "=Please wait" < NUL
call :fillTree
echo/

echo/
echo Binary Tree (level=%level%):
echo/
set /A "node=heap+1"
set "node[%node%].data=_"
set "spaces= "
for /L %%i in (1,1,%level%) do set "spaces=!spaces!!spaces!"
for /L %%i in (0,1,%level%) do (
   set /A "left=(1<<(level-%%i))-1, sep=(1<<(level-%%i+1))-1"
   for %%n in (!left!) do set "sep0=!spaces:~0,%%n!"
   for %%n in (!sep!) do set "sep1=!spaces:~0,%%n!"
   set "line="
   for %%j in (!level[%%i]!) do (
      set "line=!line!!sep0!!node[%%j].data!"
      set "sep0=!sep1!"
   )
   echo !line!
)
exit /B


:getLevel
setlocal EnableDelayedExpansion
if defined node[%node%].data (

   set /A thisLevel+=1
   if !thisLevel! gtr %level% set "level=!thisLevel!"

   if defined node[%node%].left (
      set /A "node=node[%node%].left"
      call :getLevel
   )

   if defined node[%node%].right (
      set /A "node=node[%node%].right"
      call :getLevel
   )

)
endlocal & set "level=%level%"
exit /B


:fillTree
set /P "=." < NUL
setlocal EnableDelayedExpansion
set /A thisLevel+=1

if %thisLevel% leq %level% (

   set "level[%thisLevel%]=!level[%thisLevel%]! %node%"

   if defined node[%node%].left (
      set /A "node=node[%node%].left"
   ) else (
      set /A "node=heap+1"
   )
   call :fillTree

   if defined node[%node%].right (
      set /A "node=node[%node%].right"
   ) else (
      set /A "node=heap+1"
   )
   call :fillTree

)
set "leve=1"
for /F "delims=" %%a in ('set leve') do (
   if defined leve (endlocal) else set "%%a"
)
exit /B

Here there are some examples of the binary tree output:

Code: Select all
Binary Tree (level=5):

                               E
               D                               P
       C               _               K               X
   _       _       _       _       J       M       U       Z
 _   _   _   _   _   _   _   _   I   _   L   O   S   V   _   _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ H _ _ _ _ _ _ _ Q _ _ _ _ _ _ _


Binary Tree (level=5):

                               G
               C                               P
       B               D               K               R
   A       _       _       F       J       M       Q       U
 _   _   _   _   _   _   E   _   _   _   L   _   _   _   T   V
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ S _ _ X


Binary Tree (level=6):

                                                               O
                               N                                                               T
               K                               _                               S                               Y
       B               M               _               _               R               _               _               Z
   _       I       L       _       _       _       _       _       Q       _       _       _       _       _       _       _
 _   _   E   J   _   _   _   _   _   _   _   _   _   _   _   _   P   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _
_ _ _ _ C G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _


Binary Tree (level=6):

                                                               J
                               G                                                               O
               F                               H                               M                               S
       D               _               _               I               K               _               Q               U
   _       _       _       _       _       _       _       _       _       L       _       _       P       _       _       W
 _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   V   Z
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ X _

Antonio


Top
   
PostPosted: 08 Jan 2017 20:39 
Offline

Joined: 24 Jun 2013 17:10
Posts: 421
Location: Bulgaria
That's impressive , tough I still hadn't checked your code :)


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 5 posts ] 

All times are UTC-06:00


Who is online

Users browsing this forum: Yahoo [Bot] and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited