public class FavoriteListMTF extends FavoriteList { /** Default constructor */ public FavoriteListMTF() { } /** Helper method */ protected int count(Position p) { return ((Entry) p.element()).count(); } /** Move up an entry to the first position; O(1) time */ protected void moveUp(Position pos) { fList.insertFirst(fList.remove(pos)); } /** Return the k most accessed elements, for a given k; O(kn) time */ public List top(int k) { if (k < 0 || k > size()) throw new IllegalArgumentException("Invalid argument"); List T = new NodeList(); // top-k list if (!isEmpty()) { int n = fList.size(); // copy entries into a temporary list List C = new NodeList(); // copy of the list of entries Position p = fList.first(); for (int i = 1; i < n; i++) { C.insertLast(p.element()); p = fList.next(p); } C.insertLast(p.element()); // find the top k elements, one at a time for (int j = 1; j <= k; j++) { Position maxPos = null; int maxCount = 0; Position q = C.first(); while (true) { if (count(q) > maxCount) { maxCount = count(q); maxPos = q; } if (q == C.last()) break; q = C.next(q); } T.insertLast(value(maxPos)); C.remove(maxPos); } } return T; } }