diff options
| -rw-r--r-- | changelog.md | 1 | ||||
| -rw-r--r-- | lib/pure/collections/critbits.nim | 16 |
2 files changed, 17 insertions, 0 deletions
diff --git a/changelog.md b/changelog.md index 35da0381d..ee584e611 100644 --- a/changelog.md +++ b/changelog.md @@ -31,6 +31,7 @@ - The file descriptors created for internal bookkeeping by `ioselector_kqueue` and `ioselector_epoll` will no longer be leaked to child processes. +- `critbits` adds `commonPrefixLen`. - `relativePath(rel, abs)` and `relativePath(abs, rel)` used to silently give wrong results (see #13222); instead they now use `getCurrentDir` to resolve those cases, and this can now throw in edge cases where `getCurrentDir` throws. diff --git a/lib/pure/collections/critbits.nim b/lib/pure/collections/critbits.nim index 21354e0a8..8128877bd 100644 --- a/lib/pure/collections/critbits.nim +++ b/lib/pure/collections/critbits.nim @@ -518,6 +518,22 @@ proc `$`*[T](c: CritBitTree[T]): string = result.addQuoted(val) result.add("}") +proc commonPrefixLen*[T](c: CritBitTree[T]): int {.inline, since((1, 3)).} = + ## Returns longest common prefix length of all keys of `c`. + ## If `c` is empty, returns 0. + runnableExamples: + var c: CritBitTree[void] + doAssert c.commonPrefixLen == 0 + incl(c, "key1") + doAssert c.commonPrefixLen == 4 + incl(c, "key2") + doAssert c.commonPrefixLen == 3 + + if c.root != nil: + if c.root.isLeaf: len(c.root.key) + else: c.root.byte + else: 0 + runnableExamples: static: |