### B-tree Order 3 Example Visualization Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst A visual representation of a B-tree of order 3, illustrating the arrangement of keys and nodes (interior and leaf) and the hierarchical structure. ```none Example: B-tree of order 3 +---+ | 4 | root node / interior node +---+ / \ +---+ +---+---+ | 2 | | 7 | 9 | interior nodes +---+ +---+---+ | | / | \ +---+ +---+ +---+---+ +---+ +---+ | 1 | | 3 | | 5 | 6 | | 8 | | 10| leaf nodes +---+ +---+ +---+---+ +---+ +---+ ``` -------------------------------- ### Install Fmlib Libraries with Opam Source: https://github.com/hbr/fmlib/blob/master/README.md Installs various Fmlib libraries using the OCaml package manager 'opam'. This is the recommended method for integrating Fmlib into your projects. ```shell opam install fmlib_std opam install fmlib_pretty opam install fmlib_parse opam install fmlib_browser ``` -------------------------------- ### Configure Dune for Fmlib Usage Source: https://github.com/hbr/fmlib/blob/master/README.md Example of a dune file configuration for a program named 'foo' that utilizes the 'fmlib_std' library. This demonstrates how to link external libraries in a dune project. ```dune (executable (name foo) (libraries fmlib_std ... ) ) ``` -------------------------------- ### OCaml Start and End Indent Functions Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/parsing/layout.rst Implements OCaml functions 'start_indent' and 'end_indent' for managing indented blocks. 'start_indent' calculates the new indentation state based on the current column and indentation amount, while 'end_indent' restores the previous state. ```ocaml let start_indent (i: int) (ind: t): t = assert (0 <= i); if ind.abs then (* No effect on aligned structures which have not yet received a first token. *) ind else match ind.ub with | None -> (* It does not make sense to indent relative to something which does not yet have any token. *) ind | Some ub -> { lb = ub + i; ub = None; abs = false; } let end_indent (ind0: t) (ind: t): t = if ind0.abs || ind0.ub = None then ind else ind0 ``` -------------------------------- ### Fmlib_parse: Byte vs. Character Position Distinction Source: https://github.com/hbr/fmlib/blob/master/CHANGES.md Enhances the `Position` module to differentiate between byte and character positions, including the absolute byte offset from the start of the file. ```ocaml - `Fmlib_parse`: - module `Position` distinguishes byte and character position. The absolute byte offset from the beginning of the file is included. ``` -------------------------------- ### OCaml Helper Function: Subarray Extraction Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Extracts a subarray from a given array within specified start and beyond indices. Asserts valid index ranges. ```ocaml subarray (arr: 'a array) (start: int) (beyond: int): 'a t = (* The subarray of [arr] starting at [start] and ending one before [beyond]. *) assert (0 <= start); assert (start <= beyond); assert (beyond <= Array.length arr); Array.sub arr start (beyond - start) ``` -------------------------------- ### Fmlib_browser: Animation Subscription and HTML Mapping Source: https://github.com/hbr/fmlib/blob/master/CHANGES.md Adds subscription for animations and introduces mapping functions for HTML elements and attributes, improving dynamic content updates. ```ocaml - `Fmlib_browser`: - Added subscription `on_animation`. - Added `Html.map` and `Attribute.map`. - Text in textnodes is now overwritten instead of creating a new node. ``` -------------------------------- ### Fmlib_browser: Debugging, Property Updates, and Sandbox Features Source: https://github.com/hbr/fmlib/blob/master/CHANGES.md Introduces debugging functions, corrects the update mechanism for 'value' to use properties instead of attributes, and adds advanced features like `sandbox_plus` and `basic_application`. ```ocaml - `Fmlib_browser`: - Added `debug` functions - Fix: Set `value` property and not `value` attribute. Reason: The browser updates only the property and not the attribute. - Added `sandbox_plus` (a sandbox with subscriptions) and `basic_application`(an application without javascript communication). - Added namespace elements and `svg` elements. - Added `Subscription.on_keyup`. - Added `Command.map`. - Added `Command.just_do` which does not send a message back to the application. - Added examples from the 7 Guis. ``` -------------------------------- ### B-Tree Node Splitting: Even Order (m = 2k) Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Illustrates the splitting of an interior node in a B-tree when the order is even (m = 2k). It covers two cases: i < k and i >= k, showing the 'before' and 'after' states of the node structure with key-value pairs and child pointers. ```none i < k: before: i k +---------+---+----+---+------------------+ | | z | | s | | +---------+---+----+---+------------------+ | t after: +---+ | s | +---+ i | | +---------+---+---+-----+ +------------------+ | | y | z | | | | +---------+---+---+-----+ +------------------+ | | u v i >= k: before: k i +------------------+---+----+---+---------+ | | s | | z | | +------------------+---+----+---+---------+ | t after: +---+ | s | +---+ | | +------------------+ +-----+---+---+---------+ ``` -------------------------------- ### JavaScript WebApp Message Handling Source: https://github.com/hbr/fmlib/blob/master/src/examples/browser/index.html A JavaScript function 'receive' designed to handle incoming messages from a web application. It logs the received value, echoes it back, and posts it using 'webapp.post'. The 'webapp.init' function is used to initialize the web application with this message handler. ```javascript function receive (v) { console.log ("message received in javascript"); console.log (v); console.log ("echo back"); webapp.post(v); } webapp.init ({ data: null, onMessage: receive }); ``` -------------------------------- ### OCaml Binary Search Basic Algorithm Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/array.rst Illustrates the core logic of the binary search algorithm, focusing on the recursive search between lower and upper bounds. It handles the case where an exact match is found or narrows down the search range. ```OCaml let rec search lower upper = (* Invariant: 0 <= lower < upper < len arr.(lower) < key < arr.(upper) *) if lower + 1 = upper then upper, false else let mid = lower + (upper - lower) / 2 in let cmp = compare key (key_of arr.(mid)) in if cmp < 0 then search lower mid else if cmp = 0 then mid, true else search mid upper ``` -------------------------------- ### Google Analytics Configuration Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/_templates/layout.html This snippet configures Google Analytics for the project using gtag.js. It initializes the data layer and sets the tracking configuration. ```html {% extends "!layout.html" %} {% block extrahead %} window.dataLayer = window.dataLayer || [ ]; function gtag(){dataLayer.push(arguments);} gtag('js', new Date()); gtag('config', 'G-W295PVPC2K'); {% endblock %} ``` -------------------------------- ### B-Tree Merge Visualization (None) Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Diagram illustrating the 'merge before' and 'merge after' states of B-tree siblings during an underflow resolution. It shows how keys and children are rearranged to maintain the B-tree properties. ```none merge before: i +---------------------+---+--------------------+ parent node | | y | | +---------------------+---+--------------------+ | | +-----------+---+ +---+-----------------+ siblings | | x | | z | | +-----------+---+ +---+-----------------+ | | u v underflow minimal merge after: i +---------------------+--------------------+ parent node | | | +---------------------+--------------------+ | +-----------+---+---+---+-----------------+ siblings | | x | y | z | | +-----------+---+---+---+-----------------+ | | u v ``` -------------------------------- ### B-Tree Node Splitting: Odd Order (m = 2k + 1) Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Illustrates the splitting of an interior node in a B-tree when the order is odd (m = 2k + 1). It covers three cases: i = k, i < k, and i > k, showing the 'before' and 'after' states of the node structure with key-value pairs and child pointers. ```none i = k: before: i k 2k +-----------------+---+---+------------------+ | | s1| s2| | +-----------------+---+---+------------------+ | t after: +---+ | y | +---+ | | +-----------------+---+ +---+------------------+ | | s1| | s2| | +-----------------+---+ +---+------------------+ | | u v i < k: before: i k 2k +------+---+------+---+---+------------------+ | | z | | s1| s2| | +------+---+------+---+---+------------------+ | t after: +---+ | s1| +---+ i | | +------+---+---+------+ +---+------------------+ | | y | z | | | s2| | +------+---+---+------+ +---+------------------+ | | u v i > k: before: k i 2k +-----------------+---+---+----+---+---------+ | | s1| s2| | z | | +-----------------+---+---+----+---+---------+ | t after: +---+ | s2| +---+ | | +-----------------+---+ +-----+---+---+--------+ | | s1| | | y | z | | +-----------------+---+ +-----+---+---+--------+ ``` -------------------------------- ### OCaml Binary Search Complete Algorithm Signature Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/array.rst Provides the signature for the complete binary search function in OCaml, including the necessary comparison and key extraction functions, the search key, and the array. ```OCaml let binsearch (compare: 'key -> 'key -> int) (* Comparison function. *) (key_of: 'item -> 'key) (* Extract a key from an item. *) ``` -------------------------------- ### Radix Balanced Array Structure (B=2) Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/rb_array.rst Illustrates the chunking of elements into arrays and their organization within a radix tree for a branching factor of 2. Shows how elements are distributed across different levels of the tree. ```none chunk₀ chunk₁ chunk₂ +---+---+ +---+---+ +---+ | e₀| e₁| | e₂| e₃| | e₄| +---+---+ +---+---+ +---+ 0 1 2 3 4 size 5 +---+---+ | | | level 2 +---+---+ / \ size 4 / \size 1 +---+---+ +---+ | | | | | level 1 +---+---+ +---+ / \ / / \ / +---+---+ +---+---+ +---+ | e₀| e₁| | e₂| e₃| | e₄| level 0 +---+---+ +---+---+ +---+ 0 1 2 3 4 ``` -------------------------------- ### Fmlib_parse: Unicode Parsing and Partial Parsing Support Source: https://github.com/hbr/fmlib/blob/master/CHANGES.md Introduces unicode parsing capabilities and enhances support for partial parsing, including lexer integration. It also adds byte position tracking for more precise error reporting. ```ocaml - `Fmlib_parse`: Added unicode parsing Added `byte_position` and `byte_offset` to module `Position` Added and streamlined support for partial parsing. In particular the parsers with lexers support fully partial parsers. Glueing of partial parsers now works with `fold_lookahead` or `transfer_lookahead`. ``` -------------------------------- ### Fmlib_parse: Lexer Error Reporting and Character Module Enhancements Source: https://github.com/hbr/fmlib/blob/master/CHANGES.md Addresses an issue with syntax error reporting in parsers with separate lexers, improves documentation for lexer-parser combinations, and expands the `Character` module for lexer development. ```ocaml - `Fmlib_parse`: - Fix: In a parser with a separate lexer a syntax error in the lexer immedately before the end of input had not been reported correctly. - More documentation on parsers with lexers. - More functionality in the module `Character` to support writing of lexers. E.g. `make_partial`, `restart_partial`, `lexer`. - Removed duplicate module `Error_reporter`. ``` -------------------------------- ### Visual Representation of Leaf Node Insertion (i < k) Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Diagram illustrating the state of a leaf node before and after inserting element 'y' when the insertion index 'i' is less than the split point 'k'. ```none before: i k +---------+---+----+---+------------------+ | | z | | s | | +---------+---+----+---+------------------+ after: +---+ | s | +---+ i | | +---------+---+---+-----+ +------------------+ | | y | z | | | | +---------+---+---+-----+ +------------------+ ``` -------------------------------- ### Fmlib_pretty: Write to Channel Functionality Source: https://github.com/hbr/fmlib/blob/master/CHANGES.md Adds the `write_to_channel` function to the `Fmlib_pretty` module for outputting pretty-printed content to a channel. ```ocaml ## `Fmlib_pretty` - Added function 'write_to_channel' ``` -------------------------------- ### APIDOC: Parsing Expression Grammar Formalism Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/parsing/layout.rst This section details the formal mathematical notation used to describe the parsing expression grammar, including success and failure conditions for various grammar constructs. ```APIDOC Indentation Sets: - Represented as [a, b], where a is the lower bound and b is the upper bound (can be infinity). - A valid set has a <= b. - If b is not infinity, it's the column of the leftmost token encountered. - If b is infinity, no token has been encountered yet. - The initial indentation set for a start expression is [0, infinity]. Parsing Success Condition: (A, u, [0, infinity], -) => top^f_[j,k] u where A is the start symbol, u is the input stream, [0, infinity] is the initial indentation set, and k is the final indentation. Empty Expression (epsilon): - Succeeds without consuming tokens or changing state. - (epsilon, u, I, f) => top^f_I epsilon Terminal Expression (a): - Without alignment flag (+): - Success: If token a_i is at an allowed position i (j <= i) and a == b. (a, b_i u, [j,k], -) => top^-_[j, min i k] a - Failure: If i < j or a != b. (a, b_i u, [j,k], -) => perp epsilon - On success, the upper bound of the indentation set might be updated. - With alignment flag (+): - Success: If token a_i is within the indentation set I and a == b. (a, b_i u, I, +) => top^-_[i,i] a - Failure: If i is not in I or a != b. (a, b_i u, I, +) => perp epsilon - On success, the token is consumed, indentation set becomes [i,i], and alignment flag is reset. Nonterminal Expression (Ae): - Requires mapping nonterminal A to its parsing expression using function delta. - (delta(A)e, u, I, f) => o - (Ae, u, I, f) => o - Left recursion is not allowed. Sequence Expression (p1 p2): - Case 1: p1 fails. (p1, w1 w2 u, I, f) => perp w1 (p1 p2, w1 w2 u, I, f) => perp w1 - Case 2: p1 succeeds, p2 fails. (p1, w1 w2 u, I, f) => top^g_J w1 (p2, w2 u, J, g) => perp w2 (p1 p2, w1 w2 u, I, f) => perp (w1 w2) - Case 3: Both p1 and p2 succeed. The second expression uses the output state of the first as input. The final state is the final state of the second expression. ``` -------------------------------- ### Radix Tree Helper Functions (OCaml) Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/rb_array.rst Provides helper functions for radix balanced trees, including calculating bit size, slot index, and offset within a slot. These are fundamental for navigating the tree structure. ```ocaml let bitsize: int = 32 let slot (i: int) (l: int): int = (* The slot of index [i] at level [l]. i / 2^(l * bitsize) *) i lsr (l * bitsize) let offset (i: int) (s: int) (l: int): int = (* The offset of index [i] in slot [s] in a tree at level [l]. i- s * 2^(l * bitsize) *) i - s lsl (l * bitsize) ``` -------------------------------- ### Radix Balanced Array Level Properties Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/rb_array.rst Details the slot sizes and maximum element capacities for different levels of a radix balanced tree, comparing scenarios with branching factors of 2 and 32. ```none +----------+-------------+------------+-------------+------------+ | level | slot size | max size | slot size | max size | | | (B = 2) | (B = 2) | (B = 32) | (B = 32) | +----------+-------------+------------+-------------+------------+ | 0 | 1 | 2 | 1 | 32 | +----------+-------------+------------+-------------+------------+ | 1 | 2 | 4 | 32 | 1024 | +----------+-------------+------------+-------------+------------+ | 2 | 4 | 8 | 1024 | 32768 | +----------+-------------+------------+-------------+------------+ | 3 | 8 | 16 | 32768 | 1048576 | +----------+-------------+------------+-------------+------------+ ``` -------------------------------- ### Fmlib_std: Performance Improvement with Physical Identity Source: https://github.com/hbr/fmlib/blob/master/CHANGES.md Optimizes `Array` and `Btree` modules by exploiting physical identity, allowing updates with identical elements to be ignored for performance gains. ```ocaml - `Fmlib_std`: - Improved `Array` and `Btree` to exploit physical identity. An update operation where the new element is the same as the original element can be ignored. ``` -------------------------------- ### Construct Singleton Tree for Insertion Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/rb_array.rst Constructs a singleton tree at a specified level with a given element. This is used as a building block for inserting elements into a full radix balanced array, ensuring the new structure remains balanced. ```ocaml let rec singleton_tree (lev: int) (e: 'a): 'a t = (* Construct tree at level [lev] with the element [e]. *) if lev = 0 then Leaf [| e |] else Node { size = 1; level = lev; nodes = [| singleton_tree (lev - 1) e |] } ``` -------------------------------- ### Visual Representation of Leaf Node Insertion (i >= k) Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Diagram illustrating the state of a leaf node before and after inserting element 'y' when the insertion index 'i' is greater than or equal to the split point 'k'. ```none before: k i +------------------+---+----+---+---------+ | | s | | z | | +------------------+---+----+---+---------+ after: +---+ | s | +---+ | | +------------------+ +-----+---+---+---------+ | | | | y | z | | +------------------+ +-----+---+---+---------+ ``` -------------------------------- ### B-Tree Underflow Scenario Visualization Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst A visual representation of an underflow situation in a B-Tree, showing a parent node, its children, and a sibling that has underflowed. This diagram helps in understanding the context for rebalancing operations. ```none i +---------------------+---+--------------------+ parent node | | y | | +---------------------+---+--------------------+ | | +-----------+---+ +---+-----------------+ siblings | | x | | z | | +-----------+---+ +---+-----------------+ | | u v underflow no underflow ``` -------------------------------- ### Fmlib_parse: Stream Module Removal and Error Reporting Fixes Source: https://github.com/hbr/fmlib/blob/master/CHANGES.md Removes deprecated Stream module usage and includes fixes for error reporting, specifically addressing an issue with the `` operator in layout parsing. ```ocaml - Stream module is deprecated in ocaml stdlib. Therefore all usages of the Stream module are removed from `Fmlib`. - `Fmlib_parse`: - Some fixes in error reporting - Fix: Error in `` operator with layout parsing ``` -------------------------------- ### B-Tree Add Function Implementation Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Shows the OCaml implementation of the 'add' function for inserting a key-value pair into a B-Tree. It handles the case where insertion causes a split at the root. ```ocaml let add (key: Key.t) (value: 'a) (map: 'a t): 'a t = match add_aux key value map with | Normal_insert map -> map | Split_insert (left, popup_key, right) -> (* tree grows at the root *) Node ([| popup_key |], [| left; right |]) ``` -------------------------------- ### OCaml Radix Tree Pop Optional Implementation Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/rb_array.rst A variation of the 'pop' function that handles empty trees by returning an option type. It returns None for an empty tree and Some of the result for a non-empty tree. ```ocaml let pop_opt (t: 'a t): ('a * 'a t) option = if is_empty t then None else Some (pop_aux true t) ``` -------------------------------- ### OCaml Binary Search Specification Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/array.rst Defines the interface and expected behavior of the binary search function in OCaml. It specifies the comparison function, key extraction function, the key to search for, and the array to search within. ```OCaml let binsearch (compare: 'key -> 'key -> int) (* Comparison function. *) (key_of: 'item -> 'key) (* Extract a key from an item. *) (key: 'key) (* The key to be found. *) (arr: 'item array) (* The array to be search in. *) : int * bool = ... ``` -------------------------------- ### Fmlib_parse: Operator Parsing and Layout Rework Source: https://github.com/hbr/fmlib/blob/master/CHANGES.md Introduces a generic combinator for parsing operator expressions and significantly reworks the layout parsing mechanism. Also includes functions for pretty-printing errors and code snippets. ```ocaml ## `Fmlib_parse` - Changed signature of repetition combinators (e.g. 'one_or_more' and 'zero_or_more'). - Added a generic parsing combinator for parsing of operator expressions. - Complete rework of layout parsing. - Added functions to pretty print error messages and code snippets containing an error. - Documentation for parsing improved and augmented significantly. ``` -------------------------------- ### Fmlib_parse: Reworked Lookahead Access and Parser Interfaces Source: https://github.com/hbr/fmlib/blob/master/CHANGES.md Refactors lookahead access with the introduction of `fold_lookahead` as the main function. New interfaces like `MINIMAL_PARSER`, `NORMAL_PARSER`, `FULL_PARSER`, and `LEXER` are added to support token-based parsing. ```ocaml - `Fmlib_parse`: - Rework of lookahead access. Main function now `fold_lookahead`. - Added interfaces `MINIMAL_PARSER`, `NORMAL_PARSER`, `FULL_PARSER`, `LEXER`. - Added `Token_parser` and `Parse_with_lex` to support the separation of parsing and lexing. ``` -------------------------------- ### B-Tree Leaf Node Structure Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Illustrates the structure of a leaf node in a B-Tree, which consists of an array of keys or key-value pairs. ```none 0 1 2 len +----+----+------------------------------+ | k0 | k1 | ... | +----+----+------------------------------+ ``` -------------------------------- ### B-Tree Rotation Before Rebalancing Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Diagram illustrating the state of a B-Tree before a rotation operation, where an underflow has occurred in a child node and a redistribution with the right sibling is being considered. ```none rotation before: i +---------------------+---+--------------------+ parent node | | y | | +---------------------+---+--------------------+ | | +-----------+---+ +---+-----------------+ siblings | | x | | z | | +-----------+---+ +---+-----------------+ | | u v underflow no underflow ``` -------------------------------- ### OCaml Indent Module Definition Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/parsing/layout.rst Defines the 'Indent' module in OCaml, specifying the structure for indentation state including lower bound, optional upper bound, and an alignment flag. It also provides the initial state. ```ocaml module Indent = struct type t = { lb: int; (* lower bound *) ub: int option; (* upper bound or infinity *) abs: bool; (* aligment flag *) } let initial: t = {lb = 0; ub = None; align = false} ... end ``` -------------------------------- ### OCaml Consume Function for Indentation Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/parsing/layout.rst Provides the 'consume' function in OCaml, which updates the indentation state 'ind' after a token is successfully consumed at column 'i'. It handles alignment flag and updates the upper bound if necessary. ```ocaml let consume (i: int) (ind: t): t = assert (check_column i ind); if not ind.abs then (* The token might be the new leftmost token. *) match ind.ub with | Some ub when ub <= i -> ind | _ -> {ind with ub = Some i} else (* First token in an aligned structure *) { lb = i; ub = Some i; abs = false; } ``` -------------------------------- ### FMLIB Alignment Operator Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/parsing/layout.rst Explains the alignment operator (|p|) in FMLIB, which describes input sequences aligned vertically by their first token. It details how sequences like (|p| |q| ...)^n align and indent blocks. ```OCaml (* Transition of an aligned block *) (p, wu, I, +) => o ---------------------------------- (|p|, wu, I, f) => o (* adapt flag *) (* Adaptation for empty sequences: ensures alignment flag is handled correctly *) ``` -------------------------------- ### OCaml Radix Tree Pop Implementation Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/rb_array.rst The main 'pop' function implementation that asserts the tree is not empty and calls the auxiliary 'pop_aux' function. ```ocaml let pop (t: 'a t): 'a * 'a t = assert (has_some t); pop_aux true t ``` -------------------------------- ### Radix Tree Element Retrieval by Index (OCaml) Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/rb_array.rst Implements random access to elements within a radix balanced tree. It navigates the tree based on the index, calculating the appropriate slot and offset at each level. ```ocaml let rec element (i: int) (t: 'a t): 'a = (* The element at index [i] in the radix balanced array [t]. *) assert (0 <= i); assert (i < length t); match t with | Leaf arr -> arr.(i) | Node node -> let s = slot i node.level in let o = offset i s node.level in element o node.nodes.(s) ``` -------------------------------- ### Fmlib_parse: Syntax Error Range Reporting Source: https://github.com/hbr/fmlib/blob/master/CHANGES.md Fixes a bug in the Source_extractor and adds the ability to retrieve the specific range of a token that caused a syntax error, improving debugging. ```ocaml - `Fmlib_parse:`: Fix: Bug in `Source_extractor`, introduced in the previous release. Added `Parse_with_lexer.range` to return the range of the token which caused a syntax error. ``` -------------------------------- ### OCaml B-tree Map Functor Structure Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Defines the structure of an OCaml module functor for implementing finite maps using B-trees. It includes parameters like order, key comparison, and the type for B-tree nodes. ```ocaml module Map (Key: SORTABLE) = struct let order = ... (* usually 32 for cache efficiency *) let odd_order: bool = (* is the order odd? *) assert (3 <= order); (* minimal order 3 is a must *) order / 2 * 2 < order let max_keys: int = order - 1 (* the maximal number of keys *) let min_keys: int = (* the minimal number of keys *) if odd_order then (order - 1) / 2 else order / 2 - 1 type 'a pairs = (Key.t * 'a) array type 'a t = | Leaf of 'a pairs (* key value pairs *) | Node of 'a pairs * 'a t array (* key value pairs + children *) ... (* Search, insert and delete see below ... *) end ``` -------------------------------- ### Binary Search Implementation in OCaml Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/array.rst Implements a binary search algorithm for finding a key within a sorted array. Handles edge cases for empty and single-element arrays, and performs recursive searching for larger arrays. It returns the index and a boolean indicating if an exact match was found. ```ocaml let search_in_array (key: 'key) (arr: 'item array) : int * bool = let len = length arr in if len = 0 then len, false else if len = 1 then let cmp = compare key (key_of arr.(0)) in if cmp <= 0 then 0, cmp = 0 else len, false else (** length is at least 2! *) let rec search lower upper = if lower >= upper then (lower, compare key (key_of arr.(lower)) = 0) else let mid = lower + (upper - lower) / 2 in let cmp = compare key (key_of arr.(mid)) in if cmp = 0 then (mid, true) else if cmp < 0 then search lower mid else search (mid + 1) upper in let lower, upper = 0, len - 1 in let cmp = compare key (key_of arr.(lower)) in if cmp <= 0 then (* key is less or equal the first element *) lower, cmp = 0 else (* key is greater than the first element *) let cmp = compare key (key_of arr.(upper)) in if cmp < 0 then (* invariant for [search] satisfied. *) search lower upper else if cmp = 0 then (* exact match with the last element *) upper, true else (* key is greater than all elements *) len, false ``` -------------------------------- ### OCaml Node Insertion Logic Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Implements the logic for inserting a key-value pair into a node. Handles cases where the node is not full and cases where the node is full, requiring a split. It manages the rearrangement of pairs and children arrays. ```ocaml let add_in_node (i: int) (left: 'a t) (pair: Key.t * 'a) (right: 'a t) (pairs: 'a pairs) (children: 'a t array) : 'a insert = let len = Array.length pairs in if len < max_keys then let pairs = Array.insert i pair pairs and children = Array.insert i left children in children.(i + 1) <- right; Normal_insert (Node (pairs, children)) else (* Node is full. *) let k = order / 2 and insert_subarray = insert_subarray pairs i pair and split_subarray start beyond = split_subarray children i left right start beyond in if odd_order then if i = k then let left_pairs = subarray pairs 0 k and left_children = subarray children 0 (k + 1) and right_pairs = subarray pairs k len and right_children = subarray children k (len + 1) in left_children.(k) <- left; right_children.(0) <- right; Split_insert ( Node (left_pairs, left_children), pair, Node (right_pairs, right_children)) else if i < k then let left_pairs = insert_subarray 0 (k - 1) and left_children = split_subarray 0 k and right_pairs = subarray pairs k len and right_children = subarray children k (len + 1) in Split_insert ( Node (left_pairs, left_children), pairs.(k - 1), Node (right_pairs, right_children)) else begin let left_pairs = subarray pairs 0 k and left_children = subarray children 0 (k + 1) and right_pairs = insert_subarray (k + 1) len and right_children = split_subarray (k + 1) (len + 1) in Split_insert ( Node (left_pairs, left_children), pairs.(k), Node (right_pairs, right_children)) end else begin (* even order *) if i < k then let left_pairs = insert_subarray 0 (k - 1) and left_children = split_subarray 0 k and right_pairs = subarray pairs k len and right_children = subarray children k (len + 1) in Split_insert ( Node (left_pairs, left_children), pairs.(k - 1), Node (right_pairs, right_children)) else let left_pairs = subarray pairs 0 (k - 1) and left_children = subarray children 0 k and right_pairs = insert_subarray k len and right_children = split_subarray k (len + 1) in Split_insert ( Node (left_pairs, left_children), pairs.(k - 1), Node (right_pairs, right_children)) end ``` -------------------------------- ### FMLIB Indentation Operator Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/parsing/layout.rst Details the indentation operator (p^n) in FMLIB. It explains its behavior based on the alignment flag: no effect if set, and specific transitions if not set, including handling failures. ```OCaml (* Indentation with alignment flag set: no effect *) (p, wu, I, +) => o ---------------------------------- (p^n, wu, I, +) => o (* Indentation with alignment flag not set: transitions *) (p, wu, [i+n, infinity], -) => top^f_[k,l] w ---------------------------------- (p^n, wu, [i,j], -) => top^f_[i, min j (l-n)] w (* Indentation failure case *) (p, wu, I^n, -) => perp w ---------------------------------- (p^n, wu, I, -) => perp w ``` -------------------------------- ### B-Tree Search Implementation Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Provides a recursive OCaml implementation for searching a key within a B-Tree. It handles both leaf and interior nodes, utilizing the bsearch function. ```ocaml let rec find_opt (key: Key.t) (map: 'a t): 'a option = match map with | Leaf pairs -> let i, exact = bsearch key pairs in if exact then Some (snd pairs.(i)) else None | Node (pairs, children) -> let i, exact = bsearch key pairs in if exact then Some (snd pairs.(i)) else find_opt key children.(i) ``` -------------------------------- ### B-Tree Handle Delete Function Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Manages the aftermath of a deletion, specifically checking for and initiating the reparation of underflow conditions in the B-tree. ```OCaml let handle_delete (i: int) (* Index of the child where the deletion occurred. *) (pair: Key.t * 'a) (* The deleted key value pair. *) (d: 'a delete) (* The new tree with the key value pair deleted. *) (pairs: 'a pairs) (* The key value pairs of the parent. *) (children: 'a t array) (* The children of the parent. *) : 'a delete = if not d.underflow then { ``` -------------------------------- ### FMLIB Backtrack Operator Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/parsing/layout.rst Describes the effect of the backtrack operator (<-p) in FMLIB. It handles success cases without modification and converts failures with token consumption to failures without token consumption. ```OCaml (* Success case: no effect *) (p, u w, I, f) => top^g_J w ---------------------------------- (<-p, u, I, f) => top^g_J w (* Failure with token consumption: converted to failure without token consumption *) (p, u w, I, f) => perp u ---------------------------------- (<-p, u, I, f) => perp epsilon ``` -------------------------------- ### Radix Tree Level and Fullness Checks (OCaml) Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/rb_array.rst Provides functions to determine the level of a radix balanced tree node and to check if a node is full or empty. These are essential for maintaining tree invariants and performing operations efficiently. ```ocaml let level: 'a t -> int = function | Leaf _ -> 0 | Node node -> node.level let is_full: 'a t -> bool = function | Leaf arr -> Array.length arr = full_size 0 | Node node -> node.size = full_size node.level let is_empty (t: 'a t): bool = length t = 0 let has_some (t: 'a t): bool = length t > 0 ``` -------------------------------- ### Radix Tree First Element Retrieval (OCaml) Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/rb_array.rst Retrieves the first element of a non-empty radix balanced tree. It efficiently navigates to the first element by always selecting the first child node until a leaf is reached. ```ocaml let first (t: 'a t): 'a = (* The first element of the non empty radix balanced array [t]. *) assert (has_some t); let rec fst = function | Leaf arr -> Array.first arr | Node node -> fst (Array.first node.nodes) in fst t ``` -------------------------------- ### OCaml Check Column Function Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/parsing/layout.rst Implements the 'check_column' function in OCaml to determine if a token is allowed at a specific column 'i' based on the provided indentation state 'ind'. It checks lower bound and alignment conditions. ```ocaml let check_column (i: int) (ind: t): bool = ind.lb <= i && ( match ub with | Some ub when ind.abs -> i <= ub | _ -> true ) ``` -------------------------------- ### CSS Keyframes for Rolling Animation Source: https://github.com/hbr/fmlib/blob/master/src/examples/browser/index.html Defines a CSS keyframe animation named 'rolling'. This animation controls the 'left' property of an element, creating a back-and-forth movement. ```css @keyframes rolling { 0% {left:0px;} 50% {left:10px;} 100% {left:0px;} } ``` -------------------------------- ### FMLIB Biased Choice Operator Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/parsing/layout.rst Defines the behavior of the biased choice operator (p1 / p2) in FMLIB, distinguishing cases based on the success or failure of the first expression and token consumption. ```OCaml (* Case 1: First expression succeeds *) (p1, w u, I, f) => top^g_J w ---------------------------------- (p1 / p2, w u, I, f) => top^g_J w (* Case 2: First expression fails with token consumption *) (p1, w u, I, f) => perp w w != epsilon ---------------------------------- (p1 / p2, w u, I, f) => perp w (* Case 3: First expression fails without token consumption *) (p1, u, I, f) => perp epsilon (p2, u, I, f) => o ---------------------------------- (p1 / p2, u, I, f) => o ``` -------------------------------- ### Binary Search Function Signature Source: https://github.com/hbr/fmlib/blob/master/src/sdoc/datastructures/btree.rst Defines the signature for a binary search function used within B-Tree nodes to find keys. It returns the position of the key and a boolean indicating an exact match. ```ocaml let bsearch (key: Key.t) (arr: 'a pairs): int * bool = ... ```