Jibini.CommonUtil

Shared parsing and algorithmic utilities which often come in handy

Provided Data Structures

Finite State Automata (Regex)

Parsers and evaluators to work with a subset of regular expression in a lexical analysis context.

• Validate and compile regular expression into state machines
• Minimize FSAs into deterministic state machines
• Knit FSAs for multiple tokens into one larger state machine which can match several tokens
• Tokenize input texts with a default single token of lookahead
• Serialize and deserialize state machines

Quad-tree Spatial Search

Search for items in 2D space having coordinates within a square search area.

• Optimize searching for an element's closest neighbor
• Optimize searching for elements near the coordinates of a user's interaction
• Find all elements falling within a 2D fenced search area

Trampolined Execution Context

Execution wrapper for unbound recursion on the heap. Execution frames are allowed to execute work at the time of initial execution, call recursive actions, and push actions for exection after all recursive work is complete.

Provided Algorithms

Lexer Generator

Define a grammar of tokens and create a matching DFA which will match and identify any token from the language in linear time.

• Generate grammars at runtime
• Generate grammars at development time and load them from file

Parser Generator

Define language production rules and top-down parsing logic which will be called in a trampolined execution context for theoretically unlimited push-down.

• Match sequences of tokens based on first and follow sets
• Emit syntax correctness validation messages
• Collect structural and literal content into abstract syntax trees (ASTs) based on the language's data contract

Parity Calculations for RAID-5 and -6

Calculate the stripes A, B, P, and Q used in data redundancy applications. Restore missing stripes from surviving data.

• Calculate singly-redundant parity P from stripes A and B
• Restore A or B given P and one of the other two stripes
• Calculate second parity Q
• Restore up to two missing stripes given any combination of two surviving stripes from A, B, P, or Q

Additional Utilities

• Extension functions for inline JSON (de-)serialization
• Extension functions to (de-)serialize FSAs
• Extension functions to create and parse standards-compliant data URIs
• Simple helper to generate random distinct colors