/*************************************************************************

 Handling Recursive hierarchies using the LR Method
 A code sample from www.bimonkey.com
 Written by James Beresford for www.bimonkey.com on 15/09/2009
 Please contact via email at the admin account of the bimonkey.com domain

 Re-use for educational purposes is permitted but if used in
 any environment no liability is accepted unless by
 prior commercial agreement.

************************************************************************/

/*************************************************************************

Index

Step 1: Create tables
Step 2: Populate tables
Step 3: Create LR Values 
Step 4: Demonstrate use of LR Values

************************************************************************/


/*************************************************************************

Step 1: Create tables

dbo.Hierarchy - contains the recursive Hierarchy
dbo.Values - contains the values for the Hierarchy
dbo.RecursiveHierarchy - contains the LR Values

************************************************************************/

SET ANSI_NULLS ON
GO

SET QUOTED_IDENTIFIER ON
GO

CREATE TABLE [dbo].[Hierarchy](
	[ParentLevel] [nchar](10) NOT NULL,
	[ChildLevel] [nchar](10) NOT NULL
) ON [PRIMARY]

GO

CREATE TABLE [dbo].[Values](
	[Level] [nchar](10) NOT NULL,
	[Value] [tinyint] NOT NULL
) ON [PRIMARY]

GO

CREATE TABLE [dbo].[RecursiveHierarchy](
	[LevelKey] [nchar](10) NOT NULL,
	[L_Value] [int] NULL,
	[R_Value] [int] NULL
) ON [PRIMARY]

GO

/*************************************************************************

Step 2: Populate tables

dbo.Hierarchy - contains the recursive Hierarchy
dbo.Values - contains the values for the Hierarchy
dbo.RecursiveHierarchy - contains the LR Values

************************************************************************/

INSERT INTO [dbo].[Hierarchy]
           ([ParentLevel]
           ,[ChildLevel])
     VALUES
			('A1','A2'),
			('A1','A3'),
			('A2','A4'),
			('A2','A5'),
			('A3','A6'),
			('B1','B2'),
			('B1','B3'),
			('B2','B4'),
			('B3','B5'),
			('B3','B6'),
			('B6','B7'),
			('B6','B8')

GO

INSERT INTO [dbo].[Values]
           ([Level]
           ,[Value])
     VALUES
			('A1','43'),
			('A2','32'),
			('A3','22'),
			('A4','10'),
			('A5','33'),
			('A6','20'),
			('B1','35'),
			('B2','21'),
			('B3','23'),
			('B4','48'),
			('B5','40'),
			('B6','14'),
			('B7','17'),
			('B8','35')

GO

INSERT INTO [dbo].[RecursiveHierarchy]

SELECT	sub.LevelKey , NULL, NULL

FROM (	SELECT DISTINCT [ParentLevel] AS LevelKey FROM [dbo].[Hierarchy]
		UNION
		SELECT DISTINCT [ChildLevel] AS LevelKey  FROM [dbo].[Hierarchy]	) as sub

GO

/*************************************************************************

Step 3: Create LR Values 

Walks up and down the Hierarchy, assigning LR Values to nodes
as it goes. Handles multiple trees within a hierarchy.

************************************************************************/

-- 3a: Declare Variables
DECLARE @TopLevel as char(2)			-- Top level Node of Tree
DECLARE @CurrentParent as char(2)		-- Current Parent Node
DECLARE @CurrentChild as char(2)		-- CurrenT Child Level Node
DECLARE @LR_Counter as integer = 1		-- L/R Value counter
DECLARE @ScanDirection as varchar(10) 	-- Direction Code is walking through the Tree

-- 3b: Identify Trees in Hierarchy for seperate processing

DECLARE TopLevels CURSOR FOR
SELECT	DISTINCT ParentLevel
FROM	dbo.Hierarchy
WHERE	ParentLevel not in (Select distinct ChildLevel from dbo.Hierarchy)

-- 3c: Handle each tree separately

OPEN TopLevels

FETCH NEXT FROM TopLevels INTO @TopLevel

WHILE @@FETCH_STATUS = 0

	BEGIN
	
		SET @ScanDirection = 'Down'
		SET @CurrentParent = @TopLevel
	
		-- Begin scan through hierarchy
		WHILE @ScanDirection <> 'Finished'
				
			BEGIN
			
				IF @ScanDirection = 'Down' 	
				
					-- Scanning downwards
					BEGIN
					
						-- Log progress
						print 'Scanning down for branches from ' + @CurrentParent					
						
						
						-- Test if L Value already set
						IF (SELECT L_Value FROM dbo.RecursiveHierarchy WHERE LevelKey = @CurrentParent) IS NULL
						
							-- L Value has not been set, this is first pass down branch
							BEGIN
							
								print 'Set L Value for ' + @CurrentParent + ' to ' + cast(@LR_Counter as varchar(20))
							
								-- Set L_Value for current parent node
								UPDATE dbo.RecursiveHierarchy SET L_Value = @LR_Counter WHERE LevelKey = @CurrentParent
								-- Increase counter
								SET @LR_Counter = @LR_Counter + 1
							
							
							END
			
						-- Clear CurrentChild variable
						SET @CurrentChild = NULL

						-- Select the first child with no L Value
						SELECT TOP 1 @CurrentChild = ChildLevel
						FROM dbo.Hierarchy
						WHERE ParentLevel = @CurrentParent
						AND ChildLevel IN (	SELECT LevelKey 
											FROM dbo.RecursiveHierarchy
											WHERE L_Value is null)
											
						IF @CurrentChild IS NULL
						
							-- End of tree has been reached
							BEGIN

								-- Log progress
								print 'End of branch at ' + @CurrentParent
								print 'Set R Value for ' + @CurrentParent + ' to ' + cast(@LR_Counter as varchar(20))

								-- Set R_Value
								UPDATE dbo.RecursiveHierarchy SET R_Value = @LR_Counter WHERE LevelKey = @CurrentParent
								-- Increase counter
								SET @LR_Counter = @LR_Counter + 1
																														
								-- Change scan direction
								SET @ScanDirection = 'Up'
							
							END
							
						ELSE
						

							--Still traversing down tree
							BEGIN

								-- Log progress
								print 'Branch found, next node down is ' + @CurrentChild							

								-- Set next child as new parent
								SET @CurrentParent = @CurrentChild								
							
							END							
					
					END
					
				ELSE
					
					-- Scanning back upwards
					BEGIN

						-- Log progress
						print 'Scanning up from node ' + @CurrentParent
						
						-- Get parent of current node
						SELECT @CurrentParent = ParentLevel
						FROM dbo.Hierarchy
						WHERE ChildLevel = @CurrentParent
			
						-- Log progress
						print 'New parent node is ' + @CurrentParent			
			
						-- Clear CurrentChild variable
						SET @CurrentChild = NULL
			
						-- Test if any more children with no L Value
						SELECT TOP 1 @CurrentChild = ChildLevel
						FROM dbo.Hierarchy
						WHERE ParentLevel = @CurrentParent
						AND ChildLevel IN (	SELECT LevelKey 
											FROM dbo.RecursiveHierarchy
											WHERE L_Value is null)
											
						IF @CurrentChild IS NULL
							
							-- No branches of tree remain
							BEGIN
															
								-- Log progress
								print 'No remaining un-numbered branches for parent ' + @CurrentParent
								print 'Set R Value for ' + @CurrentParent + ' to ' + cast(@LR_Counter as varchar(20))

								-- Set R_Value
								UPDATE dbo.RecursiveHierarchy SET R_Value = @LR_Counter WHERE LevelKey = @CurrentParent
								-- Increase counter
								SET @LR_Counter = @LR_Counter + 1
								
							
								-- Stop if top parent and no remaining children
								IF @CurrentParent = @TopLevel
								
									BEGIN
									
										SET @ScanDirection = 'Finished'
									
									END					

							END
							
						ELSE
						
							-- Children remain
							BEGIN
							
								print 'Remaining un-numbered branches for parent ' + @CurrentParent							
													
								-- Change scan direction
								SET @ScanDirection = 'Down'
								
							END
										
					
					
					
					END
			
			
			END	
	
		FETCH NEXT FROM TopLevels INTO @TopLevel
	
	END

CLOSE TopLevels
DEALLOCATE TopLevels

/*************************************************************************

Step 4: Demonstrate use of LR Values

Change the value of @Node to get the sum of different nodes

************************************************************************/

DECLARE @Node nchar(10)

SET @Node = 'A2'

SELECT	SUM([Value])
FROM	dbo.[Values] v

LEFT JOIN	dbo.RecursiveHierarchy lr
ON			v.[Level] = lr.[LevelKey]

WHERE	lr.L_Value BETWEEN
		(SELECT L_Value FROM dbo.RecursiveHierarchy WHERE LevelKey = @Node)
		AND
		(SELECT R_Value FROM dbo.RecursiveHierarchy WHERE LevelKey = @Node)