using System.Collections.Generic;
using System.Diagnostics;
public static void Main()
FrameIndex<Frame> frameIndex = new FrameIndex<Frame>();
Random random = new Random();
List<int> knownFrames = new ();
Stopwatch addFramesStopwatch = new Stopwatch();
Stopwatch lookupStopwatch = new Stopwatch();
for(int i=0; i<=15000; i++){
int ms = random.Next(1, 1000000);
addFramesStopwatch.Start();
frameIndex.AddFrame(ms,new Frame(ms, new Vector3(1, 2, 3)));
addFramesStopwatch.Stop();
TimeSpan timeTaken = addFramesStopwatch.Elapsed;
string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:000}",
timeTaken.Hours, timeTaken.Minutes, timeTaken.Seconds,
Console.WriteLine("Add Frames Time taken: " + elapsedTime);
for(int i=0; i<=1000; i++){
int frameMs = random.Next(1, 1000000);
Frame nearestPastFrame = frameIndex.GetNearestPastFrame(frameMs);
TimeSpan timeTaken2 = lookupStopwatch.Elapsed;
string elapsedTime2 = String.Format("{0:00}:{1:00}:{2:00}.{3:000}",
timeTaken2.Hours, timeTaken2.Minutes, timeTaken2.Seconds,
timeTaken2.Milliseconds);
Console.WriteLine("Lookups Time taken: " + elapsedTime2);
public Vector3(float x, float y, float z)
public override string ToString()
return $"({x}, {y}, {z})";
public int FrameMs { get; set; }
public Vector3 Data { get; set; }
public Frame(int frameMs, Vector3 data)
public class FrameIndex<T>
private readonly SortedDictionary<int, SortedDictionary<int, SortedDictionary<int, T>>> dataTree = new ();
private SortedDictionary<int, int[]> _blockTimes = new SortedDictionary<int, int[]>();
private int GetBlockNumberForFrame(int frameMs)
return frameMs < 100000 ? 1 : frameMs < 200000 ? 2 : frameMs < 300000 ? 3 : frameMs < 400000 ? 4 : frameMs < 500000 ? 5 : frameMs < 600000 ? 6 : frameMs < 700000 ? 7 : frameMs < 800000 ? 8 : frameMs < 900000 ? 9 : 10;
private void TrackBlock(int block, int[] blockTimes)
_blockTimes.Add(block,blockTimes);
private int GetLevelKey(int frameMs, int level)
case 1: return GetBlockNumberForFrame(frameMs);
case 2: return (frameMs % 100000) / 10000;
default: throw new ArgumentOutOfRangeException(nameof(level));
private (int, int) GetLevelKeys(int frameMs)
int level1 = GetLevelKey(frameMs, 1);
int level2 = GetLevelKey(frameMs, 2);
public T Get(int frameMs)
var (level1,level2) = GetLevelKeys(frameMs);
if (dataTree.TryGetValue(level1, out var level1Dict) &&
level1Dict.TryGetValue(level2, out var frameDict))
if (frameDict.TryGetValue(frameMs, out var frame))
public void AddFrame(int frameMs, T frame)
int key1 = GetLevelKey(frameMs, 1);
int key2 = GetLevelKey(frameMs, 2);
if (!dataTree.ContainsKey(key1))
new SortedDictionary<int, SortedDictionary<int, T>>();
if (!dataTree[key1].ContainsKey(key2))
dataTree[key1][key2] = new SortedDictionary<int, T>();
dataTree[key1][key2][key3] = frame;
public T GetNearestPastFrame(int frameMs)
var (level1,level2) = GetLevelKeys(frameMs);
SearchNearestInLevel(dataTree, level1, level2, frameMs, 0, out T nearestFrame, isNext:false);
public T GetNearestFutureFrame(int frameMs)
var (level1,level2) = GetLevelKeys(frameMs);
SearchNearestInLevel(dataTree, level1, level2, frameMs, 0, out T nearestFrame, isNext:true);
private bool SearchNearestInLevel<TValue>(SortedDictionary<int, TValue> level, int level1, int level2, int frameMs, int currentLevel, out T nearestFrame,bool isNext=false)
string indent = currentLevel == 1 ? " " : currentLevel == 2 ? " " : "";
if (level == null || level.Count == 0) return false;
var keys = new List<int>(level.Keys);
int searchKey = currentLevel == 0 ? level1 : currentLevel == 1 ? level2 : frameMs;
int index = keys.BinarySearch(searchKey);
SortedDictionary<int, T> sortedDict = level as SortedDictionary<int, T>;
nearestFrame = sortedDict[frameMs];
if(currentLevel == 0 && SearchNearestInLevel(dataTree[keys[index]], level1, level2, frameMs, currentLevel + 1, out nearestFrame)){
else if(currentLevel == 1){
var nextLevel = level[keys[index]] as SortedDictionary<int, T>;
if(SearchNearestInLevel(nextLevel, level1, level2, frameMs, currentLevel + 1, out nearestFrame)){
nearestFrame = TraverseAdjacent(dataTree, frameMs, isNext, currentLevel, providedIndex: index);
else if(currentLevel == 1){
var branch = level as SortedDictionary<int, SortedDictionary<int, T>>;
nearestFrame = TraverseAdjacent(branch, frameMs, isNext, currentLevel, providedIndex: index);
else if(currentLevel == 2){
var branch = level as SortedDictionary<int, T>;
nearestFrame = TraverseAdjacent(branch, frameMs, isNext, currentLevel, providedIndex: index);
return !EqualityComparer<T>.Default.Equals(nearestFrame, default(T));
public T GetPreviousFrame(int frameMs)
return GetAdjacentFrame(frameMs, isNext: false);
public T GetNextFrame(int frameMs)
return GetAdjacentFrame(frameMs, isNext: true);
private T GetAdjacentFrame(int frameMs, bool isNext)
var (level1,level2) = GetLevelKeys(frameMs);
T existingFrame = Get(frameMs);
if(EqualityComparer<T>.Default.Equals(existingFrame, default(T)))
throw new Exception($"Frame ({frameMs}) provided to GetAdjacentFrame does not exist");
var leafNode = dataTree[level1][level2];
if (leafNode != null && leafNode.ContainsKey(frameMs))
var keys = leafNode.Keys.ToList();
int index = keys.BinarySearch(frameMs);
if (!isNext && index > 0)
return leafNode[keys[index - 1]];
if(isNext && index >= 0 && index < keys.Count-1)
return leafNode[keys[index + 1]];
return TraverseAdjacent(dataTree[level1], frameMs, isNext, 1);
private T TraverseAdjacent<TValue>(SortedDictionary<int, TValue> level, int frameMs, bool isNext, int currentLevel = 2, int? providedIndex = null)
var (level1, level2) = GetLevelKeys(frameMs);
var keys = level.Keys.ToList();
int searchKey = currentLevel == 0 ? level1 : level2;
int index = providedIndex ?? keys.BinarySearch(searchKey);
int nearestIndex = (index < 0 ? ~index : index);
int prevOrNextIndex = nearestIndex + (isNext ? 1 : -1);
int lastIndex = keys.Count - 1;
if (prevOrNextIndex < 0 || prevOrNextIndex > lastIndex)
if (currentLevel == 0) return default;
return TraverseAdjacent(dataTree,frameMs,isNext,currentLevel-1);
SortedDictionary<int, SortedDictionary<int, T>> prevLevel1 = dataTree[level1];
return TraverseAdjacent(prevLevel1,frameMs,isNext,currentLevel-1);
var branch = level as SortedDictionary<int, SortedDictionary<int, T>>;
return branch[keys[prevOrNextIndex]].First().Value;
} else if(currentLevel == 2){
var branch = level as SortedDictionary<int, T>;
return branch[keys[prevOrNextIndex]];
return dataTree[keys[prevOrNextIndex]].Last().Value.Last().Value;
var branch = level as SortedDictionary<int, SortedDictionary<int, T>>;
return branch[keys[prevOrNextIndex]].Last().Value;
} else if(currentLevel == 2){
var branch = level as SortedDictionary<int, T>;
return branch[keys[prevOrNextIndex]];
return dataTree[keys[prevOrNextIndex]].First().Value.First().Value;