Class AbstractLinkedList<E,T extends LinkedListEntry<E,T>>
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- net.automatalib.common.smartcollection.AbstractSmartCollection<E>
-
- net.automatalib.common.smartcollection.AbstractLinkedList<E,T>
-
- Type Parameters:
E
- element typeT
- linked list entry type
- All Implemented Interfaces:
Iterable<E>
,Collection<E>
,SmartCollection<E>
,SmartSequence<E>
- Direct Known Subclasses:
DefaultLinkedList
,IntrusiveLinkedList
public abstract class AbstractLinkedList<E,T extends LinkedListEntry<E,T>> extends AbstractSmartCollection<E> implements SmartSequence<E>
Abstract base class for linked lists.This class implements the base functionality for dealing with linked lists of elements implementing the
LinkedListEntry
interface. It provides the logic for the basic operations (esp. the (re-/un-)linking of elements), but not how entries into the lists are created. Therefore, it can be used by both intrusive and non-intrusive linked lists.- See Also:
IntrusiveLinkedList
,DefaultLinkedList
-
-
Constructor Summary
Constructors Constructor Description AbstractLinkedList()
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected T
castRef(ElementReference ref)
Helper function for casting a generalElementReference
to the specific linked list entry type.E
choose()
Retrieves an arbitrary element from the collection.ElementReference
chooseRef()
Retrieves the reference to an arbitrary element from the collection.void
clear()
void
concat(AbstractLinkedList<? extends E,? extends T> other)
Concatenates two linked lists.E
get(ElementReference ref)
Retrieves an element by its reference.E
getBack()
Retrieves the last element in the list.protected @Nullable T
getBackEntry()
Retrieves the last entry in the list, ornull
if the list is empty.@Nullable ElementReference
getBackReference()
Retrieves a reference to the last element in the list.E
getFront()
Retrieves the first element in the list.protected @Nullable T
getFrontEntry()
Retrieves the first entry in the list, ornull
if the list is empty.@Nullable ElementReference
getFrontReference()
Retrieves a reference to the first element in the list.ElementReference
insertAfter(E element, ElementReference ref)
Inserts the given element after the element referenced by the specified reference.protected void
insertAfterEntry(T e, T insertPos)
Inserts a new entry after a given one.ElementReference
insertBefore(E element, ElementReference ref)
Inserts the given element before the element referenced by the specified reference.protected void
insertBeforeEntry(T e, T insertPos)
Inserts a new entry before a given one.boolean
isEmpty()
Iterator<E>
iterator()
protected abstract T
makeEntry(E element)
Creates (if necessary) aLinkedListEntry
for the given element.E
popBack()
Retrieves and removes the last element in the list.protected @Nullable T
popBackEntry()
Removes and returns the last entry in the list.E
popFront()
Retrieves and removes the first element in the list.protected @Nullable T
popFrontEntry()
Removes and returns the first entry in the list.@Nullable ElementReference
pred(ElementReference ref)
Retrieves the reference to the preceding element, ornull
if the given reference references the first element in the list.ElementReference
pushBack(E element)
Adds an element at the end of the list.protected void
pushBackEntry(T e)
Adds an entry at the end of the list.ElementReference
pushFront(E element)
Adds an element at the beginning of the list.protected void
pushFrontEntry(T e)
Adds an entry at the beginning of the list.ElementReference
referencedAdd(E elem)
Adds an element to the collection, returning a reference to the newly added element.Iterator<ElementReference>
referenceIterator()
Retrieves an iterator for iterating over the references of elements in this collection.void
remove(ElementReference elem)
Removes an element (by its reference) from the collection.protected void
removeEntry(T entry)
Removes an entry from the list.void
replace(ElementReference ref, E newElement)
Replaces the element referenced by the given reference with the specified element.protected void
replaceEntry(T oldEntry, T newEntry)
Replaces an entry in the list.int
size()
@Nullable ElementReference
succ(ElementReference ref)
Retrieves the reference to the succeeding element, ornull
if the given reference references the last element in the list.void
swap(AbstractLinkedList<E,T> other)
Swaps the contents of two linked lists with the same entry types.-
Methods inherited from class net.automatalib.common.smartcollection.AbstractSmartCollection
add, addAll, addAll, deepClear, find, quickClear, references, remove
-
Methods inherited from class java.util.AbstractCollection
addAll, contains, containsAll, removeAll, retainAll, toArray, toArray, toString
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface java.util.Collection
add, addAll, contains, containsAll, equals, hashCode, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray
-
Methods inherited from interface net.automatalib.common.smartcollection.SmartCollection
addAll, addAll, deepClear, find, quickClear, references, remove
-
-
-
-
Method Detail
-
getFrontEntry
protected @Nullable T getFrontEntry()
Retrieves the first entry in the list, ornull
if the list is empty.- Returns:
- the first entry or
null
.
-
getBackEntry
protected @Nullable T getBackEntry()
Retrieves the last entry in the list, ornull
if the list is empty.- Returns:
- the first entry or
null
.
-
concat
public void concat(AbstractLinkedList<? extends E,? extends T> other)
Concatenates two linked lists. All elements of the specified list (which will be empty afterward) are added at the end of this list. This operation runs in constant time.- Parameters:
other
- the list to append,
-
choose
public E choose()
Description copied from interface:SmartCollection
Retrieves an arbitrary element from the collection.- Specified by:
choose
in interfaceSmartCollection<E>
- Overrides:
choose
in classAbstractSmartCollection<E>
- Returns:
- an arbitrary element from the collection
-
chooseRef
public ElementReference chooseRef()
Description copied from interface:SmartCollection
Retrieves the reference to an arbitrary element from the collection. If the collection is empty, aNoSuchElementException
is thrown.- Specified by:
chooseRef
in interfaceSmartCollection<E>
- Overrides:
chooseRef
in classAbstractSmartCollection<E>
- Returns:
- the reference to an arbitrary element in the collection
-
iterator
public Iterator<E> iterator()
- Specified by:
iterator
in interfaceCollection<E>
- Specified by:
iterator
in interfaceIterable<E>
- Overrides:
iterator
in classAbstractSmartCollection<E>
-
get
public E get(ElementReference ref)
Description copied from interface:SmartCollection
Retrieves an element by its reference.If the reference belongs to another collection, the behavior is undefined.
- Specified by:
get
in interfaceSmartCollection<E>
- Parameters:
ref
- the element's reference.- Returns:
- the element.
-
referencedAdd
public ElementReference referencedAdd(E elem)
Description copied from interface:SmartCollection
Adds an element to the collection, returning a reference to the newly added element. If the collection does not support containing the same element multiple times, a reference to the previously existing element is returned.- Specified by:
referencedAdd
in interfaceSmartCollection<E>
- Parameters:
elem
- the element to be added.- Returns:
- a reference to this element in the collection.
-
remove
public void remove(ElementReference elem)
Description copied from interface:SmartCollection
Removes an element (by its reference) from the collection.If the reference does not belong to this collection, the behavior is undefined.
- Specified by:
remove
in interfaceSmartCollection<E>
- Parameters:
elem
- the reference to the element to be removed.
-
removeEntry
protected void removeEntry(T entry)
Removes an entry from the list.- Parameters:
entry
- the entry to remove.
-
referenceIterator
public Iterator<ElementReference> referenceIterator()
Description copied from interface:SmartCollection
Retrieves an iterator for iterating over the references of elements in this collection.- Specified by:
referenceIterator
in interfaceSmartCollection<E>
- Returns:
- the reference iterator.
-
replace
public void replace(ElementReference ref, E newElement)
Description copied from interface:SmartCollection
Replaces the element referenced by the given reference with the specified element.- Specified by:
replace
in interfaceSmartCollection<E>
- Parameters:
ref
- the reference of the element to be replaced.newElement
- the replacement.
-
replaceEntry
protected void replaceEntry(T oldEntry, T newEntry)
Replaces an entry in the list.- Parameters:
oldEntry
- the entry to be replaced.newEntry
- the replacement entry.
-
makeEntry
protected abstract T makeEntry(E element)
Creates (if necessary) aLinkedListEntry
for the given element. For intrusive linked lists, e.g., the argument itself is returned.- Parameters:
element
- the element for which to retrieve an entry.- Returns:
- the entry for the given element.
-
pushBackEntry
protected void pushBackEntry(T e)
Adds an entry at the end of the list.- Parameters:
e
- the entry to add.
-
size
public int size()
- Specified by:
size
in interfaceCollection<E>
- Specified by:
size
in classAbstractCollection<E>
-
isEmpty
@EnsuresQualifierIf(qualifier=org.checkerframework.checker.nullness.qual.NonNull.class, expression={"this.head","this.last"}, result=false) public boolean isEmpty()
- Specified by:
isEmpty
in interfaceCollection<E>
- Overrides:
isEmpty
in classAbstractCollection<E>
-
clear
public void clear()
- Specified by:
clear
in interfaceCollection<E>
- Overrides:
clear
in classAbstractCollection<E>
-
getBack
public E getBack()
Retrieves the last element in the list. If the list is empty, aNoSuchElementException
will be thrown.- Returns:
- the last element in the list.
-
getBackReference
public @Nullable ElementReference getBackReference()
Retrieves a reference to the last element in the list. If the list is empty,null
is returned.- Returns:
- a reference to the last element, or
null
.
-
getFront
public E getFront()
Retrieves the first element in the list. If the list is empty, aNoSuchElementException
will be thrown- Returns:
- the first element in the list.
-
getFrontReference
public @Nullable ElementReference getFrontReference()
Retrieves a reference to the first element in the list. If the list is empty,null
is returned.- Returns:
- a reference to the first element, or
null
.
-
popBack
public E popBack()
Retrieves and removes the last element in the list. If the list is empty, aNullPointerException
may be thrown.- Returns:
- the formerly last element in the list.
-
popBackEntry
protected @Nullable T popBackEntry()
Removes and returns the last entry in the list. If the list is empty, it remains unmodified andnull
is returned.- Returns:
- the previously first entry in the list, or
null
.
-
popFront
public E popFront()
Retrieves and removes the first element in the list. If the list is empty, aNullPointerException
may be thrown.- Returns:
- the formerly first element in the list.
-
popFrontEntry
protected @Nullable T popFrontEntry()
Removes and returns the first entry in the list. If the list is empty, it remains unmodified andnull
is returned.- Returns:
- the previously first entry in the list, or
null
.
-
pushBack
public ElementReference pushBack(E element)
Adds an element at the end of the list.- Parameters:
element
- the element to add.- Returns:
- a reference to the newly added element.
-
pushFront
public ElementReference pushFront(E element)
Adds an element at the beginning of the list.- Parameters:
element
- the element to add.- Returns:
- a reference to the newly added element.
-
pushFrontEntry
protected void pushFrontEntry(T e)
Adds an entry at the beginning of the list.- Parameters:
e
- the entry to add.
-
pred
public @Nullable ElementReference pred(ElementReference ref)
Description copied from interface:SmartSequence
Retrieves the reference to the preceding element, ornull
if the given reference references the first element in the list.- Specified by:
pred
in interfaceSmartSequence<E>
- Parameters:
ref
- the reference- Returns:
- the reference to the preceding element
-
castRef
protected T castRef(ElementReference ref)
Helper function for casting a generalElementReference
to the specific linked list entry type.- Parameters:
ref
- the reference.- Returns:
- the argument cast to the entry type.
-
succ
public @Nullable ElementReference succ(ElementReference ref)
Description copied from interface:SmartSequence
Retrieves the reference to the succeeding element, ornull
if the given reference references the last element in the list.- Specified by:
succ
in interfaceSmartSequence<E>
- Parameters:
ref
- the reference- Returns:
- the reference to the succeeding element
-
insertBefore
public ElementReference insertBefore(E element, ElementReference ref)
Description copied from interface:SmartSequence
Inserts the given element before the element referenced by the specified reference.- Specified by:
insertBefore
in interfaceSmartSequence<E>
- Parameters:
element
- the element to be added.ref
- reference to the element before which the new element is to be inserted.- Returns:
- reference to the newly added element.
-
insertBeforeEntry
protected void insertBeforeEntry(T e, T insertPos)
Inserts a new entry before a given one.- Parameters:
e
- the entry to add.insertPos
- the entry before which to add the new one.
-
insertAfter
public ElementReference insertAfter(E element, ElementReference ref)
Description copied from interface:SmartSequence
Inserts the given element after the element referenced by the specified reference.- Specified by:
insertAfter
in interfaceSmartSequence<E>
- Parameters:
element
- the element to be added.ref
- reference to the element after which the new element is to be inserted.- Returns:
- reference to the newly added element.
-
insertAfterEntry
protected void insertAfterEntry(T e, T insertPos)
Inserts a new entry after a given one.- Parameters:
e
- the entry to add.insertPos
- the entry before which to add the new one.
-
swap
public void swap(AbstractLinkedList<E,T> other)
Swaps the contents of two linked lists with the same entry types. This method runs in constant time.- Parameters:
other
- the other list to swap contents with.
-
-