Как создать очередь в ATS?

Я могу использовать список, как стек, но что такое правильный способ создания очереди в ATS? Например, скажем, у меня есть следующий псевдокод:Как создать очередь в ATS?

val xs = queue_create() 
val() = xs.enqueue(1) 
val() = xs.enqueue(2) 
val() = print(xs.dequeue()) // print 1 
val() = xs.enqueue(3) 
val() = print(xs.dequeue()) // print 2 
val() = print(xs.dequeue()) // print 3

я должен видеть, что 1, 2 и 3 распечатываются.

источник

2016-10-25 Anonymous

Поскольку я не знаю о типе очереди, построенном в стандартной библиотеке АТС, я предлагаю свою собственную базовую реализацию одного из моих проектов, заимствован из кода, на который ссылается Linear Channels for Asynchronous IPC главы Введения в программирование в АТС книга.

См. Рабочий пример в this snippet.

источник

2016-10-25 16:14:33

Вы можете пойти длинным способом: используя два указателя на голову и хвост односвязного списка.

Однако обеспечение того, что эта реализация действительно работает, не так уж и тривиально. Он полагается на представления данных для кодирования определенных инвариантов и, следовательно, довольно сложно, но API-интерфейс, выходящий за пределы внешней стороны, совсем не сложно. Я также использовал «навязчивые» связанные списки, чтобы упростить порядок использования.

сердцевине определения являются следующие:

Просмотр для кодирования Односвязные сегментов списка: сегмент просто Односвязные где «последний» next указатель может указывать в любом месте, в том числе NULL:

dataview slseg_v 
    (addr(*self*), addr(*last node's [next]*), int(*segment length*)) = 
    | {n:nat} {l1,l2,l3:addr} 
    slseg_v_cons (l1, l3, n+1) of (
     mfree_gc_v (l1), slseg_node_v (l2, l1), slseg_v (l2, l3, n) 
    ) // end of [slseg_v_cons] 
    | {l:addr} slseg_v_nil (l, l, 0) 
// end of [slseg_v]

Тип для списка на основе очереди: оно либо пусто, либо содержит размер, указатель на голову сегмента и указатель на хвост сегмента:

datavtype queuelst_vt (int) = 
    | {n:nat} {l1,l2,l3:addr} 
    queuelst_vt_some (n+1) of (
     slseg_v (l1, l2, n), 
     mfree_gc_v (l2), 
     slseg_node_v (null, l2) 
    | int n, ptr l1, ptr l2 
    ) // end of [queuelst_vt_some] 
    | queuelst_vt_none (0) of()

Вы можете запустить полный код на Glot.io

Вот немного очистили версию того же code - на этот раз, я пытался убедиться, что код имеет четкое разделение интерфейса/реализации.

источник

2016-10-26 16:02:09

Как создать очередь в ATS?

ответ

Смежные вопросы