use super::environment::*;
use crate::algos::dependency::{Process, ProcessId, ResourceId};
use std::collections::HashSet;
#[derive(Debug)]
pub struct BacktrackingInfo {
failed_steps: HashSet<ProcessId>,
reason: BacktrackReason,
}
#[derive(Clone, Debug, PartialEq)]
pub enum BacktrackReason {
NotEnoughResources,
NewUnfailedEmptyinputs,
NewUnfailedOutputsBiggerEqualInputs,
NewUnfailed,
OldOutputsGenerating,
Unspecified,
}
pub fn next<R, P>(
environment: &Environment<R, P>,
path: &Path<BacktrackingInfo>,
) -> (BacktrackReason, Vec<Step<BacktrackingInfo>>)
where
P: Process,
{
let (inventory, possibles) = possible_with_inventory(environment, path);
if possibles.is_empty() {
return (BacktrackReason::NotEnoughResources, vec![]);
}
let create_step = |id: ProcessId, meta: &Meta, reason: &BacktrackReason| Step {
process: id,
inventory_after: inventory.clone() - Inventory::with_list(&meta.inputs) + Inventory::with_list(&meta.outputs),
algorithm_data: BacktrackingInfo {
failed_steps: HashSet::new(),
reason: reason.clone(),
},
};
let empty_hashset = HashSet::new();
let last_failed_steps = path
.steps
.last()
.map(|s| &s.algorithm_data.failed_steps)
.unwrap_or(&empty_hashset);
let already_run = path.processes();
#[derive(Clone, PartialEq)]
struct Constrain {
new: bool,
failed: bool,
empty_inputs: bool,
outputs_greater_equal_inputs: bool,
outputs_generating: bool,
same_reason_loop: bool,
}
let possibles: Vec<(u64, Meta, Constrain)> = possibles
.into_iter()
.map(|(id, meta)| {
let outputs_greater_equal_inputs =
Inventory::with_list(&meta.outputs).contains(&Inventory::with_list(&meta.inputs));
let con = Constrain {
new: !already_run.items.contains_key(&id),
failed: last_failed_steps.contains(&id),
empty_inputs: meta.inputs.is_empty(),
outputs_greater_equal_inputs,
outputs_generating: !outputs_greater_equal_inputs && !Inventory::with_list(&meta.inputs).contains(&Inventory::with_list(&meta.outputs)),
same_reason_loop: same_reason_loop(path, id),
};
(id, meta, con)
})
.collect();
#[allow(clippy::type_complexity)]
let conditions_checks: &[(fn(&Constrain) -> bool, BacktrackReason); 4] = &[
(
|con: &Constrain| con.new && !con.failed && con.empty_inputs,
BacktrackReason::NewUnfailedEmptyinputs,
),
(
|con: &Constrain| con.new && !con.failed && con.outputs_greater_equal_inputs,
BacktrackReason::NewUnfailedOutputsBiggerEqualInputs,
),
(|con: &Constrain| con.new && !con.failed, BacktrackReason::NewUnfailed),
(
|con: &Constrain| !con.new && !con.failed && con.outputs_generating && !con.same_reason_loop,
BacktrackReason::OldOutputsGenerating,
),
];
for (check, reason) in conditions_checks {
let possible_result: Vec<_> = possibles
.iter()
.filter(|(_, _, con)| check(con))
.map(|(id, meta, _)| create_step(*id, meta, reason))
.collect();
if !possible_result.is_empty() {
return (reason.clone(), possible_result);
}
}
(
BacktrackReason::Unspecified,
possibles
.iter()
.map(|(p, meta, _)| create_step(*p, meta, &BacktrackReason::Unspecified))
.collect(),
)
}
struct Meta {
tools: Vec<ResourceId>,
inputs: Vec<ResourceId>,
outputs: Vec<ResourceId>,
}
fn possible_with_inventory<'a, R, P>(
environment: &'a Environment<R, P>,
path: &'a Path<BacktrackingInfo>,
) -> (&'a Inventory<ResourceId>, Vec<(u64, Meta)>)
where
P: Process,
{
let inventory = path
.steps
.last()
.map(|s| &s.inventory_after)
.unwrap_or(environment.initial());
let mut possibles: Vec<(u64, Meta)> = environment
.processes()
.iter()
.map(|(id, p)| {
(*id, Meta {
tools: p.tools().into_iter().collect(),
inputs: p.inputs().into_iter().collect(),
outputs: p.outputs().into_iter().collect(),
})
})
.filter(|(_, meta)| {
inventory.contains(&(Inventory::with_list(&meta.inputs) + Inventory::with_list(&meta.tools)))
})
.collect();
possibles.sort_by_key(|v| v.0);
(inventory, possibles)
}
fn same_reason_loop(path: &Path<BacktrackingInfo>, potential: ProcessId) -> bool {
let reason = match path.steps.last() {
Some(last) => &last.algorithm_data.reason,
None => return false,
};
for s in path.steps.iter().rev() {
if s.algorithm_data.reason != *reason {
return false;
}
if s.process == potential {
return true;
}
}
false
}
#[cfg(test)]
mod tests {
use super::{super::EnvironmentBuilder, Environment, ProcessId, ResourceId};
use crate::algos::dependency::{
backtrack::{BacktrackReason, BacktrackingInfo},
Inventory, Path, Step,
};
pub struct Process {
id: ProcessId,
inputs: Vec<u64>,
reference: Vec<u64>,
outputs: Vec<u64>,
name: String,
}
pub struct Resource {
id: ResourceId,
name: String,
}
impl crate::algos::dependency::Process for Process {
type I = Vec<ResourceId>;
fn cost(&self) -> u64 { 64 }
fn id(&self) -> ProcessId { self.id }
fn inputs(&self) -> Self::I { self.inputs.iter().map(|id| id.to_string()).collect() }
fn outputs(&self) -> Self::I { self.outputs.iter().map(|id| id.to_string()).collect() }
fn tools(&self) -> Self::I { self.reference.iter().map(|id| id.to_string()).collect() }
fn name(&self) -> &str { &self.name }
}
impl crate::algos::dependency::Resource for Resource {
fn id(&self) -> ResourceId { self.id.clone() }
fn name(&self) -> &str { &self.name }
}
pub fn setup() -> Environment<Resource, Process> {
let mut env = EnvironmentBuilder::default();
env.add_process(Process {
id: 0,
reference: Vec::new(),
inputs: Vec::new(),
outputs: vec![0],
name: "S".to_string(),
});
env.add_process(Process {
id: 1,
reference: Vec::new(),
inputs: vec![0],
outputs: vec![1],
name: "A".to_string(),
});
env.add_process(Process {
id: 2,
reference: Vec::new(),
inputs: vec![1],
outputs: vec![2],
name: "B".to_string(),
});
env.add_process(Process {
id: 3,
reference: Vec::new(),
inputs: vec![1],
outputs: vec![2],
name: "C".to_string(),
});
env.add_process(Process {
id: 4,
reference: Vec::new(),
inputs: vec![2],
outputs: vec![2, 3],
name: "D".to_string(),
});
env.add_process(Process {
id: 5,
reference: Vec::new(),
inputs: vec![3],
outputs: vec![1, 2],
name: "E".to_string(),
});
env.add_process(Process {
id: 6,
reference: Vec::new(),
inputs: vec![0, 1, 2, 3, 3],
outputs: Vec::new(),
name: "F".to_string(),
});
env.add_resource(Resource {
id: "0".to_string(),
name: "a".to_string(),
});
env.add_resource(Resource {
id: "1".to_string(),
name: "b".to_string(),
});
env.add_resource(Resource {
id: "2".to_string(),
name: "c".to_string(),
});
env.add_resource(Resource {
id: "3".to_string(),
name: "d".to_string(),
});
env.build()
}
#[test]
pub fn first() {
let env = setup();
let path = Path::default();
let (reason, nexts) = super::next(&env, &path);
assert_eq!(reason, BacktrackReason::NewUnfailedEmptyinputs);
assert_eq!(nexts.into_iter().map(|s| s.process).collect::<Vec<_>>(), vec!(0));
}
#[test]
pub fn first_motherlode() {
let mut env = setup();
env.initial_mut().push("0".to_string());
env.initial_mut().push("1".to_string());
env.initial_mut().push("2".to_string());
env.initial_mut().push("3".to_string());
env.initial_mut().push("3".to_string());
let path = Path::default();
let (reason, nexts) = super::next(&env, &path);
assert_eq!(reason, BacktrackReason::NewUnfailedEmptyinputs);
assert_eq!(nexts.into_iter().map(|s| s.process).collect::<Vec<_>>(), vec!(0));
}
#[test]
pub fn second() {
let mut env = setup();
env.initial_mut().push("2".to_string());
let mut path = Path::default();
path.steps.push(Step {
process: 0,
inventory_after: env.initial().clone() + Inventory::with_list(&["0".to_string()]),
algorithm_data: BacktrackingInfo {
failed_steps: Default::default(),
reason: BacktrackReason::Unspecified,
},
});
let (reason, nexts) = super::next(&env, &path);
assert_eq!(reason, BacktrackReason::NewUnfailedOutputsBiggerEqualInputs);
assert_eq!(nexts.into_iter().map(|s| s.process).collect::<Vec<_>>(), vec!(4));
}
}