The Algorithms logo
The Algorithms
AboutDonate

Timeline

A
/*
    Author: Lorenzo Lotti
    Name: Timeline (DataStructures.Timeline<TValue>)
    Type: Data structure (class)
    Description: A collection of dates/times and values sorted by dates/times easy to query.
    Usage:
        this data structure can be used to represent an ordered series of dates or times with which to associate values.
        An example is a chronology of events:
            306: Constantine is the new emperor,
            312: Battle of the Milvian Bridge,
            313: Edict of Milan,
            330: Constantine move the capital to Constantinople.
*/

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace DataStructures;

/// <summary>
///     A collection of <see cref="DateTime" /> and <see cref="TValue" />
///     sorted by <see cref="DateTime" /> field.
/// </summary>
/// <typeparam name="TValue">Value associated with a <see cref="DateTime" />.</typeparam>
public class Timeline<TValue> : ICollection<(DateTime Time, TValue Value)>, IEquatable<Timeline<TValue>>
{
    /// <summary>
    ///     Inner collection storing the timeline events as key-tuples.
    /// </summary>
    private readonly List<(DateTime Time, TValue Value)> timeline = new();

    /// <summary>
    ///     Initializes a new instance of the <see cref="Timeline{TValue}"/> class.
    /// </summary>
    public Timeline()
    {
    }

    /// <summary>
    ///     Initializes a new instance of the <see cref="Timeline{TValue}"/> class populated with an initial event.
    /// </summary>
    /// <param name="time">The time at which the given event occurred.</param>
    /// <param name="value">The event's content.</param>
    public Timeline(DateTime time, TValue value)
        => timeline = new List<(DateTime, TValue)>
        {
            (time, value),
        };

    /// <summary>
    ///     Initializes a new instance of the <see cref="Timeline{TValue}"/> class containing the provided events
    ///     ordered chronologically.
    /// </summary>
    /// <param name="timeline">The timeline to represent.</param>
    public Timeline(params (DateTime, TValue)[] timeline)
        => this.timeline = timeline
            .OrderBy(pair => pair.Item1)
            .ToList();

    /// <summary>
    /// Gets he number of unique times within this timeline.
    /// </summary>
    public int TimesCount
        => GetAllTimes().Length;

    /// <summary>
    ///     Gets all events that has occurred in this timeline.
    /// </summary>
    public int ValuesCount
        => GetAllValues().Length;

    /// <summary>
    ///     Get all values associated with <paramref name="time" />.
    /// </summary>
    /// <param name="time">Time to get values for.</param>
    /// <returns>Values associated with <paramref name="time" />.</returns>
    public TValue[] this[DateTime time]
    {
        get => GetValuesByTime(time);
        set
        {
            var overridenEvents = timeline.Where(@event => @event.Time == time).ToList();
            foreach (var @event in overridenEvents)
            {
                timeline.Remove(@event);
            }

            foreach (var v in value)
            {
                Add(time, v);
            }
        }
    }

    /// <inheritdoc />
    bool ICollection<(DateTime Time, TValue Value)>.IsReadOnly
        => false;

    /// <summary>
    ///     Gets the count of pairs.
    /// </summary>
    public int Count
        => timeline.Count;

    /// <summary>
    ///     Clear the timeline, removing all events.
    /// </summary>
    public void Clear()
        => timeline.Clear();

    /// <summary>
    ///     Copy a value to an array.
    /// </summary>
    /// <param name="array">Destination array.</param>
    /// <param name="arrayIndex">The start index.</param>
    public void CopyTo((DateTime, TValue)[] array, int arrayIndex)
        => timeline.CopyTo(array, arrayIndex);

    /// <summary>
    ///     Add an event at a given time.
    /// </summary>
    /// <param name="item">The tuple containing the event date and value.</param>
    void ICollection<(DateTime Time, TValue Value)>.Add((DateTime Time, TValue Value) item)
        => Add(item.Time, item.Value);

    /// <summary>
    ///     Check whether or not a event exists at a specific date in the timeline.
    /// </summary>
    /// <param name="item">The tuple containing the event date and value.</param>
    /// <returns>True if this event exists at the given date, false otherwise.</returns>
    bool ICollection<(DateTime Time, TValue Value)>.Contains((DateTime Time, TValue Value) item)
        => Contains(item.Time, item.Value);

    /// <summary>
    ///     Remove an event at a specific date.
    /// </summary>
    /// <param name="item">The tuple containing the event date and value.</param>
    /// <returns>True if the event was removed, false otherwise.</returns>
    bool ICollection<(DateTime Time, TValue Value)>.Remove((DateTime Time, TValue Value) item)
        => Remove(item.Time, item.Value);

    /// <inheritdoc />
    IEnumerator IEnumerable.GetEnumerator()
        => timeline.GetEnumerator();

    /// <inheritdoc />
    IEnumerator<(DateTime Time, TValue Value)> IEnumerable<(DateTime Time, TValue Value)>.GetEnumerator()
        => timeline.GetEnumerator();

    /// <inheritdoc />
    public bool Equals(Timeline<TValue>? other)
        => other is not null && this == other;

    /// <summary>
    ///     Checks whether or not two <see cref="Timeline{TValue}"/> are equals.
    /// </summary>
    /// <param name="left">The first timeline.</param>
    /// <param name="right">The other timeline to be checked against the <paramref name="left"/> one.</param>
    /// <returns>True if both timelines are similar, false otherwise.</returns>
    public static bool operator ==(Timeline<TValue> left, Timeline<TValue> right)
    {
        var leftArray = left.ToArray();
        var rightArray = right.ToArray();

        if (left.Count != rightArray.Length)
        {
            return false;
        }

        for (var i = 0; i < leftArray.Length; i++)
        {
            if (leftArray[i].Time != rightArray[i].Time
                && !leftArray[i].Value!.Equals(rightArray[i].Value))
            {
                return false;
            }
        }

        return true;
    }

    /// <summary>
    ///     Checks whether or not two <see cref="Timeline{TValue}"/> are not equals.
    /// </summary>
    /// <param name="left">The first timeline.</param>
    /// <param name="right">The other timeline to be checked against the <paramref name="left"/> one.</param>
    /// <returns>False if both timelines are similar, true otherwise.</returns>
    public static bool operator !=(Timeline<TValue> left, Timeline<TValue> right)
        => !(left == right);

    /// <summary>
    ///     Get all <see cref="DateTime" /> of the timeline.
    /// </summary>
    public DateTime[] GetAllTimes()
        => timeline.Select(t => t.Time)
            .Distinct()
            .ToArray();

    /// <summary>
    ///     Get <see cref="DateTime" /> values of the timeline that have this <paramref name="value" />.
    /// </summary>
    public DateTime[] GetTimesByValue(TValue value)
        => timeline.Where(pair => pair.Value!.Equals(value))
            .Select(pair => pair.Time)
            .ToArray();

    /// <summary>
    ///     Get all <see cref="DateTime" /> before <paramref name="time" />.
    /// </summary>
    public DateTime[] GetTimesBefore(DateTime time)
        => GetAllTimes()
            .Where(t => t < time)
            .OrderBy(t => t)
            .ToArray();

    /// <summary>
    ///     Get all <see cref="DateTime" /> after <paramref name="time" />.
    /// </summary>
    public DateTime[] GetTimesAfter(DateTime time)
        => GetAllTimes()
            .Where(t => t > time)
            .OrderBy(t => t)
            .ToArray();

    /// <summary>
    ///     Get all <see cref="TValue" /> of the timeline.
    /// </summary>
    public TValue[] GetAllValues()
        => timeline.Select(pair => pair.Value)
            .ToArray();

    /// <summary>
    ///     Get all <see cref="TValue" /> associated with <paramref name="time" />.
    /// </summary>
    public TValue[] GetValuesByTime(DateTime time)
        => timeline.Where(pair => pair.Time == time)
            .Select(pair => pair.Value)
            .ToArray();

    /// <summary>
    ///     Get all <see cref="TValue" /> before <paramref name="time" />.
    /// </summary>
    public Timeline<TValue> GetValuesBefore(DateTime time)
        => new(this.Where(pair => pair.Time < time).ToArray());

    /// <summary>
    ///     Get all <see cref="TValue" /> before <paramref name="time" />.
    /// </summary>
    public Timeline<TValue> GetValuesAfter(DateTime time)
        => new(this.Where(pair => pair.Time > time).ToArray());

    /// <summary>
    ///     Gets all values that happened at specified millisecond.
    /// </summary>
    /// <param name="millisecond">Value to look for.</param>
    /// <returns>Array of values.</returns>
    public Timeline<TValue> GetValuesByMillisecond(int millisecond)
        => new(timeline.Where(pair => pair.Time.Millisecond == millisecond).ToArray());

    /// <summary>
    ///     Gets all values that happened at specified second.
    /// </summary>
    /// <param name="second">Value to look for.</param>
    /// <returns>Array of values.</returns>
    public Timeline<TValue> GetValuesBySecond(int second)
        => new(timeline.Where(pair => pair.Time.Second == second).ToArray());

    /// <summary>
    ///     Gets all values that happened at specified minute.
    /// </summary>
    /// <param name="minute">Value to look for.</param>
    /// <returns>Array of values.</returns>
    public Timeline<TValue> GetValuesByMinute(int minute)
        => new(timeline.Where(pair => pair.Time.Minute == minute).ToArray());

    /// <summary>
    ///     Gets all values that happened at specified hour.
    /// </summary>
    /// <param name="hour">Value to look for.</param>
    /// <returns>Array of values.</returns>
    public Timeline<TValue> GetValuesByHour(int hour)
        => new(timeline.Where(pair => pair.Time.Hour == hour).ToArray());

    /// <summary>
    ///     Gets all values that happened at specified day.
    /// </summary>
    /// <param name="day">Value to look for.</param>
    /// <returns>Array of values.</returns>
    public Timeline<TValue> GetValuesByDay(int day)
        => new(timeline.Where(pair => pair.Time.Day == day).ToArray());

    /// <summary>
    ///     Gets all values that happened at specified time of the day.
    /// </summary>
    /// <param name="timeOfDay">Value to look for.</param>
    /// <returns>Array of values.</returns>
    public Timeline<TValue> GetValuesByTimeOfDay(TimeSpan timeOfDay)
        => new(timeline.Where(pair => pair.Time.TimeOfDay == timeOfDay).ToArray());

    /// <summary>
    ///     Gets all values that happened at specified day of the week.
    /// </summary>
    /// <param name="dayOfWeek">Value to look for.</param>
    /// <returns>Array of values.</returns>
    public Timeline<TValue> GetValuesByDayOfWeek(DayOfWeek dayOfWeek)
        => new(timeline.Where(pair => pair.Time.DayOfWeek == dayOfWeek).ToArray());

    /// <summary>
    ///     Gets all values that happened at specified day of the year.
    /// </summary>
    /// <param name="dayOfYear">Value to look for.</param>
    /// <returns>Array of values.</returns>
    public Timeline<TValue> GetValuesByDayOfYear(int dayOfYear)
        => new(timeline.Where(pair => pair.Time.DayOfYear == dayOfYear).ToArray());

    /// <summary>
    ///     Gets all values that happened at specified month.
    /// </summary>
    /// <param name="month">Value to look for.</param>
    /// <returns>Array of values.</returns>
    public Timeline<TValue> GetValuesByMonth(int month)
        => new(timeline.Where(pair => pair.Time.Month == month).ToArray());

    /// <summary>
    ///     Gets all values that happened at specified year.
    /// </summary>
    /// <param name="year">Value to look for.</param>
    /// <returns>Array of values.</returns>
    public Timeline<TValue> GetValuesByYear(int year)
        => new(timeline.Where(pair => pair.Time.Year == year).ToArray());

    /// <summary>
    ///     Add an event at a given <paramref name="time"/>.
    /// </summary>
    /// <param name="time">The date at which the event occurred.</param>
    /// <param name="value">The event value.</param>
    public void Add(DateTime time, TValue value)
    {
        timeline.Add((time, value));
    }

    /// <summary>
    ///     Add a set of <see cref="DateTime" /> and <see cref="TValue" /> to the timeline.
    /// </summary>
    public void Add(params (DateTime, TValue)[] timeline)
    {
        this.timeline.AddRange(timeline);
    }

    /// <summary>
    ///     Append an existing timeline to this one.
    /// </summary>
    public void Add(Timeline<TValue> timeline)
        => Add(timeline.ToArray());

    /// <summary>
    ///     Add a <paramref name="value" /> associated with <see cref="DateTime.Now" /> to the timeline.
    /// </summary>
    public void AddNow(params TValue[] value)
    {
        var now = DateTime.Now;
        foreach (var v in value)
        {
            Add(now, v);
        }
    }

    /// <summary>
    ///     Check whether or not a event exists at a specific date in the timeline.
    /// </summary>
    /// <param name="time">The date at which the event occurred.</param>
    /// <param name="value">The event value.</param>
    /// <returns>True if this event exists at the given date, false otherwise.</returns>
    public bool Contains(DateTime time, TValue value)
        => timeline.Contains((time, value));

    /// <summary>
    ///     Check if timeline contains this set of value pairs.
    /// </summary>
    /// <param name="timeline">The events to checks.</param>
    /// <returns>True if any of the events has occurred in the timeline.</returns>
    public bool Contains(params (DateTime, TValue)[] timeline)
        => timeline.Any(@event => Contains(@event.Item1, @event.Item2));

    /// <summary>
    ///     Check if timeline contains any of the event of the provided <paramref name="timeline"/>.
    /// </summary>
    /// <param name="timeline">The events to checks.</param>
    /// <returns>True if any of the events has occurred in the timeline.</returns>
    public bool Contains(Timeline<TValue> timeline)
        => Contains(timeline.ToArray());

    /// <summary>
    ///     Check if timeline contains any of the time of the provided <paramref name="times"/>.
    /// </summary>
    /// <param name="times">The times to checks.</param>
    /// <returns>True if any of the times is stored in the timeline.</returns>
    public bool ContainsTime(params DateTime[] times)
    {
        var storedTimes = GetAllTimes();
        return times.Any(value => storedTimes.Contains(value));
    }

    /// <summary>
    ///     Check if timeline contains any of the event of the provided <paramref name="values"/>.
    /// </summary>
    /// <param name="values">The events to checks.</param>
    /// <returns>True if any of the events has occurred in the timeline.</returns>
    public bool ContainsValue(params TValue[] values)
    {
        var storedValues = GetAllValues();
        return values.Any(value => storedValues.Contains(value));
    }

    /// <summary>
    ///     Remove an event at a specific date.
    /// </summary>
    /// <param name="time">The date at which the event occurred.</param>
    /// <param name="value">The event value.</param>
    /// <returns>True if the event was removed, false otherwise.</returns>
    public bool Remove(DateTime time, TValue value)
        => timeline.Remove((time, value));

    /// <summary>
    ///     Remove a set of value pairs from the timeline.
    /// </summary>
    /// <param name="timeline">An collection of all events to remove.</param>
    /// <returns>Returns true if the operation completed successfully.</returns>
    public bool Remove(params (DateTime, TValue)[] timeline)
    {
        var result = false;
        foreach (var (time, value) in timeline)
        {
            result |= this.timeline.Remove((time, value));
        }

        return result;
    }

    /// <summary>
    ///     Remove an existing timeline from this timeline.
    /// </summary>
    /// <param name="timeline">An collection of all events to remove.</param>
    /// <returns>Returns true if the operation completed successfully.</returns>
    public bool Remove(Timeline<TValue> timeline)
        => Remove(timeline.ToArray());

    /// <summary>
    ///     Remove a value pair from the timeline if the time is equal to <paramref name="times" />.
    /// </summary>
    /// <returns>Returns true if the operation completed successfully.</returns>
    public bool RemoveTimes(params DateTime[] times)
    {
        var isTimeContainedInTheTimeline = times.Any(time => GetAllTimes().Contains(time));

        if (!isTimeContainedInTheTimeline)
        {
            return false;
        }

        var eventsToRemove = times.SelectMany(time =>
            timeline.Where(@event => @event.Time == time))
            .ToList();

        foreach (var @event in eventsToRemove)
        {
            timeline.Remove(@event);
        }

        return true;
    }

    /// <summary>
    ///     Remove a value pair from the timeline if the value is equal to <paramref name="values" />.
    /// </summary>
    /// <returns>Returns true if the operation completed successfully.</returns>
    public bool RemoveValues(params TValue[] values)
    {
        var isValueContainedInTheTimeline = values.Any(v => GetAllValues().Contains(v));

        if (!isValueContainedInTheTimeline)
        {
            return false;
        }

        var eventsToRemove = values.SelectMany(value =>
            timeline.Where(@event => EqualityComparer<TValue>.Default.Equals(@event.Value, value)))
            .ToList();

        foreach (var @event in eventsToRemove)
        {
            timeline.Remove(@event);
        }

        return true;
    }

    /// <summary>
    ///     Convert the timeline to an array.
    /// </summary>
    /// <returns>
    /// The timeline as an array of tuples of (<see cref="DateTime"/>, <typeparamref name="TValue"/>).
    /// </returns>
    public (DateTime Time, TValue Value)[] ToArray()
        => timeline.ToArray();

    /// <summary>
    ///     Convert the timeline to a list.
    /// </summary>
    /// <returns>
    /// The timeline as a list of tuples of (<see cref="DateTime"/>, <typeparamref name="TValue"/>).
    /// </returns>
    public IList<(DateTime Time, TValue Value)> ToList()
        => timeline;

    /// <summary>
    ///     Convert the timeline to a dictionary.
    /// </summary>
    /// <returns>
    /// The timeline as an dictionary of <typeparamref name="TValue"/> by <see cref="DateTime"/>.
    /// </returns>
    public IDictionary<DateTime, TValue> ToDictionary()
        => timeline.ToDictionary(@event => @event.Time, @event => @event.Value);

    /// <inheritdoc />
    public override bool Equals(object? obj)
        => obj is Timeline<TValue> otherTimeline
           && this == otherTimeline;

    /// <inheritdoc />
    public override int GetHashCode()
        => timeline.GetHashCode();
}