I am looking for a map-like data structure with the following properties:

  • it uses subsets of some set S as keys. The size of S is potentially unbounded, but does not change during the runtime
  • the values associated with the keys are generic objects - poiters/references. Their properties are not important for the data structure
  • the size of the subsets, used as keys, can vary between keys, i.e. one key can be a 3 element subset, while another might be a 7 element subset
  • it must support insertion of new entries (key - value pairs) into the "map"
  • it does not need to support removal of entries from the "map"
  • if I have some subset B of S and want to get a value from the map using B, I want the following:
    • find the largest key (the key with the larges cardinality) in the map that is a subset of B, and return it along with the value associated with it
    • if B itself is a key in the map, I want to return the entry for B
    • if there are multiple keys that satisfy this condition, I don't care which one gets returned
    • if there are multiple keys that satisfy this condition, I don't care if a different one is returned for consecutive read operations
  • if neccessary, I can guarantee that the entries with the atoms (one element subsets of S) as keys are always present in the map

My understanding is, that the keys form a partially ordered set based on set inclusion, and the read opperation is to find some sort of an infimum.

I looked at the disjoint-set (union-find) data strcutrue, but as far as I understand, this is not what I am looking for.

I have also looked at other questions around here with similar keywords, but could not find anything that would fit my requirements:

Any help is greatly appriciated. Doubly so, if I would be pointed in the dirrection of a javascript/typescript implementation of the data structure.



Your Answer

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

Browse other questions tagged or ask your own question.