001: ///////////////////////////////////////////////////////////////////////////////
002: // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
003: //
004: // This library is free software; you can redistribute it and/or
005: // modify it under the terms of the GNU Lesser General Public
006: // License as published by the Free Software Foundation; either
007: // version 2.1 of the License, or (at your option) any later version.
008: //
009: // This library is distributed in the hope that it will be useful,
010: // but WITHOUT ANY WARRANTY; without even the implied warranty of
011: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: // GNU General Public License for more details.
013: //
014: // You should have received a copy of the GNU Lesser General Public
015: // License along with this program; if not, write to the Free Software
016: // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
017: ///////////////////////////////////////////////////////////////////////////////
018:
019: package gnu.trove;
020:
021: import junit.framework.*;
022: import java.io.*;
023: import java.util.*;
024:
025: /**
026: *
027: * Created: Sat Nov 10 15:57:07 2001
028: *
029: * @author Eric D. Friedman
030: * @version $Id: TLinkedListTest.java,v 1.5 2007/11/01 16:01:09 robeden Exp $
031: */
032:
033: public class TLinkedListTest extends TestCase {
034: protected TLinkedList<Data> list;
035:
036: public TLinkedListTest(String name) {
037: super (name);
038: }
039:
040: public void setUp() throws Exception {
041: list = new TLinkedList<Data>();
042: }
043:
044: public void tearDown() throws Exception {
045: list = null;
046: }
047:
048: public void testAdd() throws Exception {
049: Data[] data = { new Data(1), new Data(2), new Data(3) };
050: for (int i = 0; i < data.length; i++) {
051: list.add(data[i]);
052: }
053: assertEquals(3, list.size());
054: }
055:
056: public void testInsert() throws Exception {
057: Data[] data = { new Data(2), new Data(4), new Data(6) };
058: for (int i = 0; i < data.length; i++) {
059: list.add(data[i]);
060: }
061:
062: list.insert(0, new Data(1));
063: list.insert(2, new Data(3));
064: list.insert(4, new Data(5));
065: list.insert(list.size(), new Data(7));
066:
067: assertEquals(7, list.size());
068: for (int i = 0; i < list.size(); i++) {
069: assertEquals(i + 1, list.get(i)._val);
070: }
071: }
072:
073: public void testNextIterator() throws Exception {
074: Data[] data = new Data[100];
075: for (int i = 0; i < data.length; i++) {
076: data[i] = new Data(i);
077: list.add(data[i]);
078: }
079:
080: int count = 0;
081: for (Iterator i = list.iterator(); i.hasNext();) {
082: assertEquals(data[count++], i.next());
083: }
084: assertEquals(data.length, count);
085:
086: count = 4;
087: for (Iterator i = list.listIterator(4); i.hasNext();) {
088: assertEquals(data[count++], i.next());
089: }
090: assertEquals(data.length, count);
091: }
092:
093: public void testPreviousIterator() throws Exception {
094: Data[] data = new Data[100];
095: for (int i = 0; i < data.length; i++) {
096: data[i] = new Data(i);
097: list.add(data[i]);
098: }
099:
100: int count = 100;
101: for (ListIterator i = list.listIterator(list.size()); i
102: .hasPrevious();) {
103: assertEquals(data[--count], i.previous());
104: }
105: assertEquals(0, count);
106:
107: count = 5;
108: for (ListIterator i = list.listIterator(count); i.hasPrevious();) {
109: assertEquals(data[--count], i.previous());
110: }
111: assertEquals(0, count);
112: }
113:
114: public void testIteratorSet() throws Exception {
115: Data[] data = new Data[100];
116: for (int i = 0; i < data.length; i++) {
117: data[i] = new Data(i);
118: list.add(data[i]);
119: }
120:
121: ListIterator i;
122:
123: i = list.listIterator(5);
124: i.next();
125: Data d = new Data(999);
126: i.set(d);
127: assertEquals(d, list.get(5));
128: }
129:
130: public void testRemoveOnlyElementInList() throws Exception {
131: Data d = new Data(0);
132: list.add(d);
133: ListIterator i = list.listIterator();
134: assertTrue(i.hasNext());
135: assertEquals(d, i.next());
136: i.remove();
137: assertTrue(!i.hasNext());
138: assertTrue(!i.hasPrevious());
139: assertEquals(0, list.size());
140: }
141:
142: public void testRemovePrevious() throws Exception {
143: Data[] d = { new Data(0), new Data(1), new Data(2) };
144: list.addAll(Arrays.asList(d));
145:
146: ListIterator i = list.listIterator(list.size());
147: i.previous();
148: i.previous();
149: i.remove();
150: assertEquals(2, list.size());
151: assertTrue(i.hasPrevious());
152: assertEquals(d[0], i.previous());
153: assertTrue(!i.hasPrevious());
154: assertTrue(i.hasNext());
155: assertEquals(d[0], i.next());
156: assertTrue(i.hasNext());
157: assertEquals(d[2], i.next());
158: assertTrue(!i.hasNext());
159: assertTrue(i.hasPrevious());
160: assertEquals(2, list.size());
161: }
162:
163: public void testRemoveLast() throws Exception {
164: Data[] d = { new Data(0), new Data(1), new Data(2) };
165: list.addAll(Arrays.asList(d));
166:
167: ListIterator i = list.listIterator(list.size());
168: i.previous();
169: i.remove();
170: assertEquals(2, list.size());
171: assertTrue(i.hasPrevious());
172: assertTrue(!i.hasNext());
173: }
174:
175: public void testRemoveFirst() throws Exception {
176: Data[] d = { new Data(0), new Data(1), new Data(2) };
177: list.addAll(Arrays.asList(d));
178:
179: ListIterator i = list.listIterator(0);
180: i.next();
181: i.remove();
182: assertEquals(2, list.size());
183: assertTrue(!i.hasPrevious());
184: assertTrue(i.hasNext());
185: }
186:
187: public void testRemoveNext() throws Exception {
188: Data[] d = { new Data(0), new Data(1), new Data(2) };
189: list.addAll(Arrays.asList(d));
190:
191: ListIterator i = list.listIterator();
192: assertTrue(i.hasNext());
193: i.next();
194: assertTrue(i.hasNext());
195: assertTrue(i.hasPrevious());
196: i.remove();
197: assertEquals(2, list.size());
198: assertTrue(!i.hasPrevious());
199: assertTrue(i.hasNext());
200: assertEquals(d[1], i.next());
201: assertTrue(i.hasNext());
202: assertEquals(d[2], i.next());
203: assertTrue(i.hasPrevious());
204: assertTrue(!i.hasNext());
205: }
206:
207: public void testRemoveThrowsAfterAdd() throws Exception {
208: Data d = new Data(0);
209: list.add(d);
210: ListIterator i = list.listIterator();
211: boolean didThrow = false;
212:
213: try {
214: i.remove();
215: } catch (IllegalStateException e) {
216: didThrow = true;
217: } // end of try-catch
218: assertTrue(didThrow);
219: }
220:
221: public void testRemoveThrowsWithoutPrevious() throws Exception {
222: Data d = new Data(0);
223: list.add(d);
224: ListIterator i = list.listIterator(list.size());
225: boolean didThrow = false;
226:
227: assertTrue(i.hasPrevious());
228: try {
229: i.remove();
230: } catch (IllegalStateException e) {
231: didThrow = true;
232: } // end of try-catch
233: assertTrue(didThrow);
234: }
235:
236: public void testRemoveThrowsWithoutNext() throws Exception {
237: Data d = new Data(0);
238: list.add(d);
239: ListIterator i = list.listIterator();
240: boolean didThrow = false;
241:
242: assertTrue(i.hasNext());
243: try {
244: i.remove();
245: } catch (IllegalStateException e) {
246: didThrow = true;
247: } // end of try-catch
248: assertTrue(didThrow);
249: }
250:
251: public void testIteratorAddFront() throws Exception {
252: Data[] d = { new Data(0), new Data(1), new Data(2) };
253: list.addAll(Arrays.asList(d));
254:
255: ListIterator i = list.listIterator();
256: Data d1 = new Data(5);
257: assertTrue(!i.hasPrevious());
258: i.add(d1);
259: assertTrue(i.hasPrevious());
260: assertEquals(d1, i.previous());
261: assertEquals(d1, i.next());
262: assertEquals(d[0], i.next());
263: assertEquals(d1, list.get(0));
264: }
265:
266: public void testIteratorAddBack() throws Exception {
267: Data[] d = { new Data(0), new Data(1), new Data(2) };
268: list.addAll(Arrays.asList(d));
269:
270: ListIterator i = list.listIterator(list.size());
271: Data d1 = new Data(5);
272: assertEquals(3, list.size());
273: assertTrue(i.hasPrevious());
274: assertTrue(!i.hasNext());
275: i.add(d1);
276: assertTrue(i.hasPrevious());
277: assertTrue(!i.hasNext());
278: assertEquals(4, list.size());
279:
280: assertEquals(d1, i.previous());
281: assertEquals(d1, i.next());
282: assertEquals(d1, list.get(3));
283: }
284:
285: public void testIteratorAddMiddle() throws Exception {
286: Data[] d = { new Data(0), new Data(1), new Data(2) };
287: list.addAll(Arrays.asList(d));
288:
289: ListIterator i = list.listIterator(1);
290: Data d1 = new Data(5);
291: assertEquals(3, list.size());
292: assertTrue(i.hasPrevious());
293: assertTrue(i.hasNext());
294: i.add(d1);
295: assertTrue(i.hasPrevious());
296: assertTrue(i.hasNext());
297: assertEquals(4, list.size());
298:
299: assertEquals(d1, i.previous());
300: assertEquals(d1, i.next());
301: assertEquals(d1, list.get(1));
302: }
303:
304: public void testIteratorSetSingleElementList() throws Exception {
305: Data d1 = new Data(5);
306: Data d2 = new Data(4);
307: list.add(d1);
308:
309: ListIterator i = list.listIterator(0);
310: i.next();
311: i.set(d2);
312: assertEquals(1, list.size());
313: assertTrue(!i.hasNext());
314: assertTrue(i.hasPrevious());
315: assertEquals(d2, i.previous());
316: assertTrue(i.hasNext());
317: assertTrue(!i.hasPrevious());
318: assertEquals(d2, i.next());
319: }
320:
321: public void testIteratorAddEmptyList() throws Exception {
322: ListIterator i = list.listIterator();
323: Data d1 = new Data(5);
324: assertTrue(!i.hasPrevious());
325: assertTrue(!i.hasNext());
326: i.add(d1);
327: assertTrue(i.hasPrevious());
328: assertTrue(!i.hasNext());
329: assertEquals(d1, i.previous());
330: assertEquals(d1, i.next());
331: assertEquals(d1, list.get(0));
332: }
333:
334: public void testIteratorRemoveOnNext() throws Exception {
335: Data[] data = new Data[100];
336: for (int i = 0; i < data.length; i++) {
337: data[i] = new Data(i);
338: list.add(data[i]);
339: }
340:
341: ListIterator i;
342:
343: i = list.listIterator(5);
344: i.next();
345: i.remove();
346: Data d = new Data(6);
347: assertEquals(d, list.get(5));
348: }
349:
350: public void testSerialize() throws Exception {
351: TLinkedList list1 = new TLinkedList();
352: Data[] data = new Data[100];
353: for (int i = 0; i < data.length; i++) {
354: data[i] = new Data(i);
355: list1.add(data[i]);
356: }
357:
358: ByteArrayOutputStream baos = new ByteArrayOutputStream();
359: ObjectOutputStream oos = new ObjectOutputStream(baos);
360: oos.writeObject(list1);
361:
362: ByteArrayInputStream bais = new ByteArrayInputStream(baos
363: .toByteArray());
364: ObjectInputStream ois = new ObjectInputStream(bais);
365:
366: TLinkedList list2 = (TLinkedList) ois.readObject();
367: assertEquals(list1, list2);
368: }
369:
370: public void testForEach() throws Exception {
371: list.add(new Data(0));
372: list.add(new Data(1));
373: list.add(new Data(2));
374: list.add(new Data(3));
375: list.add(new Data(4));
376:
377: // test exiting early
378: boolean processed_full_list = list
379: .forEachValue(new TObjectProcedure<Data>() {
380: public boolean execute(Data object) {
381: if (object._val == 2)
382: return false;
383:
384: object._val++;
385:
386: return true;
387: }
388: });
389: assertFalse(processed_full_list);
390:
391: assertEquals(1, list.get(0)._val);
392: assertEquals(2, list.get(1)._val);
393: assertEquals(2, list.get(2)._val);
394: assertEquals(3, list.get(3)._val);
395: assertEquals(4, list.get(4)._val);
396:
397: // test full list processing
398: processed_full_list = list
399: .forEachValue(new TObjectProcedure<Data>() {
400: public boolean execute(Data object) {
401: object._val++;
402: return true;
403: }
404: });
405: assertTrue(processed_full_list);
406:
407: assertEquals(2, list.get(0)._val);
408: assertEquals(3, list.get(1)._val);
409: assertEquals(3, list.get(2)._val);
410: assertEquals(4, list.get(3)._val);
411: assertEquals(5, list.get(4)._val);
412: }
413:
414: public void testAddBefore() {
415: Data one = new Data(1);
416: Data three = new Data(3);
417: Data four = new Data(4);
418: Data five = new Data(5);
419:
420: list.add(one);
421: list.add(three);
422: list.add(four);
423: list.add(five);
424:
425: list.addBefore(one, new Data(0));
426: list.addBefore(three, new Data(2));
427: list.addBefore(null, new Data(6));
428:
429: System.out.println("List: " + list);
430:
431: int value = -1;
432: Data cur = list.getFirst();
433: while (cur != null) {
434: assertEquals(value + 1, cur._val);
435: value = cur._val;
436:
437: cur = cur.getNext();
438: }
439:
440: assertEquals(6, value);
441: }
442:
443: public void testAddAfter() {
444: Data one = new Data(1);
445: Data three = new Data(3);
446: Data four = new Data(4);
447: Data five = new Data(5);
448:
449: list.add(one);
450: list.add(three);
451: list.add(four);
452: list.add(five);
453:
454: list.addBefore(one, new Data(0));
455: list.addBefore(three, new Data(2));
456: list.addBefore(null, new Data(6));
457:
458: System.out.println("List: " + list);
459:
460: int value = -1;
461: Data cur = list.getFirst();
462: while (cur != null) {
463: assertEquals(value + 1, cur._val);
464: value = cur._val;
465:
466: cur = cur.getNext();
467: }
468:
469: assertEquals(6, value);
470: }
471:
472: public void testPastIndexGet() {
473: try {
474: list.get(0);
475: fail("Shouldn't have allowed get of index 0");
476: } catch (IndexOutOfBoundsException ex) {
477: // this is good
478: }
479:
480: try {
481: list.get(1);
482: fail("Shouldn't have allowed get of index 1");
483: } catch (IndexOutOfBoundsException ex) {
484: // this is good
485: }
486:
487: list.add(new Data(1));
488: list.get(0);
489:
490: try {
491: list.get(1);
492: fail("Shouldn't have allowed get of index 1");
493: } catch (IndexOutOfBoundsException ex) {
494: // this is good
495: }
496: }
497:
498: static class Data implements TLinkable {
499: protected int _val;
500:
501: public Data(int val) {
502: _val = val;
503: }
504:
505: protected TLinkable _next;
506:
507: // NOTE: use covariant overriding
508: /**
509: * Get the value of next.
510: * @return value of next.
511: */
512: public Data getNext() {
513: return (Data) _next;
514: }
515:
516: /**
517: * Set the value of next.
518: * @param next value to assign to next.
519: */
520: public void setNext(TLinkable next) {
521: this ._next = next;
522: }
523:
524: protected TLinkable _previous;
525:
526: // NOTE: use covariant overriding
527: /**
528: * Get the value of previous.
529: * @return value of previous.
530: */
531: public Data getPrevious() {
532: return (Data) _previous;
533: }
534:
535: /**
536: * Set the value of previous.
537: * @param previous value to assign to previous.
538: */
539: public void setPrevious(TLinkable previous) {
540: this ._previous = previous;
541: }
542:
543: public String toString() {
544: return "" + _val;
545: }
546:
547: public boolean equals(Object o) {
548: Data that = (Data) o;
549: return this ._val == that._val;
550: }
551: }
552:
553: } // TLinkedListTests
|