ini/trakem2/persistence/CacheImageMipMaps.java

   1 /**
   2
   3 TrakEM2 plugin for ImageJ(C).
   4 Copyright (C) 2008 Albert Cardona and Stephan Preibisch.
   5
   6 This program is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU General Public License
   8 as published by the Free Software Foundation (http://www.gnu.org/licenses/gpl.txt )
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18
  19 You may contact Albert Cardona at acardona at ini.phys.ethz.ch
  20 Institute of Neuroinformatics, University of Zurich / ETH, Switzerland.
  21 **/
  22
  23 package ini.trakem2.persistence;
  24
  25
  26 import ini.trakem2.utils.IJError;
  27 import java.util.ArrayList;
  28 import java.util.Hashtable;
  29 import java.util.HashMap;
  30 import java.util.ListIterator;
  31 import java.util.LinkedList;
  32 import java.util.Iterator;
  33 import java.util.Map;
  34 import java.awt.Image;
  35
  36 /** A cache for TrakEM2's rolling memory of java.awt.Image instances.
  37  *  Uses both a list and a map. When the list goes beyond a certain LINEAR_SEARCH_LIMIT, then the map is used.
  38  *  Each image is added as a CacheImageMipMaps.Entry, which stores the image, the corresponding Patch id and the level of the image (0, 1, 2 ... mipmap level of descresing power of 2 sizes).
  39  *  The map contains unique Patch id keys versus Image arrays of values, where the array index is the index.
  40  */
  41 public class CacheImageMipMaps {
  42
  43         private final LinkedList<Entry> cache;
  44         private final HashMap<Long,Image[]> map = new HashMap<Long,Image[]>();
  45         private boolean use_map = false;
  46         public static int LINEAR_SEARCH_LIMIT = 0;
  47
  48         private class Entry {
  49                 final long id;
  50                 final int level;
  51                 Image image;
  52                 Entry (final long id, final int level, final Image image) {
  53                         this.id = id;
  54                         this.level = level;
  55                         this.image = image;
  56                 }
  57                 public final boolean equals(final Object ob) {
  58                         final Entry e = (Entry)ob;
  59                         return e.id == id && e.level == level;
  60                 }
  61                 public final boolean equals(final long id, final int level) {
  62                         return this.id == id && this.level == level;
  63                 }
  64         }
  65
  66         public CacheImageMipMaps(int initial_size) {
  67                 cache = new LinkedList<Entry>();
  68         }
  69
  70         private final Entry rfind(final long id, final int level) {
  71                 final ListIterator<Entry> li = cache.listIterator(cache.size()); // descendingIterator() is from java 1.6 !
  72                 while (li.hasPrevious()) {
  73                         final Entry e = li.previous();
  74                         if (e.equals(id, level)) return e;
  75                 }
  76                 return null;
  77         }
  78
  79         /** Replace or put. */
  80         public void replace(final long id, final Image image, final int level) {
  81                 final Entry e = rfind(id, level);
  82                 if (null == e) put(id, image, level);
  83                 else {
  84                         if (null != e.image) e.image.flush();
  85                         e.image = image;
  86                 }
  87         }
  88
  89         static private final int computeLevel(final int i) {
  90                 return (int)(0.5 + ((Math.log(i) - Math.log(32)) / Math.log(2))) + 1;
  91         }
  92
  93         /** The position in the array is the Math.max(width, height) of an image. */
  94         private final static int[] max_levels = new int[50000]; // don't change to smaller than 33. Here 50000 is the maximum width or height for which precomputed mipmap levels will exist.
  95         static {
  96                 // from 0 to 31 all zeros
  97                 for (int i=32; i<max_levels.length; i++) {
  98                         max_levels[i] = computeLevel(i);
  99                 }
 100         }
 101
 102         private final int maxLevel(final Image image, final int starting_level) {
 103                 final int w = image.getWidth(null);
 104                 final int h = image.getHeight(null);
 105                 /*
 106                 int max_level = starting_level;
 107
 108                 while (w > 32 || h > 32) {
 109                         w /= 2;
 110                         h /= 2;
 111                         max_level++;
 112                 }
 113                 return max_level;
 114                 */
 115
 116                 final int max = Math.max(w, h);
 117                 if (max >= max_levels.length) {
 118                         //if (max <= 32) return starting_level;
 119                         return starting_level + computeLevel(max);
 120                 } else {
 121                         return starting_level + max_levels[max];
 122                 }
 123         }
 124
 125         /** No duplicates allowed: if the id exists it's sended to the end and the image is first flushed (if different), then updated with the new one provided. */
 126         public final void put(final long id, final Image image, final int level) {
 127                 final ListIterator<Entry> li = cache.listIterator(cache.size());
 128                 while (li.hasPrevious()) { // images are more likely to be close to the end
 129                         final Entry e = li.previous();
 130                         if (id == e.id && level == e.level) {
 131                                 li.remove();
 132                                 cache.addLast(e);
 133                                 if (image != e.image) {
 134                                         // replace
 135                                         e.image.flush();
 136                                         e.image = image;
 137                                         // replace in map
 138                                         if (use_map) {
 139                                                 Image[] images = map.get(id);
 140                                                 if (null == images) images = new Image[maxLevel(image, level)];
 141                                                 images[level] = image;
 142                                         }
 143                                 }
 144                                 return;
 145                         }
 146                 }
 147                 // else, new
 148                 cache.addLast(new Entry(id, level, image));
 149
 150                 if (use_map) {
 151                         // add new to the map
 152                         Image[] images = map.get(id);
 153                         try {
 154                                 if (null == images) {
 155                                         //System.out.println("CREATION maxLevel, level, image.width: " + maxLevel(image, level) + ", " + level + ", " + image.getWidth(null));
 156                                         images = new Image[maxLevel(image, level)];
 157                                         images[level] = image;
 158                                         map.put(id, images);
 159                                 } else {
 160                                         images[level] = image;
 161                                 }
 162                         } catch (Exception e) {
 163                                 System.out.println("length of images[]: " + images.length);
 164                                 System.out.println("level to add: " + level);
 165                                 System.out.println("size of the image: " + image.getWidth(null));
 166                                 System.out.println("maxlevel is: " + maxLevel(image, level));
 167                         }
 168                 } else if (cache.size() >= LINEAR_SEARCH_LIMIT) { // create the map one step before it's used, hence the >= not > alone.
 169                         // initialize map
 170                         final ListIterator<Entry> lim = cache.listIterator(0);
 171                         while (lim.hasNext()) {
 172                                 final Entry e = lim.next();
 173                                 if (!map.containsKey(e.id)) {
 174                                         final Image[] images = new Image[maxLevel(image, level)];
 175                                         images[e.level] = e.image;
 176                                         map.put(e.id, images);
 177                                 } else {
 178                                         final Image[] images = map.get(e.id);
 179                                         images[e.level] = e.image;
 180                                 }
 181                         }
 182                         use_map = true;
 183                         //System.out.println("CREATED map");
 184                 }
 185         }
 186
 187         /** A call to this method puts the element at the end of the list, and returns it. Returns null if not found. */
 188         public final Image get(final long id, final int level) {
 189                 if (0 == LINEAR_SEARCH_LIMIT) return getFromMap(id, level);
 190                 final ListIterator<Entry> li = cache.listIterator(cache.size());
 191                 int i = 0;
 192                 while (li.hasPrevious()) { // images are more likely to be close to the end
 193                         if (i > LINEAR_SEARCH_LIMIT) {
 194                                 return getFromMap(id, level);
 195                         }
 196                         i++;
 197                         ///
 198                         final Entry e = li.previous();
 199                         if (id == e.id && level == e.level) {
 200                                 li.remove();
 201                                 cache.addLast(e);
 202                                 return e.image;
 203                         }
 204                 }
 205                 return null;
 206         }
 207
 208         private final Image getFromMap(final long id, final int level) {
 209                 final Image[] images = map.get(id);
 210                 if (null == images) return null;
 211                 return level < images.length ? images[level] : null;
 212         }
 213
 214         private final Image getAboveFromMap(final long id, final int level) {
 215                 final Image[] images = map.get(id);
 216                 if (null == images) return null;
 217
 218                 for (int i=Math.min(level, images.length-1); i>-1; i--) {
 219                         if (null != images[i]) return images[i];
 220                 }
 221                 return null;
 222         }
 223
 224         private final Image getBelowFromMap(final long id, final int level) {
 225                 final Image[] images = map.get(id);
 226                 if (null == images) return null;
 227
 228                 for (int i=level; i<images.length; i++) {
 229                         if (null != images[i]) return images[i];
 230                 }
 231                 return null;
 232         }
 233
 234         /** Find the cached image of the given level or its closest but smaller image (larger level), or null if none found. */
 235         public final Image getClosestBelow(final long id, final int level) {
 236                 if (0 == LINEAR_SEARCH_LIMIT) return getBelowFromMap(id, level);
 237                 Entry ee = null;
 238                 int lev = Integer.MAX_VALUE;
 239                 final ListIterator<Entry> li = cache.listIterator(cache.size());
 240                 int i = 0;
 241                 while (li.hasPrevious()) { // images are more likely to be close to the end
 242                         if (i > LINEAR_SEARCH_LIMIT) {
 243                                 return getBelowFromMap(id, level);
 244                         }
 245                         i++;
 246                         ///
 247                         final Entry e = li.previous();
 248                         if (e.id != id) continue;
 249                         if (e.level == level) return e.image;
 250                         if (e.level > level) {
 251                                 // if smaller image (larger level) than asked, choose the less smaller
 252                                 if (e.level < lev) {
 253                                         lev = e.level;
 254                                         ee = e;
 255                                 }
 256                         }
 257                 }
 258                 if (null != ee) {
 259                         cache.remove(ee); // unfortunaelly, removeLastOcurrence is java 1.6 only
 260                         cache.addLast(ee);
 261                         return ee.image;
 262                 }
 263                 return null;
 264         }
 265
 266         /** Find the cached image of the given level or its closest but larger image (smaller level), or null if none found. */
 267         public final Image getClosestAbove(final long id, final int level) {
 268                 if (0 == LINEAR_SEARCH_LIMIT) return getAboveFromMap(id, level);
 269                 int lev = -1;
 270                 Entry ee = null;
 271                 final ListIterator<Entry> li = cache.listIterator(cache.size());
 272                 int i = 0;
 273                 while (li.hasPrevious()) { // images are more likely to be close to the end
 274                         if (i > LINEAR_SEARCH_LIMIT) {
 275                                 return getAboveFromMap(id, level);
 276                         }
 277                         i++;
 278                         final Entry e = li.previous();
 279                         if (e.id != id) continue;
 280                         // if equal level as asked, just return it
 281                         if (e.level == level) return e.image;
 282                         // if exactly one above, just return it // may hinder finding an exact one, but potentially cuts down search time a lot
 283                         // if (e.level == level + 1) return e.image; // WOULD NOT BE THE PERFECT IMAGE if the actual asked level is cached at a previous entry.
 284                         if (e.level < level) {
 285                                 if (e.level > lev) {
 286                                         lev = e.level;
 287                                         ee = e;
 288                                 }
 289                         }
 290                 }
 291                 if (null != ee) {
 292                         cache.remove(ee);
 293                         cache.addLast(ee);
 294                         return ee.image;
 295                 }
 296                 return null;
 297         }
 298
 299         /** Remove the Image if found and returns it, without flushing it. Returns null if not found. */
 300         public final Image remove(final long id, final int level) {
 301                 final ListIterator<Entry> li = cache.listIterator(cache.size());
 302                 while (li.hasPrevious()) {
 303                         final Entry e = li.previous();
 304                         if (id == e.id && level == e.level) {
 305                                 li.remove();
 306                                 return e.image;
 307                         }
 308                 }
 309                 if (use_map) {
 310                         final Image[] images = map.get(id);
 311                         if (images == null) return null;
 312                         images[level] = null;
 313                 }
 314                 return null;
 315         }
 316
 317         /** Removes and flushes all images, and shrinks arrays. */
 318         public final void removeAndFlushAll() {
 319                 final ListIterator<Entry> li = cache.listIterator(cache.size());
 320                 while (li.hasPrevious()) {
 321                         final Entry e = li.previous();
 322                         e.image.flush();
 323                 }
 324                 cache.clear();
 325                 if (use_map) map.clear();
 326         }
 327
 328         /** Remove all awts associated with a level different than 0 (that means all scaled down versions) for any id. */
 329         public void removeAllPyramids() {
 330                 final ListIterator<Entry> li = cache.listIterator(cache.size());
 331                 while (li.hasPrevious()) {
 332                         final Entry e = li.previous();
 333                         if (e.level > 0) {
 334                                 e.image.flush();
 335                                 li.remove();
 336                         }
 337                 }
 338                 if (use_map) {
 339                         final Iterator<Map.Entry<Long,Image[]>> it = map.entrySet().iterator();
 340                         while (it.hasNext()) {
 341                                 Map.Entry<Long,Image[]> entry = it.next();
 342                                 final Image[] images = entry.getValue();
 343                                 if (null == images[0]) it.remove();
 344                                 for (int i=1; i<images.length; i++) {
 345                                         images[i] = null;
 346                                 }
 347                         }
 348                 }
 349         }
 350
 351         /** Remove all awts associated with a level different than 0 (that means all scaled down versions) for the given id. */
 352         public void removePyramid(final long id) {
 353                 final ListIterator<Entry> li = cache.listIterator(cache.size());
 354                 while (li.hasPrevious()) {
 355                         final Entry e = li.previous();
 356                         if (id == e.id && e.level > 0) {
 357                                 e.image.flush();
 358                                 li.remove();
 359                         }
 360                 }
 361                 if (use_map) {
 362                         final Image[] images = map.get(id);
 363                         if (null != images) {
 364                                 for (int i=1; i<images.length; i++) {
 365                                         images[i] = null;
 366                                 }
 367                                 if (null == images[0]) map.remove(id);
 368                         }
 369                 }
 370         }
 371
 372         /** Remove all images that share the same id (but have different levels). */
 373         public final ArrayList<Image> remove(final long id) {
 374                 final ArrayList<Image> al = new ArrayList<Image>();
 375                 final ListIterator<Entry> li = cache.listIterator(cache.size());
 376                 while (li.hasPrevious()) {
 377                         final Entry e = li.previous();
 378                         if (id == e.id) {
 379                                 al.add(e.image);
 380                                 li.remove();
 381                         }
 382                 }
 383                 if (use_map) {
 384                         map.remove(id);
 385                 }
 386                 return al;
 387         }
 388
 389         /** Returns a table of level keys and image values that share the same id (that is, belong to the same Patch). */
 390         public final Hashtable<Integer,Image> getAll(final long id) {
 391                 final Hashtable<Integer,Image> ht = new Hashtable<Integer,Image>();
 392                 if (use_map) {
 393                         final Image[] images = map.get(id);
 394                         if (null != images) {
 395                                 for (int i=0; i<images.length; i++) {
 396                                         if (null != images[i]) {
 397                                                 ht.put(i, images[i]);
 398                                         }
 399                                 }
 400                         }
 401                 } else {
 402                         final ListIterator<Entry> li = cache.listIterator(cache.size());
 403                         while (li.hasPrevious()) {
 404                                 final Entry e = li.previous();
 405                                 if (id == e.id) ht.put(e.level, e.image);
 406                         }
 407                 }
 408                 return ht;
 409         }
 410
 411         /** Remove and flush away all images that share the same id. */
 412         public final void removeAndFlush(final long id) {
 413                 final ListIterator<Entry> li = cache.listIterator(cache.size());
 414                 while (li.hasPrevious()) {
 415                         final Entry e = li.previous();
 416                         if (id == e.id) {
 417                                 e.image.flush();
 418                                 li.remove();
 419                         }
 420                 }
 421                 if (use_map) map.remove(id);
 422         }
 423
 424         /** Remove the given index and return it, returns null if outside range. */
 425         public final Image remove(int i) {
 426                 if (i < 0 || i >= cache.size()) return null;
 427                 final Entry e = cache.remove(i);
 428                 if (use_map) {
 429                         nullifyMap(e.id, e.level);
 430                 }
 431                 return e.image;
 432         }
 433
 434         private final void nullifyMap(final long id, final int level) {
 435                 final Image[] images = map.get(id);
 436                 if (null != images) {
 437                         images[level] = null;
 438                         for (Image im : images) {
 439                                 if (null != im) return;
 440                         }
 441                         // all null, remove
 442                         map.remove(id);
 443                 }
 444         }
 445
 446         /** Remove the first element and return it. Returns null if none. The underlaying arrays are untouched besides nullifying the proper pointer. */
 447         public final Image removeFirst() {
 448                 final Entry e = cache.removeFirst();
 449                 if (use_map) {
 450                         nullifyMap(e.id, e.level);
 451                 }
 452                 return e.image;
 453         }
 454
 455         /** Checks if there's any image at all for the given id. */
 456         public final boolean contains(final long id) {
 457                 if (use_map) {
 458                         return map.containsKey(id);
 459                 } else {
 460                         final ListIterator<Entry> li = cache.listIterator(cache.size());
 461                         while (li.hasPrevious()) {
 462                                 final Entry e = li.previous();
 463                                 if (id == e.id) return true;
 464                         }
 465                 }
 466                 return false;
 467         }
 468
 469         /** Checks if there's any image for the given id and level. */
 470         public final boolean contains(final long id, final int level) {
 471                 if (use_map) {
 472                         final Image[] images = map.get(id);
 473                         if (null == images) return false;
 474                         return level < images.length ? null != images[level] : false;
 475                 }
 476                 return -1 != cache.lastIndexOf(new Entry(id, level, null));
 477         }
 478
 479         public int size() { return cache.size(); }
 480
 481         public void debug() {
 482                 System.out.println("cache size: " + cache.size() + ", " + map.size());
 483         }
 484
 485         /** Does nothing. */
 486         public void gc() {}
 487 }
 488