219Recent File List

Author: Dr. Heinz M. KabutzDate: 2014-04-30Java Version: 7Category: Tips and Tricks

Abstract: The LinkedHashMap has a little known feature that can return elements in least recently accessed order, rather than insertion order. In this newsletter we use this to construct a "Recently Used File" list.

Welcome to the 219th issue of The Java(tm) Specialists' Newsletter. On Crete we have three seasons: spring, summer and autumn. In summer we have hardly a drop of rain. But in the other seasons, it can make up for it in a big way. The storms in the movie Zorba the Greek, filmed in the area we live, are certainly not unusual around these parts. On Sunday a friend of mine filmed a hurricane in the south of the island.

But on Saturday we managed to enjoy the beach with building sand mountains, splashing one another in the sea, etc. It is still a tad chilly, but getting warmer every time we dare to go swimming. Soon summer will be here.

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

Recent File List

Last week, I was helping some friends with a Java application that required a list of recently opened files. This should be stored in normal preferences. Initially, I constructed a simple list of limited size that would drop off the old elements as I was adding new ones. This list was then persisted using a property list. However, it became a bit complicated when I wanted to open a file that had already been in the list before. I wanted the file to be removed from the middle of the list and then placed at the front.

Every piece of tricky code should start with a unit test. This is no different. For example, if I wanted to have a maximum of 10 files, I could write a test such as this one:

RecentCollection<String> recent = new RecentCollection<>();
// test overflow
for (int i = 0; i < 20; i++) {
  recent.add("" + i);
}
Iterator<String> files = recent.iterator();
for (int i = 19; i >= 10; i--) {
  assertEquals("" + i, files.next());
}
assertFalse(files.hasNext());

To write a collection that passed that test was easy. But this one is just a little bit more tricky:

RecentCollection<String> recent = new RecentCollection<>();
// test file added that is there already
recent.add("hello");
recent.add("hello");
recent.add("hello");
recent.add("goodbye");
recent.add("goodbye");
recent.add("goodbye");
recent.add("hello");
Iterator<String> files = recent.iterator();
assertEquals("hello", files.next());
assertEquals("goodbye", files.next());
assertFalse(files.hasNext());

I started writing a little data structure involving arrays. Not particularly difficult, but whilst driving along in my little Suzuki Jimny, I realized that Java already had a collection that can do this for me: LinkedHashMap.

LinkedHashMap/Set

Java 1.4 introduced the LinkedHashMap and the LinkedHashSet to the collection framework. These classes have been largely ignored by programmers, but are actually quite useful. In addition to being HashMap/Set, they also have an order of the elements. The standard order is by insertion. Thus if you want to read in a file of elements that should maintain their order, but also are quick to find, then these linked collections can be useful. But there is a little known feature of LinkedHashMap, which is unfortunately not exposed in LinkedHashSet. Instead of ordering elements by insertion order, we can also order them by access order. We do this by passing in the parameter "true" to the LinkedHashMap constructor. In addition, we can override the method removeEldestEntry() to return true once we have reached our desired capacity. Since we do not have this functionality in the LinkedHashSet, we need to create a set from the Map using Collections.newSetFromMap():

private static final int MAXIMUM = 10;

private final Collection<E> recent =
    Collections.newSetFromMap(
        new LinkedHashMap<E, Boolean>(32, 0.7f, true) {
          protected boolean removeEldestEntry(
              Map.Entry<E, Boolean> eldest) {
            return size() > MAXIMUM;
          }
        }
    );

As you can see from the code snippet above, I have made my RecentCollection genericized, so we can store Strings, Files, Girlfriends, whatever we like. When I add elements into this collection, the ones least recently used are removed once we exceed the MAXIMUM size. And if we add an element that is there already, then it becomes the most recently used element. It thus almost gives us what we need. The only problem is that when we iterate through the set, we get the elements back in the least recently used order and what we need for our "Recent Files" view is the most recently used order.

To solve that, I wrote the ReverseCollection, which takes as a parameter a Collection of items and allows us to iterate through them in reverse. If the collection passed into the class implements the RandomAccess interface, then we know it is a list which allows us to access elements in constant time, irrespective of where they are located. An example of a RandomAccess list is ArrayList. LinkedList is not RandomAccess. If we do not have a RandomAccess, then we copy the collection into an ArrayList. Our ReverseCollection is also unmodifiable:

import java.util.*;

/**
 * Provides an unmodifiable collection that returns the elements
 * in the reverse order of iteration.  If the original collection
 * implements the RandomAccess interface, we point to that,
 * otherwise we wrap it with an ArrayList.
 */
public class ReverseCollection<E> extends AbstractCollection<E> {
  private final List<E> elements;

  public ReverseCollection(Collection<E> original) {
    if (original instanceof RandomAccess) {
      elements = (List<E>) original;
    } else {
      elements = new ArrayList<E>(original);
    }
  }

  public Iterator<E> iterator() {
    return new Iterator<E>() {
      private int index = elements.size();

      public boolean hasNext() {
        return index > 0;
      }

      public E next() {
        if (!hasNext()) throw new NoSuchElementException();
        return (E) elements.get(--index);
      }

      public void remove() {
        throw new UnsupportedOperationException();
      }
    };
  }

  public int size() {
    return elements.size();
  }
}

The last thing to show is now our "RecentCollection":

import java.util.*;

public class RecentCollection<E> implements Iterable<E> {
  private static final int MAXIMUM = 10;
  private final int maximumElements;

  private final Collection<E> recent =
      Collections.newSetFromMap(
          new LinkedHashMap<E, Boolean>(32, 0.7f, true) {
            protected boolean removeEldestEntry(
                Map.Entry<E, Boolean> eldest) {
              return size() > maximumElements;
            }
          }
      );

  public RecentCollection() {
    this(MAXIMUM);
  }

  public RecentCollection(int maximumElements) {
    this.maximumElements = maximumElements;
  }

  public void add(E element) {
    recent.add(element);
    // and maybe persist this in a property list ... ?
  }

  public void clear() {
    recent.clear();
    // and maybe clear the persisted property list ... ?
  }

  public Iterator<E> iterator() {
    // and maybe read the property list in case it changed ... ?
    return new ReverseCollection<E>(recent).iterator();
  }
}

The integration with Java Preferences is left as an exercise to the reader :-)

As my reader Andreas Junius pointed out, the code using an ArrayList is actually a bit shorter. Here is an example of how we could use ArrayList internally:

import java.util.*;

public class RecentList<E> implements Iterable<E> {
  private final ArrayList<E> recent = new ArrayList<>();
  private final int maxLength;

  public RecentList(int maxLength) {
    this.maxLength = maxLength;
  }

  public void add(E element) {
    recent.remove(element);
    recent.add(0, element);
    reduce();
  }

  private void reduce() {
    while (recent.size() > maxLength) {
      recent.remove(recent.size() - 1);
    }
  }

  public void clear() {
    recent.clear();
  }

  public Iterator<E> iterator() {
    return Collections.unmodifiableCollection(recent).iterator();
  }
}    

I'm not a great fan using the ArrayList as a set and thought that having the LinkedHashMap do the work for us would be more natural. I'm not sure which performs better, but logically it would seem that LinkedHashMap could do the add() in O(1) and ArrayList in O(n). However, with such small lists the difference in performance will be negligible.

Kind regards from Crete

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive