Monday, April 12, 2010

usp_DrawTree

Here is the source code for the usp_DrawTree procedure that was highlighted in my last blog post that was part of T-SQL Tuesday #005: Reporting.

You can also download this code from my SkyDrive.

Update on Jun13,2012: The code below has been updated since 2010. The code unfortunately made an assumption that the data in the temp table #TreeResult would be pulled out (via SELECT) in the same order it was INSERTed. That's incorrect. So I added an IDENTITY KEY to the table and an ORDER BY to the SELECT.

use TempDB /* Set to whatever database you wish */
go

if object_id('usp_DrawTree','P') is not null drop procedure usp_DrawTree
go

create procedure usp_DrawTree
@ID
int = null /* Desired ID value */
,@HangStyle bit = 0 /* Draw in Hanging Style? (vs. Left/Right Balanced) */
,@Direction char(1) = 'T' /* Branch Direction: R=Right L=Left M=Middle T=Top */
,@Level int = 1 /* Level to generate */
as

set nocount on

/* Make sure the Direction is valid */
if @Direction not in ('R','L','M','T')
begin
raiserror('Invalid @Direction... Must be R or L or M or T.',16,1)
return -1
end

/* Make sure the Level is valid */
if @Direction='T' set @Level=1
if @Level<1
begin
raiserror('Invalid @Level value.',16,1)
return -1
end

/*
If we are at Level 1 (the top Level), then...
Make sure our input table exists and that it has the required columns.
Also create some temp tables that will be needed as we build the tree.
*/
if @Level=1
begin
if object_id('tempdb..#TreeData','U') is null
begin
raiserror('You must have a #TreeData table prepared.',16,1)
return -1
end

declare @TreeDataColumns table
(
ColumnName nvarchar(128)
,DataType varchar(30)
)

insert @TreeDataColumns
select Name
,type_name(System_Type_ID)
from TempDB.sys.columns
where Object_ID=object_id('TempDB..#TreeData','U')

if not exists(select *
from @TreeDataColumns
where ColumnName='ID' and DataType='int')
begin
raiserror('#TreeData must contain an int column called ID.',16,1)
return -1
end
if not exists(select *
from @TreeDataColumns
where ColumnName='ParentID' and DataType='int')
begin
raiserror('#TreeData must contain an int column called ParentID.',16,1)
return -1
end
if not exists(select *
from @TreeDataColumns
where ColumnName='DataForBox')
begin
raiserror('#TreeData must contain a column called DataForBox.',16,1)
return -1
end
if not exists(select *
from @TreeDataColumns
where ColumnName='ExtraInfo')
begin
raiserror('#TreeData must contain a column called ExtraInfo.',16,1)
return -1
end
if not exists(select *
from @TreeDataColumns
where ColumnName='SortColumn')
begin
raiserror('#TreeData must contain a column called SortColumn.',16,1)
return -1
end

/* This table houses information about the branches at each level */
if object_id('TempDB..#BranchInfo','U') is not null drop table #BranchInfo
create table #BranchInfo
(
TreeLevel int primary key /* The Level 1..n */
,BoxWidth int /* The Width of the Box at that level */
,InProcess bit /* Is branch in process at that level? */
)
/* This table houses our final result that we will return to the user */
if object_id('TempDB..#TreeResult','U') is not null drop table #TreeResult
create table #TreeResult
(
TreeID int identity(1,1)
,TreeContent nvarchar(max)
)

end


/*
If the desired ID is null, then initialize it to whichever ID
in the table has a null ParentID, which will be the head honcho.
Note that TOP 1 is used just in case there is more than 1
row in the table with a ParentID equal to null
*/
if @ID is null
begin
set @ID=(select top 1 ID
from #TreeData
where ParentID is null)
end

/* Acquire the DataForBox and ExtraInfo columns into variables */
declare @DataForBox nvarchar(max)
,@ExtraInfo nvarchar(max)
select @DataForBox=cast(DataForBox as nvarchar(max))
,@ExtraInfo=cast(coalesce(ExtraInfo,'') as nvarchar(max))
from #TreeData
where ID=@ID

/* Define some more variables */
declare @MaxWidth int /* Maximum Width of Box */
,@NumBoxLines int /* Number of Lines of Data in Box */
,@PrimaryBoxLine int /* The Box Line from which we sprout a branch */
,@NumSubords int /* Quantity of Subordinates */
,@NumOnRight int /* Number of Subordinates on Right Side */
,@Counter int /* All-purpose counting variable */
,@Output nvarchar(max) /* String that we build for each line of output */
,@BoxData nvarchar(max) /* String containing line of data to put in Box */

declare @IDToProcess int /* The ID to process when we call recursively */
,@DirectionToProcess char(1) /* And the Direction to process */
,@LevelToProcess int /* And the Level to process */

/*
The @DataForBox variable contains the data we want to put in a box.
Optional vertical bars (|) can be used to indicate multiple lines to
display in the box.
The following @BoxLines table variable will split the @DataForBox
variable into rows.
*/
declare @BoxLines table
(
SeqNo int identity(1,1) primary key
,BoxData nvarchar(max)
)
insert @BoxLines
select XMLNode.value('(./text())[1]','nvarchar(max)')
from (select XMLString='<i>'+replace(@DataForBox,'|','</i><i>')+'</i>') X
cross apply (select XMLList=cast(XMLString as xml).query('.')) F1
cross apply XMLList.nodes('i') F2(XMLNode)

/*
What's the maximum width of a line in the box?
How many lines are there?
And which is the primary line (i.e. middle line) from which we sprout a child branch?
*/
select @MaxWidth=max(len(BoxData))
,@NumBoxLines=count(*)
,@PrimaryBoxLine=ceiling(1.0*count(*)/2)
from @BoxLines

/* Create an entry in #BranchInfo for the current Level if it doesn't exist */
if not exists (select * from #BranchInfo where TreeLevel=@Level)
insert #BranchInfo (TreeLevel) values (@Level)

/*
Populate #BranchInfo with information about the Level's BoxWidth
and the status of the Level in terms of Branches
*/
update #BranchInfo
set InProcess=case when @Direction in ('M','L') then 1 else 0 end
,BoxWidth=@MaxWidth+4+1 /* 4=LeftBorder+Space+Space+RightBorder, 1=BranchOutput */
where TreeLevel=@Level

/*
Collect all the subordinates of @ID into a table variable.
Order them by the SortColumn.
*/
declare @Subordinates table
(
SeqNo int identity(1,1) primary key
,ID int
)
insert @Subordinates
select ID
from #TreeData
where ParentID=@ID
order by SortColumn

/*
How many subordinates are there?
And How many on the right side?
*/
select @NumSubords=count(*)
,@NumOnRight=case
when @HangStyle=1
then 0
else count(*)/2
end
from
@Subordinates

/*
Before we draw our box, we must recursively process
all children on our right side
*/
set @Counter=0
while @Counter<@NumOnRight
begin
set @Counter=@Counter+1
select @IDToProcess=(select ID from @Subordinates where SeqNo=@Counter)
,@DirectionToProcess=case when @Counter=1 then 'R' else 'M' end
,@LevelToProcess=@Level+1
exec usp_DrawTree @IDToProcess
,@HangStyle
,@DirectionToProcess
,@LevelToProcess
end

/* Draw all branches in process for previous levels */
set @Output=''
select @Output=@Output+case
when InProcess=1
then N'│ '
else N' '
end
+space(BoxWidth)
from #BranchInfo
where TreeLevel<@Level

/*
And now draw...
1) Any in-process branch for our current level
2) The top border of our box
3) Any branch that might connect to right-hand children
*/
set @Output=@Output+case
when @Direction in ('L','M')
then N'│ '
else N' '
end
+N'┌'+replicate(N'─',@MaxWidth+2)+N'┐'
+case
when @NumSubords=0 then N' '
when @NumOnRight=0 then N' '
else N' │'
end

/* Save that to our result table */
insert #TreeResult (TreeContent)
select @Output

/*
Now it's time to output the data within the the box itself.
We will perform a loop for each line to be written in the box.
*/
set @Counter=0
while @Counter<@NumBoxLines
begin
set @Counter=@Counter+1

/* Bet the @BoxData for the line to be written */
select @BoxData=ltrim(rtrim(BoxData))
from @BoxLines
where SeqNo=@Counter

/* Pad it with spaces to center it in the box */
set @BoxData=space((@MaxWidth-len(@BoxData))/2)+@BoxData
set @BoxData=@BoxData+space(@MaxWidth-len(@BoxData))


/* Draw all branches in process for previous levels */
set @Output=''
select @Output=@Output+case
when InProcess=1
then N'│ '
else N' '
end
+space(BoxWidth)
from #BranchInfo
where TreeLevel<@Level

/*
And now draw...
1) Any in-process branch for our current level and the left border of our box
2) The line in the box (@BoxData) padded with leading and trailing space
3) The right border of our box and any any branch that might connect to children
4) Any Extra Info to appear to the right of the box
*/
set @Output=@Output+case
when @Counter<@PrimaryBoxLine
then case
when @Direction='R' then N' │'
when @Direction='L' then N'│ │'
when @Direction='M' then N'│ │'
when @Direction='T' then N' │'
end
when @Counter=@PrimaryBoxLine
then case
when @Direction='R' then N'┌─┤'
when @Direction='L' then N'└─┤'
when @Direction='M' then N'├─┤'
when @Direction='T' then N' │'
end
else case
when @Direction='R' then N'│ │'
when @Direction='L' then N' │'
when @Direction='M' then N'│ │'
when @Direction='T' then N' │'
end
end
+N' '+@BoxData+N' '
+case
when @Counter<@PrimaryBoxLine
then case
when @NumSubords=0 then N'│'
when @NumOnRight=0 then N'│'
else N'│ │'
end
when @Counter=@PrimaryBoxLine
then case
when @NumSubords=0 then N'│'
when @NumOnRight=0 then N'├─┐'
else N'├─┤'
end
else case
when @NumSubords=0 then N'│'
when @NumOnRight=0 then N'│ │'
else N'│ │'
end
end
+case
when @ExtraInfo<>'' and @Counter=@PrimaryBoxLine
then ' '+@ExtraInfo
else ''
end

/* Save that to our result table */
insert #TreeResult (TreeContent)
select @Output

end

/* Draw all branches in process for previous levels */
set @Output=''
select @Output=@Output+case
when InProcess=1
then N'│ '
else N' '
end
+space(BoxWidth)
from #BranchInfo
where TreeLevel<@Level

/*
And now draw...
1) Any in-process branch for our current level
2) The bottom border of our box
3) Any branch that might connect to left-hand children
*/
set @Output=@Output+case
when @Direction in ('R','M')
then N'│ '
else N' '
end
+N'└'+replicate(N'─',@MaxWidth+2)+N'┘'
+case
when @NumSubords=0 then N' '
when @NumOnRight=0 then N' │'
else N' │'
end

/* Save that to our result table */
insert #TreeResult (TreeContent)
select @Output

/*
Populate #BranchInfo with information about the current
Level's status in terms of Branches
*/
update #BranchInfo
set InProcess=case when @Direction in ('R','M') then 1 else 0 end
where
TreeLevel=@Level

/*
Now that we've finished drawing our box, we may recursively
process all children on our left side
*/
set @Counter=@NumOnRight
while @Counter<@NumSubords
begin
set @Counter=@Counter+1
select @IDToProcess=(select ID from @Subordinates where SeqNo=@Counter)
,@DirectionToProcess=case when @Counter=@NumSubords then 'L' else 'M' end
,@LevelToProcess=@Level+1
exec usp_DrawTree @IDToProcess
,@HangStyle
,@DirectionToProcess
,@LevelToProcess
end

/*
If we are at this point with Level 1, that means we have
successfully finished everything. So return our result
and clean up our temporary tables that we created.
*/
if @Level=1
begin
select TreeContent from #TreeResult order by TreeID
drop table #BranchInfo
drop table #TreeResult
end

1 comment: