001: /*
002: * Copyright 2001-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.map;
017:
018: import java.util.ArrayList;
019: import java.util.Iterator;
020: import java.util.List;
021: import java.util.Map;
022:
023: import junit.framework.Test;
024: import junit.textui.TestRunner;
025:
026: import org.apache.commons.collections.BulkTest;
027: import org.apache.commons.collections.OrderedMap;
028: import org.apache.commons.collections.ResettableIterator;
029:
030: /**
031: * JUnit tests.
032: *
033: * @version $Revision: 333020 $ $Date: 2005-11-13 15:16:47 +0000 (Sun, 13 Nov 2005) $
034: *
035: * @author Stephen Colebourne
036: */
037: public class TestLRUMap extends AbstractTestOrderedMap {
038:
039: public TestLRUMap(String testName) {
040: super (testName);
041: }
042:
043: public static void main(String[] args) {
044: TestRunner.run(suite());
045: }
046:
047: public static Test suite() {
048: return BulkTest.makeSuite(TestLRUMap.class);
049: }
050:
051: public Map makeEmptyMap() {
052: return new LRUMap();
053: }
054:
055: public boolean isGetStructuralModify() {
056: return true;
057: }
058:
059: public String getCompatibilityVersion() {
060: return "3";
061: }
062:
063: //-----------------------------------------------------------------------
064: public void testLRU() {
065: if (isPutAddSupported() == false
066: || isPutChangeSupported() == false)
067: return;
068: Object[] keys = getSampleKeys();
069: Object[] values = getSampleValues();
070: Iterator it = null;
071:
072: LRUMap map = new LRUMap(2);
073: assertEquals(0, map.size());
074: assertEquals(false, map.isFull());
075: assertEquals(2, map.maxSize());
076:
077: map.put(keys[0], values[0]);
078: assertEquals(1, map.size());
079: assertEquals(false, map.isFull());
080: assertEquals(2, map.maxSize());
081:
082: map.put(keys[1], values[1]);
083: assertEquals(2, map.size());
084: assertEquals(true, map.isFull());
085: assertEquals(2, map.maxSize());
086: it = map.keySet().iterator();
087: assertSame(keys[0], it.next());
088: assertSame(keys[1], it.next());
089: it = map.values().iterator();
090: assertSame(values[0], it.next());
091: assertSame(values[1], it.next());
092:
093: map.put(keys[2], values[2]);
094: assertEquals(2, map.size());
095: assertEquals(true, map.isFull());
096: assertEquals(2, map.maxSize());
097: it = map.keySet().iterator();
098: assertSame(keys[1], it.next());
099: assertSame(keys[2], it.next());
100: it = map.values().iterator();
101: assertSame(values[1], it.next());
102: assertSame(values[2], it.next());
103:
104: map.put(keys[2], values[0]);
105: assertEquals(2, map.size());
106: assertEquals(true, map.isFull());
107: assertEquals(2, map.maxSize());
108: it = map.keySet().iterator();
109: assertSame(keys[1], it.next());
110: assertSame(keys[2], it.next());
111: it = map.values().iterator();
112: assertSame(values[1], it.next());
113: assertSame(values[0], it.next());
114:
115: map.put(keys[1], values[3]);
116: assertEquals(2, map.size());
117: assertEquals(true, map.isFull());
118: assertEquals(2, map.maxSize());
119: it = map.keySet().iterator();
120: assertSame(keys[2], it.next());
121: assertSame(keys[1], it.next());
122: it = map.values().iterator();
123: assertSame(values[0], it.next());
124: assertSame(values[3], it.next());
125: }
126:
127: //-----------------------------------------------------------------------
128: public void testReset() {
129: resetEmpty();
130: OrderedMap ordered = (OrderedMap) map;
131: ((ResettableIterator) ordered.mapIterator()).reset();
132:
133: resetFull();
134: ordered = (OrderedMap) map;
135: List list = new ArrayList(ordered.keySet());
136: ResettableIterator it = (ResettableIterator) ordered
137: .mapIterator();
138: assertSame(list.get(0), it.next());
139: assertSame(list.get(1), it.next());
140: it.reset();
141: assertSame(list.get(0), it.next());
142: }
143:
144: //-----------------------------------------------------------------------
145: public void testAccessOrder() {
146: if (isPutAddSupported() == false
147: || isPutChangeSupported() == false)
148: return;
149: Object[] keys = getSampleKeys();
150: Object[] values = getSampleValues();
151: Iterator it = null;
152:
153: resetEmpty();
154: map.put(keys[0], values[0]);
155: map.put(keys[1], values[1]);
156: it = map.keySet().iterator();
157: assertSame(keys[0], it.next());
158: assertSame(keys[1], it.next());
159: it = map.values().iterator();
160: assertSame(values[0], it.next());
161: assertSame(values[1], it.next());
162:
163: // no change to order
164: map.put(keys[1], values[1]);
165: it = map.keySet().iterator();
166: assertSame(keys[0], it.next());
167: assertSame(keys[1], it.next());
168: it = map.values().iterator();
169: assertSame(values[0], it.next());
170: assertSame(values[1], it.next());
171:
172: // no change to order
173: map.put(keys[1], values[2]);
174: it = map.keySet().iterator();
175: assertSame(keys[0], it.next());
176: assertSame(keys[1], it.next());
177: it = map.values().iterator();
178: assertSame(values[0], it.next());
179: assertSame(values[2], it.next());
180:
181: // change to order
182: map.put(keys[0], values[3]);
183: it = map.keySet().iterator();
184: assertSame(keys[1], it.next());
185: assertSame(keys[0], it.next());
186: it = map.values().iterator();
187: assertSame(values[2], it.next());
188: assertSame(values[3], it.next());
189:
190: // change to order
191: map.get(keys[1]);
192: it = map.keySet().iterator();
193: assertSame(keys[0], it.next());
194: assertSame(keys[1], it.next());
195: it = map.values().iterator();
196: assertSame(values[3], it.next());
197: assertSame(values[2], it.next());
198:
199: // change to order
200: map.get(keys[0]);
201: it = map.keySet().iterator();
202: assertSame(keys[1], it.next());
203: assertSame(keys[0], it.next());
204: it = map.values().iterator();
205: assertSame(values[2], it.next());
206: assertSame(values[3], it.next());
207:
208: // no change to order
209: map.get(keys[0]);
210: it = map.keySet().iterator();
211: assertSame(keys[1], it.next());
212: assertSame(keys[0], it.next());
213: it = map.values().iterator();
214: assertSame(values[2], it.next());
215: assertSame(values[3], it.next());
216: }
217:
218: public void testClone() {
219: LRUMap map = new LRUMap(10);
220: map.put("1", "1");
221: Map cloned = (Map) map.clone();
222: assertEquals(map.size(), cloned.size());
223: assertSame(map.get("1"), cloned.get("1"));
224: }
225:
226: public void testRemoveLRU() {
227: MockLRUMapSubclass map = new MockLRUMapSubclass(2);
228: assertNull(map.entry);
229: map.put("A", "a");
230: assertNull(map.entry);
231: map.put("B", "b");
232: assertNull(map.entry);
233: map.put("C", "c"); // removes oldest, which is A=a
234: assertNotNull(map.entry);
235: assertEquals("A", map.key);
236: assertEquals("a", map.value);
237: assertEquals("C", map.entry.getKey()); // entry is reused
238: assertEquals("c", map.entry.getValue()); // entry is reused
239: assertEquals(false, map.containsKey("A"));
240: assertEquals(true, map.containsKey("B"));
241: assertEquals(true, map.containsKey("C"));
242: }
243:
244: static class MockLRUMapSubclass extends LRUMap {
245: LinkEntry entry;
246: Object key;
247: Object value;
248:
249: MockLRUMapSubclass(int size) {
250: super (size);
251: }
252:
253: protected boolean removeLRU(LinkEntry entry) {
254: this .entry = entry;
255: this .key = entry.getKey();
256: this .value = entry.getValue();
257: return true;
258: }
259: }
260:
261: public void testRemoveLRUBlocksRemove() {
262: MockLRUMapSubclassBlocksRemove map = new MockLRUMapSubclassBlocksRemove(
263: 2, false);
264: assertEquals(0, map.size());
265: map.put("A", "a");
266: assertEquals(1, map.size());
267: map.put("B", "b");
268: assertEquals(2, map.size());
269: map.put("C", "c"); // should remove oldest, which is A=a, but this is blocked
270: assertEquals(3, map.size());
271: assertEquals(2, map.maxSize());
272: assertEquals(true, map.containsKey("A"));
273: assertEquals(true, map.containsKey("B"));
274: assertEquals(true, map.containsKey("C"));
275: }
276:
277: public void testRemoveLRUBlocksRemoveScan() {
278: MockLRUMapSubclassBlocksRemove map = new MockLRUMapSubclassBlocksRemove(
279: 2, true);
280: assertEquals(0, map.size());
281: map.put("A", "a");
282: assertEquals(1, map.size());
283: map.put("B", "b");
284: assertEquals(2, map.size());
285: map.put("C", "c"); // should remove oldest, which is A=a, but this is blocked
286: assertEquals(3, map.size());
287: assertEquals(2, map.maxSize());
288: assertEquals(true, map.containsKey("A"));
289: assertEquals(true, map.containsKey("B"));
290: assertEquals(true, map.containsKey("C"));
291: }
292:
293: static class MockLRUMapSubclassBlocksRemove extends LRUMap {
294: MockLRUMapSubclassBlocksRemove(int size, boolean scanUntilRemove) {
295: super (size, scanUntilRemove);
296: }
297:
298: protected boolean removeLRU(LinkEntry entry) {
299: return false;
300: }
301: }
302:
303: public void testRemoveLRUFirstBlocksRemove() {
304: MockLRUMapSubclassFirstBlocksRemove map = new MockLRUMapSubclassFirstBlocksRemove(
305: 2);
306: assertEquals(0, map.size());
307: map.put("A", "a");
308: assertEquals(1, map.size());
309: map.put("B", "b");
310: assertEquals(2, map.size());
311: map.put("C", "c"); // should remove oldest, which is A=a but this is blocked - so advance to B=b
312: assertEquals(2, map.size());
313: assertEquals(2, map.maxSize());
314: assertEquals(true, map.containsKey("A"));
315: assertEquals(false, map.containsKey("B"));
316: assertEquals(true, map.containsKey("C"));
317: }
318:
319: static class MockLRUMapSubclassFirstBlocksRemove extends LRUMap {
320: MockLRUMapSubclassFirstBlocksRemove(int size) {
321: super (size, true);
322: }
323:
324: protected boolean removeLRU(LinkEntry entry) {
325: if ("a".equals(entry.getValue())) {
326: return false;
327: } else {
328: return true;
329: }
330: }
331: }
332:
333: //-----------------------------------------------------------------------
334: static class SingleHashCode {
335: private final String code;
336:
337: SingleHashCode(String code) {
338: this .code = code;
339: }
340:
341: public int hashCode() {
342: // always return the same hashcode
343: // that way, it will end up in the same bucket
344: return 12;
345: }
346:
347: public String toString() {
348: return "SingleHashCode:" + code;
349: }
350: }
351:
352: public void testInternalState_Buckets() {
353: if (isPutAddSupported() == false
354: || isPutChangeSupported() == false)
355: return;
356: SingleHashCode one = new SingleHashCode("1");
357: SingleHashCode two = new SingleHashCode("2");
358: SingleHashCode three = new SingleHashCode("3");
359: SingleHashCode four = new SingleHashCode("4");
360: SingleHashCode five = new SingleHashCode("5");
361: SingleHashCode six = new SingleHashCode("6");
362:
363: LRUMap map = new LRUMap(3, 1.0f);
364: int hashIndex = map.hashIndex(map.hash(one), 4);
365: map.put(one, "A");
366: map.put(two, "B");
367: map.put(three, "C");
368:
369: assertEquals(4, map.data.length);
370: assertEquals(3, map.size);
371: assertEquals(null, map.header.next);
372: assertEquals(one, map.header.after.key); // LRU
373: assertEquals(two, map.header.after.after.key);
374: assertEquals(three, map.header.after.after.after.key); // MRU
375: assertEquals(three, map.data[hashIndex].key);
376: assertEquals(two, map.data[hashIndex].next.key);
377: assertEquals(one, map.data[hashIndex].next.next.key);
378:
379: map.put(four, "D"); // reuses last in next list
380:
381: assertEquals(4, map.data.length);
382: assertEquals(3, map.size);
383: assertEquals(null, map.header.next);
384: assertEquals(two, map.header.after.key); // LRU
385: assertEquals(three, map.header.after.after.key);
386: assertEquals(four, map.header.after.after.after.key); // MRU
387: assertEquals(four, map.data[hashIndex].key);
388: assertEquals(three, map.data[hashIndex].next.key);
389: assertEquals(two, map.data[hashIndex].next.next.key);
390:
391: map.get(three);
392:
393: assertEquals(4, map.data.length);
394: assertEquals(3, map.size);
395: assertEquals(null, map.header.next);
396: assertEquals(two, map.header.after.key); // LRU
397: assertEquals(four, map.header.after.after.key);
398: assertEquals(three, map.header.after.after.after.key); // MRU
399: assertEquals(four, map.data[hashIndex].key);
400: assertEquals(three, map.data[hashIndex].next.key);
401: assertEquals(two, map.data[hashIndex].next.next.key);
402:
403: map.put(five, "E"); // reuses last in next list
404:
405: assertEquals(4, map.data.length);
406: assertEquals(3, map.size);
407: assertEquals(null, map.header.next);
408: assertEquals(four, map.header.after.key); // LRU
409: assertEquals(three, map.header.after.after.key);
410: assertEquals(five, map.header.after.after.after.key); // MRU
411: assertEquals(five, map.data[hashIndex].key);
412: assertEquals(four, map.data[hashIndex].next.key);
413: assertEquals(three, map.data[hashIndex].next.next.key);
414:
415: map.get(three);
416: map.get(five);
417:
418: assertEquals(4, map.data.length);
419: assertEquals(3, map.size);
420: assertEquals(null, map.header.next);
421: assertEquals(four, map.header.after.key); // LRU
422: assertEquals(three, map.header.after.after.key);
423: assertEquals(five, map.header.after.after.after.key); // MRU
424: assertEquals(five, map.data[hashIndex].key);
425: assertEquals(four, map.data[hashIndex].next.key);
426: assertEquals(three, map.data[hashIndex].next.next.key);
427:
428: map.put(six, "F"); // reuses middle in next list
429:
430: assertEquals(4, map.data.length);
431: assertEquals(3, map.size);
432: assertEquals(null, map.header.next);
433: assertEquals(three, map.header.after.key); // LRU
434: assertEquals(five, map.header.after.after.key);
435: assertEquals(six, map.header.after.after.after.key); // MRU
436: assertEquals(six, map.data[hashIndex].key);
437: assertEquals(five, map.data[hashIndex].next.key);
438: assertEquals(three, map.data[hashIndex].next.next.key);
439: }
440:
441: public void testInternalState_getEntry_int() {
442: if (isPutAddSupported() == false
443: || isPutChangeSupported() == false)
444: return;
445: SingleHashCode one = new SingleHashCode("1");
446: SingleHashCode two = new SingleHashCode("2");
447: SingleHashCode three = new SingleHashCode("3");
448: SingleHashCode four = new SingleHashCode("4");
449: SingleHashCode five = new SingleHashCode("5");
450: SingleHashCode six = new SingleHashCode("6");
451:
452: LRUMap map = new LRUMap(3, 1.0f);
453: int hashIndex = map.hashIndex(map.hash(one), 4);
454: map.put(one, "A");
455: map.put(two, "B");
456: map.put(three, "C");
457:
458: assertEquals(one, map.getEntry(0).key);
459: assertEquals(two, map.getEntry(1).key);
460: assertEquals(three, map.getEntry(2).key);
461: try {
462: map.getEntry(-1);
463: fail();
464: } catch (IndexOutOfBoundsException ex) {
465: }
466: try {
467: map.getEntry(3);
468: fail();
469: } catch (IndexOutOfBoundsException ex) {
470: }
471: }
472:
473: // public void testCreate() throws Exception {
474: // resetEmpty();
475: // writeExternalFormToDisk((java.io.Serializable) map, "D:/dev/collections/data/test/LRUMap.emptyCollection.version3.obj");
476: // resetFull();
477: // writeExternalFormToDisk((java.io.Serializable) map, "D:/dev/collections/data/test/LRUMap.fullCollection.version3.obj");
478: // }
479: }
|