| 15 | 15 | # - "Record id is invalid or out of order." - when IDs are non-continuous or root is missing |
| 16 | 16 | # - "Node parent_id should be smaller than it's record_id." - when parent_id >= record_id (except root) |
| 17 | 17 | # - "Only root should have equal record and parent id." - when non-root has record_id == parent_id |
| 18 | | root = None |
| 18 | |
| 19 | if not records: |
| 20 | return None |
| 21 | |
| 22 | # Sort records by ID for validation |
| 19 | 23 | records.sort(key=lambda x: x.record_id) |
| 20 | | ordered_id = [i.record_id for i in records] |
| 21 | | if records: |
| 22 | | if ordered_id[-1] != len(ordered_id) - 1: |
| 24 | |
| 25 | # Validate record IDs are continuous and start from 0 |
| 26 | for i, record in enumerate(records): |
| 27 | if record.record_id != i: |
| 23 | 28 | raise ValueError('Record id is invalid or out of order.') |
| 24 | | if ordered_id[0] != 0: |
| 25 | | raise ValueError('Record id is invalid or out of order.') |
| 26 | | trees = [] |
| 27 | | parent = {} |
| 28 | | for i in range(len(ordered_id)): |
| 29 | | for j in records: |
| 30 | | if ordered_id[i] == j.record_id: |
| 31 | | if j.record_id == 0: |
| 32 | | if j.parent_id != 0: |
| 33 | | raise ValueError("Node parent_id should be smaller than it's record_id.") |
| 34 | | if j.record_id < j.parent_id: |
| 35 | | raise ValueError("Node parent_id should be smaller than it's record_id.") |
| 36 | | if j.record_id == j.parent_id: |
| 37 | | if j.record_id != 0: |
| 38 | | raise ValueError('Only root should have equal record and parent id.') |
| 39 | | trees.append(Node(ordered_id[i])) |
| 40 | | for i in range(len(ordered_id)): |
| 41 | | for j in trees: |
| 42 | | if i == j.node_id: |
| 43 | | parent = j |
| 44 | | for j in records: |
| 45 | | if j.parent_id == i: |
| 46 | | for k in trees: |
| 47 | | if k.node_id == 0: |
| 48 | | continue |
| 49 | | if j.record_id == k.node_id: |
| 50 | | child = k |
| 51 | | parent.children.append(child) |
| 52 | | if len(trees) > 0: |
| 53 | | root = trees[0] |
| 54 | | return root |
| 29 | |
| 30 | # Create nodes for all records |
| 31 | nodes = {i: Node(i) for i in range(len(records))} |
| 32 | |
| 33 | # Validate parent-child relationships and build tree |
| 34 | for record in records: |
| 35 | record_id = record.record_id |
| 36 | parent_id = record.parent_id |
| 37 | |
| 38 | # Root validation |
| 39 | if record_id == 0: |
| 40 | if parent_id != 0: |
| 41 | raise ValueError("Node parent_id should be smaller than it's record_id.") |
| 42 | else: |
| 43 | # Non-root validations |
| 44 | if parent_id == record_id: |
| 45 | raise ValueError('Only root should have equal record and parent id.') |
| 46 | if parent_id >= record_id: |
| 47 | raise ValueError("Node parent_id should be smaller than it's record_id.") |
| 48 | |
| 49 | # Add child to parent (skip root self-reference) |
| 50 | if record_id != 0: |
| 51 | nodes[parent_id].children.append(nodes[record_id]) |
| 52 | |
| 53 | return nodes[0] |