Creating an interval-associative array in the Caché DBMS

This is a translation of the following article. Thanks [@Evgeny Shvarov] for the help in translation.

This post is also available on Habrahabr^ru.

The post was inspired by this Habrahabr article: Interval-associative array^ru→en.

Since the original implementation relies on Python slices, the Caché public may find the following article useful: Everything you wanted to know about slices^ru→en.

Note: Please note that the exact functional equivalent of Python slices has never been implemented in Caché, since this functionality has never been required.

And, of course, some theory: Interval tree^ru→en.

All right, let’s cut to the chase and take a look at some examples.

In general, it works pretty much the same way as it does in Python.

Easy to assign:

USER>s i=##class(test.intervalmap).%New()
USER>d i.%("08:00","12:00","Johns")
USER>d i.%("12:00","16:00","Peters")

How do you find out who was on duty at 13:51?

USER>w i.%Get("13:51"),!
Peters

Easy to view the full list by element (for those who are used to thinking “globally”):

USER>k % m %=i.% zw %
%("08:00","12:00")="Johns"
%("12:00","16:00")="Peters"

...or in one line:

USER>w i.Display(),!
[08:00, 12:00] => Johns, [12:00, 16:00] => Peters

Removal by parts:

USER>d i.%("15:00","16:00")
USER>w i.Display(),!
[08:00, 12:00] => Johns, [12:00, 15:00] => Peters

...or the whole thing at once:

USER>d i.%("12:00","16:00")
USER>w i.Display(),!
[08:00, 12:00] => Johns

Key overlapping should be handled properly:

USER>d i.%("11:00","15:00","Smith")
USER>w i.Display(),!
[08:00, 11:00] => Johns, [11:00, 15:00] => Smith

Adjacent keys with identical values should be merged automatically. For instance, if you assigned Smith to also be on duty from 15:00 to 17:00, it’s unlikely that these will be two shifts in a row, rather one long shift:

USER>d i.%("15:00","17:00","Smith")
USER>w i.Display(),!
[08:00, 11:00] => Johns, [11:00, 17:00] => Smith

Let’s add a couple of records now:

USER>d i.%("17:00","20:00","Peters")
USER>d i.%("21:00","23:00","Smith")
USER>w i.Display(),!
[08:00, 11:00] => Johns, [11:00, 17:00] => Smith, [17:00, 20:00] => Peters, [21:00, 23:00] => Smith

You may often need to shrink the schedule by leaving the last in a series of elements. For example, you may want to find out who checked out last:

USER>d i.Shrink()
USER>w i.Display(),!
[08:00, 20:00] => Peters, [21:00, 23:00] => Smith

The same method can be used to verify that your schedule fully fits into a working day.

Extra

• We took account of a small error in the source code for merging adjoining keys, and specifically:

  Python:

  >>> timetable = intervalmap()
  >>> timetable[:] = 'Johns'
  >>> timetable['11:00':'13:00'] = 'Johns'
  >>> print timetable
  {[None, '13:00'] => 'Johns', ['13:00', None] => 'Johns'}

  COS:

  USER>s i=##class(test.intervalmap).%New()
  USER>d i.%(,,"Johns")
  USER>d i.%("11:00","13:00","Johns")
  USER>w i.Display(),!
  [None, None] => Johns

• Paired identical keys, like the ones found in the source code, are not allowed here, but you can turn them back on if you need to.
• Of course, any numeric/string values can be used as keys – just make sure they are of the same type within a single array (object).
  Example:

  USER>s i=##class(test.intervalmap).%New()
  USER>d i.%(9,,"!")
  USER>d i.%(,5,"Hello")
  USER>d i.%(6,7,"World")
  USER>w i.Display(),!
  [None, 5] => Hello, [6, 7] => World, [9, None] => !
  USER>d i.Reset()
  USER>d i.%(,$zdh("24.10.2005"),"A")
  USER>d i.%($zdh("11.11.2005"),$zdh("17.11.2005"),"B")
  USER>d i.%($zdh("30.11.2005"),,"C")
  USER>w i.Display(),!
  [None, 60197] => A, [60215, 60221] => B, [60234, None] => C

• Finally, a slightly more complex example:
  

  USER>d i.Reset()
  USER>d i.%(,,$c(8734))
  USER>d i.%(10,11,"Johns")
  USER>d i.%(12,13,"Johns")
  USER>d i.%(14,16,"Peters")
  USER>d i.%(11,15,"Johns")
  USER>d i.%(8,12,"Smith")
  USER>d i.%(20,21)
  USER>d i.%(22,,"Smith")
  USER>w i.Display(),!
  [None, 8] => ∞, [8, 12] => Smith, [12, 15] => Johns, [15, 16] => Peters, [16, 20] => ∞, [21, 22] => ∞, [22, None] => Smith

  More examples are available in the source code.

• The code was tested in Caché 2015.1, but you won’t have any problems rewriting it for older versions.

As always, we encourage you to improve, extend and fix the test.intervalmap class for your needs.