I am currently building an LRU cache where I need to store the last N inserted items. Items will be inserted frequently (i.e. many write operations) and read operations will typically return a large number of events always strictly in sequence albeit starting at an arbitrary point in the cache. For example, suppose the cache contains events:
[1, 2, 3, 4, 5, 6]
A legal read operation would be to return an iterator over events [2, 3, 4].
Due to read operations potentially being long-lived I'd like to use a data structure where I can safely iterate over a logical copy of the sequence for each read attempt, thus preventing a cache read from holding up any subsequent writes. However, using a vanilla Java ArrayList or LinkedList implies a large overhead in making a full copy.
My question: Are there any 3rd party Java libraries that provide immutable data structures similar to Scala, whereby attempts to modify the data structure return a new immutable copy (which is in fact based on the original data structure and hence the copy operation is very fast)? Obviously the data structure could not conform to the Java Collections API as operations like add(T) would need to return the new collection (rather than void).
(Please no comments / answers citing this as a case of premature optimisation.)
Thanks in advance.
Note
Guava's ImmutableList nearly achieves what I need: It allows to you call copyOf where the copy typically references the original (avoiding performing an actual copy). Unfortunately you can't go the other way and add an item to the list and get back a copy that includes the new element.
Functional Java comes in the form of a library (not a different language) and provides immutable collections. Not sure if it'll fit your needs but worth a try. The List Sort example of Functional Java is also available here.