pub fn explore<P, Ctx, OnState, OnTransition>(

    lps: &P,

    strategy: ExplorationStrategy,

    timing: &Timing,

    ctx: &mut Ctx,

    mut on_state: OnState,

    mut on_transition: OnTransition,

) -> Result<StateIndex, MercError>

where

    P: LPS,

    OnState: FnMut(&mut Ctx, StateIndex, &P::StateInfo) -> Result<(), MercError>,

    OnTransition: FnMut(&mut Ctx, StateIndex, &P::Label, StateIndex) -> Result<(), MercError>,

    let discovered: DiscoveredSet<P::Value> = DiscoveredSet::new();

    let (initial_ref, _) = discovered.insert(&lps.initial_state());

    let mut working: VecDeque<StateRef> = VecDeque::from([initial_ref]);

    let mut current_state: Vec<P::Value> = Vec::new();

    let mut forest_context = SequenceForestContext::new();

    let mut enumerate_context = lps.create_context();

    timing.measure("explore", || -> Result<(), MercError> {

            let current = match strategy {

                ExplorationStrategy::Dfs => working.pop_back(),

                ExplorationStrategy::Bfs => working.pop_front(),

            let Some(current) = current else { break };

            let found = discovered.get_into(current, &mut current_state);

            debug_assert!(found, "StateRef from working queue must be valid");

            let from = StateIndex::new(current.index());

            let summands_to_explore = lps.prepare(&mut enumerate_context, &current_state);

            let info = lps.state_info(&current_state);

            on_state(ctx, from, &info)?;

            let summands = lps.summands();

            for index in summands_to_explore {

                summands[index].enumerate(&mut enumerate_context, &current_state, |label, next_state| {

                    let (target_ref, is_new) = discovered.insert_with(next_state, &mut forest_context);

                    let to = StateIndex::new(target_ref.index());

                    on_transition(ctx, from, label, to)?;

                    if is_new {

                        working.push_back(target_ref);

                    }

                    Ok(())

                })?;

        Ok(())

    })?;

    Ok(StateIndex::new(initial_ref.index()))

}

pub fn explore_parallel<P, Local, MakeLocal, OnState, OnTransition>(

    lps: &P,

    make_local: MakeLocal,

    on_state: OnState,

    on_transition: OnTransition,

) -> Result<(StateIndex, Vec<Local>), MercError>

where

    P: LPS + Sync,

    P::Value: Send + Sync,

    <P::Summand as Summand>::Context: Send,

    Local: Send,

    MakeLocal: Fn() -> Local + Sync,

    OnState: Fn(&mut Local, StateIndex, &P::StateInfo) -> Result<(), MercError> + Sync,

    OnTransition: Fn(&mut Local, StateIndex, &P::Label, StateIndex) -> Result<(), MercError> + Sync,

    let discovered: DiscoveredSet<P::Value> = DiscoveredSet::new();

    let (initial_ref, _) = discovered.insert(&lps.initial_state());

    let num_workers = rayon::current_num_threads().max(1);

    let stealers: Vec<OnceLock<Stealer<StateRef>>> = (0..num_workers).map(|_| OnceLock::new()).collect();

    let pending = AtomicUsize::new(1);

    let aborted = AtomicBool::new(false);

    let results = rayon::broadcast(|broadcast| -> (Local, Option<MercError>) {

        let me = broadcast.index();

        let local_deque: Worker<StateRef> = Worker::new_lifo();

        let _ = stealers[me].set(local_deque.stealer());

        if me == 0 {

            local_deque.push(initial_ref);

        }

        let mut context = lps.create_context();

        let mut forest_context = SequenceForestContext::new();

        let mut state_buf: Vec<P::Value> = Vec::new();

        let mut successors: Vec<StateRef> = Vec::new();

        let mut local = make_local();

        let mut first_error: Option<MercError> = None;

        let mut stats = StealMetrics::default();

        let mut rng = SmallRng::from_rng(&mut rand::rng());

        let backoff = Backoff::new();

            if aborted.load(Ordering::Relaxed) {

                break;

            }

            let Some(state_ref) = find_task(&local_deque, &stealers, me, &mut rng, &mut stats) else {

                if pending.load(Ordering::Acquire) == 0 {

                    break;

                }

                stats.idle_sweeps += 1;

                backoff.snooze();

                continue;

            backoff.reset();

            let result = (|| -> Result<(), MercError> {

                let found = discovered.get_into(state_ref, &mut state_buf);

                debug_assert!(found, "StateRef from work queue must be valid");

                let from = StateIndex::new(state_ref.index());

                let summands_to_explore = lps.prepare(&mut context, &state_buf);

                let info = lps.state_info(&state_buf);

                on_state(&mut local, from, &info)?;

                let summands = lps.summands();

                for index in summands_to_explore {

                    summands[index].enumerate(&mut context, &state_buf, |label, next_state| {

                        let (target_ref, is_new) = discovered.insert_with(next_state, &mut forest_context);

                        let to = StateIndex::new(target_ref.index());

                        on_transition(&mut local, from, label, to)?;

                        if is_new {

                            successors.push(target_ref);

                        }

                        Ok(())

                    })?;

                Ok(())

            match result {

                    let produced = successors.len();

                    if produced == 0 {

                        pending.fetch_sub(1, Ordering::AcqRel);

                    } else {

                        pending.fetch_add(produced - 1, Ordering::AcqRel);

                        for successor in successors.drain(..) {

                            local_deque.push(successor);

                        }

                Err(err) => {

                    first_error = Some(err);

                    aborted.store(true, Ordering::Relaxed);

                    break;

        stats.log(me);

        (local, first_error)

    });

    let mut first_error: Option<MercError> = None;

    let mut locals = Vec::with_capacity(results.len());

    for (local, error) in results {

        if first_error.is_none() {

            first_error = error;

        }

        locals.push(local);

    if let Some(error) = first_error {

        return Err(error);

    }

    Ok((StateIndex::new(initial_ref.index()), locals))

}

    fn log(&self, worker: usize) {

        let processed = self.local_pops + self.steals;

        let stolen_pct = if processed == 0 {

            0.0

            100.0 * self.steals as f64 / processed as f64

        log::debug!(

    }

fn find_task<T>(

    local: &Worker<T>,

    stealers: &[OnceLock<Stealer<T>>],

    me: usize,

    rng: &mut SmallRng,

    stats: &mut StealMetrics,

) -> Option<T> {

    if let Some(task) = local.pop() {

        stats.local_pops += 1;

        return Some(task);

    }

    for _ in 0..stealers.len() {

        let index = rng.random_range(0..stealers.len());

        if index == me {

            continue;

        }

        let Some(stealer) = stealers[index].get() else {

            continue;

        match stealer.steal_batch_and_pop(local) {

            Steal::Success(task) => {

                stats.steals += 1;

                return Some(task);

            Steal::Retry => stats.steal_retries += 1,

            Steal::Empty => {}

    None

}