/// Groups [`QueryChunkMeta`] objects into disjoint sets of overlapped time range.
/// Does not preserve or guarantee any ordering.
Groups [`QueryChunkMeta`] objects into disjoint sets of overlapped time range.
Does not preserve or guarantee any ordering.
Groups [ ` QueryChunkMeta ` ] objects into disjoint sets of overlapped time range . Does not preserve or guarantee any ordering .
pub fn group_potential_duplicates<T>(chunks: Vec<T>) -> Result<Vec<Vec<T>>>
where
    T: QueryChunkMeta,
{
    // If at least one of the chunks has no time range,
    // all chunks are considered to overlap with each other.
    if chunks.iter().any(|c| c.timestamp_min_max().is_none()) {
        debug!("At least one chunk has not timestamp mim max");
        return Ok(vec![chunks]);
    }
    // Use this algorithm to group them
    // https://towardsdatascience.com/overlapping-time-period-problem-b7f1719347db
    let num_chunks = chunks.len();
    let mut grouper = Vec::with_capacity(num_chunks * 2);
    #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    enum StartEnd {
        Start,
        End,
    }
    #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    struct StartEndChunk<I> {
        start_end: StartEnd,
        chunk: Option<I>,
    }
    struct GrouperRecord<I, V: PartialOrd> {
        value: V,
        start_end_chunk: StartEndChunk<I>,
    }
    for chunk in chunks {
        let time_range = chunk
            .timestamp_min_max()
            .expect("Time range should have value");
        grouper.push(GrouperRecord {
            value: time_range.min,
            start_end_chunk: StartEndChunk {
                start_end: StartEnd::Start,
                chunk: None,
            },
        });
        grouper.push(GrouperRecord {
            value: time_range.max,
            start_end_chunk: StartEndChunk {
                start_end: StartEnd::End,
                chunk: Some(chunk),
            },
        });
    }
    grouper.sort_by_key(|gr| (gr.value, gr.start_end_chunk.start_end));
    let mut cumulative_sum = 0;
    let mut groups = Vec::with_capacity(num_chunks);
    for gr in grouper {
        cumulative_sum += match gr.start_end_chunk.start_end {
            StartEnd::Start => 1,
            StartEnd::End => -1,
        };
        if matches!(gr.start_end_chunk.start_end, StartEnd::Start) && cumulative_sum == 1 {
            groups.push(Vec::with_capacity(num_chunks));
        }
        if let StartEnd::End = gr.start_end_chunk.start_end {
            groups
                .last_mut()
                .expect("a start should have pushed at least one empty group")
                .push(gr.start_end_chunk.chunk.expect("Must have chunk value"));
        }
    }
    Ok(groups)
}
pub fn group_potential_duplicates < T > ( chunks : Vec < T > ) -> Result < Vec < Vec < T > > > where T : QueryChunkMeta , { // If at least one of the chunks has no time range, // all chunks are considered to overlap with each other. if chunks . iter ( ) . any ( | c | c . timestamp_min_max ( ) . is_none ( ) ) { debug ! ( " " ) ; return Ok ( vec ! [ chunks ] ) ; } // Use this algorithm to group them // https://towardsdatascience.com/overlapping-time-period-problem-b7f1719347db let num_chunks = chunks . len ( ) ; let mut grouper = Vec :: with_capacity ( num_chunks * 2 ) ; # [ derive ( Clone Copy PartialEq Eq PartialOrd Ord ) ] enum StartEnd { Start , End , } # [ derive ( Clone Copy PartialEq Eq PartialOrd Ord ) ] struct StartEndChunk < I > { start_end : StartEnd , chunk : Option < I > , } struct GrouperRecord < I , V : PartialOrd > { value : V , start_end_chunk : StartEndChunk < I > , } for chunk in chunks { let time_range = chunk . timestamp_min_max ( ) . expect ( " " ) ; grouper . push ( GrouperRecord { value : time_range . min , start_end_chunk : StartEndChunk { start_end : StartEnd :: Start , chunk : None , } , } ) ; grouper . push ( GrouperRecord { value : time_range . max , start_end_chunk : StartEndChunk { start_end : StartEnd :: End , chunk : Some ( chunk ) , } , } ) ; } grouper . sort_by_key ( | gr | ( gr . value , gr . start_end_chunk . start_end ) ) ; let mut cumulative_sum = 0 ; let mut groups = Vec :: with_capacity ( num_chunks ) ; for gr in grouper { cumulative_sum += match gr . start_end_chunk . start_end { StartEnd :: Start => 1 , StartEnd :: End => - 1 , } ; if matches ! ( gr start_end_chunk start_end StartEnd Start ) && cumulative_sum == 1 { groups . push ( Vec :: with_capacity ( num_chunks ) ) ; } if let StartEnd :: End = gr . start_end_chunk . start_end { groups . last_mut ( ) . expect ( " " ) . push ( gr . start_end_chunk . chunk . expect ( " " ) ) ; } } Ok ( groups ) }
Groups [`QueryChunkMeta`] objects into disjoint sets of overlapped time range.
Groups [ ` QueryChunkMeta ` ] objects into disjoint sets of overlapped time range .
chunks
Vec<T>