Pull to refresh
66.09
Rating
InterSystems
InterSystems IRIS: СУБД, ESB, BI, Healthcare

Реализация интервально-ассоциативного массива в СУБД Caché

InterSystems corporate blog Programming *
Пост написан на основе статьи на хабре: «Интервально-ассоциативный массив».

Поскольку изначальная реализация основана на слайсах (срезах) питона, нелишней для прочтения будет статья: Всё, что вы хотели знать о слайсах. И, конечно, немного теории: Дерево Интервалов (Отрезков).
Итак, как же слайсы будут выглядеть в Caché?

В целом всё (почти) как в питоне.

Легко назначить:

i=##class(test.intervalmap).%New()
i.%("08:00","12:00","Иванов")
i.%("12:00","16:00","Петров")
Как узнать кто дежурил в 13:51 ?

i.%Get("13:51"),!
Петров
Легко просмотреть поэлементно полный список (для тех, кто привык мыслить "глобально"):

%=i.% zw %
%("08:00","12:00")="Иванов"
%("12:00","16:00")="Петров"

… или одной строкой:

i.Display(),!
[08:00, 12:00] => Иванов, [12:00, 16:00] => Петров
Удаление как по частям:

i.%("15:00","16:00")
i.Display(),!
[08:00, 12:00] => Иванов, [12:00, 15:00] => Петров
… так и целиком:

i.%("12:00","16:00")
i.Display(),!
[08:00, 12:00] => Иванов
Перекрывание ключей должно обрабатываться корректно:

i.%("11:00","15:00","Сидоров")
i.Display(),!
[08:00, 11:00] => Иванов, [11:00, 15:00] => Сидоров
Cоседние ключи с одинаковыми значениями должны склеиваться автоматически. Например, если вы назначили Сидорову подежурить так же с 15 до 17, то навряд ли это должно быть две смены подряд, скорее — одна более длинная:

i.%("15:00","17:00","Сидоров")
i.Display(),!
[08:00, 11:00] => Иванов, [11:00, 17:00] => Сидоров
Добавим пару записей:

i.%("17:00","20:00","Петров")
i.%("21:00","23:00","Сидоров")
i.Display(),!
[08:00, 11:00] => Иванов, [11:00, 17:00] => Сидоров, [17:00, 20:00] => Петров, [21:00, 23:00] => Сидоров
Часто возникает задача урезать расписание, оставив из нескольких идущих подряд элементов только последние. Например, нужно узнать, кто закрывал рабочий день:

i.Shrink()
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:

i=##class(test.intervalmap).%New()
i.%(,,"Иванов")
i.%("11:00","13:00","Иванов")
i.Display(),!
[None, None] => Иванов
Одинаковые ключи в паре, как в исходном коде, здесь не допускаются, но вы для себя можете включить их обратно.
Конечно же в качестве ключей могут выступать любые числовые/строковые значения. Единственное, нужно следить, чтобы все они в рамках одного массива (объекта) были однотипны.
Например:

i=..%New()
i.%(9,,"!")
i.%(,5,"Hello")
i.%(6,7,"World")
i.Display(),!
[None, 5] => Hello, [6, 7] => World, [9, None] => !

i.Reset()
i.%(,$zdh("24.10.2005"),"A")
i.%($zdh("11.11.2005"),$zdh("17.11.2005"),"B")
i.%($zdh("30.11.2005"),,"C")
i.Display(),!
[None, 60197] => A, [60215, 60221] => B, [60234, None] => C
И напоследок ещё один пример посложнее:

i.Reset()
i.%(,,$c(8734))
i.%(10,11,"Иванов")
i.%(12,13,"Иванов")
i.%(14,16,"Петров")
i.%(11,15,"Иванов")
i.%(8,12,"Сидоров")
i.%(20,21)
i.%(22,,"Сидоров")
i.Display(),!
Результат под спойлером
[None, 8] => ∞, [8, 12] => Сидоров, [12, 15] => Иванов, [15, 16] => Петров, [16, 20] => ∞, [21, 22] => ∞, [22, None] => Сидоров

Больше примеров вы найдёте в исходном коде.

Код класса

Class test.intervalmap Extends %RegisteredObject Final ]
{
Parameter None [ FinalInternal ] = -1;
Property bounds As %List InternalPrivateReadOnlyServerOnly = 1, Transient ];
Property items As %List InternalPrivateReadOnlyServerOnly = 1, Transient ];
Property upperItem [ InitialExpression = {..#None}, InternalPrivateReadOnlyServerOnly = 1, Transient ];
Property % [ MultiDimensionalReadOnlyServerOnly = 1, Transient ];
ClassMethod Slice(list As %Liststartendvalue As %ListAs %List InternalPrivate ]
{
    
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(liststart=start+1
                
set $list(list,start,start)=value_$listbuild($list(list,start))
            
}
        }
    }
else{
        
if end="" {
            
set:start>$listlength(liststart=$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)<startstartPoint startPoint + 1
      
set:(endPoint >= 1)&&(endPoint <= $listlength(..bounds))&&($list(..bounds,endPoint)<=stopendPoint 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(xAs %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(xAs %String InternalPrivateServerOnly = 1 ]
{
    
set lo = 1
    
set hi $listlength(i%bounds)+1
    
while (lo hi{
    
set mid = (lo+hi)\2
    
if $list(i%bounds,mid) < {
        
set lo mid+1
    
else {
        
set hi mid
    
}
    }
    
quit lo
}
Method bisectRight(xAs %String InternalPrivateServerOnly = 1 ]
{
    
set lo = 1
    
set hi $listlength(i%bounds)+1
    
while (lo hi{
    
set mid = (lo+hi)\2
    
if $list(i%bounds,mid{
        
set hi mid
    
else {
        
set lo mid+1
    
}
    }
    
quit lo
}
Method repr() [ InternalPrivateServerOnly = 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() [ InternalServerOnly = 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() [ InternalServerOnly = 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() [ InternalServerOnly = 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)
}
}


Или скачать класс test.intervalmap.
Код тестировался на версии Caché 2015.1, но переделать класс для предыдущих версий не составит особого труда.
Tags:
Hubs:
Total votes 10: ↑9 and ↓1 +8
Views 2.8K
Comments Leave a comment

Information

Founded
1978
Location
США
Website
www.intersystems.com
Employees
1,001–5,000 employees
Registered