title: Java: versioned data structures?
body: <p>I have a data structure that is pretty simple (basically a structure containing some arrays and single values), but I need to record the history of the data structure so that I can efficiently get the contents of the data structure at any point in time.</p>
  
  <p>Is there a relatively straightforward way to do this?</p>
  
  <p>The best way I can think of would be to encapsulate the whole data structure with something that handles all the mutating operations by storing data in <a href="https://stackoverflow.com/questions/1683430/functional-data-structures-in-java">functional data structures</a>, and then for each mutation operation caching a copy of the data structure in a Map indexed by time-ordering (e.g. a TreeMap with real time as keys, or a HashMap with a counter of mutation operations combined with one or more indexes stored in TreeMaps mapping real time / tick count / etc. to mutation operations)</p>
  
  <p>any suggestions?</p>
  
  <p><strong>edit:</strong> In one case I already have the history as a series of transactions (this is reading items from a data file) so I can replay them, but this takes O(n) steps (n = # of transactions) every time I need to access the data. I'm looking for alternatives.</p>