title: Is there a Java data structure that is effectively an ArrayList with double indicies and built-in interpolation?
body: <p>I am looking for a pre-built Java data structure with the following characteristics:</p>
  
  <ol>
  <li><p>It should look something like an ArrayList but should allow indexing via double-precision rather than integers.  Note that this means that it's likely that you'll see indicies that don't line up with the original data points (i.e., asking for the value that corresponds to key "1.5").  <strong>EDIT</strong>: For clarity, based on the comments, I'm not looking to <em>change</em> the ArrayList implementation.  I'm looking for a similar interface and developer experience.</p></li>
  <li><p>As a consequence, the value returned will likely be interpolated.  For example, if the key is 1.5, the value returned could be the average of the value at key 1.0 and the value at key 2.0.</p></li>
  <li><p>The keys will be sorted but the values are not ensured to be monotonically increasing.  In fact, there's no assurance that the first derivative of the values will be continuous (making it a poor fit for certain types of splines).</p></li>
  <li><p>Freely available code only, please.</p></li>
  </ol>
  
  <p>For clarity, I know how to write such a thing.  In fact, we already have an implementation of this and some related data structures in legacy code that I want to replace due to some performance and coding issues.  </p>
  
  <p>What I'm trying to avoid is spending a lot of time rolling my own solution when there might already be such a thing in the <a href="http://java.sun.com/javase/6/docs/api/index.html?overview-summary.html" rel="noreferrer">JDK</a>, <a href="http://commons.apache.org/" rel="noreferrer">Apache Commons</a> or another standard library.  Frankly, that's exactly the approach that got this legacy code into the situation that it's in right now....</p>
  
  <p>Is there such a thing out there in a freely available library?</p>