Tree-like Document Builder for Typst

README.md

Tree-like Document Builder for Typst

This is a show rule for building tree-like documents in Typst. The initial version was developed by @hongjr03, and I have refined the code, adding #end-sect and numbering-related features.

Although I've made efforts to extract customizable options from the huge build-tree function, I still think the code is too tightly coupled to be suitable for release as a public package.

Features

• Tree-like Document Structure The original structure of Typst documents is linear, meaning headings and other content are arranged sequentially. This makes it challenging to customize styles (like section indentation) and add summaries after subsections. With #show: build-tree(func: xxx), you can easily construct a tree-like document structure and use #end-sect to return to the parent "node".

• Section-Prefixed Numbering Numbers for math.equation and figure (by default, customizable through build-tree parameters) will be prefixed with heading numbers. This feature works consistently, even behind the last subsections of sections.

Usage Notes

• It is recommended to place #show: build-tree(func: xxx) after other show and set statements, particularly those that wrap the entire document in a style or other structures that build-tree cannot interpret.

• The maximum supported tree depth is approximately 30 due to typst's maximum show rule depth limitation. If you really need more depth, you can either wait for typst to support customizing this limitation or use a modified version of typst.

• If you encounter any issues while using this tool, please feel free to report bugs.

Example

Click to expand

The example content is generated by LLM.

example.typ

#import "tree.typ": build-tree, end-sect

#set heading(numbering: "1.1")
#set par(justify: true)

#show: build-tree.with(
  func: (level: 0, heading: none, body) => {
    if (level == 0) {
      return body
    }
    heading
    let fill = black.transparentize((1 - calc.pow(1.3, -level)) * 100%)
    block(
      stroke: (left: 0.5pt + fill),
      inset: (left: 1em, bottom: 0.5em),
      outset: (left: -0.3em),
      body,
    )
  },
)

= Search Algorithms and Data Structures

== Sequential Search Structures
Search algorithms form the backbone of data retrieval, with time complexity varying based on the algorithm design. For a sequence of length n, the efficiency can range from linear to logarithmic time:

$
  T_"linear" (n) = c dot n "for some constant" c > 0 \
  T_"binary" (n) = c dot log_2 (n) "for some constant" c > 0
$

=== Linear Search
Linear search represents the most basic form of search algorithms, operating on unordered sequences. The algorithm examines each element sequentially until the target is found or the sequence is exhausted, resulting in a time complexity of $O(n)$ for a sequence of length $n$.

=== Binary Search
Binary search operates on ordered sequences by repeatedly dividing the search interval in half. For a sequence of length $n$, the algorithm achieves a time complexity of $O(log n)$ through the following recurrence relation:

$ T(n) = T(n / 2) + O(1) $

#end-sect

The efficiency gain of binary search over linear search becomes evident as the sequence size grows, demonstrated by the relationship:

$ O(log n) << O(n) "for large" n $

== Tree-Based Search Structures

=== Binary Search Trees
Binary Search Trees (BSTs) maintain a hierarchical ordering where for any node, all elements in the left subtree are smaller and all elements in the right subtree are larger. The search operation traverses a path from root to target, with average-case time complexity governed by:

$ T_"avg"(n) = O(log n) $

=== AVL Trees
AVL trees enhance BSTs by maintaining balance through rotation operations. The height-balance property ensures that for any node, the heights of its left and right subtrees differ by at most one:

$ abs(h_"left"(v) - h_"right"(v)) <= 1 $

This balance condition guarantees logarithmic time complexity for all operations.

#end-sect

The relationship between tree height and node count in AVL trees satisfies:

$ h <= 1.44 log_2(n + 2) - 1.328 $

== Hash-Based Search Structures

=== Direct Addressing
Direct addressing provides constant-time operations by using array indices as keys. The space complexity directly relates to the key range:

$ S(n) = O(max("key") - min("key")) $

=== Hash Tables
Hash tables overcome the space limitations of direct addressing through hash functions that map keys to array indices. The expected time for operations under simple uniform hashing is:

$ T_"expected"(n) = O(1 + alpha) $

where $alpha = n/m$ is the load factor, $n$ is the number of elements, and $m$ is the table size.

#end-sect

The probability of collision in a hash table follows the birthday problem approximation:

$ P("collision") approx 1 - e^(-n^2 / (2m)) $

tree.typ

#let end-sect = metadata("_tree_end_sect")

#let build-tree(
  body,
  func: none,
  counters: (
    math.equation,
    figure.where(kind: image),
    figure.where(kind: table),
    figure.where(kind: raw),
  ),
  numberings: (
    (math.equation, "(1.1)"),
    (figure, "1.1"),
  ),
) = {
  let stack = ()
  let nodes = ()

  // fold a node into stack or nodes
  let fold(stack, nodes, node) = {
    if stack.len() > 0 {
      stack.last().children.push(node)
    } else {
      nodes.push(node)
    }
    (stack, nodes)
  }

  // traverse body(supposed to be a sequnce) and build tree
  for c in body.children {
    if c.func() == heading {
      while stack.len() > 0 and stack.last().heading.depth >= c.depth {
        let node = stack.pop()
        (stack, nodes) = fold(stack, nodes, node)
      }

      stack.push((
        heading: c,
        children: (),
      ))
    } else if c.func() == metadata and c.value == end-sect.value {
      let node = stack.pop()
      (stack, nodes) = fold(stack, nodes, node)
    } else {
      (stack, nodes) = fold(stack, nodes, c)
    }
  }

  // process remaining nodes in stack
  while stack.len() > 0 {
    let node = stack.pop()
    (stack, nodes) = fold(stack, nodes, node)
  }

  // merge continuous content to reduce show-rule depth consumed
  let func-seq = [].func()
  let merge-contents(nodes) = {
    let result = ()
    let current-contents = ()

    for node in nodes {
      if type(node) == dictionary {
        if current-contents.len() > 0 {
          result.push(func-seq(current-contents))
          current-contents = ()
        }
        node.children = merge-contents(node.children)
        result.push(node)
      } else {
        current-contents.push(node)
      }
    }
    if current-contents.len() > 0 {
      result.push(func-seq(current-contents))
    }
    result
  }
  nodes = merge-contents(nodes)

  // convert the tree to content with given func
  let display-func(node, level: 0, wrapping-func: func) = {
    let body = context {
      // store and restore counter values for counters "interrupted" by subsections
      let f(counter-ckpt, children) = {
        // base case
        if children.len() == 0 {
          return
        }
        // process children one by one
        let c = children.first()
        let others = children.slice(1)
        // content -> store counter value after displayed
        if type(c) == content {
          c
          context f(counters.map(x => counter(x)).map(x => x.get().first()), others)
        } // dict(subsection) -> restore counter value after displayed
        else if type(c) == dictionary {
          counters.map(x => counter(x).update(0)).join()
          display-func(level: level + 1, wrapping-func: wrapping-func, c)
          counters.zip(counter-ckpt).map(x => counter(x.first()).update(x.last())).join()
          f(counter-ckpt, others)
        } else {
          panic("unexpected node in document tree")
        }
      }
      // all counters begin with 0
      f((0,) * counters.len(), node.children)
    }

    // call given wrapping-func to finally create contents
    wrapping-func(
      level: level,
      heading: node.heading,
      context {
        // get heading counter state
        let h-count = if node.heading == none {
          ()
        } else {
          counter(heading).get()
        }

        // util func for build heading-prefixed numbering
        let f-numbering(numbering: "1.1", x) = {
          std.numbering(numbering, ..h-count + (x,))
        }

        // set numberings
        show: x => numberings.fold(
          x,
          (it, config) => {
            let f = config.first()
            set f(numbering: f-numbering.with(numbering: config.last()))
            it
          },
        )
        body
      },
    )
  }
  display-func(
    wrapping-func: func,
    level: 0,
    (
      heading: none,
      children: nodes,
    ),
  )
}