Реализация интервально-ассоциативного массива в СУБД Cache / forpes.ru

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

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

28.04.2015 10:46

Источник

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

Поскольку изначальная реализация основана на слайсах (срезах) питона, нелишней для прочтения будет статья: Всё, что Вы хотели знать о слайсах. И, конечно, немного теории: Дерево Интервалов (Отрезков).
Итак, как же слайсы будут выглядеть в 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] => Сидоров

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

Код класса

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)
}
}

Или скачать класс test.intervalmap.
Код тестировался на версии Cache 2015.1, но переделать класс для предыдущих версий не составит особого труда.

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

Комментарии ()