/// Folds a flat list into a tree.
final class TreeFolder {
  private enum NestableKind { case unordered, ordered, quote }

  private let blocks: [NorgBlock]
  private var index = 0
  private var strongReset = false

  init(_ blocks: [NorgBlock]) {
    self.blocks = blocks
  }

  func fold() -> [NorgNode] {
    foldStructural(level: 0)
  }

  /// Folds structural items, that can have any block under them.
  private func foldStructural(level: Int) -> [NorgNode] {
    var nodes: [NorgNode] = []
    while index < blocks.count {
      let block = blocks[index]
      switch block {
      case .heading(let headingLevel, _, _, _):

        // A heading of the same or higher level belongs to an ancestor;
        // leave it for the caller.
        if headingLevel <= level { return nodes }
        index += 1
        let children = foldStructural(level: headingLevel)
        nodes.append(NorgNode(block: block, children: children))
        if strongReset {
          if level == 0 { strongReset = false } else { return nodes }
        }

      case .unorderedListItem(let itemLevel, _, _, _):
        nodes.append(foldNestableItem(block, kind: .unordered, level: itemLevel))
      case .orderedListItem(let itemLevel, _, _, _):
        nodes.append(foldNestableItem(block, kind: .ordered, level: itemLevel))
      case .quote(let itemLevel, _, _, _):
        nodes.append(foldNestableItem(block, kind: .quote, level: itemLevel))

      case .weakDelimiter:
        index += 1
        if level > 0 { return nodes }

      case .strongDelimiter:
        index += 1
        if level > 0 {
          strongReset = true
          return nodes
        }

      default:
        index += 1
        nodes.append(NorgNode(block: block, children: []))
      }
    }
    return nodes
  }

  /// Folds nestable items that can only consume more of their kind.
  private func foldNestableItem(_ block: NorgBlock, kind: NestableKind, level: Int) -> NorgNode {
    index += 1
    var children: [NorgNode] = []
    while index < blocks.count, let child = nestableDescriptor(blocks[index]),
      child.kind == kind, child.level > level {
      children.append(foldNestableItem(blocks[index], kind: child.kind, level: child.level))
    }
    return NorgNode(block: block, children: children)
  }

  /// The kind and nesting level of a nestable block, or `nil` if `block` is not
  /// a nestable item.
  private func nestableDescriptor(_ block: NorgBlock) -> (kind: NestableKind, level: Int)? {
    switch block {
    case .unorderedListItem(let level, _, _, _): return (.unordered, level)
    case .orderedListItem(let level, _, _, _): return (.ordered, level)
    case .quote(let level, _, _, _): return (.quote, level)
    default: return nil
    }
  }
}