区間データから重複を削除するアルゴリズム

$ viewrec --from 207707070900 --to 207707071700 --tags freedom liberty

use std::collections::{HashMap, HashSet};
use std::fmt::Debug;
use std::iter::FromIterator;
use std::marker::Sized;

pub trait BoundOps: Copy + Debug + Eq + Ord
where
    Self: Sized,
{
}
impl<T> BoundOps for T where T: Copy + Debug + Eq + Ord {}

// タグ付き区間を表す構造体
#[derive(Clone, Debug, PartialEq)]
pub struct TaggedInterval<Bound>
where
    Bound: BoundOps,
{
    lower: Bound, // 区間の始点
    upper: Bound, // 区間の終点
    tags: HashSet<String>, // タグ
}

#[derive(Clone, Copy, Debug, PartialEq)]
enum BoundKind {
    Specified, // コマンドラインで指定されたもの
    History, // 履歴に存在するもの
}

#[derive(Clone, Copy, Debug, PartialEq)]
enum BoundDirection {
    Lower, // 始点
    Upper, // 終点
}

// タグ付き区間を始点・終点にバラした構造体
#[derive(Clone, Debug, PartialEq)]
struct TaggedBound<Bound>
where
    Bound: BoundOps,
{
    kind: BoundKind,
    direction: BoundDirection,
    bound: Bound,
    tags: HashSet<String>,
}

impl<Bound> TaggedBound<Bound>
where
    Bound: BoundOps,
{
    fn from_interval(interval: &TaggedInterval<Bound>, kind: BoundKind) -> (Self, Self) {
        (
            Self {
                kind,
                direction: BoundDirection::Lower,
                bound: interval.lower,
                tags: interval.tags.clone(),
            },
            Self {
                kind,
                direction: BoundDirection::Upper,
                bound: interval.upper,
                tags: interval.tags.clone(),
            },
        )
    }

    fn from_history(intervals: &Vec<TaggedInterval<Bound>>) -> Vec<Self> {
        let mut bounds = vec![];
        for iv in intervals {
            let (lower, upper) = Self::from_interval(iv, BoundKind::History);
            bounds.push(lower);
            bounds.push(upper);
        }
        bounds
    }

    fn from_specified(interval: &TaggedInterval<Bound>) -> Vec<Self> {
        let mut bounds = vec![];
        let (lower, upper) = Self::from_interval(interval, BoundKind::Specified);
        bounds.push(lower);
        bounds.push(upper);
        bounds
    }

    pub fn from_intervals(
        specified: &TaggedInterval<Bound>,
        history: &Vec<TaggedInterval<Bound>>,
    ) -> Vec<Self> {
        vec![Self::from_specified(specified), Self::from_history(history)].concat()
    }

    pub fn sort(bounds: &mut Vec<Self>) -> &mut Vec<Self> {
        bounds.sort_by(|x, y| x.bound.partial_cmp(&y.bound).unwrap());
        bounds
    }
}

// 重複した要素を持ち得る ベクタ v1 と v2 の差分を求める。
// 例) ["freedom", "freedom"] - ["freedom"] = ["freedom"]
fn difference_with_dups(v1: &Vec<String>, v2: &Vec<String>) -> Vec<String> {
    let mut result = v1.clone();
    let mut counts: HashMap<String, i128> = HashMap::new();
    v2.iter().for_each(|s| {
        counts.entry(s.clone()).and_modify(|n| *n += 1).or_insert(1);
    });
    result.retain(|s| {
        *counts
            .entry(s.clone())
            .and_modify(|n| *n -= 1)
            .or_insert(-1)
            < 0
    });
    result
}

impl<Bound> TaggedInterval<Bound>
where
    Bound: BoundOps,
{
    pub fn new(lower: Bound, upper: Bound, tags: HashSet<String>) -> Self {
        Self { lower, upper, tags }
    }

    // 未取得範囲・タグを求めるアルゴリズム
    pub fn difference(self, history: Vec<Self>) -> Vec<Self> {
        let mut bounds = TaggedBound::from_intervals(&self, &history);
        TaggedBound::sort(&mut bounds);

        let mut result = vec![];
        let mut in_specified_range = false;
        let mut current_tags = vec![];
        let mut current_bound = self.lower;
        let num_bounds = bounds.len();
        let mut i = 0;

        while i < num_bounds {
            let mut specified_lower_found = false;
            let mut specified_range_will_be_over = false;
            let mut lower_tags = vec![];
            let mut upper_tags = vec![];
            let mut j = i;

            while j < num_bounds && bounds[j].bound.eq(&bounds[i].bound) {
                match bounds[j].kind {
                    BoundKind::History => match bounds[j].direction {
                        BoundDirection::Lower => {
                            bounds[j]
                                .tags
                                .iter()
                                .for_each(|t| lower_tags.push(t.clone()));
                        }
                        BoundDirection::Upper => {
                            bounds[j]
                                .tags
                                .iter()
                                .for_each(|t| upper_tags.push(t.clone()));
                        }
                    },
                    BoundKind::Specified => match bounds[j].direction {
                        BoundDirection::Lower => {
                            specified_lower_found = true;
                        }
                        BoundDirection::Upper => {
                            specified_range_will_be_over = true;
                        }
                    },
                }
                j += 1;
            }

            let mut next_tags = difference_with_dups(&current_tags, &upper_tags);
            next_tags.append(&mut lower_tags);

            let continuous = in_specified_range
                && HashSet::<String>::from_iter(next_tags.iter().cloned())
                    .eq(&HashSet::from_iter(current_tags.iter().cloned()));

            if in_specified_range && (!continuous || specified_range_will_be_over) {
                let current_tag_set = current_tags.iter().cloned().collect();
                let tags: HashSet<String> =
                    self.tags.difference(&current_tag_set).cloned().collect();
                if !tags.is_empty() {
                    let tagged_bound = TaggedInterval::new(current_bound, bounds[i].bound, tags);
                    result.push(tagged_bound);
                }
            }

            if specified_range_will_be_over {
                break;
            }
            if specified_lower_found {
                in_specified_range = true;
            }
            if !continuous {
                current_bound = bounds[i].bound;
            }

            i = j;
            current_tags = next_tags;
        }

        result
    }
}