1#
2#
3#            Nim's Runtime Library
4#        (c) Copyright 2012 Andreas Rumpf
5#
6#    See the file "copying.txt", included in this
7#    distribution, for details about the copyright.
8#
9
10## An implementation of a `deque`:idx: (double-ended queue).
11## The underlying implementation uses a `seq`.
12##
13## .. note:: None of the procs that get an individual value from the deque should be used
14##   on an empty deque.
15##
16## If compiled with the `boundChecks` option, those procs will raise an `IndexDefect`
17## on such access. This should not be relied upon, as `-d:danger` or `--checks:off` will
18## disable those checks and then the procs may return garbage or crash the program.
19##
20## As such, a check to see if the deque is empty is needed before any
21## access, unless your program logic guarantees it indirectly.
22
23runnableExamples:
24  var a = [10, 20, 30, 40].toDeque
25
26  doAssertRaises(IndexDefect, echo a[4])
27
28  a.addLast(50)
29  assert $a == "[10, 20, 30, 40, 50]"
30
31  assert a.peekFirst == 10
32  assert a.peekLast == 50
33  assert len(a) == 5
34
35  assert a.popFirst == 10
36  assert a.popLast == 50
37  assert len(a) == 3
38
39  a.addFirst(11)
40  a.addFirst(22)
41  a.addFirst(33)
42  assert $a == "[33, 22, 11, 20, 30, 40]"
43
44  a.shrink(fromFirst = 1, fromLast = 2)
45  assert $a == "[22, 11, 20]"
46
47## See also
48## ========
49## * `lists module <lists.html>`_ for singly and doubly linked lists and rings
50## * `channels module <channels_builtin.html>`_ for inter-thread communication
51
52import std/private/since
53
54import math
55
56type
57  Deque*[T] = object
58    ## A double-ended queue backed with a ringed `seq` buffer.
59    ##
60    ## To initialize an empty deque,
61    ## use the `initDeque proc <#initDeque,int>`_.
62    data: seq[T]
63    head, tail, count, mask: int
64
65const
66  defaultInitialSize* = 4
67
68template initImpl(result: typed, initialSize: int) =
69  let correctSize = nextPowerOfTwo(initialSize)
70  result.mask = correctSize - 1
71  newSeq(result.data, correctSize)
72
73template checkIfInitialized(deq: typed) =
74  when compiles(defaultInitialSize):
75    if deq.mask == 0:
76      initImpl(deq, defaultInitialSize)
77
78proc initDeque*[T](initialSize: int = defaultInitialSize): Deque[T] =
79  ## Creates a new empty deque.
80  ##
81  ## Optionally, the initial capacity can be reserved via `initialSize`
82  ## as a performance optimization
83  ## (default: `defaultInitialSize <#defaultInitialSize>`_).
84  ## The length of a newly created deque will still be 0.
85  ##
86  ## **See also:**
87  ## * `toDeque proc <#toDeque,openArray[T]>`_
88  result.initImpl(initialSize)
89
90proc len*[T](deq: Deque[T]): int {.inline.} =
91  ## Returns the number of elements of `deq`.
92  result = deq.count
93
94template emptyCheck(deq) =
95  # Bounds check for the regular deque access.
96  when compileOption("boundChecks"):
97    if unlikely(deq.count < 1):
98      raise newException(IndexDefect, "Empty deque.")
99
100template xBoundsCheck(deq, i) =
101  # Bounds check for the array like accesses.
102  when compileOption("boundChecks"): # `-d:danger` or `--checks:off` should disable this.
103    if unlikely(i >= deq.count): # x < deq.low is taken care by the Natural parameter
104      raise newException(IndexDefect,
105                         "Out of bounds: " & $i & " > " & $(deq.count - 1))
106    if unlikely(i < 0): # when used with BackwardsIndex
107      raise newException(IndexDefect,
108                         "Out of bounds: " & $i & " < 0")
109
110proc `[]`*[T](deq: Deque[T], i: Natural): lent T {.inline.} =
111  ## Accesses the `i`-th element of `deq`.
112  runnableExamples:
113    let a = [10, 20, 30, 40, 50].toDeque
114    assert a[0] == 10
115    assert a[3] == 40
116    doAssertRaises(IndexDefect, echo a[8])
117
118  xBoundsCheck(deq, i)
119  return deq.data[(deq.head + i) and deq.mask]
120
121proc `[]`*[T](deq: var Deque[T], i: Natural): var T {.inline.} =
122  ## Accesses the `i`-th element of `deq` and returns a mutable
123  ## reference to it.
124  runnableExamples:
125    var a = [10, 20, 30, 40, 50].toDeque
126    inc(a[0])
127    assert a[0] == 11
128
129  xBoundsCheck(deq, i)
130  return deq.data[(deq.head + i) and deq.mask]
131
132proc `[]=`*[T](deq: var Deque[T], i: Natural, val: sink T) {.inline.} =
133  ## Sets the `i`-th element of `deq` to `val`.
134  runnableExamples:
135    var a = [10, 20, 30, 40, 50].toDeque
136    a[0] = 99
137    a[3] = 66
138    assert $a == "[99, 20, 30, 66, 50]"
139
140  checkIfInitialized(deq)
141  xBoundsCheck(deq, i)
142  deq.data[(deq.head + i) and deq.mask] = val
143
144proc `[]`*[T](deq: Deque[T], i: BackwardsIndex): lent T {.inline.} =
145  ## Accesses the backwards indexed `i`-th element.
146  ##
147  ## `deq[^1]` is the last element.
148  runnableExamples:
149    let a = [10, 20, 30, 40, 50].toDeque
150    assert a[^1] == 50
151    assert a[^4] == 20
152    doAssertRaises(IndexDefect, echo a[^9])
153
154  xBoundsCheck(deq, deq.len - int(i))
155  return deq[deq.len - int(i)]
156
157proc `[]`*[T](deq: var Deque[T], i: BackwardsIndex): var T {.inline.} =
158  ## Accesses the backwards indexed `i`-th element and returns a mutable
159  ## reference to it.
160  ##
161  ## `deq[^1]` is the last element.
162  runnableExamples:
163    var a = [10, 20, 30, 40, 50].toDeque
164    inc(a[^1])
165    assert a[^1] == 51
166
167  xBoundsCheck(deq, deq.len - int(i))
168  return deq[deq.len - int(i)]
169
170proc `[]=`*[T](deq: var Deque[T], i: BackwardsIndex, x: sink T) {.inline.} =
171  ## Sets the backwards indexed `i`-th element of `deq` to `x`.
172  ##
173  ## `deq[^1]` is the last element.
174  runnableExamples:
175    var a = [10, 20, 30, 40, 50].toDeque
176    a[^1] = 99
177    a[^3] = 77
178    assert $a == "[10, 20, 77, 40, 99]"
179
180  checkIfInitialized(deq)
181  xBoundsCheck(deq, deq.len - int(i))
182  deq[deq.len - int(i)] = x
183
184iterator items*[T](deq: Deque[T]): lent T =
185  ## Yields every element of `deq`.
186  ##
187  ## **See also:**
188  ## * `mitems iterator <#mitems.i,Deque[T]>`_
189  runnableExamples:
190    from std/sequtils import toSeq
191
192    let a = [10, 20, 30, 40, 50].toDeque
193    assert toSeq(a.items) == @[10, 20, 30, 40, 50]
194
195  var i = deq.head
196  for c in 0 ..< deq.count:
197    yield deq.data[i]
198    i = (i + 1) and deq.mask
199
200iterator mitems*[T](deq: var Deque[T]): var T =
201  ## Yields every element of `deq`, which can be modified.
202  ##
203  ## **See also:**
204  ## * `items iterator <#items.i,Deque[T]>`_
205  runnableExamples:
206    var a = [10, 20, 30, 40, 50].toDeque
207    assert $a == "[10, 20, 30, 40, 50]"
208    for x in mitems(a):
209      x = 5 * x - 1
210    assert $a == "[49, 99, 149, 199, 249]"
211
212  var i = deq.head
213  for c in 0 ..< deq.count:
214    yield deq.data[i]
215    i = (i + 1) and deq.mask
216
217iterator pairs*[T](deq: Deque[T]): tuple[key: int, val: T] =
218  ## Yields every `(position, value)`-pair of `deq`.
219  runnableExamples:
220    from std/sequtils import toSeq
221
222    let a = [10, 20, 30].toDeque
223    assert toSeq(a.pairs) == @[(0, 10), (1, 20), (2, 30)]
224
225  var i = deq.head
226  for c in 0 ..< deq.count:
227    yield (c, deq.data[i])
228    i = (i + 1) and deq.mask
229
230proc contains*[T](deq: Deque[T], item: T): bool {.inline.} =
231  ## Returns true if `item` is in `deq` or false if not found.
232  ##
233  ## Usually used via the `in` operator.
234  ## It is the equivalent of `deq.find(item) >= 0`.
235  runnableExamples:
236    let q = [7, 9].toDeque
237    assert 7 in q
238    assert q.contains(7)
239    assert 8 notin q
240
241  for e in deq:
242    if e == item: return true
243  return false
244
245proc expandIfNeeded[T](deq: var Deque[T]) =
246  checkIfInitialized(deq)
247  var cap = deq.mask + 1
248  if unlikely(deq.count >= cap):
249    var n = newSeq[T](cap * 2)
250    var i = 0
251    for x in mitems(deq):
252      when nimvm: n[i] = x # workaround for VM bug
253      else: n[i] = move(x)
254      inc i
255    deq.data = move(n)
256    deq.mask = cap * 2 - 1
257    deq.tail = deq.count
258    deq.head = 0
259
260proc addFirst*[T](deq: var Deque[T], item: sink T) =
261  ## Adds an `item` to the beginning of `deq`.
262  ##
263  ## **See also:**
264  ## * `addLast proc <#addLast,Deque[T],sinkT>`_
265  runnableExamples:
266    var a = initDeque[int]()
267    for i in 1 .. 5:
268      a.addFirst(10 * i)
269    assert $a == "[50, 40, 30, 20, 10]"
270
271  expandIfNeeded(deq)
272  inc deq.count
273  deq.head = (deq.head - 1) and deq.mask
274  deq.data[deq.head] = item
275
276proc addLast*[T](deq: var Deque[T], item: sink T) =
277  ## Adds an `item` to the end of `deq`.
278  ##
279  ## **See also:**
280  ## * `addFirst proc <#addFirst,Deque[T],sinkT>`_
281  runnableExamples:
282    var a = initDeque[int]()
283    for i in 1 .. 5:
284      a.addLast(10 * i)
285    assert $a == "[10, 20, 30, 40, 50]"
286
287  expandIfNeeded(deq)
288  inc deq.count
289  deq.data[deq.tail] = item
290  deq.tail = (deq.tail + 1) and deq.mask
291
292proc toDeque*[T](x: openArray[T]): Deque[T] {.since: (1, 3).} =
293  ## Creates a new deque that contains the elements of `x` (in the same order).
294  ##
295  ## **See also:**
296  ## * `initDeque proc <#initDeque,int>`_
297  runnableExamples:
298    let a = toDeque([7, 8, 9])
299    assert len(a) == 3
300    assert $a == "[7, 8, 9]"
301
302  result.initImpl(x.len)
303  for item in items(x):
304    result.addLast(item)
305
306proc peekFirst*[T](deq: Deque[T]): lent T {.inline.} =
307  ## Returns the first element of `deq`, but does not remove it from the deque.
308  ##
309  ## **See also:**
310  ## * `peekFirst proc <#peekFirst,Deque[T]_2>`_ which returns a mutable reference
311  ## * `peekLast proc <#peekLast,Deque[T]>`_
312  runnableExamples:
313    let a = [10, 20, 30, 40, 50].toDeque
314    assert $a == "[10, 20, 30, 40, 50]"
315    assert a.peekFirst == 10
316    assert len(a) == 5
317
318  emptyCheck(deq)
319  result = deq.data[deq.head]
320
321proc peekLast*[T](deq: Deque[T]): lent T {.inline.} =
322  ## Returns the last element of `deq`, but does not remove it from the deque.
323  ##
324  ## **See also:**
325  ## * `peekLast proc <#peekLast,Deque[T]_2>`_ which returns a mutable reference
326  ## * `peekFirst proc <#peekFirst,Deque[T]>`_
327  runnableExamples:
328    let a = [10, 20, 30, 40, 50].toDeque
329    assert $a == "[10, 20, 30, 40, 50]"
330    assert a.peekLast == 50
331    assert len(a) == 5
332
333  emptyCheck(deq)
334  result = deq.data[(deq.tail - 1) and deq.mask]
335
336proc peekFirst*[T](deq: var Deque[T]): var T {.inline, since: (1, 3).} =
337  ## Returns a mutable reference to the first element of `deq`,
338  ## but does not remove it from the deque.
339  ##
340  ## **See also:**
341  ## * `peekFirst proc <#peekFirst,Deque[T]>`_
342  ## * `peekLast proc <#peekLast,Deque[T]_2>`_
343  runnableExamples:
344    var a = [10, 20, 30, 40, 50].toDeque
345    a.peekFirst() = 99
346    assert $a == "[99, 20, 30, 40, 50]"
347
348  emptyCheck(deq)
349  result = deq.data[deq.head]
350
351proc peekLast*[T](deq: var Deque[T]): var T {.inline, since: (1, 3).} =
352  ## Returns a mutable reference to the last element of `deq`,
353  ## but does not remove it from the deque.
354  ##
355  ## **See also:**
356  ## * `peekFirst proc <#peekFirst,Deque[T]_2>`_
357  ## * `peekLast proc <#peekLast,Deque[T]>`_
358  runnableExamples:
359    var a = [10, 20, 30, 40, 50].toDeque
360    a.peekLast() = 99
361    assert $a == "[10, 20, 30, 40, 99]"
362
363  emptyCheck(deq)
364  result = deq.data[(deq.tail - 1) and deq.mask]
365
366template destroy(x: untyped) =
367  reset(x)
368
369proc popFirst*[T](deq: var Deque[T]): T {.inline, discardable.} =
370  ## Removes and returns the first element of the `deq`.
371  ##
372  ## See also:
373  ## * `popLast proc <#popLast,Deque[T]>`_
374  ## * `shrink proc <#shrink,Deque[T],int,int>`_
375  runnableExamples:
376    var a = [10, 20, 30, 40, 50].toDeque
377    assert $a == "[10, 20, 30, 40, 50]"
378    assert a.popFirst == 10
379    assert $a == "[20, 30, 40, 50]"
380
381  emptyCheck(deq)
382  dec deq.count
383  result = move deq.data[deq.head]
384  deq.head = (deq.head + 1) and deq.mask
385
386proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} =
387  ## Removes and returns the last element of the `deq`.
388  ##
389  ## **See also:**
390  ## * `popFirst proc <#popFirst,Deque[T]>`_
391  ## * `shrink proc <#shrink,Deque[T],int,int>`_
392  runnableExamples:
393    var a = [10, 20, 30, 40, 50].toDeque
394    assert $a == "[10, 20, 30, 40, 50]"
395    assert a.popLast == 50
396    assert $a == "[10, 20, 30, 40]"
397
398  emptyCheck(deq)
399  dec deq.count
400  deq.tail = (deq.tail - 1) and deq.mask
401  result = move deq.data[deq.tail]
402
403proc clear*[T](deq: var Deque[T]) {.inline.} =
404  ## Resets the deque so that it is empty.
405  ##
406  ## **See also:**
407  ## * `shrink proc <#shrink,Deque[T],int,int>`_
408  runnableExamples:
409    var a = [10, 20, 30, 40, 50].toDeque
410    assert $a == "[10, 20, 30, 40, 50]"
411    clear(a)
412    assert len(a) == 0
413
414  for el in mitems(deq): destroy(el)
415  deq.count = 0
416  deq.tail = deq.head
417
418proc shrink*[T](deq: var Deque[T], fromFirst = 0, fromLast = 0) =
419  ## Removes `fromFirst` elements from the front of the deque and
420  ## `fromLast` elements from the back.
421  ##
422  ## If the supplied number of elements exceeds the total number of elements
423  ## in the deque, the deque will remain empty.
424  ##
425  ## **See also:**
426  ## * `clear proc <#clear,Deque[T]>`_
427  ## * `popFirst proc <#popFirst,Deque[T]>`_
428  ## * `popLast proc <#popLast,Deque[T]>`_
429  runnableExamples:
430    var a = [10, 20, 30, 40, 50].toDeque
431    assert $a == "[10, 20, 30, 40, 50]"
432    a.shrink(fromFirst = 2, fromLast = 1)
433    assert $a == "[30, 40]"
434
435  if fromFirst + fromLast > deq.count:
436    clear(deq)
437    return
438
439  for i in 0 ..< fromFirst:
440    destroy(deq.data[deq.head])
441    deq.head = (deq.head + 1) and deq.mask
442
443  for i in 0 ..< fromLast:
444    destroy(deq.data[deq.tail])
445    deq.tail = (deq.tail - 1) and deq.mask
446
447  dec deq.count, fromFirst + fromLast
448
449proc `$`*[T](deq: Deque[T]): string =
450  ## Turns a deque into its string representation.
451  runnableExamples:
452    let a = [10, 20, 30].toDeque
453    assert $a == "[10, 20, 30]"
454
455  result = "["
456  for x in deq:
457    if result.len > 1: result.add(", ")
458    result.addQuoted(x)
459  result.add("]")
460