need code snippet for copying tree node

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2000 Forums

Transact-SQL (2000)

need code snippet for copying tree node

Author

Topic

gdeconto
Posting Yak Master

107 Posts

Posted - 2004-08-18 : 13:57:03

I have seen many tree/hierarchy related articles on this site (and other sites) regarding creating, updating, traversing, etc. They have been of great use and I use the information in maintaining a number of tree structures that I work with in mssql

however, I have not seen any examples of copying a node (and its subnodes).

does anyone have a code snippet I can use as a starting point? assuming the table has an ID field, a parentID field and one or more data fields.

have been looking at this and do not see a simple (and fast) way to do this.

any help/advice appreciated.

p.s. not being lazy here; problem just does not lend itself to simple solution via my [very] gray matter.

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-08-18 : 15:52:30

What do you mean by 'copy a node'. In the tree structures I have built, I use a relationships table to relate nodes. So to make a copy of one, I suppose all I would do is create a new node and generate a copy of all of the relationships that the orig node was part of substuting in the new nodeid. Make sense?

Corey

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2004-08-18 : 16:01:49

Nested set models better lend themselves to these types of tasks. They are more complex to work with but are strucutred to allow fast operations (Ins,Upd,Del,Copy and Paste) and can typically be performed as set-based operation rather than procedural (loops). Joe Celko has done some writing on this topic which can be found here and on other sites.

gdeconto
Posting Yak Master

107 Posts

Posted - 2004-08-18 : 16:02:50

so do I.

NOTE that when I say "copy a node", I am working with a table that an ID field (an auto-incrementing int Identity field) and parentID field (int values) and one or more data fields

so the problem is in maintaining the node relationships in the cloned node as you perform the copy so that the cloned subnodes point to their respective cloned parent node

for example, say I have the following tree in a table:

id parentid data
1 0 A
2 1 A1
3 1 A2
4 3 A1A
5 4 A1A1

if I create a copy and set the parentid of the copy to 0 then I should end up with something like:

id parentid data
1 0 A
2 1 A1
3 1 A2
4 3 A1A
5 4 A1A1
6 0 A
7 6 A1
8 6 A2
9 8 A1A
10 9 A1A1

this is an overly simple example,of course, for what can be a very complex tree but you get the idea.

note that the depth of the hierarchy is unknown so this makes it a bit more complex.

also note: I am part way thru creating something to do this but the code is pretty convoluted and was hoping someone would have come up with a simple way to do this.

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-08-18 : 16:15:53

That shouldn't be too hard if you look at it from the path standpoint.

Consider the following tree
...
000;001;004
000;001;004;008
000;001;005
000;001;005;006
000;001;005;007
...

Lets say we want to copy the tree from node 000;001

Using the paths we can Identify all of the nodes we need to copy (anything below 000;001)
4,5,6,7, and 8

So we create new nodes and keep track of what they correlate to. Lastly, copy all of the relationship records that pertain to 4,5,6,7, and 8.

That simple?

Corey

gdeconto
Posting Yak Master

107 Posts

Posted - 2004-08-18 : 16:24:43

ummm...not really. you lost me, as dont see how this simplifies the issue of maintaining the node relationships when the ID field is an Identity field.

at any rate, here is what I have come up with (seems to work but just finished typing so cant verify that it is any good):

CREATE PROCEDURE putNodeClone @fromnodeid int, @tonodeid int, @clonesubnodes bit
AS

SET NOCOUNT ON
SET XACT_ABORT ON

DECLARE @fromid int, @newnodeid int, @newparentid int, @parentid int

SET @fromid = @fromnodeid
SET @newparentid = @tonodeid

SELECT @parentid = parentid
FROM tnodes
WHERE nodeid = @fromid

-- create working table of node(s) to be copied for later use
-- note that fNodeHierarchy is a function that returns the tree structure as of a given node
-- (ie the complete subtree of the specified node)
SELECT nodeid, parentid, cast(0 as int) as newnodeid, cast(0 as int) as newparentid
INTO #t1
FROM fNodeHierarchy(@fromid)

-- make sure to include FROM node in working table
INSERT #t1
(nodeid, parentid, newnodeid, newparentid)
VALUES
(@fromid, @parentid, 0, 0)

-- clone the FROM node
INSERT tnodes
(parentid, mydata)
SELECT
@newparentid,
mydata
FROM tnodes
WHERE nodeid = @fromid

SET @newnodeid = @@identity

-- update working copy
UPDATE #t1
SET newnodeid = @newnodeid, newparentid = @newparentid
WHERE nodeid = @fromid

-- clone any FROM subnodes
IF @clonesubnodes = 1
BEGIN
DECLARE mycursor CURSOR FOR
SELECT nodeid, parentid FROM #t1
WHERE nodeid <> @fromnodeid

OPEN mycursor

FETCH NEXT FROM mycursor
INTO @fromid, @parentid
WHILE @@FETCH_STATUS = 0
BEGIN
SELECT @newparentid = newnodeid
FROM #t1
WHERE nodeid = @parentid

INSERT tnodes
(parentid, mydata)
SELECT
@newparentid,
mydata
FROM tnodes
WHERE nodeid = @fromid

SET @newnodeid = @@identity

-- update working copy
UPDATE #t1
SET newnodeid = @newnodeid, newparentid = @newparentid
WHERE nodeid = @fromid

FETCH NEXT FROM mycursor
INTO @fromid, @parentid
END

CLOSE mycursor
DEALLOCATE mycursor
END
GO

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2004-08-18 : 16:48:01

Ok here is my copy using my article (http://www.seventhnight.com/treestructs.asp).


/********************************
            00
          / |          01  02  03
      /  |  |  / |
    04  05  06   07
   /  \     |    |   08  09    10  11  12
********************************/
Declare @nodes table (NodeId int identity(1,1), node varchar(100), tag int)
Insert Into @nodes Values('Node1',null)
Insert Into @nodes Values('Node2',null)
Insert Into @nodes Values('Node3',null)
Insert Into @nodes Values('Node4',null)
Insert Into @nodes Values('Node5',null)
Insert Into @nodes Values('Node6',null)
Insert Into @nodes Values('Node7',null)
Insert Into @nodes Values('Node8',null)
Insert Into @nodes Values('Node9',null)
Insert Into @nodes Values('Node10',null)
Insert Into @nodes Values('Node11',null)
Insert Into @nodes Values('Node12',null)


Declare @tree table (pNodeId int, cNodeId int, processed bit default(0))
Insert Into @tree (pNodeId, cNodeId) Values (0,1)
Insert Into @tree (pNodeId, cNodeId) Values (0,2)
Insert Into @tree (pNodeId, cNodeId) Values (0,3)
Insert Into @tree (pNodeId, cNodeId) Values (1,4)
Insert Into @tree (pNodeId, cNodeId) Values (1,5)
Insert Into @tree (pNodeId, cNodeId) Values (2,6)
Insert Into @tree (pNodeId, cNodeId) Values (3,6)
Insert Into @tree (pNodeId, cNodeId) Values (3,7)
Insert Into @tree (pNodeId, cNodeId) Values (4,8)
Insert Into @tree (pNodeId, cNodeId) Values (4,9)
Insert Into @tree (pNodeId, cNodeId) Values (6,10)
Insert Into @tree (pNodeId, cNodeId) Values (7,11)
Insert Into @tree (pNodeId, cNodeId) Values (7,12)

Declare @pad nvarchar(100),
	@lastCnt int
Set @Pad = '0000'

/*********************
Begin Build Path section
*********************/
Declare @paths table (path nvarchar(1000), pNodeId int, cNodeId int)

Insert Into @paths
Select 
	path=right(@pad + convert(nvarchar,pNodeId),len(@pad))+';' + right(@pad + convert(nvarchar,cNodeId),len(@pad))+';',
	pNodeId,
	cNodeId
From @Tree where pNodeId=0

Update A
Set Processed = 1
From @Tree as A
Inner Join @paths as B
On A.pNodeId = B.pNodeId
and A.cNodeId = B.cNodeId

While exists(Select * From @tree Where Processed = 0)
Begin
	Insert Into @paths
	Select 
		path=path + case when B.cNodeId is not null then right(@pad + convert(nvarchar,B.cNodeId),len(@pad))+';' else '' end,
		B.pNodeId,
		B.cNodeId
	From @Paths as A
	Left Join @Tree as B
	On A.cNodeId = B.pNodeId
	Where B.Processed = 0

	Update A
	Set Processed = 1
	From @Tree as A
	Inner Join @paths as B
	On A.pNodeId = B.pNodeId
	and A.cNodeId = B.cNodeId
	Where A.Processed = 0
End
/*********************
End Build Path section
*********************/
Select * From @Paths Order By path


/*********************
Begin Copy Node section
*********************/
Declare @nodeId int
Set @nodeId = 3 -- nodeid to copy from

Insert Into @nodes
Select Z.Node, Tag = Z.NodeId
From @nodes as Z
Inner Join
	(
	Select distinct A.cNodeId
	from @paths as A
	Inner Join @paths as B
	On A.Path like B.Path + '%'
	Where B.cNodeId = @nodeId
	) as Y
On Z.nodeId = y.cNodeId

Insert Into @tree
Select 
	pNodeId = isnull((select nodeId From @nodes where tag = A.pNodeId),pNodeId),
	cNodeId = isnull((select nodeId From @nodes where tag = A.cNodeId),pNodeId),
	processed = 0
From @tree as A
Where
A.cNodeId in (Select tag From @nodes Where tag is not null)
or A.pNodeId in (Select tag From @nodes Where tag is not null)

Update @nodes Set tag = null
/*********************
End Copy Node section
*********************/


/*********************
Begin Re-Build Path section
*********************/

Update @tree Set processed = 0
Delete From @paths

Insert Into @paths
Select 
	path=right(@pad + convert(nvarchar,pNodeId),len(@pad))+';' + right(@pad + convert(nvarchar,cNodeId),len(@pad))+';',
	pNodeId,
	cNodeId
From @Tree where pNodeId=0

Update A
Set Processed = 1
From @Tree as A
Inner Join @paths as B
On A.pNodeId = B.pNodeId
and A.cNodeId = B.cNodeId

While exists(Select * From @tree Where Processed = 0)
Begin
	Insert Into @paths
	Select 
		path=path + case when B.cNodeId is not null then right(@pad + convert(nvarchar,B.cNodeId),len(@pad))+';' else '' end,
		B.pNodeId,
		B.cNodeId
	From @Paths as A
	Left Join @Tree as B
	On A.cNodeId = B.pNodeId
	Where B.Processed = 0

	Update A
	Set Processed = 1
	From @Tree as A
	Inner Join @paths as B
	On A.pNodeId = B.pNodeId
	and A.cNodeId = B.cNodeId
	Where A.Processed = 0
End
/*********************
End Re-Build Path section
*********************/

Select * From @Paths Order By path

Corey

gdeconto
Posting Yak Master

107 Posts

Posted - 2004-08-18 : 17:02:43

thx, Corey.

cool, think I understand what you were talking about.

thx to all who responded.

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources