Simon
Simon

Reputation: 2115

order records by depth AND sibling order

I have a tree structure I want to order. Vertically and horizontally.

From SQLite doc I got the ordering by depth :

WITH RECURSIVE
  under_alice(name,level) AS (
    VALUES('Alice',0)
    UNION ALL
    SELECT org.name, under_alice.level+1
      FROM org JOIN under_alice ON org.boss=under_alice.name
     ORDER BY 2 DESC
  )
SELECT substr('..........',1,level*3) || name FROM under_alice;

Which gives:

Alice
...Bob
......Dave
......Emma
...Cindy
......Fred
......Gail

In that request the ordering is only on the level. So the order of siblings (Bob & Cindy, Dave & Emma, Fred & Gail) is not constrained (ie it is insert order).

But I also need to order siblings. So I think about a sibling column with the id of the next sibling (like in a linked list).

The table would be table org (name text, boss name, sibling name)

The data :

'Alice', null, null
'Cindy', 'Alice', 'Bob'
'Bob', 'Alice', null
'Dave', 'Bob', 'Emma'
'Emma', 'Bob', null
'Gail', 'Cindy', 'Fred'
'Fred', 'Cindy', null

And the result would then be:

Alice
...Cindy
......Gail
......Fred
...Bob
......Dave
......Emma

How can I integrate that into the recursive request ?

Upvotes: 2

Views: 172

Answers (1)

CL.
CL.

Reputation: 180310

To convert the sibling specification into a format usable for ORDER BY, use another recursive CTE to count the siblings under the same boss. Because there is nothing that identifies the first sibling, the search is easier backwards:

WITH RECURSIVE OrderedOrg(Name, Boss, SiblingOrder) AS (
  SELECT Name, Boss, 0
  FROM org
  WHERE Sibling IS NULL

  UNION ALL

  SELECT org.Name, org.Boss, OrderedOrg.SiblingOrder + 1
  FROM org
  JOIN OrderedOrg ON org.Boss    = OrderedOrg.Boss
                 AND org.Sibling = OrderedOrg.Name
),
under_alice(...) AS (
  ...
  SELECT ...
  FROM ... OrderedOrg ...
  ...
  ORDER BY level DESC, SiblingOrder DESC
)
SELECT ...

Upvotes: 1

Related Questions