Memoizing positions

[i30817]

I've got this... iterator class. It's type doesn't really matter (it's a document find iterator)

Anyway, it's logic is implemented using hasNext() as the code that actually calculates the new index... and it's hasPrevious() is:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28

public boolean hasPrevious() {         [...already done at least once logic...]                 //lame O(n) backward search        //TODO please memoize this        int localIndex = searchIndex;         searchIndex = 0;         int tmp, tmp2 = -1;         while (hasNext()) {             tmp = next();             if ((tmp + 1) < localIndex) {                 tmp2 = tmp;             } else {                 break;             }         }         if (tmp2 == -1) {             //revert the index if found nothing.            searchIndex = localIndex;             return false;         } else {             //prepare for previous (next() clobbered lastFoundLocation)            lastFound = tmp2;             return true;         }     }

  (so embarrassed)

Anyway since the underlying search algorithms don't support backwards searching, memoization is the obvious answer to this problem, although it would introduce stale cache issues.
I don't have much experience with memoization - what do you think it's the best policy: to expand the table (much harder it looks like) or just null it and let it be reconstructed from scratch?

[jonjava]

What do you mean by "memorizing this"? Saving it to file?

[i30817]

Memory. Save the preprocessed hits to memory

it's a waste of processing cycles - each 'has previous' is actually recalculating the hits of the search phrase in the whole text prior to the current index (and having a cache may actually help in hasnext too).

What is making me hesitate is that i hate and fear caches because of the complexity introduced in maintaining them:
The document may change, the search index may change, the search phrase may change, actually finding the cache index. Of these, only the first two look amenable to retaining part of the cached search, haven't really thought about it more than this, it makes me so mad about this inelegance, oh why didn't you make a backwards search variant mr moore, oh why do i have to deal with caching behaviour anyway for better performance ffgfgdgufgfgdgfdgdfjdkgdjfjgdjk.