View Javadoc

1   /*
2    * Copyright (C) 2004 Christian Siefkes <christian@siefkes.net>.
3    * Development of this software is supported by the German Research Society,
4    * Berlin-Brandenburg Graduate School in Distributed Information Systems
5    * (DFG grant no. GRK 316).
6    *
7    * This library is free software; you can redistribute it and/or
8    * modify it under the terms of the GNU Lesser General Public
9    * License as published by the Free Software Foundation; either
10   * version 2.1 of the License, or (at your option) any later version.
11   *
12   * This library is distributed in the hope that it will be useful,
13   * but WITHOUT ANY WARRANTY; without even the implied warranty of
14   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15   * Lesser General Public License for more details.
16   *
17   * You should have received a copy of the GNU Lesser General Public
18   * License along with this library; if not, visit
19   * http://www.gnu.org/licenses/lgpl.html or write to the Free Software
20   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
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             // collect candidates for the pruner
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                 //Util.LOG.debug("Calling entryIter.next");
172                 candidates[i] = (Map.Entry) entryIter.next();
173                 //Util.LOG.debug("Called entryIter.next");
174             }
175 
176             // let the pruner decide + delete the chosen entry
177             final Map.Entry[] resortedEntries =
178                 pruner.sortForPruning(candidates);
179 
180             // remove specified number of entries
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             // deleted chosen entries, no need for further action
188             return false;
189         } else {
190             // standard LRU behavior: let superclass delete entry
191             return true;
192         }
193     }
194 
195 }