CODEWITHSUNDEEP
algorithmheapguavafinger-treeredisson
V P
V P

Reputation: 865

Q: Optimized data structure for Branched and Versioned entities

Given an entity (say a file or a library/package) that can evolve its versions and branches over time, looking for a optimized data structure that lets me navigate through the versions to a specific instance of the entity.

For example (a bit contrived example) given entries such as:

MySIMDIntristicsLib.v1~archMIPS.v1~fbsd.v1 
MySIMDIntristicsLib.v1~archMIPS.v2~fbsd.v1
MySIMDIntristicsLib.v1~archX86.v1~win.v1
MySIMDIntristicsLib.v1~archX86.v2~win.v1
MySIMDIntristicsLib.v1~archX86.v2~win.v2
MySIMDIntristicsLib.v2~archX86.v1~win.v1


// get latest across all branches 
get( Entity="MySIMDIntristicsLib", branch[(latest) "~"] ) 
returns: "MySIMDIntristicsLib.v2~archX86.v1~win.v1"


// get latest across  archMips/fbsd branch 
get( Entity="MySIMDIntristicsLib", branch[(latest) "archMIPS~fbsd"] ) 
returns: "MySIMDIntristicsLib.v1~archMIPS.v2~fbsd.v1"



// get earliest   for archX86 v2 branch 
get( Entity="MySIMDIntristicsLib", branch[(earliest) "archX86.v2~"] ) 
returns "MySIMDIntristicsLib.v1~archX86.v2~win.v1"

I suspect something like that already exists (since package management or source code management leverages similar to the above access semantics).

I was looking for in-memory data structures for the above with good Latest/Earliest access time, but also descent insert/remove speed.

In a brutal force approach, I think the above can be implemented using Min Max heap for every branch that can have versions.

However, there may be something better already out there. I also checked my usual source of these types of things, Redisson -- but did not see if there is an explicit implementation of the data structure for the above

The DSL above is of my own construction, probably has some holes too, so if there are better DSLs/APIs for this kind of data access -- would like to learn as well.

Upvotes: 0

Views: 71

Answers (1)

mfulton26
mfulton26

Reputation: 31234

If your list is small then the quickest solution is likely to scan a sorted collection of your entities filtering out those you don't want or simply grabbing the first that meets your criteria (e.g. you could iterate over your entities above in reverse order and grab the first "archMIPS~fbsd" to get the "latest").

If your list is large then you'll want to index your branches/versions and you can do so using an in-memory database such as H2 Database Engine, HSQLDB, CQEngine, etc.

Upvotes: 0

Related Questions