Arrays, structures and linked lists in Batch files
Posted: 22 Apr 2012 00:10
In this SO topic the OP asked for "Arrays, linked lists and other data structures in Batch scripts". This subject was quite interesting to me, so I made some fascinating developments in this area and replied with this answer.
Before enter this topic I want to insert here a phrase I used before:
1- ARRAY MANAGEMENT IN BATCH FILES
Arrays in Batch files may be simulated in a straightforward way: just write variable names in the form of array elements:
To use another variable as index use Delayed Expansion: enclose index variable in percent symbols, and enclose the array element in exclamation marks:
You must use !index! to store values in array elements when the index is changed inside a FOR or IF:
To get the value of an element when the index changes inside FOR/IF, enclose the element in double percent symbols and precede the command with CALL. For example, to move a range of array elements four places to the left:
Another way to achieve the previous process is to use an additional FOR command to change the delayed expansion of the index by an equivalent replaceable parameter, and then use the delayed expansion for the array element. This method runs faster than previous CALL:
If the array contain numbers, you may use SET /A command to directly process array element values with no need of the additional value expansion:
Multi-dimensional arrays may be simulated in the same way, but there are different flavors to write the multiple indexes. The C-like notation matrix[%i%][%j%] have some advantages because we may extract a row from a matrix as a vector in a very easy way:
An interesting difference that Batch arrays have versus other programming languages is that the indexes are not restricted to be numerical values, so they may be any string. The Batch file below is an example of a two-dimensional array management program that uses no-numerical indexes; it is a very basic multi-language translation program that may "learn" new translation terms. The program have multiple limitations because it is focused on the array management part only.
TRANSLATE.BAT:
TRANSLATION.BAT:
2- STRUCTURES AND LINKED LISTS IN BATCH FILES
The Batch file below simulate structures and linked-list management. The program use such simulations to traverse through the directory tree of a given subdirectory and assemble a complex data scheme that include multiple linked lists comprised of these self-referential structures:
After the whole data structure is created, the program process it and output a result similar of TREE command's.
I used structName.memberName notation for structure members and "%pointer%->memberName" notation for dynamic structures allocated via :malloc routine (quotes are mandatory). I simulated a pointer, that in C language is a real memory address, with an unique address that distinguish a certain variable from other instances of itself (in the same way of C language).
Most subroutines below have not any error checking to made they simpler and smaller, but such checking may be added if someone want to use these features in a real application. Of course, Batch is too slow to make good use of such features, but it may be a very good example of such features for educative purposes (i.e. to have a first contact with these concepts before using they in C language).
I suggest you to take paper and pencil and draw small rectangles ("nodes") that include arrows ("pointers") to other rectangles ("linked-list") while you review the Batch file below. Also, the program have a few commands written in UPPERCASE letters that are used just to trace the execution, so I suggest you to ignore such commands in the first reading.
MyTree.bat:
Antonio
Before enter this topic I want to insert here a phrase I used before:
You may see this topic as a simulation of such features written in Batch language, but in the final analysis, most features of high level languages are also simulations in one or other way (remember that the RAM is just a flat set of bytes with no structure at all!). I tried to use the simplest/clearest way to achieve these simulations, but I know that many different ways to do the same thing exist.I occasionally wrote:I think the important point here is not to discuss if Batch really have such features or not, but the fact that you may use such features in a Batch file with the aid of a couple small tricks.
1- ARRAY MANAGEMENT IN BATCH FILES
Arrays in Batch files may be simulated in a straightforward way: just write variable names in the form of array elements:
Code: Select all
set "elem[1]=First element"
set "elem[2]=Second one"
set "elem[3]=The third one"
To use another variable as index use Delayed Expansion: enclose index variable in percent symbols, and enclose the array element in exclamation marks:
Code: Select all
setlocal EnableDelayedExpansion
set "elem[1]=First element"
set "elem[2]=Second one"
set "elem[3]=The third one"
set i=2
echo !elem[%i%]!
rem You may use parameters of FOR command as indexes:
for /L %%i in (1,1,3) do echo !elem[%%i]!
You must use !index! to store values in array elements when the index is changed inside a FOR or IF:
Code: Select all
set num=0
for /F "delims=" %%a in (severalLines.txt) do (
set /A num+=1
set "elem[!num!]=%%a"
)
To get the value of an element when the index changes inside FOR/IF, enclose the element in double percent symbols and precede the command with CALL. For example, to move a range of array elements four places to the left:
Code: Select all
for /L %%i in (%start%,1,%end%) do (
set /A j=%%i + 4
call set "elem[%%i]=%%elem[!j!]%%"
)
Another way to achieve the previous process is to use an additional FOR command to change the delayed expansion of the index by an equivalent replaceable parameter, and then use the delayed expansion for the array element. This method runs faster than previous CALL:
Code: Select all
for /L %%i in (%start%,1,%end%) do (
set /A j=%%i + 4
for %%j in (!j!) do set "elem[%%i]=!elem[%%j]!"
)
If the array contain numbers, you may use SET /A command to directly process array element values with no need of the additional value expansion:
Code: Select all
for /L %%i in (%start%,1,%end%) do (
set /A j=%%i + 4
set /A "elem[%%i]=elem[!j!]"
)
Multi-dimensional arrays may be simulated in the same way, but there are different flavors to write the multiple indexes. The C-like notation matrix[%i%][%j%] have some advantages because we may extract a row from a matrix as a vector in a very easy way:
Code: Select all
:setVector vector=matrix[!row!]
for /F "tokens=3,4 delims=[]=" %%a in ('set %2') do (
set "%1[%%a]=%%b"
)
exit /B
An interesting difference that Batch arrays have versus other programming languages is that the indexes are not restricted to be numerical values, so they may be any string. The Batch file below is an example of a two-dimensional array management program that uses no-numerical indexes; it is a very basic multi-language translation program that may "learn" new translation terms. The program have multiple limitations because it is focused on the array management part only.
TRANSLATE.BAT:
Code: Select all
@echo off
setlocal EnableDelayedExpansion
rem Example of Multi-dimensional array management in Batch files
rem Antonio Perez Ayala - Apr/22/2012
rem Load Translation matrix from saved file, and define Language vector
call Translation.bat
for /F "tokens=2 delims=[]" %%v in ('set Translation[') do (
set Language[%%v]=1
)
set anyModification=
:chooseFromTo
cls
echo I know these translation languages:
echo/
for /F "tokens=2 delims=[]" %%a in ('set Language[') do (
echo %%a
)
echo/
set fromTo=
set /P "fromTo=Type one or enter a new one (empty to end): "
if not defined fromTo goto endTranslation
for /F "tokens=1,2 delims=-" %%a in ("%fromTo%") do (
set from=%%a
set to=%%b
)
set Language[%fromTo%]=1
set Language[%to%-%from%]=1
:readWord
echo/
set word=
set /P "word=Enter word in first language: "
if not defined word goto chooseFromTo
if defined Translation[%fromTo%][%word%] (
echo The translated word is: !Translation[%fromTo%][%word%]!
) else (
set new=%to%
set /P "new=I don't know that word, enter %to% equivalent: "
set Translation[%fromTo%][%word%]=!new!
set Translation[%to%-%from%][!new!]=%word%
set anyModification=TRUE
)
goto readWord
:endTranslation
if defined anyModification (
for /F %%v in ('set Translation[') do echo set %%v
) > Translation.bat
cls
Code: Select all
set Translation[ENGLISH-SPANISH][RED]=ROJO
set Translation[ENGLISH-SPANISH][SUNDAY]=DOMINGO
set Translation[SPANISH-ENGLISH][DOMINGO]=SUNDAY
set Translation[SPANISH-ENGLISH][ROJO]=RED
2- STRUCTURES AND LINKED LISTS IN BATCH FILES
The Batch file below simulate structures and linked-list management. The program use such simulations to traverse through the directory tree of a given subdirectory and assemble a complex data scheme that include multiple linked lists comprised of these self-referential structures:
Code: Select all
struct DirNode {
DirName = Name of this DirNode
Prev = Pointer to previous DirNode at this level
Next = Pointer to next DirNode at this level
NestedDir = Pointer to first nested DirNode
NestedFile = Pointer to first nested FileNode
}
struct FileNode {
FileName = Name of this FileNode
Prev = Pointer to previous FileNode
Next = Pointer to next FileNode
}
After the whole data structure is created, the program process it and output a result similar of TREE command's.
I used structName.memberName notation for structure members and "%pointer%->memberName" notation for dynamic structures allocated via :malloc routine (quotes are mandatory). I simulated a pointer, that in C language is a real memory address, with an unique address that distinguish a certain variable from other instances of itself (in the same way of C language).
Most subroutines below have not any error checking to made they simpler and smaller, but such checking may be added if someone want to use these features in a real application. Of course, Batch is too slow to make good use of such features, but it may be a very good example of such features for educative purposes (i.e. to have a first contact with these concepts before using they in C language).
I suggest you to take paper and pencil and draw small rectangles ("nodes") that include arrows ("pointers") to other rectangles ("linked-list") while you review the Batch file below. Also, the program have a few commands written in UPPERCASE letters that are used just to trace the execution, so I suggest you to ignore such commands in the first reading.
MyTree.bat:
Code: Select all
@echo off
rem Example of Structures and Linked-lists management in Batch files
rem Antonio Perez Ayala - Apr/22/2012
rem Auxiliary variables for easier structure declaration
setlocal DisableDelayedExpansion
set struct=set
set {==^^
set ;=^^
set }=
FOR /F "SKIP=4 DELIMS=pR TOKENS=1,2" %%A IN (
'reg query hkcu\environment /v temp' ) DO SET TAB=%%B
FOR /F %%A IN ('COPY /Z "%~F0" NUL') DO SET CR=%%A
setlocal EnableDelayedExpansion
rem Initialize global variables
set NULL=0
set heapPointer=%NULL%
goto Main
rem Auxiliary subroutine to echo "%pointer%->structMember" with no quotes
:show "value"
echo %~1
exit /B
/* "Method" to allocate a structure
Parameter %1 is the structure name, that must be defined this way:
set structName= member1=value1, member2="value2 with delimiters", ...
Values are assigned to members when the struct is allocated
Value returned in %2 variable is a "pointer" to the allocated struct */
:malloc structName pointer=
set /A heapPointer+=1, %2=heapPointer
set #=
for %%a in (!%1!) do (
if not defined # (
set #=%%a
) else (
set "!%2!->!#!=%%~a"
set #=
)
)
exit /B
/* "Method" to release a structure
Parameter %1 must be a "pointer" value to the struct to release */
:free pointer
for /F "delims==" %%a in ('set "%1->"') do (
set "%%a="
)
exit /B
/* "Method" to insert a Node struct into a linked or double-linked list
Param %1->Node after which the new Param %2->Node will be inserted
This method use standard "Prev" and "Next" member names for the links */
:insert original new
rem Update new-Node links (backward if defined, and forward)
if "!%2->Prev!" neq "" (
set "%2->Prev=%1"
)
set "%2->Next=!%1->Next!"
rem Change original-Node forward link to new-Node
set "%1->Next=%2"
rem Change "originally next"-Node backward link to new-Node, if defined and exists
if "!%2->Prev!" neq "" (
if "!%2->Next!" neq "%NULL%" (
set "!%2->Next!->Prev=%2"
)
)
exit /B
/* "Method" to remove a Node struct from a linked or double-linked list
Param %1->Node after which the %1->Node->Node will be removed
This method use standard "Prev" and "Next" member names for the links
Note that you must use :free to release the Head-node of a linked-list
and that that node must be the last one to be released! */
:remove afterThis
rem Get a pointer to the Node after this one
set "#2=!%1->Next!"
rem Change this Node forward link to the node 2 places forward, if exists
if %#2% neq %NULL% (
if "!%#2%->Next!" neq "%NULL%" (
set "%1->Next=!%#2%->Next!"
) else (
set "%1->Next=%NULL%"
)
)
rem Change "2 places forward"-Node backward link to this Node, if defined and exists
if "!%1->Prev!" neq "" (
if %#2% neq %NULL% (
if "!%#2%->Next!" neq "%NULL%" (
set "!%#2%->Next!->Prev=%1"
)
)
)
rem Release the Node after this one
call :free %#2%
exit /B
rem Recursive subroutine to create the data structure beneath a subDir
rem Parameter %1->parentDir Node of this Dir
:ProcessThisDir parentDir
rem This sub can NOT have SetLocal, because its purpose is create global variables
SET /A LEVEL+=1
rem Create the linked list of nested files in this level
set parentDir=%1
for %%f in (*.*) do (
SET /A NODES_IN_LEVEL[%LEVEL%]+=1
SET /P "=!CR!NODES BY LEVEL" <NUL >&2
(FOR /L %%I IN (1,1,%LEVEL%) DO (
SET /P "=!TAB!%%I: !NODES_IN_LEVEL[%%I]!"
)) <NUL >&2
call :malloc FileNode thisFile=
set "!thisFile!->FileName=%%f"
if defined parentDir (
rem This node is the Head node of a new linked list
set "%parentDir%->NestedFile=!thisFile!"
set parentDir=
) else (
rem This node is an additional one in the list
set "!prevFile!->Next=!thisFile!"
)
rem In next iteration "thisNode" becomes "prevNode"
set prevFile=!thisFile!
)
rem Create the linked list of nested directories in this level
set parentDir=%1
for /D %%d in (*) do (
SET /A NODES_IN_LEVEL[%LEVEL%]+=1
SET /P "=!CR!NODES BY LEVEL" <NUL >&2
(FOR /L %%I IN (1,1,%LEVEL%) DO (
SET /P "=!TAB!%%I: !NODES_IN_LEVEL[%%I]!"
)) <NUL >&2
call :malloc DirNode thisDir=
set "!thisDir!->DirName=%%d"
if defined parentDir (
rem This node is the Head node of a new linked list
set "%parentDir%->NestedDir=!thisDir!"
set parentDir=
) else (
rem This node is an additional one in the list
set "!prevDir!->Next=!thisDir!"
)
rem In next iteration "thisNode" becomes "prevNode"
set prevDir=!thisDir!
rem Enter to each Subdir, process it recursively and go back to original Dir
cd "%%d"
rem Simulate a SetLocal on prevDir variable (and undefined parentDir)
set /A sp+=1
set prevDir[!sp!]=!prevDir!
call :ProcessThisDir !thisDir!
rem Simulate an EndLocal on prevDir variable (and undefined parentDir)
set /A prevDir=prevDir[!sp!], sp-=1
set parentDir=
cd ..
)
SET /A LEVEL-=1
exit /B
rem Recursive subroutine to display the data structure beneath a DirNode
rem Parameter %1->DirNode to display
rem Parameter %2: nextMargin to add to current one
:DisplayThisNode thisNode nextMargin
setlocal EnableDelayedExpansion
set "margin=%margin%%~2"
rem Display FileNodes, if requested
if not defined showFiles% goto endShowFiles
rem Get current file margin
if "!%1->NestedDir!" neq "%NULL%" (
set "fileMargin=│ "
) else (
set "fileMargin= "
)
rem Display nested FileNodes
set "nextFile=!%1->NestedFile!"
:While_nextFile neq %NULL% do
if %nextFile% equ %NULL% goto WEnd_nextFile
call :show "%margin%%fileMargin%!%nextFile%->FileName!"
set "nextFile=!%nextFile%->Next!"
goto While_nextFile
:WEnd_nextFile
if "!%1->NestedFile!" neq "%NULL%" (
echo/%margin%%fileMargin%
)
:endShowFiles
rem Display nested DirNodes
set "nextDir=!%1->NestedDir!"
:While_nextDir neq %NULL% do
if %nextDir% equ %NULL% goto WEnd_nextDir
rem Get current dir margin
if "!%nextDir%->Next!" neq "%NULL%" (
set "dirMargin=├───"
set "nextMargin=│ "
) else (
set "dirMargin=└───"
set "nextMargin= "
)
rem Display Name of next DirNode
call :show "%margin%%dirMargin%!%nextDir%->DirName!"
rem Display contents of next DirNode
call :DisplayThisNode %nextDir% "%nextMargin%"
rem Pass to next DirNode in this level
set "nextDir=!%nextDir%->Next!"
goto While_nextDir
:WEnd_nextDir
exit /B
:Main
rem Show the help, if requested
if "%1" equ "/?" (
echo Graphically displays the folder structure of a drive or path.
echo/
echo MYTREE [drive:][path] [/F]
echo/
echo /F Display the names of the files in each folder.
goto :EOF
)
rem Get the parameters
set showFiles=
set targetDir=.
if "%~1" neq "" (
if /I "%~1" equ "/F" (
set showFiles=YES
) else (
set "targetDir=%~1"
)
shift
)
if "%~1" neq "" (
if /I "%~1" equ "/F" (
set showFiles=YES
) else (
set "targetDir=%~1"
)
)
pushd .
cd /D "%targetDir%" || popd && goto :EOF
rem Single-line (Batch style) struct definition:
set FileNode= FileName=name, Prev="%NULL% not used in this example", Next=%NULL%
rem Multi-line (C style) struct definition (with the aid of some variables)
rem Do NOT leave any space between structName and %{%
%struct% DirNode%{%
DirName = name %;%
Prev = "%NULL% not used in this example" %;%
Next = %NULL% %;%
NestedDir = %NULL% %;%
NestedFile = %NULL% %;%
%}%
rem Create the node of target directory
call :malloc DirNode targetDir=
set "%targetDir%->DirName=%CD%"
rem Create the whole data structure beneath it
SET LEVEL=0
set sp=0
call :ProcessThisDir %targetDir%
(ECHO/&ECHO/) >&2
REM DUMP HEAP MEMORY
REM IF %HEAPPOINTER% GTR 9 SET HEAPPOINTER=9
REM FOR /L %%I IN (1,1,%HEAPPOINTER%) DO SET %%I
REM PAUSE
rem Show the created data structure in TREE command format
echo Folder PATH listing
for /F "skip=1 delims=" %%a in ('vol') do echo %%a
call :show "!%targetDir%->DirName!"
set margin=
call :DisplayThisNode %targetDir%
if "!%targetDir%->NestedDir!" equ "%NULL%" (
echo No subfolders exists
echo/
)
popd
Antonio
