[UIMA-5496] uv3 replace FsIndex_set_sorted, apply many fixes to replaced one

• Type: Improvement
• Status: Resolved
• Priority: Minor
• Resolution: Fixed
• Fix Version/s: 3.0.0SDK-beta
• Assignee: Marshall Schor
• Reporter: Marshall Schor
• Created: 18/Jul/17 16:00
• Updated: 01/Sep/17 18:40
• Resolved: 01/Sep/17 18:40

Description

The first implementation of FsIndex_set_sorted assumed the underlying index was implemented by OrderedFsSet_array2. This did a complex set of tradeoffs that improved insert/remove performance at the expense of more complex iteration. The OrderedFsSet_array2 impl was complex and was buggy (many bugs were removed, though, in this most recent commit).

This implementation was based on "NavigableSet" apis, which required creation of multiple iterators as direction of iteration was reversed, and was quite complex.

This change reverts both of these to a simpler more straight forward implementation, closer to how UIMA v2 did this, but with significant improvements in both iteration and insert/remove. The underlying OrderedFsSet_array keeps the indexed items for one type in a compacted array, with free space possible at the begin and/or end, and rebalancing done as needed. The iterator implementation removed several layers of indirection and is now implemented directly on top of the OrderedFsSet_array itself.