1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 package de.fu_berlin.ties.util;
23
24 import java.util.Iterator;
25 import java.util.Map;
26
27 import org.apache.commons.collections.map.AbstractLinkedMap;
28 import org.apache.commons.collections.map.LRUMap;
29
30 /***
31 * A fixed-size map that uses an flexible adaptable strategy for pruning
32 * entries based on LRU (pruning one the least recently used entries).
33 * Instances of this class are not thread-safe and must be synchronized
34 * externally, if required.
35 *
36 * @author Christian Siefkes
37 * @version $Revision: 1.7 $, $Date: 2004/06/04 17:13:22 $, $Author: siefkes $
38 */
39 public class AdaptableLRUMap extends LRUMap {
40
41 /***
42 * Used to decide which entries to prune.
43 */
44 private final Pruner pruner;
45
46 /***
47 * The number of candidates to consider for each pruning operation.
48 */
49 private final int candidateNumber;
50
51 /***
52 * The number of elements to remove by each pruning operation.
53 */
54 private final int pruneNumber;
55
56 /***
57 * Constructs a new, empty map with the specified initial capacity and
58 * the default load factor. If the number of candidates is one, this
59 * class behaves like a normal {@link LRUMap}; otherwise the
60 * {@link Pruner} is consulted to decide which entry to prune.
61 *
62 * @param maxSize the maximum size of the map
63 * @param prun Used to decide which entries to prune
64 * @param candidates The number of candidates to consider for each pruning
65 * operation
66 * @param pruneNum The number of elements to remove by each pruning
67 * operation, must not be larger than <code>candidates</code>
68 * @throws IllegalArgumentException if one of the input parameters is
69 * invalid
70 */
71 public AdaptableLRUMap(final int maxSize, final Pruner prun,
72 final int candidates, final int pruneNum)
73 throws IllegalArgumentException {
74 super(maxSize);
75 checkArguments(maxSize, candidates, pruneNum);
76
77 pruner = prun;
78 candidateNumber = candidates;
79 pruneNumber = pruneNum;
80 }
81
82 /***
83 * Constructs a new, empty map with the specified initial capacity and
84 * load factor. If the number of candidates is one, this
85 * class behaves like a normal {@link LRUMap}; otherwise the
86 * {@link Pruner} is consulted to decide which entry to prune.
87 *
88 * @param maxSize the maximum size of the map
89 * @param loadFactor the load factor
90 * @param prun Used to decide which entries to prune
91 * @param candidates The number of candidates to consider for each pruning
92 * operation
93 * @param pruneNum The number of elements to remove by each pruning
94 * operation, must not be larger than <code>candidates</code>
95 * @throws IllegalArgumentException if one of the input parameters is
96 * invalid
97 */
98 public AdaptableLRUMap(final int maxSize, final float loadFactor,
99 final Pruner prun, final int candidates,
100 final int pruneNum)
101 throws IllegalArgumentException {
102 super(maxSize, loadFactor);
103 checkArguments(maxSize, candidates, pruneNum);
104
105 pruner = prun;
106 candidateNumber = candidates;
107 pruneNumber = pruneNum;
108 }
109
110 /***
111 * Helper method that checks whether constructor arguments are valid and
112 * throws an exception if this is not the case.
113 *
114 * @param maxSize the maximum size of the map
115 * @param candidates The number of candidates to consider for each pruning
116 * operation
117 * @param pruneNum The number of elements to remove by each pruning
118 * operation, must not be larger than <code>candidates</code>
119 * @throws IllegalArgumentException if one of the input parameters is
120 * invalid
121 */
122 private void checkArguments(final int maxSize, final int candidates,
123 final int pruneNum) throws IllegalArgumentException {
124 if ((candidates < 1) || (candidates > maxSize)) {
125 throw new IllegalArgumentException("Number of pruning candidates "
126 + "must be in range from 1 to maxSize (" + maxSize + "): "
127 + candidates);
128 }
129
130 if ((pruneNum < 1) || (pruneNum > candidates)) {
131 throw new IllegalArgumentException("Number of elements to prun "
132 + "must be in range from 1 to number of candidates ("
133 + candidates + "): " + pruneNum);
134 }
135 }
136
137 /***
138 * Returns the number of candidates considered for each pruning operation.
139 * @return the value of the attribute
140 */
141 public int getCandidateNumber() {
142 return candidateNumber;
143 }
144
145 /***
146 * Returns the number of elements removed by each pruning operation.
147 * @return the value of the attribute
148 */
149 public int getPruneNumber() {
150 return pruneNumber;
151 }
152
153 /***
154 * Controls removal of one of the least recently used entries from the map.
155 * Lets the pruner decide if there are multiple candidates to consider.
156 *
157 * @param entry the least recently used entry
158 * @return <code>true</code> if the superclass should delete the
159 * specified entry; <code>false</code> if this class took the necessary
160 * action by deleting the first {@link #getPruneNumber()} entries selected
161 * by the pruner
162 */
163 protected boolean removeLRU(final AbstractLinkedMap.LinkEntry entry) {
164 if (candidateNumber > 1) {
165
166 final int consideredCandidates = Math.min(candidateNumber, size());
167 final Map.Entry[] candidates = new Map.Entry[consideredCandidates];
168 final Iterator entryIter = entrySet().iterator();
169
170 for (int i = 0; i < candidates.length; i++) {
171
172 candidates[i] = (Map.Entry) entryIter.next();
173
174 }
175
176
177 final Map.Entry[] resortedEntries =
178 pruner.sortForPruning(candidates);
179
180
181 final int entriesToPrune =
182 Math.min(pruneNumber, resortedEntries.length);
183 for (int i = 0; i < entriesToPrune; i++) {
184 remove(resortedEntries[i].getKey());
185 }
186
187
188 return false;
189 } else {
190
191 return true;
192 }
193 }
194
195 }