groostav/largetext

Implement Java's CharSequence over very large text files; usable with regexes, or grappa

largetext's Issues

Rewrite work to better reflect performance paradigms

This is a copy of EmpowerOperations/OASIS#1191

The referenced issue is EmpowerOperations/OASIS#1158, and is responsible for this repository existing in the first place.

As a software architect I want to know that the component scanning files for use with the external tool follows best practices, namely:

• including stream files (not loading them in all at once),
• smart use of DirectBuffers (DMA) and operating-assisted file transfers (FileChannel.transferFrom())
  so that I can be more assured about development of new work around those features

So, I started off on #1158 attempting to implement a really robust read-write model for external tool files. I fell short of this goal because I was ultimately defeated by the more pathological issues of that goal. Namely, if random index-based modifications are supported (such as model.appendAt(123, 25, "hello") --a change which replaces 25 characters in the source with 5 characters "hello"), then your data model is no longer index-accurate, and each future addition or mutation to that model must be updated to reflect the new contents length as well as the old contents length; we dont have a single contiguous data model, and that would (in a naiive approach) cause us to do a great deal of excessive math.

I attempted to implement this on master at Groostav/largetext

To properly support this notion, some kind of tree data structure akin to google's RangeMap is required, but using offsets rather than ranges. The exact specifications of such a data structure elude me, but coming up with such a specification would be part of this issue. Implementing it is not.

Thus, this issue calls for:

• a complete implementation of a lazy-string-buffer-like data structure outlined in the above repo
• a complete set of tests against such a data structure
• slow (linear) time performance on as many operations as is necessary; without the RangeTree-like structure, many operations, such as length() and subString() will likely require linear-time traversal of things. this is fine for this issue.
• an issue to be written up to replace the linear time calls with a tree-based (and thus logarithmic-time) data structure.