Appearance
| 1 | namespace IR.Program is | |
| 2 | use Collections.LIST | |
| 3 | use Collections.MAP | |
| 4 | ||
| 5 | /// Numbers a class tree depth first, so a class and everything derived | |
| 6 | /// from it hold one unbroken run of numbers, and a union's variants | |
| 7 | /// number consecutively. Children are numbered in the order added. | |
| 8 | class CLASS_ID_NUMBERING[T] is | |
| 9 | _roots: LIST[T] | |
| 10 | _children: MAP[T, LIST[T]] | |
| 11 | _ids: MAP[T, int] | |
| 12 | _last_descendants: MAP[T, int] | |
| 13 | ||
| 14 | init() is | |
| 15 | _roots = LIST[T]() | |
| 16 | _children = MAP[T, LIST[T]]() | |
| 17 | _ids = MAP[T, int]() | |
| 18 | _last_descendants = MAP[T, int]() | |
| 19 | si | |
| 20 | ||
| 21 | /// Adds a tree's root. | |
| 22 | add_root(node: T) is | |
| 23 | _roots.add(node) | |
| 24 | _children[node] = LIST[T]() | |
| 25 | si | |
| 26 | ||
| 27 | /// Adds `node` under `parent`, which must already have been added. | |
| 28 | add(node: T, parent: T) is | |
| 29 | _children[parent].add(node) | |
| 30 | _children[node] = LIST[T]() | |
| 31 | si | |
| 32 | ||
| 33 | /// Assigns the numbers; call after the last node is added. | |
| 34 | number() is | |
| 35 | _ids.clear() | |
| 36 | _last_descendants.clear() | |
| 37 | ||
| 38 | let next mut = 0 | |
| 39 | ||
| 40 | for root in _roots do | |
| 41 | next = _number(root, next) | |
| 42 | od | |
| 43 | si | |
| 44 | ||
| 45 | _number(node: T, first: int) -> int is | |
| 46 | _ids[node] = first | |
| 47 | ||
| 48 | let next mut = first + 1 | |
| 49 | ||
| 50 | for child in _children[node] do | |
| 51 | next = _number(child, next) | |
| 52 | od | |
| 53 | ||
| 54 | _last_descendants[node] = next - 1 | |
| 55 | ||
| 56 | return next | |
| 57 | si | |
| 58 | ||
| 59 | /// The number of `node`. | |
| 60 | id(node: T) -> int => _ids[node] | |
| 61 | ||
| 62 | /// The highest number held by `node` or anything derived from it. | |
| 63 | last_descendant(node: T) -> int => _last_descendants[node] | |
| 64 | ||
| 65 | /// Whether anything was added under `node`. | |
| 66 | has_children(node: T) -> bool => _children[node].count > 0 | |
| 67 | ||
| 68 | /// The nodes added directly under `node`, in the order added. | |
| 69 | children(node: T) -> Collections.List[T] => _children[node] | |
| 70 | ||
| 71 | /// Whether `node` is `ancestor` or derives from it. | |
| 72 | is_within(node: T, ancestor: T) -> bool is | |
| 73 | let id = _ids[node] | |
| 74 | ||
| 75 | return id >= _ids[ancestor] /\ id <= _last_descendants[ancestor] | |
| 76 | si | |
| 77 | ||
| 78 | /// Every node, parents before their children, in number order. | |
| 79 | in_order() -> Collections.List[T] is | |
| 80 | let result = LIST[T]() | |
| 81 | ||
| 82 | for root in _roots do | |
| 83 | _collect(root, result) | |
| 84 | od | |
| 85 | ||
| 86 | return result | |
| 87 | si | |
| 88 | ||
| 89 | _collect(node: T, into: LIST[T]) is | |
| 90 | into.add(node) | |
| 91 | ||
| 92 | for child in _children[node] do | |
| 93 | _collect(child, into) | |
| 94 | od | |
| 95 | si | |
| 96 | si | |
| 97 | si |