hierarchy_traversal.bend
bendvy-ecs-core@0.1.0.0 · 59 lines · 0 definitions
1import Base
2import entity_key.bend as K
3import bendvy-ecs-core@0.1.0.0/relation_types.bend as G
4import bendvy-ecs-core@0.1.0.0/relation_graph.bend as Graph
5
6# Raw graph helpers are trusted setup, not gameplay authority. Valid hierarchy
7# edges have one parent per source and no cycle; traversal uses E+1 small fuel.
8# Unsupported forged cyclic graph traversal remains an incomplete diagnostic.
9type Order is Data:
10 Depth{}
11 Breadth{}
12type Walk is Data:
13 Complete{ids:List<&2,K.Key>}
14 Incomplete{ids:List<&2,K.Key>,pending:List<&2,K.Key>}
15def budget(~S:Data,graph:G.Graph<S>) -> Nat:
16 match graph:
17 case G.Graph{edges,_}: 1n+List.length(&2,G.Edge<S>,edges)
18def finished(acc:List<&2,K.Key>,pending:List<&2,K.Key>) -> Walk:
19 match pending:
20 case []: Complete{List.reverse(&2,K.Key,acc)}
21 case pending: Incomplete{List.reverse(&2,K.Key,acc),pending}
22def enqueue(order:Order,children:List<&2,K.Key>,rest:List<&2,K.Key>) -> List<&2,K.Key>:
23 match order:
24 case Depth{}: List.append(&2,K.Key,children,rest)
25 case Breadth{}: List.append(&2,K.Key,rest,children)
26def next_desc(~S:Data,graph:G.Graph<S>,descriptor:G.Descriptor<S>,order:Order,state:List<&2,K.Key> & List<&2,K.Key>) -> List<&2,K.Key> & List<&2,K.Key>:
27 match state:
28 case ([],acc): ([],acc)
29 case (+id <> rest,acc): (enqueue(order,Graph.inverse(~S,graph,descriptor,id),rest),id <> acc)
30def descendants_loop(~S:Data,n:Nat,state:List<&2,K.Key> & List<&2,K.Key>,+graph:G.Graph<S>,+descriptor:G.Descriptor<S>,+order:Order) -> Walk:
31 match n state:
32 case 0n Tuple{pending,acc}: finished(acc,pending)
33 case 1n+rest Tuple{[],acc}: Complete{List.reverse(&2,K.Key,acc)}
34 case 1n+rest state: descendants_loop(~S,rest,next_desc(~S,graph,descriptor,order,state),graph,descriptor,order)
35def descendants(~S:Data,+graph:G.Graph<S>,+descriptor:G.Descriptor<S>,target:K.Key,order:Order) -> Walk:
36 descendants_loop(~S,budget(~S,graph),(Graph.inverse(~S,graph,descriptor,target),[]),graph,descriptor,order)
37def next_ancestor(~S:Data,graph:G.Graph<S>,descriptor:G.Descriptor<S>,state:Maybe<&2,K.Key> & List<&2,K.Key>) -> Maybe<&2,K.Key> & List<&2,K.Key>:
38 match state:
39 case (None{},acc): (None{},acc)
40 case (Some{+id},acc): (Graph.target(~S,graph,descriptor,id),id <> acc)
41def ancestor_finished(state:Maybe<&2,K.Key> & List<&2,K.Key>) -> Walk:
42 match state:
43 case (None{},acc): Complete{List.reverse(&2,K.Key,acc)}
44 case (Some{id},acc): Incomplete{List.reverse(&2,K.Key,acc),[id]}
45def ancestors_loop(~S:Data,n:Nat,state:Maybe<&2,K.Key> & List<&2,K.Key>,+graph:G.Graph<S>,+descriptor:G.Descriptor<S>) -> Walk:
46 match n state:
47 case 0n state: ancestor_finished(state)
48 case 1n+rest Tuple{None{},acc}: Complete{List.reverse(&2,K.Key,acc)}
49 case 1n+rest state: ancestors_loop(~S,rest,next_ancestor(~S,graph,descriptor,state),graph,descriptor)
50def ancestors(~S:Data,+graph:G.Graph<S>,+descriptor:G.Descriptor<S>,target:K.Key) -> Walk:
51 ancestors_loop(~S,budget(~S,graph),(Graph.target(~S,graph,descriptor,target),[]),graph,descriptor)
52def root_ids(ids:List<&2,K.Key>,current:K.Key) -> K.Key:
53 match ids:
54 case []: current
55 case id <> rest: root_ids(rest,id)
56def root(walk:Walk,target:K.Key) -> Maybe<&2,K.Key>:
57 match walk:
58 case Complete{ids}: Some{root_ids(ids,target)}
59 case _: None{}