Skip to content

Instantly share code, notes, and snippets.

@rgchris
Last active May 5, 2025 14:13
Show Gist options
  • Save rgchris/fb1e87a7ffd785560455cbf42f625eff to your computer and use it in GitHub Desktop.
Save rgchris/fb1e87a7ffd785560455cbf42f625eff to your computer and use it in GitHub Desktop.
Tree iterator

Tree-Walking Iterator

This script features an iterated method of traversing a tree-structure (specifically, a tree created by the Rebol 2 mezzanine PARSE-XML). The iterator returns events—OPEN, CLOSE, EMPTY, and TEXT—upon request until the tree has been fully traversed.

Concept Note

Using an iterated approach to tree traversal allows for fine control of the process that can be dropped and picked up fairly intuitively, effectively reducing the traversal process to a linear stream of events useful for serialization or extraction. This stands in contrast to the callback approach that fully traverses a tree firing callback functions until the tree has been fully traversed.

Rebol [
Title: "Walker"
Author: "Christopher Ross-Gill"
Date: 22-Apr-2025
Home: https://gist.github.com/rgchris/fb1e87a7ffd785560455cbf42f625eff
File: %walker.r
Version: 0.1.0
Rights: http://opensource.org/licenses/Apache-2.0
Purpose: {
Walk a markup tree structure
}
Type: module
Name: rgchris.walker
]
_: none
walker: context [
prototype: [
node: _
kids: _
path: _
event: _
next: func [] [
event: case [
none? kids [
_
]
; initial state
;
empty? kids [
insert/only path node
insert/only kids any [
node/3 []
]
'open
]
tail? kids/1 [
remove kids
node: take path
; all nodes processed
;
if empty? kids [
kids: _
]
'close
]
(
kids/1: skip kids/1 1
string? node: first back kids/1
) [
'text
]
block? node/3 [
insert/only path node
insert/only kids node/3
'open
]
<else> [
'empty
]
]
]
close: func [] [
kids/1: tail kids/1
]
]
new: func [
node [block! map!]
/local new
][
new: make object! prototype
new/node: node
new/path: make block! 16
new/kids: make block! 16
new
]
text-of: func [
walker [object!]
/local event
][
head collect/into [
while [
walker/next
][
if walker/event == 'text [
keep walker/node
]
]
] make string! 128
]
path-of: func [
walker [object!]
][
walker/path: tail walker/path
collect [
while [
not head? walker/path
][
walker/path: back walker/path
keep walker/path/1/1
]
if not find/only/match walker/path walker/node [
keep walker/node/1
]
]
]
]
Rebol [
Title: "Walker Test"
Date: 22-Apr-2025
]
*walk: walker/new parse-xml "<a><b/><c/><d><e/></d>f</a>"
; Rebol 2 mezzanine function PARSE-XML
assert [
equal?
[<document> <a> <b/> <c/> <d> </d> "F" </a> </document>]
collect [
while [
*walk/next
][
switch *walk/event [
open [
keep to tag! *walk/node/1
if *walk/node/1 == "d" [
*walk/close
; skip contents of <d>
]
]
empty [
keep to tag! join *walk/node/1 #"/"
]
text [
keep uppercase copy *walk/node
]
close [
keep to tag! join #"/" *walk/node/1
]
]
]
]
]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment