This Nim code implements the Merge Sort algorithm, a highly efficient, comparison-based sorting technique. It recursively divides the input sequence into smaller halves, sorts them, and then merges the sorted halves. Thi...

Merge Sort is a divide-and-conquer algorithm. It works by recursively breaking down the array into halves until each subarray contains only one element (which is considered sorted). Then, it repeatedly merges these subarrays to produce new sorted subarrays until there is only one sorted array remaining. The `mergeSortRecursive` function handles the division, and the `merge` function combines two sorted subarrays. The time complexity is O(n log n) in all cases (best, average, and worst) because the dividing and merging steps always take the same amount of time. The space complexity is O(n) due to the auxiliary space required for the temporary buffer used during the merge operation. Edge cases like empty arrays or arrays with a single element are handled by the base case condition `arr.len <= 1`.

function mergeSort(array): if array.length <= 1: return create tempBuffer of same size as array call mergeSortRecursive(array, tempBuffer, 0, array.length - 1) function mergeSortRecursive(array, temp, left, right): if le...

This Nim code implements a recursive binary search algorithm to efficiently find a target value within a sorted sequence of integers. It handles edge cases such as an empty input sequence. Binary search is a fundamental...

The binary search algorithm works by repeatedly dividing the search interval in half. It starts with an interval covering the whole sequence. If the value of the search key is less than the item in the middle of the interval, the algorithm narrows the interval to the lower half. Otherwise, it narrows it to the upper half. This process continues until the value is found or the interval is empty. The time complexity is O(log n) because the search space is halved in each step. The space complexity is O(log n) due to the recursive call stack, or O(1) if implemented iteratively. Edge cases like an empty array or the target being outside the range are handled. The loop invariant is that the target, if present, always lies within the `low` and `high` indices.

function binarySearch(array, target): if array is empty: return -1 call binarySearchHelper(array, target, 0, array.length - 1) function binarySearchHelper(array, target, low, high): if low > high: return -1 mid = low + (...

This Nim code defines a simple procedure `reverseString` that takes a string and returns its reversed version. It iterates through the input string from the last character to the first, appending each character to a new...

The `reverseString` procedure iterates through the input string `s` from its last character (index `s.len - 1`) down to the first character (index 0) using the `countdown` iterator. In each iteration, the character at the current index `i` is appended to the `reversed` string. This builds the reversed string character by character. The time complexity is O(N), where N is the length of the string, because each character is processed exactly once. The space complexity is also O(N) because a new string of the same length is created to store the reversed result. Edge cases like an empty string or a single-character string are handled correctly by the loop bounds.

Procedure reverseString(inputString): Initialize reversedString as empty For i from length(inputString) - 1 down to 0: Append character at inputString[i] to reversedString Return reversedString

This Nim code demonstrates binary serialization and deserialization for a custom `Person` object. It defines procedures to write the object's fields (string, int, bool) into a byte stream and read them back. This is cruc...

The `serializePerson` procedure writes the `Person` object's fields to a `Stream`. For the `name` string, it first writes its length as a 32-bit integer, followed by the raw bytes of the string. The `age` (an `int`) is written as a 32-bit integer, assuming little-endian byte order. The `isStudent` boolean is written as a single byte. The `deserializePerson` procedure reverses this process: it reads the name length, then the name bytes, then the age, and finally the boolean. Basic validation is included for string length during deserialization. The time complexity for both serialization and deserialization is O(L), where L is the length of the string field, as string operations dominate. Space complexity is O(L) for creating byte sequences during string handling. Edge cases like empty strings and different boolean values are handled.

Type Person: name: string age: integer isStudent: boolean Procedure serializePerson(person, stream): Convert person.name to bytes Write length of name bytes to stream (as int32) Write name bytes to stream Write person.ag...

This Nim code implements a thread-safe bounded queue using Nim's `concurrency` module, specifically `Channel`. The `BoundedQueue` type wraps a `Channel` and enforces a capacity. Producers `enqueue` items, and if the queu...

Nim's `Channel[T]` type inherently provides bounded queue functionality. When a `Channel` is created with a capacity, `send` operations will block if the channel is full, and `recv` operations will block if it's empty. The `BoundedQueue` object simply wraps this `Channel` and exposes `enqueue` and `dequeue` methods. The `producer` and `consumer` procedures demonstrate how to use the queue concurrently. Producers add items, simulating work with `sleep`, and consumers remove items, also simulating work. The `main` procedure sets up multiple producers and consumers, spawns them using `spawn`, and then uses `joinAsyncProcess` to wait for all threads to complete. The time complexity for `enqueue` and `dequeue` is O(1) on average, as channel operations are typically efficient. The space complexity is O(C) where C is the capacity of the channel, for storing items in the queue.

Type BoundedQueue[T]: channel: Channel[T] capacity: integer Procedure newBoundedQueue[T](capacity): If capacity <= 0, raise error Create a Channel[T] with the given capacity Return BoundedQueue with the channel and capac...

This Nim code implements a basic memory pool for fixed-size objects. It pre-allocates a contiguous block of memory and manages a linked list of free blocks. When an object is requested, a block is taken from the free lis...

The `MemoryPool` object manages a contiguous chunk of memory (`poolPtr`) divided into fixed-size `blockSize` blocks. A `freeList` (a linked list of `MemoryBlock` pointers) tracks available blocks. `allocate` removes a block from the head of the `freeList` and returns its pointer. If `freeList` is `nil`, the pool is exhausted, and an error is raised. `deallocate` takes a pointer, validates it (basic checks for being within pool bounds and alignment), and prepends it to the `freeList`. `destroyMemoryPool` frees the entire pre-allocated memory chunk. The time complexity for `allocate` and `deallocate` is O(1) because they involve simple pointer manipulations. The space complexity is O(N) where N is `numBlocks`, for the pre-allocated memory. This approach avoids the overhead of general-purpose allocators for frequent small allocations.

Type MemoryBlock: next: pointer to MemoryBlock // data follows Type MemoryPool: blockSize: integer numBlocks: integer poolPtr: pointer to MemoryBlock freeList: pointer to MemoryBlock Procedure newMemoryPool(blockSize, nu...

This Nim code defines a compile-time macro `stringToIntLiteral` that converts a string literal into an integer. It leverages `strutils.parseInt` within the macro to perform the conversion during compilation, ensuring tha...

The `stringToIntLiteral` macro takes a `typedesc[string]` argument, which signifies that it expects a string literal. Inside the macro, it first checks if the input `s` is indeed a string literal (`nnkStrLit`). If not, it raises a compile-time error. If it is a string literal, it extracts the string value (`s.strVal`) and attempts to parse it into an integer using `strutils.parseInt`. If `parseInt` succeeds, a new integer literal node (`nnkIntLit`) is created with the parsed value and returned. If `parseInt` fails (e.g., the string is not a valid integer), a compile-time error is raised. The time complexity of the macro execution is effectively O(L) where L is the length of the string literal, due to the `parseInt` operation. The space complexity is O(1) during macro expansion.

Macro stringToIntLiteral(s): If s is not a string literal: Raise compile-time error "Argument must be a string literal." Get the string value from s Try: Parse the string value into an integer (intVal) Create and return...

This Nim code defines a simple Domain-Specific Language (DSL) using macros for creating application configurations. The `defineConfig` macro parses a declarative syntax, allowing users to define configuration sections an...

The `defineConfig` macro leverages Nim's metaprogramming capabilities to parse a custom syntax at compile time. The macro expects a body of code that defines sections (using identifier followed by a colon) and key-value pairs (identifier = string literal). It iterates through the `body`'s children, identifying `nnkIdentDefs` as section headers and `nnkCall` (specifically, identifier = string literal) as key-value assignments. It builds a `Table[string, Table[string, ConfigValue]]` structure (`AppConfig`) to store the configuration. Error handling is included for incorrect syntax or attempting to define keys outside of sections. The time complexity during macro expansion is proportional to the size of the configuration definition. The generated code's runtime complexity for accessing configuration values is O(1) on average for hash table lookups.

Macro defineConfig(body): Initialize result as an empty AppConfig table Initialize currentSection as empty string For each item in body: If item is an identifier followed by a colon (section definition): Set currentSecti...