///|
pub struct Searcher {
  run : (EGraph) -> Array[Match]
}

///|
pub fn Searcher::search(self : Searcher, egraph : EGraph) -> Array[Match] {
  (self.run)(egraph)
}

///|
pub fn Searcher::pattern(lhs : Pattern) -> Searcher {
  Searcher::{ run: egraph => search_pattern(lhs, egraph) }
}

///|
pub fn Searcher::pattern_with(
  lhs : Pattern,
  pred : (EGraph, Map[String, Id]) -> Bool,
) -> Searcher {
  Searcher::{
    run: egraph => search_pattern(lhs, egraph).filter(m => pred(egraph, m.subst)),
  }
}

///|
pub fn Searcher::filter(
  self : Searcher,
  pred : (EGraph, Map[String, Id]) -> Bool,
) -> Searcher {
  Searcher::{
    run: egraph => self.search(egraph).filter(m => pred(egraph, m.subst)),
  }
}

///|
pub fn Searcher::with_binding(
  self : Searcher,
  binder : (EGraph, Map[String, Id]) -> (String, Id)?,
) -> Searcher {
  Searcher::{
    run: egraph => {
      let results : Array[Match] = Array::new()
      for m in self.search(egraph) {
        match binder(egraph, m.subst) {
          None => results.push(m)
          Some((name, id)) => {
            let next = m.subst.copy()
            match next.get(name) {
              Some(existing) if existing != id => continue
              _ => {
                next.set(name, id)
                results.push(Match::{ root: m.root, subst: next })
              }
            }
          }
        }
      }
      results
    },
  }
}

///|
pub fn Searcher::multi(patterns : Array[Pattern]) -> Searcher {
  if patterns.is_empty() {
    return Searcher::{ run: (_ : EGraph) => [] }
  }
  Searcher::{ run: egraph => search_multi_patterns(patterns, egraph) }
}

///|
fn search_pattern(lhs : Pattern, egraph : EGraph) -> Array[Match] {
  let program = Program::compile_from_pattern(lhs)
  execute_program(program, egraph)
}

///|
fn execute_program(program : Program, egraph : EGraph) -> Array[Match] {
  let results : Array[Match] = Array::new()
  for class_id in egraph.class_ids() {
    let root = egraph.find(class_id)
    let substs = program.run_with_limit(egraph, root, limit=None)
    for subst in substs {
      results.push(Match::{ root, subst })
    }
  }
  results
}

///|
fn search_multi_patterns(
  patterns : Array[Pattern],
  egraph : EGraph,
) -> Array[Match] {
  let pairs : Array[(String, Pattern)] = Array::new()
  for pat in patterns {
    pairs.push(("__root__".to_string(), pat))
  }
  let program = Program::compile_from_multi(pairs)
  execute_program(program, egraph)
}