multim

where a lonely key meets multiple values

Why

They come handy. Sometimes. And at those times it's good to have them.

Time Series

Let's say we have events streaming in in a form of {timestamp {ticker event-id}}:

(def events [
  [1449088877203 {:ticker :GOOG :event-id 1}]
  [1449088876590 {:ticker :AAPL :event-id 2}]
  [1449088877601 {:ticker :MSFT :event-id 3}]
  [1449088877203 {:ticker :TSLA :event-id 4}]
  [1449088875914 {:ticker :NFLX :event-id 5}]
  [1449088870005 {:ticker :FB   :event-id 6}] ])

• we'd like to keep them in the map.
• we'd also like to keep them sorted by time (i.e. timestamp)

notice that Tesla and Google have the same timestamp (i.e. same key value).

Multi Mode

As events come in they can be added into something like a TreeMultimap which is both: sorted and multimap.

;; syntax: (tree-multimap [key-comparator] [value-comparator])

user=> (tree-multimap <)

#object[com.google.common.collect.TreeMultimap 0x1fabbda8 "{}"]

a map with no data is interesting, but not as much as a map with the data:

user=> (def mm (into-multi 
                 (tree-multimap <) events))

#object[com.google.common.collect.TreeMultimap 0x688a6108
"{1449088877601=[{:ticker :MSFT, :event-id 3}], 
  1449088877203=[{:ticker :GOOG, :event-id 1}, {:ticker :TSLA, :event-id 4}],
  1449088876590=[{:ticker :AAPL, :event-id 2}],
  1449088875914=[{:ticker :NFLX, :event-id 5}],
  1449088870005=[{:ticker :FB, :event-id 6}]}"]

notice how it groupped values for the 1449088877203 timestamp.

Before and After

Since the map is sorted, it should be quite simple to find all the entries before or after certain time.

before

user=> (to mm 1449088876592)

{1449088870005 #{{:ticker :FB, :event-id 6}}, 
 1449088875914 #{{:ticker :NFLX, :event-id 5}}, 
 1449088876590 #{{:ticker :AAPL, :event-id 2}}}

after

user=> (from mm 1449088876592)

{1449088877203 #{{:ticker :GOOG, :event-id 1} {:ticker :TSLA, :event-id 4}}, 
 1449088877601 #{{:ticker :MSFT, :event-id 3}}}

View with a View

While TreeMultimap has all the chops, it is mutable, hence it is better to create a navigatable view based on the same tree-multimap:

user=> (def view (into-view 
                   (tree-multimap <) events))
#'user/view

user=> (type view)
com.google.common.collect.AbstractMapBasedMultimap$NavigableAsMap

it would of course be boring if this view type was not extended with a Sliceable protocol (as the TreeMultimap above):

(defprotocol Sliceable 
  (from [this k])
  (to [this k]))

so it does extend it as well:

before

user=> (to view 1449088876592)

{1449088870005 #{{:ticker :FB, :event-id 6}}, 
 1449088875914 #{{:ticker :NFLX, :event-id 5}}, 
 1449088876590 #{{:ticker :AAPL, :event-id 2}}}

after

user=> (from view 1449088876592)

{1449088877203 #{{:ticker :GOOG, :event-id 1} {:ticker :TSLA, :event-id 4}}, 
 1449088877601 #{{:ticker :MSFT, :event-id 3}}}

License

Copyright © 2017 tolitius

Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.