1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
use std::collections;
use crate::util;
/// Trait to be implemented for iterative repair.
pub trait Problem {
/// Type defining a conflict.
type Conflict;
/// Iterator to loop over the conflicts - uses tuple with 2nd item defining a priority.
type Iter: Iterator<Item = (Self::Conflict, f64)>;
/// Function to find all conflicts in the problem space.
fn find_conflicts(&self) -> Self::Iter;
/// Routine to fix a particular conflict.
fn fix_conflict(&mut self, _: &Self::Conflict);
}
///
/// Solve a problem using iterative repair algorithm. Conflicts can be ranked.
///
/// # Example
/// ```
/// use std::vec;
///
/// use rusty_planner::iterative_repair;
///
/// struct Problem {}
///
/// impl iterative_repair::Problem for Problem {
/// type Conflict = (i32, i32);
/// type Iter = vec::IntoIter<(Self::Conflict, f64)>;
/// fn find_conflicts(&self) -> Self::Iter {
/// // TODO: Add code that finds conflicts...
/// vec![].into_iter()
/// }
/// fn fix_conflict(&mut self, conflict: &Self::Conflict) {
/// // TODO: Add code that solves a conflict...
/// }
/// }
///
/// let mut ps = Problem {};
/// iterative_repair::solve(&mut ps, 10);
/// ```
///
pub fn solve<PS: Problem>(ps: &mut PS, steps: i32) -> (bool, i32) {
let mut found: bool = false;
let mut iterations: i32 = 0;
for i in 0..steps {
iterations = i;
// TODO: find nicer way to push items on max-heap.
let mut heap: collections::BinaryHeap<util::HeapEntry<PS::Conflict>> =
collections::BinaryHeap::new();
for item in ps.find_conflicts() {
heap.push(util::HeapEntry {
state: item.0,
keys: (item.1, 0.0),
});
}
if !heap.is_empty() {
let conflict: PS::Conflict = heap.pop().unwrap().state;
ps.fix_conflict(&conflict);
// TODO: trace conflicts solved - and if we find repetition of fixes -> break.
} else {
found = true;
break;
}
}
(found, iterations)
}
#[cfg(test)]
mod tests {
use std::collections;
use std::vec;
use crate::iterative_repair;
use crate::iterative_repair::Problem;
const SIZE: i32 = 3;
struct Channel {
iden: i32,
}
// simple example - assume .e.g Wifi Channels in a 3x3 grid -> make sure no overlapping
// channels are used.
struct ScheduleProblem {
channels: collections::HashMap<i32, Channel>,
}
impl iterative_repair::Problem for ScheduleProblem {
type Conflict = (i32, i32);
type Iter = vec::IntoIter<(Self::Conflict, f64)>;
fn find_conflicts(&self) -> Self::Iter {
let mut res = Vec::new();
for (iden, chan) in self.channels.iter() {
// ngbhs to the right...
let rem = (iden + 1) % SIZE;
if rem > 0 {
for i in 0..(SIZE - rem) {
if chan.iden == self.channels[&(iden + i + 1)].iden {
res.push((
(*iden, (iden + i + 1)),
-1.0 * (chan.iden - self.channels[&(iden + i + 1)].iden) as f64,
));
}
}
}
// ngbh below me...
if (iden + SIZE) < self.channels.len() as i32 {
if chan.iden == self.channels[&(iden + SIZE)].iden {
res.push((
(*iden, (iden + SIZE)),
-1.0 * (chan.iden - self.channels[&(iden + SIZE)].iden) as f64,
));
}
}
}
res.into_iter()
}
fn fix_conflict(&mut self, conflict: &Self::Conflict) {
if self.channels[&conflict.0].iden < 16 {
self.channels.get_mut(&conflict.0).unwrap().iden += 1;
} else {
self.channels.get_mut(&conflict.0).unwrap().iden = 0;
}
}
}
// Test for success.
#[test]
fn test_solve_for_success() {
let mut data = collections::HashMap::new();
data.insert(0, Channel { iden: 1 });
data.insert(1, Channel { iden: 4 });
data.insert(2, Channel { iden: 3 });
data.insert(3, Channel { iden: 3 });
data.insert(4, Channel { iden: 4 });
data.insert(5, Channel { iden: 1 });
data.insert(6, Channel { iden: 2 });
data.insert(7, Channel { iden: 1 });
data.insert(8, Channel { iden: 3 });
let mut ps = ScheduleProblem { channels: data };
iterative_repair::solve(&mut ps, 32);
}
// Test for failure.
// TODO: figure out what to do about this...
// Test for sanity.
#[test]
fn test_solve_for_sanity() {
let mut data = collections::HashMap::new();
data.insert(0, Channel { iden: 7 });
data.insert(1, Channel { iden: 12 });
data.insert(2, Channel { iden: 16 });
data.insert(3, Channel { iden: 8 });
data.insert(4, Channel { iden: 3 });
data.insert(5, Channel { iden: 16 });
data.insert(6, Channel { iden: 4 });
data.insert(7, Channel { iden: 4 });
data.insert(8, Channel { iden: 11 });
let mut ps = ScheduleProblem { channels: data };
// 10 steps will do @ only 2 conflicts.
let res = iterative_repair::solve(&mut ps, 10);
assert_eq!(res.0, true); // solution is possible...
assert_eq!(res.1, 2); // two conflicts to repair...
assert_eq!(ps.find_conflicts().len(), 0);
}
}