#[cfg(feature = "serde")]
#[macro_use]
extern crate serde;
type Nodes<I, P> = Vec<SubsetMapNode<I, P>>;
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct SubsetMap<E, P> {
nodes: Nodes<E, P>,
}
impl<E, P> SubsetMap<E, P>
where
E: Clone,
{
pub fn new<F>(elements: &[E], mut init: F) -> SubsetMap<E, P>
where
F: FnMut(&[E]) -> Option<P>,
{
init_root::<_, _, _, ()>(elements, &mut |elements| Ok(init(elements))).unwrap()
}
pub fn fill<F>(elements: &[E], mut init: F) -> SubsetMap<E, P>
where
F: FnMut(&[E]) -> P,
{
init_root::<_, _, _, ()>(elements, &mut |elements| Ok(Some(init(elements)))).unwrap()
}
pub fn init<F, X>(elements: &[E], mut init: F) -> Result<SubsetMap<E, P>, X>
where
F: FnMut(&[E]) -> Result<Option<P>, X>,
{
init_root(elements, &mut init)
}
pub fn init_filled<F, X>(elements: &[E], mut init: F) -> Result<SubsetMap<E, P>, X>
where
F: FnMut(&[E]) -> Result<P, X>,
{
init_root::<_, _, _, X>(elements, &mut |elements| init(elements).map(Some))
}
pub fn with_value<F>(elements: &[E], mut init: F) -> SubsetMap<E, P>
where
F: FnMut() -> P,
{
init_root::<_, _, _, ()>(elements, &mut |_| Ok(Some(init()))).unwrap()
}
pub fn with_default(elements: &[E]) -> SubsetMap<E, P>
where
P: Default,
{
init_root::<_, _, _, ()>(elements, &mut |_| Ok(Some(P::default()))).unwrap()
}
pub fn get<'a>(&'a self, subset: &[E]) -> Option<&'a P>
where
E: Eq,
{
get(subset, &self.nodes)
}
pub fn get_owned(&self, subset: &[E]) -> Option<P::Owned>
where
E: Eq,
P: ToOwned,
{
get(subset, &self.nodes).map(|p| p.to_owned())
}
pub fn lookup<'a>(&'a self, subset: &[E]) -> LookupResult<'a, E, P>
where
E: Eq,
{
lookup(subset, &self.nodes)
}
pub fn find<'a>(&'a self, subset: &[E]) -> FindResult<'a, E, P>
where
E: Eq,
{
match self.lookup(subset) {
LookupResult::Perfect(Some(p)) => FindResult::Perfect(p),
LookupResult::Perfect(None) => FindResult::NotFound,
LookupResult::Excluded(Some(p), e) => FindResult::Excluded(p, e),
LookupResult::Excluded(None, _) => FindResult::NotFound,
LookupResult::NoMatch => FindResult::NotFound,
}
}
pub fn filter_values<F>(&mut self, mut predicate: F)
where
F: FnMut(&P) -> bool,
{
self.nodes
.iter_mut()
.for_each(|n| n.filter_values(&mut predicate))
}
pub fn walk_values<F>(&self, mut f: F)
where
F: FnMut(&P),
{
self.nodes.iter().for_each(|n| n.walk_values(&mut f))
}
pub fn walk_values_until<F>(&self, mut f: F)
where
F: FnMut(&P) -> bool,
{
for node in &self.nodes {
if !node.walk_values_until(&mut f) {
return;
}
}
}
pub fn walk_payloads<F>(&self, mut f: F)
where
F: FnMut(Option<&P>),
{
self.nodes.iter().for_each(|n| n.walk_payloads(&mut f))
}
pub fn walk_payloads_until<F>(&self, mut f: F)
where
F: FnMut(Option<&P>) -> bool,
{
for node in &self.nodes {
if !node.walk_payloads_until(&mut f) {
return;
}
}
}
pub fn walk<F>(&self, mut f: F)
where
F: FnMut(&[&E], Option<&P>),
{
self.nodes.iter().for_each(|n| n.walk(&mut f))
}
pub fn for_each_value<F>(&self, mut f: F)
where
F: FnMut(&P),
{
self.walk_values_until(|p| {
f(p);
true
})
}
pub fn for_each_payload<F>(&self, mut f: F)
where
F: FnMut(Option<&P>),
{
self.walk_payloads_until(|p| {
f(p);
true
})
}
pub fn all_subsets_have_values(&self) -> bool {
if self.is_empty() {
return false;
}
let mut all_set = true;
self.walk_payloads_until(|p| {
if p.is_none() {
all_set = false;
false
} else {
true
}
});
all_set
}
pub fn no_subset_with_value(&self) -> bool {
if self.is_empty() {
return true;
}
let mut no_value_set = true;
self.walk_payloads_until(|p| {
if p.is_some() {
no_value_set = false;
false
} else {
true
}
});
no_value_set
}
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
pub fn size(&self) -> usize {
2usize.pow(self.nodes.len() as u32) - 1
}
}
impl<E, P> Default for SubsetMap<E, P> {
fn default() -> Self {
SubsetMap {
nodes: Default::default(),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
struct SubsetMapNode<E, P> {
pub element: E,
pub payload: Option<P>,
pub nodes: Nodes<E, P>,
}
impl<E, P> SubsetMapNode<E, P> {
pub fn filter_values<F>(&mut self, predicate: &mut F)
where
F: FnMut(&P) -> bool,
{
let keep = self.payload.as_ref().map(|p| predicate(p)).unwrap_or(true);
if !keep {
self.payload = None;
}
self.nodes
.iter_mut()
.for_each(|n| n.filter_values(predicate))
}
pub fn walk_values<F>(&self, f: &mut F)
where
F: FnMut(&P),
{
if let Some(ref payload) = self.payload {
f(payload);
}
self.nodes.iter().for_each(|n| n.walk_values(f))
}
pub fn walk_payloads<F>(&self, f: &mut F)
where
F: FnMut(Option<&P>),
{
f(self.payload.as_ref());
self.nodes.iter().for_each(|n| n.walk_payloads(f))
}
pub fn walk_values_until<F>(&self, f: &mut F) -> bool
where
F: FnMut(&P) -> bool,
{
let go_on = if let Some(ref payload) = self.payload {
f(payload)
} else {
true
};
if go_on {
for node in &self.nodes {
if !node.walk_values_until(f) {
return false;
}
}
}
true
}
pub fn walk_payloads_until<F>(&self, f: &mut F) -> bool
where
F: FnMut(Option<&P>) -> bool,
{
if f(self.payload.as_ref()) {
for node in &self.nodes {
if !node.walk_payloads_until(f) {
return false;
}
}
true
} else {
false
}
}
pub fn walk<F>(&self, mut f: F)
where
F: FnMut(&[&E], Option<&P>),
{
let mut elements = Vec::new();
self.walk_internal(&mut elements, &mut f)
}
fn walk_internal<'a, F>(&'a self, elements: &mut Vec<&'a E>, f: &mut F)
where
F: FnMut(&[&E], Option<&P>),
{
elements.push(&self.element);
f(elements.as_slice(), self.payload.as_ref());
self.nodes.iter().for_each(|n| n.walk_internal(elements, f));
elements.pop();
}
}
#[derive(Debug)]
pub enum LookupResult<'a, E, P: 'a> {
Perfect(Option<&'a P>),
Excluded(Option<&'a P>, Vec<E>),
NoMatch,
}
impl<'a, E, P> LookupResult<'a, E, P> {
pub fn payload(&self) -> Option<&P> {
match *self {
LookupResult::Perfect(p) => p,
LookupResult::Excluded(p, _) => p,
LookupResult::NoMatch => None,
}
}
pub fn excluded_elements(&self) -> &[E] {
match *self {
LookupResult::Perfect(_) => &[],
LookupResult::Excluded(_, ref skipped) => &*skipped,
LookupResult::NoMatch => &[],
}
}
pub fn is_perfect(&self) -> bool {
match *self {
LookupResult::Perfect(_) => true,
_ => false,
}
}
pub fn is_excluded(&self) -> bool {
match *self {
LookupResult::Excluded(_, _) => true,
_ => false,
}
}
pub fn is_no_match(&self) -> bool {
!self.is_match()
}
pub fn is_match(&self) -> bool {
match *self {
LookupResult::NoMatch => false,
_ => true,
}
}
}
#[derive(Debug)]
pub enum FindResult<'a, E, P: 'a> {
Perfect(&'a P),
Excluded(&'a P, Vec<E>),
NotFound,
}
impl<'a, E, P> FindResult<'a, E, P> {
pub fn payload(&self) -> Option<&P> {
match *self {
FindResult::Perfect(p) => Some(p),
FindResult::Excluded(p, _) => Some(p),
FindResult::NotFound => None,
}
}
pub fn excluded_elements(&self) -> &[E] {
match *self {
FindResult::Perfect(_) => &[],
FindResult::Excluded(_, ref skipped) => &*skipped,
FindResult::NotFound => &[],
}
}
pub fn is_found_and_perfect(&self) -> bool {
match *self {
FindResult::Perfect(_) => true,
_ => false,
}
}
pub fn is_found_and_excluded(&self) -> bool {
match *self {
FindResult::Excluded(_, _) => true,
_ => false,
}
}
pub fn is_not_found(&self) -> bool {
!self.is_found()
}
pub fn is_found(&self) -> bool {
match *self {
FindResult::NotFound => false,
_ => true,
}
}
}
fn init_root<E, P, F, X>(elements: &[E], init_with: &mut F) -> Result<SubsetMap<E, P>, X>
where
E: Clone,
F: FnMut(&[E]) -> Result<Option<P>, X>,
{
let mut stack = Vec::new();
let mut nodes = Vec::new();
for fixed in 0..elements.len() {
let element = elements[fixed].clone();
let payload = init_with(&elements[fixed..=fixed])?;
let mut node = SubsetMapNode {
element,
payload,
nodes: Vec::new(),
};
stack.clear();
stack.push(elements[fixed].clone());
init_node(elements, &mut stack, fixed, &mut node, init_with)?;
nodes.push(node)
}
Ok(SubsetMap { nodes })
}
fn init_node<E, P, F, X>(
elements: &[E],
stack: &mut Vec<E>,
fixed: usize,
into: &mut SubsetMapNode<E, P>,
init_with: &mut F,
) -> Result<(), X>
where
E: Clone,
F: FnMut(&[E]) -> Result<Option<P>, X>,
{
for fixed in fixed + 1..elements.len() {
stack.push(elements[fixed].clone());
let mut node = SubsetMapNode {
element: elements[fixed].clone(),
payload: init_with(&stack)?,
nodes: Vec::new(),
};
let _ = init_node(elements, stack, fixed, &mut node, init_with);
stack.pop();
into.nodes.push(node);
}
Ok(())
}
fn get<'a, 'b, E, P>(subset: &'b [E], nodes: &'a [SubsetMapNode<E, P>]) -> Option<&'a P>
where
E: Eq,
{
let mut nodes = nodes;
let mut result = None;
for element in subset {
if let Some(node) = nodes.iter().find(|n| n.element == *element) {
result = node.payload.as_ref();
nodes = &node.nodes;
} else {
return None;
}
}
result
}
fn lookup<'a, 'b, E, P>(subset: &'b [E], nodes: &'a [SubsetMapNode<E, P>]) -> LookupResult<'a, E, P>
where
E: Eq + Clone,
{
let mut excluded = Vec::new();
let mut nodes = nodes;
let mut result_node = None;
for element in subset {
if let Some(node) = nodes.iter().find(|n| n.element == *element) {
result_node = Some(node);
nodes = &node.nodes;
} else {
excluded.push(element.clone())
}
}
if let Some(result_node) = result_node {
if excluded.is_empty() {
LookupResult::Perfect(result_node.payload.as_ref())
} else {
LookupResult::Excluded(result_node.payload.as_ref(), excluded)
}
} else {
LookupResult::NoMatch
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn create_empty() {
let sample = SubsetMap::<u32, ()>::default();
assert!(sample.is_empty());
}
#[test]
fn one_element() {
let sample = SubsetMap::fill(&[1], |_| 1);
assert_eq!(sample.get(&[1]), Some(&1));
assert_eq!(sample.get(&[]), None);
assert_eq!(sample.get(&[2]), None);
}
#[test]
fn two_elements() {
let sample = SubsetMap::fill(&[1, 2], |x| x.iter().sum::<i32>());
assert_eq!(sample.get(&[1]), Some(&1));
assert_eq!(sample.get(&[2]), Some(&2));
assert_eq!(sample.get(&[1, 2]), Some(&3));
assert_eq!(sample.get(&[]), None);
assert_eq!(sample.get(&[2, 1]), None);
assert_eq!(sample.get(&[0]), None);
assert_eq!(sample.get(&[0, 1]), None);
}
#[test]
fn three_elements() {
let sample = SubsetMap::fill(&[1, 2, 3], |x| x.iter().sum::<i32>());
assert_eq!(sample.get(&[1]), Some(&1));
assert_eq!(sample.get(&[2]), Some(&2));
assert_eq!(sample.get(&[3]), Some(&3));
assert_eq!(sample.get(&[1, 2]), Some(&3));
assert_eq!(sample.get(&[2, 3]), Some(&5));
assert_eq!(sample.get(&[1, 3]), Some(&4));
assert_eq!(sample.get(&[1, 2, 3]), Some(&6));
assert_eq!(sample.get(&[]), None);
assert_eq!(sample.get(&[2, 1]), None);
assert_eq!(sample.get(&[0]), None);
assert_eq!(sample.get(&[0, 1]), None);
}
#[test]
fn three_elements_identity_vec() {
let sample = SubsetMap::fill(&[1, 2, 3], |x| x.to_vec());
assert_eq!(sample.get(&[1]), Some(&vec![1]));
assert_eq!(sample.get(&[2]), Some(&vec![2]));
assert_eq!(sample.get(&[3]), Some(&vec![3]));
assert_eq!(sample.get(&[1, 2]), Some(&vec![1, 2]));
assert_eq!(sample.get(&[2, 3]), Some(&vec![2, 3]));
assert_eq!(sample.get(&[1, 3]), Some(&vec![1, 3]));
assert_eq!(sample.get(&[1, 2, 3]), Some(&vec![1, 2, 3]));
}
#[test]
fn walk_5_elems_keeps_order() {
let elements: Vec<_> = (0..5).collect();
let mut n = 0;
let map = SubsetMap::fill(&elements, |_x| {
n += 1;
n
});
let mut n = 0;
map.walk(|_elements, payload| {
n += 1;
assert_eq!(payload, Some(&n));
})
}
#[test]
fn test_lookup_result() {
let subset_map = SubsetMap::new(&[1u32, 2, 3, 4], |x| {
if x == &[2, 3] {
None
} else {
let payload = x.iter().cloned().collect::<Vec<_>>();
Some(payload)
}
});
let empty: &[u32] = &[];
let match_result = subset_map.lookup(&[]);
assert_eq!(match_result.payload(), None);
assert_eq!(match_result.excluded_elements(), empty);
assert_eq!(match_result.is_match(), false);
assert_eq!(match_result.is_perfect(), false);
assert_eq!(match_result.is_excluded(), false);
let match_result = subset_map.lookup(&[1]);
assert_eq!(match_result.payload(), Some(&vec![1]));
assert_eq!(match_result.excluded_elements(), empty);
assert_eq!(match_result.is_match(), true);
assert_eq!(match_result.is_perfect(), true);
assert_eq!(match_result.is_excluded(), false);
let match_result = subset_map.lookup(&[2, 3]);
assert_eq!(match_result.payload(), None);
assert_eq!(match_result.excluded_elements(), empty);
assert_eq!(match_result.is_match(), true);
assert_eq!(match_result.is_perfect(), true);
assert_eq!(match_result.is_excluded(), false);
let match_result = subset_map.lookup(&[42]);
assert_eq!(match_result.is_no_match(), true);
assert_eq!(match_result.is_perfect(), false);
assert_eq!(match_result.is_excluded(), false);
assert_eq!(match_result.excluded_elements(), empty);
let match_result = subset_map.lookup(&[42, 3]);
assert_eq!(match_result.payload(), Some(&vec![3]));
assert_eq!(match_result.excluded_elements(), &[42]);
assert_eq!(match_result.is_perfect(), false);
assert_eq!(match_result.is_excluded(), true);
assert_eq!(match_result.is_match(), true);
let match_result = subset_map.lookup(&[3, 1]);
assert_eq!(match_result.payload(), Some(&vec![3]));
assert_eq!(match_result.excluded_elements(), &[1]);
assert_eq!(match_result.is_perfect(), false);
assert_eq!(match_result.is_excluded(), true);
assert_eq!(match_result.is_match(), true);
let match_result = subset_map.lookup(&[3, 1, 4, 2]);
assert_eq!(match_result.payload(), Some(&vec![3, 4]));
assert_eq!(match_result.excluded_elements(), &[1, 2]);
assert_eq!(match_result.is_perfect(), false);
assert_eq!(match_result.is_excluded(), true);
assert_eq!(match_result.is_match(), true);
let match_result = subset_map.lookup(&[4, 3, 2, 1]);
assert_eq!(match_result.payload(), Some(&vec![4]));
assert_eq!(match_result.excluded_elements(), &[3, 2, 1]);
assert_eq!(match_result.is_perfect(), false);
assert_eq!(match_result.is_excluded(), true);
assert_eq!(match_result.is_match(), true);
let match_result = subset_map.lookup(&[99, 2, 1, 77, 78, 3, 4, 2, 1, 2]);
assert_eq!(match_result.payload(), Some(&vec![2, 3, 4]));
assert_eq!(match_result.excluded_elements(), &[99, 1, 77, 78, 2, 1, 2]);
assert_eq!(match_result.is_perfect(), false);
assert_eq!(match_result.is_excluded(), true);
assert_eq!(match_result.is_match(), true);
}
}