Пост написан на основе статьи на хабре: Интервально-ассоциативный массив.
Поскольку изначальная реализация основана на слайсах (срезах) питона, нелишней для прочтения будет статья: Всё, что Вы хотели знать о слайсах. И, конечно, немного теории: Дерево Интервалов (Отрезков).
Итак, как же слайсы будут выглядеть в Caché?
В целом всё (почти) как в питоне.
Легко назначить:
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] => СидоровБольше примеров вы найдёте в исходном коде.
Код класса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="" {
s list=""
}elseif start=1 {
s list=value_list
}else{
if start>$ll(list) {
s list=list_value
}else{
s:start<$ll(list) start=start+1
s $li(list,start,start)=value_$lb($li(list,start))
}
}
}else{
if end="" {
s:start>$ll(list) start=$ll(list)
s $li(list,start,*+1)=value
}else{
s start=$g(start,1)
if end=1 {
s list=..Slice(list,start,end,value)
}else{
s $li(list,start,end-1)=value
}
}
}
q list
}
Method Reset()
{
k i%%
s (i%bounds,i%items)="",i%upperItem=..#None
}
Method %(start = {$g(start,..#None)}, stop = {$g(stop,..#None)}, value = {$g(value,..#None)}) As %Status
{
q🙁start>=stop)&((start‘=..#None)&(stop‘=..#None)) $$$OK
s startPoint=$s(start=..#None:0,1:..bisectLeft(start))
s endPoint=$s(stop=..#None:0,1:..bisectLeft(stop))
if startPoint>=1 {
s🙁startPoint <= $ll(..bounds))&&($li(..bounds,startPoint)<start) startPoint = startPoint + 1
s🙁endPoint >= 1)&&(endPoint <= $ll(..bounds))&&($li(..bounds,endPoint)<=stop) endPoint = endPoint + 1
if endPoint>=1 {
s i%bounds=..Slice(i%bounds,startPoint,endPoint,$lb(start,stop))
s i%items=..Slice(i%items,startPoint,endPoint,$s(startPoint <= $ll(..items):$lb($li(..items,startPoint),value),1:$lb(..upperItem,value)))
}else{
s $li(i%bounds,startPoint,*+1) = $lb(start)
s $li(i%items,startPoint,*+1)=$s(startPoint <= $ll(..items):$lb($li(..items,startPoint),value),1:$lb(..upperItem))
s i%upperItem = value
}
}else{
if endPoint>=1 {
s i%bounds=..Slice(i%bounds,1,endPoint,$lb(stop))
s i%items=..Slice(i%items,1,endPoint,$lb(value))
}else{
s (i%bounds,i%items) = ""
s i%upperItem = value
}
}
s i=1
while (i<=($ll(..items)-1))
{
i $li(..items,i)=$li(..items,i+1) {
s $li(i%items,i,i)=""
s $li(i%bounds,i,i)=""
}else {
s i=i+1
}
}
s🙁$ll(..items)=1)&&($li(i%items,1)=i%upperItem) (i%items,i%bounds)=""
d ..repr()
q $$$OK
}
Method %Get(x) As %String [ ServerOnly = 1 ]
{
s index=..bisectRight(x)
s r=$s(index<=$ll(i%items):$li(i%items,index),1:i%upperItem)
q $s(r=..#None:"",1:r)
}
Method bisectLeft(x) As %String [ Internal, Private, ServerOnly = 1 ]
{
s lo = 1
s hi = $ll(i%bounds)+1
while (lo < hi) {
s mid = (lo+hi)\2
if $li(i%bounds,mid) < x {
s lo = mid+1
} else {
s hi = mid
}
}
q lo
}
Method bisectRight(x) As %String [ Internal, Private, ServerOnly = 1 ]
{
s lo = 1
s hi = $ll(i%bounds)+1
while (lo < hi) {
s mid = (lo+hi)\2
if x < $li(i%bounds,mid) {
s hi = mid
} else {
s lo = mid+1
}
}
q lo
}
Method repr() [ Internal, Private, ServerOnly = 1 ]
{
k i%%
s previousBound=..#None
f i=1:1:$ll(..bounds) {
s b=$li(..bounds,i)
s v=$li(..items,i)
s:v‘=..#None i%%(previousBound,b)=v
s previousBound=b
}
s:..upperItem‘=..#None i%%(previousBound,..#None)=..upperItem
}
Method Shrink()
{
s i=1
while (i<=($ll(..items)-1))
{
i $li(..items,i)’=..#None,$li(..items,i+1)’=..#None {
s $li(i%items,i,i)=""
s $li(i%bounds,i,i)=""
}else {
s i=i+1
}
}
d ..repr()
}
Method Display() As %String
{
#define IsNone(%s) $s(%s=..#None:"None",1:%s)
s key=$q(i%%,1,v),s=""
while (key‘="") {
s s=s_$lb($$$FormatText("[%1, %2] => %3",$$$IsNone($qs(key,1)),$$$IsNone($qs(key,2)),v))
s key = $q(@key,1,v)
}
q $lts(s,", ")
}
/// <example>d ##class(test.intervalmap).Test1()</example>
ClassMethod Test1() [ Internal, ServerOnly = 1 ]
{
n %
s old=$system.Process.Undefined(2)
try{
s i=..%New()
d i.%("08:00","12:00","Иванов")
d i.%("12:00","16:00","Петров")
d i.%("15:00","16:00")
d i.%("12:00","16:00")
d i.%("11:00","15:00","Сидоров")
d i.%("15:00","17:00","Сидоров")
d i.%("17:00","20:00","Петров")
d i.%("21:00","23:00","Сидоров")
w i.Display(),!
w "[13:51] = ",i.%Get("13:51"),!
;k % m %=i.% zw %
d i.Shrink()
w i.Display(),!
}catch(ex){
#dim ex As %Exception.AbstractException
w "Error = ",ex.DisplayString(),!
}
d $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),!}
s old=$system.Process.Undefined(2)
try{
s i=..%New()
d i.%(0,5,"0-5")
d i.%(8,12,"8-12")
$$$AssertGet(i,2,"0-5")
$$$AssertGet(i,10,"8-12")
$$$AssertGet(i,-1,"")
$$$AssertGet(i,17,"")
d i.%(4,9,"4-9")
$$$Assert(i,"[0, 4] => 0-5, [4, 9] => 4-9, [9, 12] => 8-12")
d 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")
d i.%(21,,"more than twenty")
$$$AssertGet(i,42,"more than twenty")
d 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")
d i.Reset()
d i.%(0,2,1)
d i.%(2,8,2)
d i.%(4,,3)
d 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
w "Error = ",ex.DisplayString(),!
}
d $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))
s old=$system.Process.Undefined(2)
try{
s i=..%New()
d i.%(9,,"!")
$$$Assert(i,"[9, None] => !")
d i.%(,5,"Hello")
d i.%(6,7,"World")
$$$Assert(i,"[None, 5] => Hello, [6, 7] => World, [9, None] => !")
d i.%(8,10,"(Test)")
$$$Assert(i,"[None, 5] => Hello, [6, 7] => World, [8, 10] => (Test), [10, None] => !")
d i.%(,3,"My,")
$$$Assert(i,"[None, 3] => My,, [3, 5] => Hello, [6, 7] => World, [8, 10] => (Test), [10, None] => !")
d 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] => !")
d 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] => !")
d 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] => !")
w "Test 1 OK",!
d i.Reset()
d i.%(,0,"A")
d i.%(2,5,"B")
d i.%(8,10,"C")
d i.%(12,,"D")
$$$Assert(i,"[None, 0] => A, [2, 5] => B, [8, 10] => C, [12, None] => D")
d i.%(,,"K")
$$$Assert(i,"[None, None] => K")
$$$AssertGet(i,5,"K")
d i.%(0,10,"L")
d i.%(6,8,"M")
d i.%(20,,"J")
$$$AssertGet(i,-1,"K")
$$$AssertGet(i,5,"L")
$$$AssertGet(i,7,"M")
$$$AssertGet(i,9,"L")
$$$AssertGet(i,15,"K")
w "Test 2 OK",!
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")
$$$AssertGet(i,$zdh("25.09.2005"),"A")
$$$AssertGet(i,$zdh("23.10.2005"),"A")
$$$AssertGet(i,$zdh("26.10.2005"),"")
$$$AssertGet(i,$zdh("09.11.2005"),"")
$$$AssertGet(i,$zdh("16.11.2005"),"B")
$$$AssertGet(i,$zdh("23.11.2005"),"")
$$$AssertGet(i,$zdh("29.11.2005"),"")
$$$AssertGet(i,$zdh("30.11.2005"),"C")
$$$AssertGet(i,$zdh("03.12.2005"),"C")
w "Test 3 OK",!
}catch(ex){
#dim ex As %Exception.AbstractException
w "Error = ",ex.DisplayString(),!
}
d $system.Process.Undefined(old)
}
}Или скачать класс test.intervalmap.
Код тестировался на версии Caché 2015.1, но переделать класс для предыдущих версий не составит особого труда.
ссылка на оригинал статьи http://habrahabr.ru/post/256455/
Добавить комментарий