public class FavoriteList { protected List fList; // List of entries /** Constructor; O(1) time */ public FavoriteList() { fList = new NodeList(); } /** Return the number of elements in the list; O(1) time */ public int size() { return fList.size(); } /** Return true iff the list is empty; O(1) time */ public boolean isEmpty() { return fList.isEmpty(); } /** Find the position of an element; O(n) time */ protected Position find(Object obj) { if (fList.isEmpty()) return null; Position p; for (p = fList.first(); p != fList.last(); p = fList.next(p)) if (value(p).equals(obj)) return p; // found it if (value(p).equals(obj)) return p; // found it at end return null; // we have not found it } /** Find and remove a given object if it's in the list; O(n) time */ public Object remove(Object obj) { Position pos = find(obj); // Search for obj in the favorites list if (pos == null) return null; // obj is not in the list in this case Entry ent = entry(pos); fList.remove(pos); // remove this entry from the favorites list return ent.value(); // return the removed object } /** Incr. access count for obj or insert it if it's not present; O(rank(obj)) time */ public void access(Object obj) { Position pos = find(obj); // search for obj in the favorites list if (pos != null) // obj is in the favorites list entry(pos).incrementCount(); // increment obj's access count else // obj is not in list, so add it at end pos = fList.insertLast(new Entry(obj)); moveUp(pos); // We may want to move obj up in fList } /** Move up an entry in the favorites list if needed; O(n) time */ protected void moveUp(Position pos) { Entry ent = entry(pos); // the entry for obj for (Position prev=null; pos != fList.first();) { // Move ent to correct position prev = fList.prev(pos); // the position before obj's if (ent.count() <= entry(prev).count()) break; // obj now at correct position Object temp = prev.element(); // move obj up in the favorites list fList.replace(prev,pos.element()); fList.replace(pos,temp); pos = fList.prev(pos); // go to prev position (new pos. for ent) } }