package util;
import java.util.List;
/**
* Eine Klasse zur Erstellung und verarbeitung einfach verketter Listen.
*
* @author Jan Müller
* @author Matthias Braeuer
*/
public class ListenElement<T> {
private T data;
private ListenElement next;
/**
* Default Konstruktor
*/
public ListenElement() {
}
/**
* Erzeugt ein Element dessen next Pointer = null ist
*
* @param data / Typ T Den Wert den das Element haben soll
*/
public ListenElement(T data) {
this.data = data;
}
/**
* Erzeugt ein ListenElement welches auf einen nachfolger zeigt.
*
* @param data / Typ T Den Wert den das Element haben soll
* @param next / Typ ListenElement das nachfolgende Element.
*/
public ListenElement(T data, ListenElement next) {
this.data = data;
this.next = next;
}
public static boolean is_a_list(Object object) {
if(object instanceof ListenElement){
ListenElement element = (ListenElement) object;
ListenElement next = element.next;
return next == null || ListenElement.is_a_list(next);
}
return false;
}
public ListenElement getNext() {
return this.next;
}
public T getData() {
return data;
}
/**
* Dreht die aufrufende Liste um und gibt dem First Pointer der umgedrehten
* Liste zurück
*
* @return Typ ListenElement
*/
public ListenElement reverse() {
if (next == null)
return this;
ListenElement secondElem = next;
next = null;
ListenElement reverseRest = secondElem.reverse();
secondElem.next = this;
return reverseRest;
}
/**
* Prüft ob der übergebene Parameter in der aufrufenden Liste vorhanden ist.
*
* @param element Object
* @return Typ boolean / Falls die Liste ein Element mit dem zu prüfenden
* Wert enthält -> true, sonst -> false
*/
public boolean include(Object element) {
ListenElement listElement = this;
if (this.data == element) {
return true;
}
while (listElement.next != null) {
listElement = listElement.next;
if (listElement.data == element) {
return true;
}
}
return false;
}
/**
* Bildet aus der Aufrufenden Liste und dem Ãœbergabeparameter die
* Differenzliste, die Differenzliste beinhaltet nur Elemente die in der
* Aufrufenden Liste vorkommen jedoch nicht in der als Parameter übergebenen
* Liste.
*
* @param liste / Typ ListenElement First Pointer der zu differenziernden
* Liste.
* @return Typ ListenElement / First Pointer der Differenzliste
*/
public ListenElement difflist(ListenElement liste) {
ListenElement listElement = this; // Iterator Variable
ListenElement prev = null; // Zwischenspeicher
ListenElement differenzListe = new ListenElement(); // Output
// Schleife um über alle Elemente der Liste drüber zu Iterieren
while (listElement != null) {
// Fall 2
if (!liste.include(listElement.data)) {
differenzListe = new ListenElement<>(listElement.data, prev);
prev = differenzListe;
}
// Fall 2: Element wird nicht in Differenzliste übernommen
listElement = listElement.next;
}
return differenzListe.reverse();
}
/**
* Prüft ob der Übergabeparameter ein Präfix der aufrufenden Liste ist (nach
* einem Präfix kommt noch was).
*
* @param praefix / Typ ListenElement First Pointer der anzunehmenden Präfix
* Liste
* @return Typ boolean / Falls es ein Präfix ist -> true, Falls nicht ->
* false
*/
public boolean praefix(ListenElement praefix) {
ListenElement listElement_1 = this; // Iterator Variable
ListenElement listElement_2 = praefix; // Iterator Variable
// Schleife um über alle Elemente der Liste drüber zu Iterieren
while (listElement_2.next != null && listElement_1.next != null) {
// Fall 1
if (listElement_2.data == listElement_1.data) {
listElement_1 = listElement_1.next;
listElement_2 = listElement_2.next;
// Fall 2
} else {
return false;
}
}
// Prüfung ob in der aufrufenden Liste noch Elemente enthalten
// sind.(hinter einem Präfix kommt noch was)
return listElement_1.next != null;
}
/**
* Prüft ob der Übergabeparameter ein Suffix der aufrufenden Liste ist (vor
* einem Suffix kommt noch was).
*
* @param suffix / Typ ListenElement First Pointer der anzunehmenden Suffix
* Liste
* @return Typ boolean / Falls es ein Suffix ist -> true, Falls nicht ->
* false
*/
public boolean suffix(ListenElement suffix) {
ListenElement listElement_1 = this;// Iterator Variable
// Schleife um über alle Elemente der Liste drüber zu Iterieren
// Fall 2
while (listElement_1.next != null) {
listElement_1 = listElement_1.next;
// Fall 1
if (listElement_1.data == suffix.data) {
ListenElement liste1 = listElement_1;
ListenElement liste2 = suffix;
// Prüft den Rest der Liste auf gleiche Werte
while ((liste1.next != null && liste2.next != null) && (liste1.data == liste2.data)) {
liste1 = liste1.next;
liste2 = liste2.next;
}
// Prüft ob auch wirlich beide Listen leer und somit identisch
// sind
if (liste1.next == null && liste2.next == null) {
return true;
}
}
}
return false;
}
/**
* Prüft ob der Übergabeparameter ein Infix der aufrufenden Liste ist(vor
* und hinter einem Infix kommt noch was).
*
* @param infix / Typ ListenElement FirstPointer der Infix Liste.
* @return Typ boolean / Falls es ein Infix ist -> true, Falls nicht ->
* false
*/
public boolean infix(ListenElement infix) {
ListenElement listElement_1 = this;// Iterator Variable
// Prüft ob der übergabeparameter ein Präfix oder Suffix ist
if (listElement_1.suffix(infix) || listElement_1.praefix(infix)) {
return false;
} else {
// Schleife um über alle Elemente der Liste drüber zu Iterieren
while (listElement_1.next != null) {
listElement_1 = listElement_1.next;
// Fall 1 (Präfixprüfung)
if (listElement_1.praefix(infix)) {
return true;
}
}
// Fall 2 (Präfixprüfung)
return false;
}
}
/**
* Zählt die Anzahl gerader und ungerader Listen in einer Liste inklusive der Liste selbst.
*
* @return int[]
*/
public int[] eo_count() {
int even = 0;
int odd = 0;
if (isListEven()) {
even += 1;
}
if (isListOdd()) {
odd += 1;
}
int[] listCount = count();
even += listCount[0];
odd += listCount[1];
return new int[]{even, odd};
}
/**
* Zählt die Anzahl gerader und ungerader Listen in einer Liste
*
* @return int[]
*/
public int[] count() {
int even = 0;
int odd = 0;
if (ListenElement.is_a_list(this.getData())) {
int[] evenOdd = ((ListenElement) this.getData()).eo_count();
even += evenOdd[0];
odd += evenOdd[1];
}
if (this.getNext() == null) return new int[]{even, odd};
int[] nextEvenOdd = this.getNext().count();
even += nextEvenOdd[0];
odd += nextEvenOdd[1];
return new int[]{even, odd};
}
private boolean isListEven() {
return length() % 2 == 0;
}
private boolean isListOdd() {
return length() % 2 == 1;
}
public int length() {
if (this.getNext() == null) return 1;
return 1 + this.getNext().length();
}
/**
* Löscht in einer Liste "element" an der Position "position".
*
* @param position / Typ char "'a' für alle vorkommen, 'e' für erstes vorkommen,
* 'l für letztes vorkommen'"
* @param element / Typ ListenElement "Das Element welches aus der Liste
* gelöscht werden soll"
* @return ListenElement / First Pointer von der neuen Liste.
*/
public ListenElement del_element(char position, ListenElement element) {
switch (position) {
case 'a':
return delAll(this, element);
case 'e':
return delFirst(this, element);
case 'l':
return delLast(this, element);
default:
return null;
}
}
private ListenElement delAll(ListenElement list, ListenElement element) {
ListenElement prev = null;// Zwischenspeicher
ListenElement result = new ListenElement();// Output
// Schleife um über alle Elemente der Liste drüber zu Iterieren
while (list != null) {
// Fall 1
if (list.data != element.data) {
result = new ListenElement<>(list.data, prev);
prev = result;
}
// Fall 2: Element wird nicht an Ergebnislist angehängt
// -> Ergebnisliste enthält dieses Element nicht und wurde aus Liste gelöscht
list = list.next;
}
return result.reverse();
}
private ListenElement delFirst(ListenElement list, ListenElement element) {
ListenElement prev = null;// Zwischenspeicher
ListenElement result = new ListenElement();// Output
boolean finish_flag = false;
// Schleife um über alle Elemente der Liste drüber zu Iterieren
while (list != null) {
// Fall 1
if (list.data != element.data || finish_flag) {
result = new ListenElement<>(list.data, prev);
prev = result;
}
// Fall 2
else if (!finish_flag) {
finish_flag = true;
}
list = list.next;
}
return result.reverse();
}
private ListenElement delLast(ListenElement list, ListenElement element) {
ListenElement result;
result = delFirst(list.reverse(), element);
return result.reverse();
}
/**
* Ersetzt in einer Liste "element" durch "element2" an der Position
* "position".
*
* @param position / Typ char "'a' für alle vorkommen, 'e' für erstes vorkommen,
* 'l für letztes vorkommen'"
* @param element / Typ ListenElement "Das Element welches aus der Liste ersetzt
* werden soll"
* @param element2 / Typ ListenElement "Das Element welches (element) ersetzt"
* @return ListenElement / First Pointer von der neuen Liste.
*/
public ListenElement substitute(char position, ListenElement element, ListenElement element2) {
switch (position) {
case 'a':
return substituteAll(this, element, element2);
case 'e':
return substituteFirst(this, element, element2);
case 'l':
return substituteLast(this, element, element2);
default:
return null;
}
}
private ListenElement substituteAll(ListenElement list, ListenElement element, ListenElement element2) {
ListenElement prev = null;// Zwischenspeicher
ListenElement result = new ListenElement(); // Output
// Schleife um über alle Elemente der Liste drüber zu Iterieren
while (list != null) {
// Fall 1
if (list.data != element.data) {
result = new ListenElement<>(list.data, prev);
}
// Fall 2
else {
result = new ListenElement<>(element2.data, prev);
}
prev = result;
list = list.next;
}
return result.reverse();
}
private ListenElement substituteFirst(ListenElement list, ListenElement element, ListenElement element2) {
ListenElement prev = null;// Zwischenspeicher
ListenElement result = new ListenElement(); // Output
boolean finish_flag = false;
// Schleife um über alle Elemente der Liste drüber zu Iterieren
while (list != null) {
// Fall 1
if (list.data != element.data || finish_flag) {
result = new ListenElement<>(list.data, prev);
}
// Fall 2
else if (!finish_flag) {
result = new ListenElement<>(element2.data, prev);
finish_flag = true;
}
prev = result;
list = list.next;
}
return result.reverse();
}
private ListenElement substituteLast(ListenElement list, ListenElement element, ListenElement element2) {
ListenElement result; // Output
result = substituteFirst(list.reverse(), element, element2);
// Ausgabe Formatierung Liste muss nochmals gedreht werden
return result.reverse();
}
public boolean deepEquals(ListenElement other) {
if (this.getNext() == null && other.getNext() == null) return this.equals(other);
if (other.getNext() == null || this.getNext() == null) return false;
return this.equals(other) && this.getNext().deepEquals(other.getNext());
}
public String toDeepString() {
if (this.getNext() == null) return toString() + ", " + "null";
return toString() + ", " + this.getNext().toDeepString();
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
ListenElement other = (ListenElement) obj;
return data.equals(other.data);
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + data.hashCode();
return result;
}
@Override
public String toString() {
return "[data=" + data + "]";
}
}
. Falls irgendjemand ansatzweise versteht was ich hier für wirres zeug rede und mir vielleicht einen Tipp geben könnte wie ich ranzugehen habe wäre ich super dankbar.
