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