Answer to Brent's Puzzle

gistfile1.txt

use tempdb;

DROP TABLE IF EXISTS dbo.Stations;
CREATE TABLE dbo.Stations
	(StationId INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
	 StationName VARCHAR(50),
	 StationPhysicalOrder INT);

INSERT INTO dbo.Stations (StationName, StationPhysicalOrder)
	SELECT CHAR(64 + n), n
	FROM (VALUES
		(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),
		(12),(13),(14),(15),(16),(17),(18),(19)
	) AS Numbers(n);

DROP TABLE IF EXISTS dbo.StationRoutingOverride;
CREATE TABLE dbo.StationRoutingOverride
	(StationRoutingOverrideId INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
	 StationFromName VARCHAR(50),
	 StationToName VARCHAR(50));

INSERT INTO dbo.StationRoutingOverride (StationFromName, StationToName)
	VALUES ('E', 'S'), ('B', 'I'), ('I', 'D');
GO

DROP FUNCTION IF EXISTS dbo.GetNextStationPhysicalOrder;
GO

CREATE FUNCTION dbo.GetNextStationPhysicalOrder
(
	@CurrentStationPhysicalOrder int
)
RETURNS INT
AS
BEGIN
	RETURN (
		SELECT TOP (1) StationPhysicalOrder
		FROM 
		(
			-- next one naturally
			SELECT TOP (1)
				StationPhysicalOrder,
				CAST(1 as bit) as IsNaturalNext
			FROM dbo.Stations
			WHERE StationPhysicalOrder > @CurrentStationPhysicalOrder
			ORDER BY StationPhysicalOrder ASC

			UNION ALL

			-- next one following override
			SELECT 
				NextStation.StationPhysicalOrder, 
				CAST(0 as bit) as IsNaturalNext
			FROM 
				dbo.Stations CurrentStation
			INNER JOIN 
				dbo.StationRoutingOverride O
				ON O.StationFromName = CurrentStation.StationName
			INNER JOIN 
				dbo.Stations NextStation
				ON NextStation.StationName = O.StationToName
			WHERE  
				CurrentStation.StationPhysicalOrder = @CurrentStationPhysicalOrder
		) NextStation
		ORDER BY IsNaturalNext ASC /* prefer override --> NaturalNext == 0 */ 
	);
END
GO

WITH CTE AS
(
	SELECT TOP (1) 
		StationId,
		StationName,
		StationPhysicalOrder, 
		1 as OutputOrder
	FROM dbo.Stations
	ORDER BY StationPhysicalOrder ASC

	UNION ALL

	SELECT 
		S.StationId, 
		S.StationName,
		S.StationPhysicalOrder, 
		C.OutputOrder + 1
	FROM CTE C
	INNER JOIN 
		dbo.Stations S
		ON S.StationPhysicalOrder = dbo.GetNextStationPhysicalOrder(C.StationPhysicalOrder)
)
SELECT 
	StationId,
	StationName,
	StationPhysicalOrder
FROM 
	CTE
ORDER BY 
	OutputOrder ASC


/* 
StationId   StationName                                        StationPhysicalOrder
----------- -------------------------------------------------- --------------------
1           A                                                  1
2           B                                                  2
9           I                                                  9
4           D                                                  4
5           E                                                  5
19          S                                                  19

(6 rows affected)
*/