TemporalCollections 1.3.0

<p align="center"> <img src="assets/logo.svg" alt="TemporalCollections logo" width="560"> </p>

TemporalCollections

TemporalCollections is a high-performance, thread-safe .NET library providing temporal data structures. Each structure associates items with precise insertion timestamps, enabling efficient time-based querying, filtering, and cleanup. This project is ideal for scenarios where you need to store, query, and manage data with temporal semantics, such as event streams, time-windowed analytics, caching with expiry, or temporal state tracking.

Table of Contents

• Overview
• Core Concept: TemporalItem<T>
• Available Collections
• Usage Guidance
• ITimeQueryable<T> Interface
  • Key Methods
• Getting Started with TemporalCollections
  • Installation
  • Basic usage
  • Common queries via ITimeQueryable<T>
• Monotonic Timestamp Guarantee
• Performance Benchmarks
• Threading Model & Big-O Cheatsheet
• Notes
• Contributing
• License
• Contact

Overview

TemporalCollections provides multiple thread-safe generic collections where Each item is timestamped at insertion using a strictly monotonic UTC clock (DateTimeOffset.UtcNow). These collections expose interfaces for querying items based on their timestamps, removing old or expired entries efficiently, and preserving concurrency guarantees.

The key design goals are:

• Temporal semantics: Items are stored with precise insertion timestamps
• Thread safety: Suitable for concurrent multi-threaded environments
• Time-based querying: Fast retrieval of items within time ranges
• Efficient cleanup: Removing stale or expired data without locking entire collections for long

Core Concept: TemporalItem<T>

At the heart of all collections lies the TemporalItem<T> struct:

• Wraps an immutable value T with a timestamp (DateTimeOffset) indicating the moment of insertion
• Guarantees strictly increasing timestamps even under rapid or concurrent creation, using atomic operations
• Provides a timestamp comparer for sorting and searching

Available Collections

Usage Guidance

ITimeQueryable<T> Interface

All temporal collections implement the ITimeQueryable<T> interface, which provides a common set of methods to query and manage items based on their associated timestamps. This interface enables consistent time-based operations across different collection types.

Key Methods

• GetInRange(DateTimeOffset from, DateTimeOffset to)
  Returns an enumerable of temporal items whose timestamps fall within the inclusive range [from, to]. This allows filtering the collection by any desired time window.

• RemoveOlderThan(DateTimeOffset cutoff)
  Removes all items with timestamps strictly older than the specified cutoff time (Timestamp < cutoff). This method is useful for pruning outdated data and maintaining collection size.

• CountInRange(DateTimeOffset from, DateTimeOffset to)
  Returns the number of items with timestamps in the inclusive range [from, to]. Throws if to < from.

• GetTimeSpan()
  Returns latest.Timestamp - earliest.Timestamp. Returns TimeSpan.Zero if the collection is empty or has a single item.

• Clear()
  Removes all items from the collection.

• RemoveRange(DateTimeOffset from, DateTimeOffset to)
  Removes all items with timestamps in the inclusive range [from, to]. Throws if to < from.

• GetLatest()
  Returns the most recent item (max timestamp), or null if empty.

• GetEarliest()
  Returns the oldest item (min timestamp), or null if empty.

• GetBefore(DateTimeOffset time)
  Returns all items with Timestamp < time (strictly before), ordered by ascending timestamp.

• GetAfter(DateTimeOffset time)
  Returns all items with Timestamp > time (strictly after), ordered by ascending timestamp.

• CountSince(DateTimeOffset from)
  Counts the number of items with timestamp greater than or equal to the specified cutoff.

• GetNearest(DateTimeOffset time)
  Retrieves the item whose timestamp is closest to the specified time.

• GetAtOrBefore(DateTimeOffset time)
  Retrieves the latest item whose timestamp is less than or equal to the specified time, or null if none exists.

• TryGetAtOrBefore(DateTimeOffset time, out TemporalItem<T>? item)
  Attempts to retrieve the latest item whose timestamp is less than or equal to the specified time.

• GetAtOrAfter(DateTimeOffset time)
  Retrieves the earliest item whose timestamp is greater than or equal to the specified time, or null if none exists.

• TryGetAtOrAfter(DateTimeOffset time, out TemporalItem<T>? item)
  Attempts to retrieve the earliest item whose timestamp is greater than or equal to the specified time.

• CountBefore(DateTimeOffset time)
  Counts the number of items whose timestamp is strictly before the specified time.

• CountAfter(DateTimeOffset time)
  Counts the number of items whose timestamp is strictly after the specified time.

These methods collectively support efficient and thread-safe temporal queries and cleanups, allowing each collection to manage its items according to their timestamps while exposing a unified API.

🚀 Getting Started with TemporalCollections

This section shows how to install and use TemporalCollections in your .NET projects with simple examples.

Installation

dotnet add package TemporalCollections

Basic usage

TemporalQueue<T>

using System;
using System.Linq;
using TemporalCollections.Collections;

var queue = new TemporalQueue<string>();

// Enqueue items (timestamps are assigned automatically)
queue.Enqueue("event-1");
queue.Enqueue("event-2");

// Peek oldest without removing (throws if empty)
var oldest = queue.Peek();
Console.WriteLine($"Oldest: {oldest.Value} @ {oldest.Timestamp}");

// Try-peek: safe non-throwing variant
if (queue.TryPeek(out var peeked))
    Console.WriteLine($"Peek: {peeked!.Value} @ {peeked.Timestamp}");

// Dequeue oldest (throws if empty)
var dequeued = queue.Dequeue();
Console.WriteLine($"Dequeued: {dequeued.Value} @ {dequeued.Timestamp}");

// Try-dequeue: safe non-throwing variant
while (queue.TryDequeue(out var item))
    Console.WriteLine($"Dequeued: {item!.Value} @ {item.Timestamp}");

// Query by time range (inclusive)
var from = DateTime.UtcNow.AddMinutes(-5);
var to   = DateTime.UtcNow;
var inRange = queue.GetInRange(from, to);
foreach (var item in inRange)
{
    Console.WriteLine($"In range: {item.Value} @ {item.Timestamp}");
}

TemporalSet<T>

using System;
using TemporalCollections.Collections;

var set = new TemporalSet<int>();

set.Add(1);
set.Add(2);
set.Add(2);

Console.WriteLine(set.Contains(1));

// Remove older than a cutoff
var cutoff = DateTime.UtcNow.AddMinutes(-10);
set.RemoveOlderThan(cutoff);

// Snapshot of all items ordered by timestamp
var items = set.GetItems();

TemporalDictionary<TKey, TValue>

using System;
using System.Linq;
using TemporalCollections.Collections;

var dict = new TemporalDictionary<string, string>();

dict.Add("user:1", "login");
dict.Add("user:2", "logout");
dict.Add("user:1", "refresh");

// Range query across all keys
var from = DateTime.UtcNow.AddMinutes(-1);
var to   = DateTime.UtcNow.AddMinutes(1);
var all = dict.GetInRange(from, to);

// Range query for a specific key
var user1 = dict.GetInRange("user:1", from, to);

// Compute span covered by all events
var span = dict.GetTimeSpan();
Console.WriteLine($"Span: {span}");

// Remove a time window across all keys
dict.RemoveRange(from, to);

TemporalStack<T>

using System;
using System.Linq;
using TemporalCollections.Collections;

var stack = new TemporalStack<string>();

// Push (timestamps assigned automatically, monotonic UTC)
stack.Push("first");
stack.Push("second");

// Peek last pushed (does not remove)
var top = stack.Peek();
Console.WriteLine($"Top: {top.Value} @ {top.Timestamp}");

// Pop last pushed (removes)
var popped = stack.Pop();
Console.WriteLine($"Popped: {popped.Value}");

// Time range query (inclusive)
var from = DateTime.UtcNow.AddMinutes(-5);
var to   = DateTime.UtcNow;
var items = stack.GetInRange(from, to).OrderBy(i => i.Timestamp);

// Remove older than cutoff
var cutoff = DateTime.UtcNow.AddMinutes(-10);
stack.RemoveOlderThan(cutoff);

TemporalSlidingWindowSet<T>

using System;
using System.Linq;
using TemporalCollections.Collections;

var window = TimeSpan.FromMinutes(10);
var swSet = new TemporalSlidingWindowSet<string>(window);

// Add unique items (insertion timestamp recorded)
swSet.Add("A");
swSet.Add("B");

// Periodically expire items older than the window
swSet.RemoveExpired();

// Snapshot (ordered by timestamp)
var snapshot = swSet.GetItems().ToList();

// Query by time range
var from = DateTime.UtcNow.AddMinutes(-5);
var to   = DateTime.UtcNow;
var inRange = swSet.GetInRange(from, to);

// Manual cleanup by cutoff (if needed)
swSet.RemoveOlderThan(DateTime.UtcNow.AddMinutes(-30));

TemporalSortedList<T>

using System;
using System.Linq;
using TemporalCollections.Collections;

var list = new TemporalSortedList<int>();

// Add items (kept sorted by timestamp internally)
list.Add(10);
list.Add(20);
list.Add(30);

// Fast range query via binary search (inclusive)
var from = DateTime.UtcNow.AddSeconds(-30);
var to   = DateTime.UtcNow;
var inRange = list.GetInRange(from, to);

// Before / After helpers
var before = list.GetBefore(DateTime.UtcNow);
var after  = list.GetAfter(DateTime.UtcNow.AddSeconds(-5));

// Housekeeping
list.RemoveOlderThan(DateTime.UtcNow.AddMinutes(-1));
Console.WriteLine($"Span: {list.GetTimeSpan()}");

TemporalPriorityQueue<TPriority, TValue>

using System;
using System.Linq;
using TemporalCollections.Collections;

var pq = new TemporalPriorityQueue<int, string>();

// Enqueue with explicit priority (lower number = higher priority)
pq.Enqueue("high", priority: 1);
pq.Enqueue("low",  priority: 10);

// TryPeek (does not remove)
if (pq.TryPeek(out var next))
{
    Console.WriteLine($"Peek: {next}");
}

// TryDequeue (removes highest-priority; stable by insertion time)
while (pq.TryDequeue(out var val))
{
    Console.WriteLine($"Dequeued: {val}");
}

// Time-based queries are also available
var from = DateTime.UtcNow.AddMinutes(-5);
var to   = DateTime.UtcNow;
var items = pq.GetInRange(from, to);

Console.WriteLine($"Count in range: {pq.CountInRange(from, to)}");

TemporalCircularBuffer<T>

using System;
using System.Linq;
using TemporalCollections.Collections;

// Fixed-capacity ring buffer; overwrites oldest when full
var buf = new TemporalCircularBuffer<string>(capacity: 3);

buf.Add("A");
buf.Add("B");
buf.Add("C");
buf.Add("D"); // Overwrites "A"

// Snapshot (oldest -> newest)
var snapshot = buf.GetSnapshot();
foreach (var it in snapshot)
{
    Console.WriteLine($"{it.Value} @ {it.Timestamp}");
}

// Range queries
var from = DateTime.UtcNow.AddMinutes(-5);
var to   = DateTime.UtcNow;
var inRange = buf.GetInRange(from, to);

// Remove a time window
buf.RemoveRange(from, to);

// Cleanup by cutoff (keeps >= cutoff)
buf.RemoveOlderThan(DateTime.UtcNow.AddMinutes(-1));

TemporalIntervalTree<T>

using System;
using System.Linq;
using TemporalCollections.Collections;

var tree = new TemporalIntervalTree<string>();

var now = DateTime.UtcNow;
tree.Insert(now, now.AddMinutes(10), "session:A");
tree.Insert(now.AddMinutes(5), now.AddMinutes(15), "session:B");

// Overlap query (values only)
var overlapValues = tree.Query(now.AddMinutes(7), now.AddMinutes(12));
// Overlap query (with timestamps = interval starts)
var overlapItems  = tree.GetInRange(now.AddMinutes(7), now.AddMinutes(12));

Console.WriteLine($"Overlaps: {string.Join(", ", overlapValues)}");

// Remove intervals that ended before a cutoff
tree.RemoveOlderThan(now.AddMinutes(9));

TemporalCache<TKey, TValue>

using System;
using TemporalCollections.Collections;

// Entries expire 5 minutes after write; use slidingExpiration: true to extend on read
var cache = new TemporalCache<string, int>(TimeSpan.FromMinutes(5));

cache.Set("user:1", 42);
cache.Set("token", 7, TimeSpan.FromSeconds(30)); // per-entry TTL

if (cache.TryGetValue("user:1", out var value))
    Console.WriteLine($"user:1 = {value}");

var computed = cache.GetOrAdd("user:2", _ => 99);
var ttl = cache.GetTimeToLive("token"); // remaining lifetime or null
cache.Touch("user:1");                  // reset lifetime

// Eager cleanup of expired entries
int removed = cache.RemoveExpired();

// Time queries on write timestamps of live entries
var recent = cache.GetAfter(DateTime.UtcNow.AddMinutes(-1));

Common queries via ITimeQueryable<T>

var latest   = collection.GetLatest();   // most recent item or null
var earliest = collection.GetEarliest(); // oldest item or null

var before = collection.GetBefore(DateTime.UtcNow); // strictly <
var after  = collection.GetAfter(DateTime.UtcNow);  // strictly >

var count = collection.CountInRange(DateTime.UtcNow.AddSeconds(-30), DateTime.UtcNow);

var span = collection.GetTimeSpan(); // latest.Timestamp - earliest.Timestamp (or TimeSpan.Zero)

Monotonic Timestamp Guarantee

A key feature of the temporal collections is the guarantee that timestamps assigned to items are strictly monotonically increasing, even when multiple items are created concurrently or in rapid succession.

This is achieved through the TemporalItem<T> record, which uses an atomic compare-and-swap operation on a static internal timestamp counter. When creating a new temporal item, the current UTC timestamp in ticks (DateTimeOffset.UtcTicks) is retrieved and compared against the last assigned timestamp:

• If the current timestamp is greater than the last one, it is used as-is.
• If the current timestamp is less than or equal to the last assigned timestamp (e.g., due to rapid creation or clock precision limits), the timestamp is artificially incremented by one tick.

This approach ensures:

• Uniqueness: No two items share the exact same timestamp.
• Strict ordering: Timestamps always increase in time order.
• Thread safety: The mechanism works correctly across multiple threads without race conditions.

By enforcing this monotonic timestamp ordering, the temporal collections can rely on consistent time-based queries and maintain correct chronological order of items.

Custom Clock (TimeProvider)

All collections accept an optional TimeProvider (.NET 8+) used for timestamps and expiration. Existing constructors keep using TimeProvider.System, so current code is unaffected.

using Microsoft.Extensions.Time.Testing; // FakeTimeProvider (optional, for tests)

var clock = new FakeTimeProvider(DateTimeOffset.UtcNow);
var window = new TemporalSlidingWindowSet<string>(TimeSpan.FromMinutes(5), clock);

window.Add("a");
clock.Advance(TimeSpan.FromMinutes(6)); // no real waiting
window.RemoveExpired();                 // "a" is removed

TemporalItem<T>.Create(value, timeProvider) is also available. Monotonicity is guaranteed per closed generic type and per TimeProvider instance.

📈 Performance Benchmarks

We provide detailed performance measurements for all temporal data structures, including insertion, range queries, and removal operations.
The full benchmark results are available here: docs/benchmarks/benchmarks.md These benchmarks help compare trade-offs between different collections and guide future optimizations.

Threading Model & Big-O Cheatsheet

All collections are thread-safe. Locking granularity and common operations (amortized):

n = items, m = matches, k = removed.

Notes

• Deterministic ordering: query results are returned in ascending timestamp order.
• Snapshot semantics: methods that return enumerables/lists provide a stable snapshot at call time.
• Thread-safety: all operations are designed to be thread-safe per collection.
• Binary-search range queries: TemporalDictionary and other sorted collections use LowerBound/UpperBound binary search internally, reducing range queries, RemoveOlderThan, RemoveRange, CountInRange, and CountSince from O(n) to O(log n + m).
• Try-pattern: TemporalQueue exposes TryDequeue/TryPeek for non-throwing access, consistent with TemporalPriorityQueue and standard .NET collection conventions.
• Intervals: for interval-based collections, the Timestamp used by this interface refers to the interval start.

⚠️ Since v1.1.0, internal timestamp storage has been migrated from DateTime to DateTimeOffset (UTC). Public APIs remain DateTime for backward compatibility, but internal semantics are now strictly UTC-aware.

Contributing

Thank you for considering to help out with the source code! If you'd like to contribute, please fork, fix, commit and send a pull request for the maintainers to review and merge into the main code base.

Getting started with Git and GitHub

• Setting up Git
• Fork the repository
• Open an issue if you encounter a bug or have a suggestion for improvements/features

License

TemporalCollections source code is available under MIT License, see license in the source.

Contact

Please contact at francesco.delre[at]protonmail.com for any details.