Пост написан на основе статьи на хабре: Интервально-ассоциативный массив.
Поскольку изначальная реализация основана на слайсах (срезах) питона, нелишней для прочтения будет статья: Всё, что Вы хотели знать о слайсах. И, конечно, немного теории: Дерево Интервалов (Отрезков).
Итак, как же слайсы будут выглядеть в Cache?
В целом всё (почти) как в питоне.
Легко назначить:
s i=##class(test.intervalmap).%New()
> d i.%("08:00","12:00","Иванов")
> d i.%("12:00","16:00","Петров")
Как узнать кто дежурил в 13:51 ?
w i.%Get("13:51"),!
Петров
Легко просмотреть поэлементно полный список (для тех, кто привык мыслить "глобально"):
> k % m %=i.% zw %
%("08:00","12:00")="Иванов"
%("12:00","16:00")="Петров"
… или одной строкой:
> w i.Display(),!
[08:00, 12:00] => Иванов, [12:00, 16:00] => Петров
Удаление как по частям:
> d i.%("15:00","16:00")
> w i.Display(),!
[08:00, 12:00] => Иванов, [12:00, 15:00] => Петров
… так и целиком:
> d i.%("12:00","16:00")
> w i.Display(),!
[08:00, 12:00] => Иванов
Перекрывание ключей должно обрабатываться корректно:
> d i.%("11:00","15:00","Сидоров")
> w i.Display(),!
[08:00, 11:00] => Иванов, [11:00, 15:00] => Сидоров
Cоседние ключи с одинаковыми значениями должны склеиваться автоматически. Например, если вы назначили Сидорову подежурить так же с 15 до 17, то навряд ли это должно быть две смены подряд, скорее — одна более длинная:
> d i.%("15:00","17:00","Сидоров")
> w i.Display(),!
[08:00, 11:00] => Иванов, [11:00, 17:00] => Сидоров
Добавим пару записей:
> d i.%("17:00","20:00","Петров")
> d i.%("21:00","23:00","Сидоров")
> w i.Display(),!
[08:00, 11:00] => Иванов, [11:00, 17:00] => Сидоров, [17:00, 20:00] => Петров, [21:00, 23:00] => Сидоров
Часто возникает задача урезать расписание, оставив из нескольких идущих подряд элементов только последние. Например, нужно узнать, кто закрывал рабочий день:
> d i.Shrink()
> w i.Display(),!
[08:00, 20:00] => Петров, [21:00, 23:00] => Сидоров
Этот же метод можно использовать для проверки полностью ли ваше расписание охватывает рабочий день.
Дополнение
Поскольку изначальная реализация основана на слайсах (срезах) питона, нелишней для прочтения будет статья: Всё, что Вы хотели знать о слайсах. И, конечно, немного теории: Дерево Интервалов (Отрезков).
Итак, как же слайсы будут выглядеть в Cache?
В целом всё (почти) как в питоне.
Легко назначить:
s i=##class(test.intervalmap).%New()
> d i.%("08:00","12:00","Иванов")
> d i.%("12:00","16:00","Петров")
Как узнать кто дежурил в 13:51 ?
w i.%Get("13:51"),!
Петров
Легко просмотреть поэлементно полный список (для тех, кто привык мыслить "глобально"):
> k % m %=i.% zw %
%("08:00","12:00")="Иванов"
%("12:00","16:00")="Петров"
… или одной строкой:
> w i.Display(),!
[08:00, 12:00] => Иванов, [12:00, 16:00] => Петров
Удаление как по частям:
> d i.%("15:00","16:00")
> w i.Display(),!
[08:00, 12:00] => Иванов, [12:00, 15:00] => Петров
… так и целиком:
> d i.%("12:00","16:00")
> w i.Display(),!
[08:00, 12:00] => Иванов
Перекрывание ключей должно обрабатываться корректно:
> d i.%("11:00","15:00","Сидоров")
> w i.Display(),!
[08:00, 11:00] => Иванов, [11:00, 15:00] => Сидоров
Cоседние ключи с одинаковыми значениями должны склеиваться автоматически. Например, если вы назначили Сидорову подежурить так же с 15 до 17, то навряд ли это должно быть две смены подряд, скорее — одна более длинная:
> d i.%("15:00","17:00","Сидоров")
> w i.Display(),!
[08:00, 11:00] => Иванов, [11:00, 17:00] => Сидоров
Добавим пару записей:
> d i.%("17:00","20:00","Петров")
> d i.%("21:00","23:00","Сидоров")
> w i.Display(),!
[08:00, 11:00] => Иванов, [11:00, 17:00] => Сидоров, [17:00, 20:00] => Петров, [21:00, 23:00] => Сидоров
Часто возникает задача урезать расписание, оставив из нескольких идущих подряд элементов только последние. Например, нужно узнать, кто закрывал рабочий день:
> d i.Shrink()
> w i.Display(),!
[08:00, 20:00] => Петров, [21:00, 23:00] => Сидоров
Этот же метод можно использовать для проверки полностью ли ваше расписание охватывает рабочий день.
Дополнение
- Была учтена небольшая ошибка в исходном коде по склейке соседних ключей, а именно:
Питон:
>>> 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.%(,,"Иванов")
> d i.%("11:00","13:00","Иванов")
> w i.Display(),!
[None, None] => Иванов - Одинаковые ключи в паре, как в исходном коде, здесь не допускаются, но вы для себя можете включить их обратно.
Конечно же в качестве ключей могут выступать любые числовые/строковые значения. Единственное, нужно следить, чтобы все они в рамках одного массива (объекта) были однотипны.
Например:
> 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("24.10.2005"),"A")
> d i.%($zdh("11.11.2005"),$zdh("17.11.2005"),"B")
> d i.%($zdh("30.11.2005"),,"C")
> w i.Display(),!
[None, 60197] => A, [60215, 60221] => B, [60234, None] => C
И напоследок ещё один пример посложнее:
> d i.Reset()
> d i.%(,,$c(8734))
> d i.%(10,11,"Иванов")
> d i.%(12,13,"Иванов")
> d i.%(14,16,"Петров")
> d i.%(11,15,"Иванов")
> d i.%(8,12,"Сидоров")
> d i.%(20,21)
> d i.%(22,,"Сидоров")
> w i.Display(),!
Результат под спойлером[None, 8] => ?, [8, 12] => Сидоров, [12, 15] => Иванов, [15, 16] => Петров, [16, 20] => ?, [21, 22] => ?, [22, None] => Сидоров
Больше примеров вы найдёте в исходном коде.
Код классаИли скачать класс test.intervalmap.
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","Иванов")
do i.%("12:00","16:00","Петров")
do i.%("15:00","16:00")
do i.%("12:00","16:00")
do i.%("11:00","15:00","Сидоров")
do i.%("15:00","17:00","Сидоров")
do i.%("17:00","20:00","Петров")
do i.%("21:00","23:00","Сидоров")
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))} else {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("24.10.2005"),"A")
do i.%($zdateh("11.11.2005"),$zdateh("17.11.2005"),"B")
do i.%($zdateh("30.11.2005"),,"C")
$$$AssertGet(i,$zdateh("25.09.2005"),"A")
$$$AssertGet(i,$zdateh("23.10.2005"),"A")
$$$AssertGet(i,$zdateh("26.10.2005"),"")
$$$AssertGet(i,$zdateh("09.11.2005"),"")
$$$AssertGet(i,$zdateh("16.11.2005"),"B")
$$$AssertGet(i,$zdateh("23.11.2005"),"")
$$$AssertGet(i,$zdateh("29.11.2005"),"")
$$$AssertGet(i,$zdateh("30.11.2005"),"C")
$$$AssertGet(i,$zdateh("03.12.2005"),"C")
write "Test 3 OK",!
}catch(ex){
#dim ex As %Exception.AbstractException
write "Error = ",ex.DisplayString(),!
}
do $system.Process.Undefined(old)
}
}
Код тестировался на версии Cache 2015.1, но переделать класс для предыдущих версий не составит особого труда.