1
$\begingroup$

I am writing a UI that needs to display a chat log, similar to Slack and Discord. In addition to being able to scroll and lazy-fetch additional pages in either direction, I need to be able to jump to a specific point in time and fetch the message records "around" it (a backend API problem, of course).

I need a "lazy range" data structure that can store "intervals" (each with bounds and an ordered list of items), respond to queries for "more before" or "more after" including items and some kind of indication of gaps, and insert new intervals (pages fetched from the backend), merging existing intervals when overlaps are detected and eliminating the gap indicator.

I have not been able to find an existing named data structure that handles this kind of access pattern. It seems similar to a range tree but has only a single level of interval nodes, and it is similar to an interval tree in that we want to detect bound overlaps/gaps, but then we want to merge overlaps. Does such a data structure already exist?

$\endgroup$
5
  • 1
    $\begingroup$ Doesn't sql do this for you? Can you specify more formally the operations you need? $\endgroup$
    – Pål GD
    Feb 9, 2022 at 19:10
  • $\begingroup$ @PålGD... SQL? There is no SQL involved anywhere in this entire application, frontend or backend. This is about the client UI storing messages that it retrieves on-demand from a REST API. $\endgroup$ Feb 9, 2022 at 19:49
  • $\begingroup$ Please specify more precisely the operations you want to perform on this data structure. I don't know what "lazy range" means. From your motivation I don't know why you need to store intervals; it seems sufficient to store a sequence of records, with a timestep and/or index for each item. I don't understand why you have rejected SQL. Even if you currently aren't using SQL, you could be, if it solved your problem. $\endgroup$
    – D.W.
    Feb 9, 2022 at 19:58
  • $\begingroup$ @D.W. The problem is knowing when there might be additional records in between the ones I know about that I haven't fetched yet. SQL seems about as relevant as GraphQL; the persistence isn't in a relational database, and this is specifically about keeping track of segments with lacunae between them. $\endgroup$ Feb 9, 2022 at 23:37
  • $\begingroup$ I'm not the one suggesting SQL, but I'd presume the point of SQL is not the persistence, but rather that it provides ability to query by ranges and complex predicates which might be sufficient for all of your needs. No need to use a full database; even sqlite might be sufficient. Again, I'm not the one advocating SQL, and I hope you'll edit your question to make the requirements clearer, as I suggested above. $\endgroup$
    – D.W.
    Feb 10, 2022 at 5:45

2 Answers 2

1
$\begingroup$

The binary search tree of @dw seems a good solution.

For something simpler, if the time density of messages is homogeneous, you can consider successive time intervals of a well-chosen fixed duration and associate to every interval the doubly-linked list of events that occurred, in chronological order. The intervals are stored in an array.

From the current event, you can move forward or backward, and switch to the next/previous interval easily. For random access, just find the relevant interval.

The duration should be such that a single interval roughly corresponds to the size of the scrolled area.


If your data structure is external (on disk), a B-tree indexed on the timestamp is appropriate.

$\endgroup$
0
$\begingroup$

I find it hard to understand your requirements, but I suspect a balanced binary search tree might meet your needs. I assume each record is associated with a timestamp, and you want to support queries like "find the record nearest time $t$", "find the 50 records immediately preceding time $t$", "find the $i$th record", and so on.

All of those can be handled in $O(\log n)$ time with a balanced binary search tree.

I am assuming here that each record represents a single chat message, and so has a single timestamp associated with it, and that a page is simply a window of consecutive records.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.