queue.pony

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Queue[A]
  embed _array: Array[A]
  var _size: USize
  var _start: USize
  var _next: USize

  new create(space': USize = 0) =>
    _array = Array[A](space')
    _size = 0
    _start = 0
    _next = 0

  fun size(): USize =>
    _size

  fun space(): USize =>
    _array.space()

  fun apply(i: USize): this->A ? =>
    if i >= _size then
      error
    end
    let index = (_start + i) % _array.size()
    _array(index)?

  fun ref clear() =>
    _array.clear()
    _array.compact()
    _size = 0
    _start = 0
    _next = 0

  fun ref compact() =>
    _array.compact()

  fun ref pop(): A ? =>
    if _size == 0 then
      error
    end
    let index = _start
    _start = (_start + 1) % _array.size()
    _size = _size - 1
    _array(index)?

  fun ref push(value: A) =>
    if _size < _array.size() then
      try
        if _next == _array.size() then
          _next = 0
        end
        _array.update(_next, consume value)?
        _next = _next + 1
        _size = _size + 1
      end
    else
      try
        _array.insert(_next, consume value)?
        if _start > _next then
          _start = _start + 1
        end
        _next = _next + 1
        _size = _size + 1
      end
    end

  fun values(): _QueueIterator[A, this->Queue[A]] =>
    _QueueIterator[A, this->Queue[A]](this)

class _QueueIterator[A, B: Queue[A] #read] is Iterator[B->A]
  let _queue: B
  var _cur: USize = 0

  new create(queue: B) =>
    _queue = queue

  fun has_next(): Bool =>
    _cur < _queue.size()

  fun ref next(): B->A ? =>
    _queue(_cur = _cur + 1)?