Implementation of interval-associative array in Caché DBMS
The post is written on the basis of an article on the habr: “Interval-associative array” .
Since the initial implementation is based on python slices (sections), an article would be useful for reading: Everything you wanted to know about slices . And, of course, a bit of theory: the Tree of Intervals (Segments) .
So, how will slices look in Caché?
In general, everything (almost) as in python.
Easy to assign:
')
s i = ## class ( test.intervalmap ). % New ()
> d i . % ( "08:00" , "12:00" , "Ivanov" )
> d i . % ( "12:00" , "16:00" , "Petrov" )
How to find out who was on duty at 13:51?
w i . % Get ( "13:51" )!
Petrov
It is easy to view the full list of elements (for those who are used to thinking "globally"):
> k % m % = i . % zw %
% ("08:00", "12:00") = "Ivanov"
% ("12:00", "16:00") = "Petrov"
... or in one line:
> w i . Display ()!
[08:00, 12:00] => Ivanov, [12:00, 16:00] => Petrov
Delete as in parts:
> d i . % ( "15:00" , "16:00" )
> w i . Display ()!
[08:00, 12:00] => Ivanov, [12:00, 15:00] => Petrov
... and the whole:
> d i . % ( "12:00" , "16:00" )
> w i . Display ()!
[08:00, 12:00] => Ivanov
Overlapping keys must be processed correctly:
> d i . % ( "11:00" , "15:00" , "Sidorov" )
> w i . Display ()!
[08:00, 11:00] => Ivanov, [11:00, 15:00] => Sidorov
Neighboring keys with the same values should be glued automatically. For example, if you appointed Sidorov to watch the same way from 15 to 17, then it is unlikely that it should be two shifts in a row, rather, one longer:
> d i . % ( "15:00" , "17:00" , "Sidorov" )
> w i . Display ()!
[08:00, 11:00] => Ivanov, [11:00, 17:00] => Sidorov
Add a couple of entries:
> d i . % ( "17:00" , "20:00" , "Petrov" )
> d i . % ( "21:00" , "23:00" , "Sidorov" )
> w i . Display ()!
[08:00, 11:00] => Ivanov, [11:00, 17:00] => Sidorov, [17:00, 20:00] => Petrov, [21:00, 23:00] => Sidorov
Often there is a task to cut the schedule, leaving only a few of the consecutive elements. For example, you need to find out who closed the working day:
> d i . Shrink ()
> w i . Display ()!
[08:00, 20:00] => Petrov, [21:00, 23:00] => Sidorov
You can use the same method to check whether your schedule completely covers a working day.
Addition
A small error was taken into account in the source code for gluing adjacent keys, namely:
Python:
COS:
> s i = ## class ( test.intervalmap ). % New ()
> d i . % (,, "Ivanov" )
> d i . % ( "11:00" , "13:00" , "Ivanov" )
> w i . Display ()!
[None, None] => Ivanov
Identical keys in a pair, as in the source code, are not allowed here, but you can turn them on for yourself.
Of course, any numeric / string values can be used as keys. The only thing you need to ensure that all of them within the same array (object) were of the same type.
For example:
> s i = .. % New ()
> d i . % (9 ,, "!" )
> d i . % (, 5, "Hello" )
> d i . % (6.7, "World" )
> w i . Display ()!
[None, 5] => Hello, [6, 7] => World, [9, None] =>!
> d i . Reset ()
> d i . % (, $ zdh ( "10.24.2005" ), "A" )
> d i . % ( $ zdh ( "11.11.2005" ), $ zdh ( " 11/17/2005 " ), "B" )
> d i . % ( $ zdh ( " 11/30/2005 " ) ,, "C" )
> w i . Display ()!
[None, 60197] => A, [60215, 60221] => B, [60234, None] => C
And finally, one more example is more complicated:
> d i . Reset ()
> d i . % (,, $ c (8734))
> d i . % (10.11, "Ivanov" )
> d i . % (12.13, "Ivanov" )
> d i . % (14.16, "Petrov" )
> d i . % (11.15, "Ivanov" )
> d i . % (8.12, "Sidorov" )
> d i . % (20.21)
> d i . % (22 ,, "Sidorov" )
> w i . Display ()!
More examples can be found in the source code.
The code has been tested on the Caché 2015.1 version, but it will not be difficult to remake the class for previous versions.
Since the initial implementation is based on python slices (sections), an article would be useful for reading: Everything you wanted to know about slices . And, of course, a bit of theory: the Tree of Intervals (Segments) .
So, how will slices look in Caché?
In general, everything (almost) as in python.
Easy to assign:
')
s i = ## class ( test.intervalmap ). % New ()
> d i . % ( "08:00" , "12:00" , "Ivanov" )
> d i . % ( "12:00" , "16:00" , "Petrov" )
How to find out who was on duty at 13:51?
w i . % Get ( "13:51" )!
Petrov
It is easy to view the full list of elements (for those who are used to thinking "globally"):
> k % m % = i . % zw %
% ("08:00", "12:00") = "Ivanov"
% ("12:00", "16:00") = "Petrov"
... or in one line:
> w i . Display ()!
[08:00, 12:00] => Ivanov, [12:00, 16:00] => Petrov
Delete as in parts:
> d i . % ( "15:00" , "16:00" )
> w i . Display ()!
[08:00, 12:00] => Ivanov, [12:00, 15:00] => Petrov
... and the whole:
> d i . % ( "12:00" , "16:00" )
> w i . Display ()!
[08:00, 12:00] => Ivanov
Overlapping keys must be processed correctly:
> d i . % ( "11:00" , "15:00" , "Sidorov" )
> w i . Display ()!
[08:00, 11:00] => Ivanov, [11:00, 15:00] => Sidorov
Neighboring keys with the same values should be glued automatically. For example, if you appointed Sidorov to watch the same way from 15 to 17, then it is unlikely that it should be two shifts in a row, rather, one longer:
> d i . % ( "15:00" , "17:00" , "Sidorov" )
> w i . Display ()!
[08:00, 11:00] => Ivanov, [11:00, 17:00] => Sidorov
Add a couple of entries:
> d i . % ( "17:00" , "20:00" , "Petrov" )
> d i . % ( "21:00" , "23:00" , "Sidorov" )
> w i . Display ()!
[08:00, 11:00] => Ivanov, [11:00, 17:00] => Sidorov, [17:00, 20:00] => Petrov, [21:00, 23:00] => Sidorov
Often there is a task to cut the schedule, leaving only a few of the consecutive elements. For example, you need to find out who closed the working day:
> d i . Shrink ()
> w i . Display ()!
[08:00, 20:00] => Petrov, [21:00, 23:00] => Sidorov
You can use the same method to check whether your schedule completely covers a working day.
Addition
A small error was taken into account in the source code for gluing adjacent keys, namely:
Python:
>>> timetable = intervalmap() >>> timetable[:] = '' >>> timetable['11:00':'13:00'] = '' >>> print timetable {[None, '13:00'] => '', ['13:00', None] => ''} COS:
> s i = ## class ( test.intervalmap ). % New ()
> d i . % (,, "Ivanov" )
> d i . % ( "11:00" , "13:00" , "Ivanov" )
> w i . Display ()!
[None, None] => Ivanov
Identical keys in a pair, as in the source code, are not allowed here, but you can turn them on for yourself.
Of course, any numeric / string values can be used as keys. The only thing you need to ensure that all of them within the same array (object) were of the same type.
For example:
> s i = .. % New ()
> d i . % (9 ,, "!" )
> d i . % (, 5, "Hello" )
> d i . % (6.7, "World" )
> w i . Display ()!
[None, 5] => Hello, [6, 7] => World, [9, None] =>!
> d i . Reset ()
> d i . % (, $ zdh ( "10.24.2005" ), "A" )
> d i . % ( $ zdh ( "11.11.2005" ), $ zdh ( " 11/17/2005 " ), "B" )
> d i . % ( $ zdh ( " 11/30/2005 " ) ,, "C" )
> w i . Display ()!
[None, 60197] => A, [60215, 60221] => B, [60234, None] => C
And finally, one more example is more complicated:
> d i . Reset ()
> d i . % (,, $ c (8734))
> d i . % (10.11, "Ivanov" )
> d i . % (12.13, "Ivanov" )
> d i . % (14.16, "Petrov" )
> d i . % (11.15, "Ivanov" )
> d i . % (8.12, "Sidorov" )
> d i . % (20.21)
> d i . % (22 ,, "Sidorov" )
> w i . Display ()!
Result under the spoiler
[None, 8] => ∞, [8, 12] => Sidorov, [12, 15] => Ivanov, [15, 16] => Petrov, [16, 20] => ∞, [21, 22] => ∞, [22, None] => Sidorov
More examples can be found in the source code.
Class code
Class test.intervalmap Extends% RegisteredObject [ Final ]
{
Parameter None [ Final , Internal ] = -1 ;
Property bounds As% List [ Internal , Private , ReadOnly , ServerOnly = 1, Transient ];
Property items As% List [ Internal , Private , ReadOnly , ServerOnly = 1, Transient ];
Property upperItem [ InitialExpression = {.. #None }, Internal , Private , ReadOnly , ServerOnly = 1, Transient ];
Property % [ MultiDimensional , ReadOnly , ServerOnly = 1, Transient ];
ClassMethod Slice ( list As% List , start , end , value As% List ) As% List [ Internal , Private ]
{
if start = end {
if start = "" {
set list = ""
} elseif start = 1 {
set list = value _ list
} else {
if start > $ listlength ( list ) {
set list = list _ value
} else {
set : start < $ listlength ( list ) start = start +1
set $ list ( list , start , start ) = value _ $ listbuild ( $ list ( list , start ))
}
}
} else {
if end = "" {
set : start > $ listlength ( list ) start = $ listlength ( list )
set $ list ( list , start , * + 1) = value
} else {
set start = $ get ( start , 1)
if end = 1 {
set list = .. Slice ( list , start , end , value )
} else {
set $ list ( list , start , end -1) = value
}
}
}
quit list
}
Method Reset ()
{
kill i %%
set (i% bounds, i% items) = "" , i% upperItem = .. #None
}
Method % ( start = { $ get ( start , .. #None )}, stop = { $ get ( stop , .. #None )}, value = { $ get ( value , .. #None )}) As% Status
{
quit :( start > = stop ) & (( start '= .. #None ) & ( stop ' = .. #None )) $$$ OK
set startPoint = $ select ( start = .. #None : 0,1: .. bisectLeft ( start ))
set endPoint = $ select ( stop = .. #None : 0,1: .. bisectLeft ( stop ))
if startPoint > = 1 {
set :( startPoint <= $ listlength (.. bounds )) && ( $ list (.. bounds , startPoint ) < start ) startPoint = startPoint + 1
set :( endPoint > = 1) && ( endPoint <= $ listlength (.. bounds )) && ( $ list (.. bounds , endPoint ) <= stop ) endPoint = endPoint + 1
if endPoint > = 1 {
set i% bounds = .. Slice (i% bounds, startPoint , endPoint , $ listbuild ( start , stop ))
set i% items = .. Slice (i% items, startPoint , endPoint , $ select ( startPoint <= $ listlength (.. items ): $ listbuild ( $ list (.. items , startPoint ), value ), 1: $ listbuild (.. upperItem , value )))
} else {
set $ list (i% bounds, startPoint , * + 1) = $ listbuild ( start )
set $ list (i% items, startPoint , * + 1) = $ select ( startPoint <= $ listlength (.. items ): $ listbuild ( $ list (.. items , startPoint ), value ), 1: $ listbuild ( .. upperItem ))
set i% upperItem = value
}
} else {
if endPoint > = 1 {
set i% bounds = .. Slice (i% bounds, 1, endPoint , $ listbuild ( stop ))
set i% items = .. Slice (i% items, 1, endPoint , $ listbuild ( value ))
} else {
set (i% bounds, i% items) = ""
set i% upperItem = value
}
}
set i = 1
while ( i <= ( $ listlength (.. items ) -1))
{
if $ list (.. items , i ) = $ list (.. items , i +1) {
set $ list (i% items, i , i ) = ""
set $ list (i% bounds, i , i ) = ""
} else {
set i = i +1
}
}
set :( $ listlength (.. items ) = 1) && ( $ list (i% items, 1) = i% upperItem) (i% items, i% bounds) = ""
do .. repr ()
quit $$$ OK
}
Method % Get ( x ) As% String [ ServerOnly = 1]
{
set index = .. bisectRight ( x )
set r = $ select ( index <= $ listlength (i% items): $ list (i% items, index ), 1: i% upperItem)
quit $ select ( r = .. #None : "" , 1: r )
}
Method bisectLeft ( x ) As% String [ Internal , Private , ServerOnly = 1]
{
set lo = 1
set hi = $ listlength (i% bounds) +1
while ( lo < hi ) {
set mid = ( lo + hi ) \ 2
if $ list (i% bounds, mid ) < x {
set lo = mid +1
} else {
set hi = mid
}
}
quit lo
}
Method bisectRight ( x ) As% String [ Internal , Private , ServerOnly = 1]
{
set lo = 1
set hi = $ listlength (i% bounds) +1
while ( lo < hi ) {
set mid = ( lo + hi ) \ 2
if x < $ list (i% bounds, mid ) {
set hi = mid
} else {
set lo = mid +1
}
}
quit lo
}
Method repr () [ Internal , Private , ServerOnly = 1]
{
kill i %%
set previousBound = .. #None
for i = 1: 1: $ listlength (.. bounds ) {
set b = $ list (.. bounds , i )
set v = $ list (.. items , i )
set : v '= .. #None i %% ( previousBound , b ) = v
set previousBound = b
}
set : .. upperItem '= .. #None i %% ( previousBound , .. #None ) = .. upperItem
}
Method Shrink ()
{
set i = 1
while ( i <= ( $ listlength (.. items ) -1))
{
if $ list (.. items , i ) '= .. #None , $ list (.. items , i +1)' = .. #None {
set $ list (i% items, i , i ) = ""
set $ list (i% bounds, i , i ) = ""
} else {
set i = i +1
}
}
do .. repr ()
}
Method Display () As% String
{
#define IsNone (% s) $ s (% s = .. # None: "None" , 1:% s)
set key = $ query (i %%, 1, v ), s = ""
while ( key '= "" ) {
set s = s _ $ listbuild ( $$$ FormatText ( "[% 1,% 2] =>% 3" , $$$ IsNone ( $ qsubscript ( key , 1)), $$$ IsNone ( $ qsubscript ( key , 2)), v ))
set key = $ query (@ key , 1, v )
}
quit $ listtostring ( s , "," )
}
/// <example> d ## class (test.intervalmap) .Test1 () </ example>
ClassMethod Test1 () [ Internal , ServerOnly = 1]
{
new %
set old = $ system .Process . Undefined (2)
try {
set i = .. % New ()
do i . % ( "08:00" , "12:00" , "Ivanov" )
do i . % ( "12:00" , "16:00" , "Petrov" )
do i . % ( "15:00" , "16:00" )
do i . % ( "12:00" , "16:00" )
do i . % ( "11:00" , "15:00" , "Sidorov" )
do i . % ( "15:00" , "17:00" , "Sidorov" )
do i . % ( "17:00" , "20:00" , "Petrov" )
do i . % ( "21:00" , "23:00" , "Sidorov" )
write i . Display ()!
write "[13:51] =" , i . % Get ( "13:51" )!
; k% m% = i.% zw%
do i . Shrink ()
write i . Display ()!
} catch ( ex ) {
#dim ex As % Exception.AbstractException
write "Error =" , ex . DisplayString () ,!
}
do $ system .Process . Undefined ( old )
}
/// <example> d ## class (test.intervalmap) .Test2 () </ example>
ClassMethod Test2 () [ Internal , ServerOnly = 1]
{
#define Assert (% i,% s) if% i.Display () '=% s {$$$ ThrowStatus ( $$$ ERROR ( $$$ GeneralError , % s )) }} {w% i.Display ( )!
#define AssertGet (% i,% t,% s) if% i.% Get (% t) '=% s {$$$ ThrowStatus ( $$$ ERROR ( $$$ GeneralError , % s )) }} else { w "(% t) =" ,% i.% Get (% t) ,!}
set old = $ system .Process . Undefined (2)
try {
set i = .. % New ()
do i . % (0.5, "0-5" )
do i . % (8.12, "8-12" )
$$$ AssertGet ( i , 2, "0-5" )
$$$ AssertGet ( i , 10, "8-12" )
$$$ AssertGet ( i , -1, "" )
$$$ AssertGet ( i , 17, "" )
do i . % (4.9, "4-9" )
$$$ Assert ( i , "[0, 4] => 0-5, [4, 9] => 4-9, [9, 12] => 8-12" )
do i . % (, 0, "less than 0" )
$$$ AssertGet ( i , -5, "less than 0" )
$$$ AssertGet ( i , 0, "0-5" )
$$$ Assert ( i , "[None, 0] => less than 0, [0, 4] => 0-5, [4, 9] => 4-9, [9, 12] => 8- 12 " )
do i . % (21 ,, "more than twenty" )
$$$ AssertGet ( i , 42, "more than twenty" )
do i . % (10.5.15.5, "10.5-15.5" )
$$$ AssertGet ( i , 11.5, "10.5-15.5" )
$$$ AssertGet ( i , 0.5, "0-5" )
$$$ Assert ( i , "[None, 0] => less than 0, [0, 4] => 0-5, [4, 9] => 4-9, [9, 10.5] => 8- 12, [10.5, 15.5] => 10.5-15.5, [21, None] => more than twenty " )
do i . Reset ()
do i . % (0,2,1)
do i . % (2.8.2)
do i . % (4,, 3)
do i . % (5,6,4)
$$$ Assert ( i , "[0, 2] => 1, [2, 4] => 2, [4, 5] => 3, [5, 6] => 4, [6, None] = > 3 " )
} catch ( ex ) {
#dim ex As % Exception.AbstractException
write "Error =" , ex . DisplayString () ,!
}
do $ system .Process . Undefined ( old )
}
/// <example> d ## class (test.intervalmap) .Test3 () </ example>
ClassMethod Test3 () [ Internal , ServerOnly = 1]
{
#define Assert (% i,% s) if% i.Display () '=% s $$$ ThrowStatus ( $$$ ERROR ( $$$ GeneralError , % s ))
#define AssertGet (% i,% t,% s) if% i.% Get (% t) '=% s $$$ ThrowStatus ( $$$ ERROR ( $$$ GeneralError , % s ))
set old = $ system .Process . Undefined (2)
try {
set i = .. % New ()
do i . % (9 ,, "!" )
$$$ Assert ( i , "[9, None] =>!" )
do i . % (, 5, "Hello" )
do i . % (6.7, "World" )
$$$ Assert ( i , "[None, 5] => Hello, [6, 7] => World, [9, None] =>!" )
do i . % (8.10, "(Test)" )
$$$ Assert ( i , "[None, 5] => Hello, [6, 7] => World, [8, 10] => (Test), [10, None] =>!" )
do i . % (, 3, "My," )
$$$ Assert ( i , "[None, 3] => My ,, [3, 5] => Hello, [6, 7] => World, [8, 10] => (Test), [10, None] =>! " )
do i . % (5.5.6, "Cruel" )
$$$ Assert ( i , "[None, 3] => My ,, [3, 5] => Hello, [5.5, 6] => Cruel, [6, 7] => World, [8, 10] => (Test), [10, None] =>! " )
do i . % (6.6.5, "And Harsh" )
$$$ Assert ( i , "[None, 3] => My ,, [3, 5] => Hello, [5.5, 6] => Cruel, [6, 6.5] => And Harsh, [6.5, 7 ] => World, [8, 10] => (Test), [10, None] =>! " )
do i . % (5.9,6.6)
$$$ Assert ( i , "[None, 3] => My ,, [3, 5] => Hello, [5.5, 5.9] => Cruel, [6.6, 7] => World, [8, 10] => (Test), [10, None] =>! " )
write "Test 1 OK" ,!
do i . Reset ()
do i . % (, 0, "A" )
do i . % (2.5, "B" )
do i . % (8.10, "C" )
do i . % (12 ,, "D" )
$$$ Assert ( i , "[None, 0] => A, [2, 5] => B, [8, 10] => C, [12, None] => D" )
do i . % (,, "K" )
$$$ Assert ( i , "[None, None] => K" )
$$$ AssertGet ( i , 5, "K" )
do i . % (0.10, "L" )
do i . % (6.8, "M" )
do i . % (20 ,, "J" )
$$$ AssertGet ( i , -1, "K" )
$$$ AssertGet ( i , 5, "L" )
$$$ AssertGet ( i , 7, "M" )
$$$ AssertGet ( i , 9, "L" )
$$$ AssertGet ( i , 15, "K" )
write "Test 2 OK" ,!
do i . Reset ()
do i . % (, $ zdateh ( "10.24.2005" ), "A" )
do i . % ( $ zdateh ( "11.11.2005" ), $ zdateh ( "17.11.2005" ), "B" )
do i . % ( $ zdateh ( " 11/30/2005 " ), "C" )
$$$ AssertGet ( i , $ zdateh ( "09/25/2005" ), "A" )
$$$ AssertGet ( i , $ zdateh ( "10/23/2005" ), "A" )
$$$ AssertGet ( i , $ zdateh ( " 10.26.2005 " ), "" )
$$$ AssertGet ( i , $ zdateh ( " 11/09/2005 " ), "" )
$$$ AssertGet ( i , $ zdateh ( "11/16/2005" ), "B" )
$$$ AssertGet ( i , $ zdateh ( "11/23/2005" ), "" )
$$$ AssertGet ( i , $ zdateh ( "11/29/2005" ), "" )
$$$ AssertGet ( i , $ zdateh ( " 11/30/2005 " ), "C" )
$$$ AssertGet ( i , $ zdateh ( " 12/03/2005 " ), "C" )
write "Test 3 OK" ,!
} catch ( ex ) {
#dim ex As % Exception.AbstractException
write "Error =" , ex . DisplayString () ,!
}
do $ system .Process . Undefined ( old )
}
}
Or download the test.intervalmap class .Class test.intervalmap Extends% RegisteredObject [ Final ]
{
Parameter None [ Final , Internal ] = -1 ;
Property bounds As% List [ Internal , Private , ReadOnly , ServerOnly = 1, Transient ];
Property items As% List [ Internal , Private , ReadOnly , ServerOnly = 1, Transient ];
Property upperItem [ InitialExpression = {.. #None }, Internal , Private , ReadOnly , ServerOnly = 1, Transient ];
Property % [ MultiDimensional , ReadOnly , ServerOnly = 1, Transient ];
ClassMethod Slice ( list As% List , start , end , value As% List ) As% List [ Internal , Private ]
{
if start = end {
if start = "" {
set list = ""
} elseif start = 1 {
set list = value _ list
} else {
if start > $ listlength ( list ) {
set list = list _ value
} else {
set : start < $ listlength ( list ) start = start +1
set $ list ( list , start , start ) = value _ $ listbuild ( $ list ( list , start ))
}
}
} else {
if end = "" {
set : start > $ listlength ( list ) start = $ listlength ( list )
set $ list ( list , start , * + 1) = value
} else {
set start = $ get ( start , 1)
if end = 1 {
set list = .. Slice ( list , start , end , value )
} else {
set $ list ( list , start , end -1) = value
}
}
}
quit list
}
Method Reset ()
{
kill i %%
set (i% bounds, i% items) = "" , i% upperItem = .. #None
}
Method % ( start = { $ get ( start , .. #None )}, stop = { $ get ( stop , .. #None )}, value = { $ get ( value , .. #None )}) As% Status
{
quit :( start > = stop ) & (( start '= .. #None ) & ( stop ' = .. #None )) $$$ OK
set startPoint = $ select ( start = .. #None : 0,1: .. bisectLeft ( start ))
set endPoint = $ select ( stop = .. #None : 0,1: .. bisectLeft ( stop ))
if startPoint > = 1 {
set :( startPoint <= $ listlength (.. bounds )) && ( $ list (.. bounds , startPoint ) < start ) startPoint = startPoint + 1
set :( endPoint > = 1) && ( endPoint <= $ listlength (.. bounds )) && ( $ list (.. bounds , endPoint ) <= stop ) endPoint = endPoint + 1
if endPoint > = 1 {
set i% bounds = .. Slice (i% bounds, startPoint , endPoint , $ listbuild ( start , stop ))
set i% items = .. Slice (i% items, startPoint , endPoint , $ select ( startPoint <= $ listlength (.. items ): $ listbuild ( $ list (.. items , startPoint ), value ), 1: $ listbuild (.. upperItem , value )))
} else {
set $ list (i% bounds, startPoint , * + 1) = $ listbuild ( start )
set $ list (i% items, startPoint , * + 1) = $ select ( startPoint <= $ listlength (.. items ): $ listbuild ( $ list (.. items , startPoint ), value ), 1: $ listbuild ( .. upperItem ))
set i% upperItem = value
}
} else {
if endPoint > = 1 {
set i% bounds = .. Slice (i% bounds, 1, endPoint , $ listbuild ( stop ))
set i% items = .. Slice (i% items, 1, endPoint , $ listbuild ( value ))
} else {
set (i% bounds, i% items) = ""
set i% upperItem = value
}
}
set i = 1
while ( i <= ( $ listlength (.. items ) -1))
{
if $ list (.. items , i ) = $ list (.. items , i +1) {
set $ list (i% items, i , i ) = ""
set $ list (i% bounds, i , i ) = ""
} else {
set i = i +1
}
}
set :( $ listlength (.. items ) = 1) && ( $ list (i% items, 1) = i% upperItem) (i% items, i% bounds) = ""
do .. repr ()
quit $$$ OK
}
Method % Get ( x ) As% String [ ServerOnly = 1]
{
set index = .. bisectRight ( x )
set r = $ select ( index <= $ listlength (i% items): $ list (i% items, index ), 1: i% upperItem)
quit $ select ( r = .. #None : "" , 1: r )
}
Method bisectLeft ( x ) As% String [ Internal , Private , ServerOnly = 1]
{
set lo = 1
set hi = $ listlength (i% bounds) +1
while ( lo < hi ) {
set mid = ( lo + hi ) \ 2
if $ list (i% bounds, mid ) < x {
set lo = mid +1
} else {
set hi = mid
}
}
quit lo
}
Method bisectRight ( x ) As% String [ Internal , Private , ServerOnly = 1]
{
set lo = 1
set hi = $ listlength (i% bounds) +1
while ( lo < hi ) {
set mid = ( lo + hi ) \ 2
if x < $ list (i% bounds, mid ) {
set hi = mid
} else {
set lo = mid +1
}
}
quit lo
}
Method repr () [ Internal , Private , ServerOnly = 1]
{
kill i %%
set previousBound = .. #None
for i = 1: 1: $ listlength (.. bounds ) {
set b = $ list (.. bounds , i )
set v = $ list (.. items , i )
set : v '= .. #None i %% ( previousBound , b ) = v
set previousBound = b
}
set : .. upperItem '= .. #None i %% ( previousBound , .. #None ) = .. upperItem
}
Method Shrink ()
{
set i = 1
while ( i <= ( $ listlength (.. items ) -1))
{
if $ list (.. items , i ) '= .. #None , $ list (.. items , i +1)' = .. #None {
set $ list (i% items, i , i ) = ""
set $ list (i% bounds, i , i ) = ""
} else {
set i = i +1
}
}
do .. repr ()
}
Method Display () As% String
{
#define IsNone (% s) $ s (% s = .. # None: "None" , 1:% s)
set key = $ query (i %%, 1, v ), s = ""
while ( key '= "" ) {
set s = s _ $ listbuild ( $$$ FormatText ( "[% 1,% 2] =>% 3" , $$$ IsNone ( $ qsubscript ( key , 1)), $$$ IsNone ( $ qsubscript ( key , 2)), v ))
set key = $ query (@ key , 1, v )
}
quit $ listtostring ( s , "," )
}
/// <example> d ## class (test.intervalmap) .Test1 () </ example>
ClassMethod Test1 () [ Internal , ServerOnly = 1]
{
new %
set old = $ system .Process . Undefined (2)
try {
set i = .. % New ()
do i . % ( "08:00" , "12:00" , "Ivanov" )
do i . % ( "12:00" , "16:00" , "Petrov" )
do i . % ( "15:00" , "16:00" )
do i . % ( "12:00" , "16:00" )
do i . % ( "11:00" , "15:00" , "Sidorov" )
do i . % ( "15:00" , "17:00" , "Sidorov" )
do i . % ( "17:00" , "20:00" , "Petrov" )
do i . % ( "21:00" , "23:00" , "Sidorov" )
write i . Display ()!
write "[13:51] =" , i . % Get ( "13:51" )!
; k% m% = i.% zw%
do i . Shrink ()
write i . Display ()!
} catch ( ex ) {
#dim ex As % Exception.AbstractException
write "Error =" , ex . DisplayString () ,!
}
do $ system .Process . Undefined ( old )
}
/// <example> d ## class (test.intervalmap) .Test2 () </ example>
ClassMethod Test2 () [ Internal , ServerOnly = 1]
{
#define Assert (% i,% s) if% i.Display () '=% s {$$$ ThrowStatus ( $$$ ERROR ( $$$ GeneralError , % s )) }} {w% i.Display ( )!
#define AssertGet (% i,% t,% s) if% i.% Get (% t) '=% s {$$$ ThrowStatus ( $$$ ERROR ( $$$ GeneralError , % s )) }} else { w "(% t) =" ,% i.% Get (% t) ,!}
set old = $ system .Process . Undefined (2)
try {
set i = .. % New ()
do i . % (0.5, "0-5" )
do i . % (8.12, "8-12" )
$$$ AssertGet ( i , 2, "0-5" )
$$$ AssertGet ( i , 10, "8-12" )
$$$ AssertGet ( i , -1, "" )
$$$ AssertGet ( i , 17, "" )
do i . % (4.9, "4-9" )
$$$ Assert ( i , "[0, 4] => 0-5, [4, 9] => 4-9, [9, 12] => 8-12" )
do i . % (, 0, "less than 0" )
$$$ AssertGet ( i , -5, "less than 0" )
$$$ AssertGet ( i , 0, "0-5" )
$$$ Assert ( i , "[None, 0] => less than 0, [0, 4] => 0-5, [4, 9] => 4-9, [9, 12] => 8- 12 " )
do i . % (21 ,, "more than twenty" )
$$$ AssertGet ( i , 42, "more than twenty" )
do i . % (10.5.15.5, "10.5-15.5" )
$$$ AssertGet ( i , 11.5, "10.5-15.5" )
$$$ AssertGet ( i , 0.5, "0-5" )
$$$ Assert ( i , "[None, 0] => less than 0, [0, 4] => 0-5, [4, 9] => 4-9, [9, 10.5] => 8- 12, [10.5, 15.5] => 10.5-15.5, [21, None] => more than twenty " )
do i . Reset ()
do i . % (0,2,1)
do i . % (2.8.2)
do i . % (4,, 3)
do i . % (5,6,4)
$$$ Assert ( i , "[0, 2] => 1, [2, 4] => 2, [4, 5] => 3, [5, 6] => 4, [6, None] = > 3 " )
} catch ( ex ) {
#dim ex As % Exception.AbstractException
write "Error =" , ex . DisplayString () ,!
}
do $ system .Process . Undefined ( old )
}
/// <example> d ## class (test.intervalmap) .Test3 () </ example>
ClassMethod Test3 () [ Internal , ServerOnly = 1]
{
#define Assert (% i,% s) if% i.Display () '=% s $$$ ThrowStatus ( $$$ ERROR ( $$$ GeneralError , % s ))
#define AssertGet (% i,% t,% s) if% i.% Get (% t) '=% s $$$ ThrowStatus ( $$$ ERROR ( $$$ GeneralError , % s ))
set old = $ system .Process . Undefined (2)
try {
set i = .. % New ()
do i . % (9 ,, "!" )
$$$ Assert ( i , "[9, None] =>!" )
do i . % (, 5, "Hello" )
do i . % (6.7, "World" )
$$$ Assert ( i , "[None, 5] => Hello, [6, 7] => World, [9, None] =>!" )
do i . % (8.10, "(Test)" )
$$$ Assert ( i , "[None, 5] => Hello, [6, 7] => World, [8, 10] => (Test), [10, None] =>!" )
do i . % (, 3, "My," )
$$$ Assert ( i , "[None, 3] => My ,, [3, 5] => Hello, [6, 7] => World, [8, 10] => (Test), [10, None] =>! " )
do i . % (5.5.6, "Cruel" )
$$$ Assert ( i , "[None, 3] => My ,, [3, 5] => Hello, [5.5, 6] => Cruel, [6, 7] => World, [8, 10] => (Test), [10, None] =>! " )
do i . % (6.6.5, "And Harsh" )
$$$ Assert ( i , "[None, 3] => My ,, [3, 5] => Hello, [5.5, 6] => Cruel, [6, 6.5] => And Harsh, [6.5, 7 ] => World, [8, 10] => (Test), [10, None] =>! " )
do i . % (5.9,6.6)
$$$ Assert ( i , "[None, 3] => My ,, [3, 5] => Hello, [5.5, 5.9] => Cruel, [6.6, 7] => World, [8, 10] => (Test), [10, None] =>! " )
write "Test 1 OK" ,!
do i . Reset ()
do i . % (, 0, "A" )
do i . % (2.5, "B" )
do i . % (8.10, "C" )
do i . % (12 ,, "D" )
$$$ Assert ( i , "[None, 0] => A, [2, 5] => B, [8, 10] => C, [12, None] => D" )
do i . % (,, "K" )
$$$ Assert ( i , "[None, None] => K" )
$$$ AssertGet ( i , 5, "K" )
do i . % (0.10, "L" )
do i . % (6.8, "M" )
do i . % (20 ,, "J" )
$$$ AssertGet ( i , -1, "K" )
$$$ AssertGet ( i , 5, "L" )
$$$ AssertGet ( i , 7, "M" )
$$$ AssertGet ( i , 9, "L" )
$$$ AssertGet ( i , 15, "K" )
write "Test 2 OK" ,!
do i . Reset ()
do i . % (, $ zdateh ( "10.24.2005" ), "A" )
do i . % ( $ zdateh ( "11.11.2005" ), $ zdateh ( "17.11.2005" ), "B" )
do i . % ( $ zdateh ( " 11/30/2005 " ), "C" )
$$$ AssertGet ( i , $ zdateh ( "09/25/2005" ), "A" )
$$$ AssertGet ( i , $ zdateh ( "10/23/2005" ), "A" )
$$$ AssertGet ( i , $ zdateh ( " 10.26.2005 " ), "" )
$$$ AssertGet ( i , $ zdateh ( " 11/09/2005 " ), "" )
$$$ AssertGet ( i , $ zdateh ( "11/16/2005" ), "B" )
$$$ AssertGet ( i , $ zdateh ( "11/23/2005" ), "" )
$$$ AssertGet ( i , $ zdateh ( "11/29/2005" ), "" )
$$$ AssertGet ( i , $ zdateh ( " 11/30/2005 " ), "C" )
$$$ AssertGet ( i , $ zdateh ( " 12/03/2005 " ), "C" )
write "Test 3 OK" ,!
} catch ( ex ) {
#dim ex As % Exception.AbstractException
write "Error =" , ex . DisplayString () ,!
}
do $ system .Process . Undefined ( old )
}
}
The code has been tested on the Caché 2015.1 version, but it will not be difficult to remake the class for previous versions.
Source: https://habr.com/ru/post/256851/
All Articles