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

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

    Поскольку изначальная реализация основана на слайсах (срезах) питона, нелишней для прочтения будет статья: Всё, что вы хотели знать о слайсах. И, конечно, немного теории: Дерево Интервалов (Отрезков).
    Итак, как же слайсы будут выглядеть в 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, но переделать класс для предыдущих версий не составит особого труда.
    InterSystems
    87,00
    Вендор: СУБД Caché, OLAP DeepSee, шина Ensemble
    Поделиться публикацией

    Похожие публикации

    Комментарии 0

    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

    Самое читаемое