check-graph(node w, graph T)
1: | L ← leaves(T) |
| 2: | L′ empty list |
| 3: | while L non-empty do |
| 4: | q ← dequeue L |
| 5: | skip q if `visited' |
| 6: | case check-node(w, q): |
| non-overlap⇒ add q to L′ | |
| places ⇒ q ← queue L′ if q still leaf | |
| extension ⇒ place here — w ← queue L′ | |
| tag extension-ancestors(w) as `visited' | |
| clash ⇒ check-graph(inclusion-graph (q)) | |
| if not placed then | |
| extension-parents(q) ← queue L | |
| q ← queue L′ | |
| 7: | leaves(T) ← L′ |
| 8: | if w placed then |
| 9: | return `placed' |