thejerf/cm

Generic Go multilevel and dual maps.

Complex Generic Maps for Go

go get github.com/thejerf/cm

import "github.com/thejerf/cm"

cm provides some generic complex maps for Go;

• The equivalent of map[A]map[B]C and map[A]map[B]map[C]D, in two flavors:

  • MapMap and MapMapMap implement that, with the constraint that the value type is comparable. This allows the equvialent of the maps' package .Equal method.
  • MapMapAny and MapMapMapAny are the same, but allowing the Value type to be any. This removes the .Equal method but allows storing any value.

• DualMap implements a map that can be keyed by either of two keys, packaging up a map[A]map[B]C and map[B]map[A]C into a single coherent package.

• MapSet implements a map that contains sets, like map[K]Set[V].

• To support MapSet, there's a full Set implementation.

  As I write this, there's a proposal for a standard-library Set type on github. This Set simply accepts that it is based on a map type, thus permitting a standard range iteration. While a custom Set type may theoretically permit higher performance for large sets, and it does make sense for the standard library to consider such a case, this set type will be acceptable for quite significantly sized sets.

  This set is also biased in the direction of mutability and performance. So, for instance, .Subtract will modify the Set it is called on. I chose this because if you have a mutation-based library, but want to create a new set, it is easy to set.Clone().Subtract(set2), but if you have a library that only works by creating new values you can't get the higher performance of direct mutation. And in my experience, direct mutation is a frequently common case, as is cloning a set once and performing many mutation operations on it (like subtracting several sets).

• To support this library there is also a Tuple2 and Tuple3 type. While these may not be 'full featured' tuples, I have found a use for them in table-based tests to avoid declaring

  type SomeTestType struct {
       In  Type1
       Out Type2
  }
  

  If you're using this library anyhow, there's no harm in using them.

There's nothing particularly "special" about this implementation, no magic sauce or anything. Just code I've had to write in several projects and would like to get factored out and into a well-tested library, rather than write over and over.

Go Versions

0.9.0 and beyond require Go 1.23 for the iterator support.

0.8.0 can be used for Go verions after 1.18, for generic support. (If you need a 0.8.1 to fix the missing ValueSlice on MapMap(Map)?, let me know.)

Performance

All of these methods are extremely strong candidates for inlining. Some brief checks with -gcflags="-m" on some test programs suggest that they are indeed all inlined. Consequently, this library should generally be zero-performance-impact versus having directly written the code. (There are a few places where nil is checked for where you might not have, but a highly-predictable branch should be lost in the noise compared to what even one map lookup requires.)

Future Plans

If the standard library implements a .Set, I am not sure if I will switch to it. It depends on the details. I am tempted just to 1.0 this package as-is, and then roll out a v2 with the built-in set if there's a compelling reason.

Status

I am using this a lot in my own code. With the release of rangefunc, I consider this a 1.0 candidate.

PRs

I am actively accepting PRs. If this almost does what you want, please by all means file a PR to add it rather than starting a new project.

However, I'm aiming for a library that does not replace things we already have built-ins or implementations in the to-be-standard maps package. Especially when implementations would be wildly slower than native support.

Users of this library are expected to understand this library as helpful methods that work on the relevant data types, not as a complete replacement data type for maps.

Code Signing

All commits and releases will be signed with a GPG key, as verified by GitHub. It is the "jerf" keybase account key.

(Bear in mind that due to the nature of how git commit signing works, there may be runs of unverified commits. What matters is that the top one is signed.)

Changelog

cm uses semantic versioning.

At the moment, this is in pre-release, which means no guarantees whatsoever about backwards compatibility. Change is still happening frequently as I hone in on the best solutions.

• 0.9.0:
  • BACKWARDS INCOMPATIBLE CHANGE: Values is renamed to ValueSlice, to allow Values to be used for iterators.
  • rangefunc support is added to the data structures, allowing efficient iteration without having to construct full slices. This adds:

    • MapMap[Any] gets All() for key/value, and Keys and Values for their respective contents.

    • Set gets SetFromIter to construct a set from an iter.Seq.

    • MapSet gets a Values iterator for all values.

      Note that a Keys iterator is already de facto available by ranging on the MapSet itself.

  • Added ValueSlice to MapMap, which was missing it.
• 0.8.0:
  • This is the last version that works back to 1.18. Future versions require 1.23 for rangefunc support. (I am not inclined to maintain multiple versions of this library in perpetuity.)
  • Add a Len method to the various maps that require a loop to compute them.
• 0.7.0:
  • Add AddByTuple to MapSet, as I encountered code where that was useful.
  • Add Intersect to Set.
• 0.6.0:
  • Add a Values method to MapMap, MapMapAny, MapMapMap, and MapMapMapAny.
• 0.5.0:
  • Trimmed off the .Get functions from the MapMap and MapMapMap as they are unnecessary.
  • NewDualMap is removed because it doesn't matter; the first Set will initialize the values and there is no reason to need them to be initialized before that.
  • DualMap's two maps are now called Primary and Reverse, which will probably be easier to remember than Left and Right.
• 0.4.0:
  • Removed MapSlice because upon an even more careful review of the behavior of nil slices, it adds nothing. The .Append method I wrote can also just be written as m[key] = append(m[key], vals...) without loss. The remaining .Set method that removes the key entirely for empty slices doesn't justify a full datatype.
• 0.3.0:
  • Worked out a way to recover the .Equal method without a lot of nasty casting on values.
• 0.2.0:
  • Renamed almost everything to something shorter, but also more comprehensible, I hope.
  • Additional data types:
    • Set
    • MapSet
    • MapSlice
• 0.1: Initial release to GitHub. This release has not been publicized as it is still missing a couple of key methods:
  • Methods for getting values.
  • Methods for getting full key/value tuples.
  • KeyTree2 may need some renaming; it works in the context of a MultiLevelMap2 but when recursively used by the MultiLevelMap3 the struct names are a bit off.