| # Here's a probably-not-new data structure I discovered after implementing weight-balanced trees with | |
| # amortized subtree rebuilds (e.g. http://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-scapegoat-splay.pdf) | |
| # and realizing it was silly to turn a subtree into a sorted array with an in-order traversal only as an | |
| # aid in constructing a balanced subtree in linear time. Why not replace the subtree by the sorted array and | |
| # use binary search when hitting that leaf array? Then you'd defer any splitting of the array until inserts and | |
| # deletes hit that leaf array. Only in hindsight did I realize this is similar to the rope data structure for strings. | |
| # Unlike ropes, it's a key-value search tree for arbitrary ordered keys. | |
| # | |
| # The main attraction of this data structure is its simplicity (on par with a standard weight-balanced tree) and that it | |
| # coalesces subtrees into contiguous arrays, which reduces memory overhead and boosts the performance of in-order traversals |
A traditional table-based DFA implementation looks like this:
uint8_t table[NUM_STATES][256]
uint8_t run(const uint8_t *start, const uint8_t *end, uint8_t state) {
for (const uint8_t *s = start; s != end; s++)
state = table[state][*s];
return state;
}
| /*** MIT LICENSE | |
| Copyright (c) 2022 torcado | |
| Permission is hereby granted, free of charge, to any person | |
| obtaining a copy of this software and associated documentation | |
| files (the "Software"), to deal in the Software without | |
| restriction, including without limitation the rights to use, | |
| copy, modify, merge, publish, distribute, sublicense, and/or sell | |
| copies of the Software, and to permit persons to whom the | |
| Software is furnished to do so, subject to the following |