/******************************************************************************
Doubly linked list.
----------------------------------------------------
Copyright (c) Gunnar Gotshalks. All Rights Reserved.
Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and
without fee is hereby granted.
*******************************************************************************/
package FlexOr.container;
import java.util.*;
// Implementation has dummy header and trailer nodes to eliminate the special
// cases of adding and removing the ends of the list.
/**
Implementation of a sequence of objects as a doubly linked list.
@author Gunnar Gotshalks
@version 1.0 1999 Jan 16
@see Sequence
*/
public class DLList implements Sequence{
/*******************************************************************************
Constructor Methods
*******************************************************************************/
/**
Establish the class invariant on an empty list.
Class invariant
To simplify assertions we assume sequence[-1] exists for all sequences. It is
implemented by a dummy header node. Also we assume sequence[size] exists for all
sequences. It is implemented by a dummy trailer node.
*/
public DLList() {
// Variables set in declaration statements. But we need to link the dummy
// header and trailer nodes to each other.
header.next = trailer;
trailer.next = header.previous = null;
trailer.previous = header;
}
/******************************************************************************
Defining the component objects
*******************************************************************************/
/** Points to the dummy header for the list. The datum is null. */
protected Node header = new Node(null);
/** Points to the dummy trailer for the list. The datum is null. */
protected Node trailer = new Node(null);
/** Number of elements in the list. */
protected int length = 0;
/** Pointer to the last referenced element. */
protected Node current = trailer;
/*******************************************************************************
Access Methods
*******************************************************************************/
/** Determines whether an element is in the sequence[first..last]. It is
O(length) as the list must be searched sequentially.
Requires: True
Ensures: contains(obj) => result = true
not contains(obj) => result = false
*/
synchronized public boolean contains(Object obj) {
current = header.next;
while (current != trailer) {
if (current.datum.equals(obj)) return true;
current = current.next;
}
return false;
}
/** Determines whether an element is in sequence[startIndex..last]. It is
O(length) as the list must be searched.
Requires: True
Ensures:
sequence[startIndex..length-1].contains(obj) => result = true
not sequence[startIndex..length-1].contains(obj) => result = false
*/
synchronized public boolean contains(Object obj, int startIndex) {
goToIndex(startIndex);
do { if (current.datum.equals(obj)) return true;
current = current.next;
} while (current != trailer);
return false;
}
/******************************************************************************/
/** Returns an enumerator from the current position. The enumeration class is
anonymous as we only need a single instance.
Requires: True
Ensures: enumeration over the elements first to last.
@exception NoSuchElementException when nextElement is called with an empty
enumeration sequence.
*/
synchronized public Enumeration