Problem beim Kombinieren von LinkedList-Elementen

Unicate

Erfahrenes Mitglied
Hallo alle zusammen!

Der Titel ist vielleicht etwas unglücklich gewählt, ich wusste aber nicht wie ich das sonst in Kurzform ausdrücken sollte.

Zu meinem Problem.

Ich habe eine Liste von Elementen. Einige dieser Elemente, habe ein "COMBINE"-Flag. welches aussagt, das es mit dem nächsten Element in der Liste kombiniert werden kann.
Ziel ist es nun die Liste durch zu gehen und kombinierbare Elemente miteinander zu kombinieren.

Beispiel:
Aus:
Code:
Liste
  Eintrag 1 (combine)
  Eintrag 2
  Eintrag 3 (combine)
  Eintrag 4

entsteht

Code:
Liste
  Eintrag 1 kombiniert mit 2
  Eintrag 3 kombiniert mit 4

Nun kommt ein erneuter Schwierigkeitsgrad hinzu, nämlich das die Einträge eine Priorität haben. D.h. Wenn im obigem Beispiel Eintrag 2 eine höhere Priorität hat als Eintrag 1, dann soll Eintrag 2 mit Eintrag 1 kombiniert werden und nicht umgekehrt.
(Die Prioritäten sind eigentlich keine Zahl. Die Elemente sind unterschiedlicher Klassentypen, wobei die einen höher priorisiert sein sollen als andere)

Beispiel:
Aus
Code:
Liste
  Eintrag(prio 1) 1 (combine)
  Eintrag(prio 3) 2
  Eintrag(prio 4) 3 (combine)
  Eintrag(prio 2) 4

ensteht

Code:
Liste
  Eintrag 2 kombiniert mit 1
  Eintrag 3 kombiniert mit 4


Ersteres halte ich für machbar, 2teres ist schon schwieriger und ich wüsste nicht wie ich da ran gehen sollte.
Hier der header der Methode
Java:
public List<Element> combineElements(LinkedList<Element> uncombinedList)


Könnt Ihr mir helfen einen Ansatz zu finden?

Mein Basisversuch:

Java:
	public List<Element> combineElements(LinkedList<Element> uncombinedList) {
	    Element lastElement = null;
	    Iterator<Element> it = uncombinedList.iterator();
	    while (it.hasNext()) {
	    	Element currentElement = it.next();
			if (null != lastElement && lastElement.hasCombineflag()) {
				if(lastElement.getPrio() > currentElement.getPrio()) {
					// combine last with current
					// and delete current (not used anymore)
				} else {
					// combine current with last
					// and delete last (not used anymore)
				}
			}
			lastElement = currentElement;
		}
	    return uncombinedList;
	}
 
Zuletzt bearbeitet:

I2oxxi

Mitglied
Hey :)
eine interessante aufgabe der ich mich mal gestellt habe ^^
leider kenne ich dieses Element interface überhaupt nicht und weiß nicht wozu es da ist, aber an der schleife änder das glaub ich nichts. bei mir sieht das ganze dann am ende so aus:
Java:
public static List<MyElement> combineElements(LinkedList<MyElement> uncombinedList){
		//neue liste anlegen
		List<MyElement> newList = new LinkedList<MyElement>();
		for(int i=0; i<uncombinedList.size();i++){
			//wenn kein flag  gesetzt dann element in die neue liste und nächstes element angucken
			if(!uncombinedList.get(i).getFlag())
				newList.add(uncombinedList.get(i));
			else{
				//falls nicht priorität vergleichen
				if(uncombinedList.get(i).getPrio() >= uncombinedList.get(i+1).getPrio()){
					//kombinieren, eintragen, ein element überspringen
					MyElement elem = uncombinedList.get(i);
					elem.combine(uncombinedList.get(i+1));
					newList.add(elem);
					i++;	
				}
				else{
					//das gleiche, nur andersherum kombinieren
					MyElement elem = uncombinedList.get(i+1);
					elem.combine(uncombinedList.get(i));
					newList.add(elem);
					i++;
				}
				
			}
		}
		return newList;
	}
ich finde es auch sehr viel einfacher eine neue liste anzulegen, und nicht die bestehende hin und her zu ändern, ist ja aber ansichtssache ^^


da ich ja nicht wusste wie deine elemente da nun in wirklichkeit funktionieren und wie diese kombiniert werden, haben ich ne kleine "simulation" gemacht, hoffe das ich damit das ziel nicht so komplett verfehlt habe, den teil hast du ja auch ausdoumentiert.
ich versteh auch nicht ganz, du benutzt ja das javax.xml.bind.Element interface oder? wird mir hier jedenfalls angezeigt wenn ich drauf klick ^^ und dieses interface bringt eine getPrio() und hasFlag() ja gar nicht mit ...
hier die gesamte simulationklasse
Java:
import java.util.LinkedList;
import java.util.List;

import javax.xml.bind.Element;

//kleine simulierung deines elements
public class MyElement implements Element{
	
	private static int counter = 1;
	private int id;
	private boolean flag;
	private int eintrag; //kp wie deine einträge aussehen aber ich nehm einfach mal zahlen, combined dann addiert
	private int prio; // beispiel einer priorität
	private String combined = "Uncombined Element";
	
	public MyElement(int eintrag, int prio, boolean flag){
		this.eintrag=eintrag;
		this.prio=prio;
		this.flag=flag;
		id = counter;
		counter++;
	}
	
	public int getEintrag(){
		return this.eintrag;
	}
	
	public boolean getFlag(){
		return this.flag;
	}
	
	public int getPrio(){
		return this.prio;
	}
	
	public String getStatus(){
		return this.combined;
	}
	
	public int getID(){
		return this.id;
	}
	
	//hier MyElement und nicht element da ich ja kp hab wie du die sachen kombinieren wills
	public void combine(MyElement e){
		this.eintrag+=e.getEintrag();
		this.combined="ID " + this.id+ " combined with ID "+ e.getID();
		//gegebenfalls noch das flag löschen, weiß ja nicht was genau du da vor hast ^^
	}
	
	//hier selbiges, kp, weiß auch nicht genau wofür das interface da ist von daher.... an der logik sollte es aber nicht viel ändern ^^
	public static List<MyElement> combineElements(LinkedList<MyElement> uncombinedList){
		//neue liste anlegen
		List<MyElement> newList = new LinkedList<MyElement>();
		for(int i=0; i<uncombinedList.size();i++){
			//wenn kein flag  gesetzt dann element in die neue liste und nächstes element angucken
			if(!uncombinedList.get(i).getFlag())
				newList.add(uncombinedList.get(i));
			else{
				//falls nicht priorität vergleichen
				if(uncombinedList.get(i).getPrio() >= uncombinedList.get(i+1).getPrio()){
					//kombinieren, eintragen, ein element überspringen
					MyElement elem = uncombinedList.get(i);
					elem.combine(uncombinedList.get(i+1));
					newList.add(elem);
					i++;	
				}
				else{
					//das gleiche, nur andersherum kombinieren
					MyElement elem = uncombinedList.get(i+1);
					elem.combine(uncombinedList.get(i));
					newList.add(elem);
					i++;
				}
				
			}
		}
		return newList;
	}
	
	public static void main(String[] args){
		MyElement e1 = new MyElement(1, 1, false);
		MyElement e2 = new MyElement(1, 2, true);
		MyElement e3 = new MyElement(1, 1, false);
		MyElement e4 = new MyElement(5, 1, true);
		MyElement e5 = new MyElement(5, 5, false);
		MyElement e6 = new MyElement(1, 1, false);
		
		LinkedList<MyElement> list = new LinkedList<MyElement>();
		list.add(e1);
		list.add(e2);
		list.add(e3);
		list.add(e4);
		list.add(e5);
		list.add(e6);
		
		List<MyElement> newList = combineElements(list);
//		erwartete ausgabe:
//		1. wird nicht kombiniert, ein element mit eintrag 1
//		2. wird mit 3 kombiniert, ein element mit eintrag 2 das aus 2 und 3 kombiniert wurde sollte entstehen
//		3. sollte dahe übersprungen werden
//		4. mit 5, diesmal aber als 5 kombiniert mit 4
//		5. überspringen
//		6. normal eintragen
		for(MyElement e : newList){
			System.out.println("ID: " + e.getID());
			System.out.println("Eintrag: " + e.getEintrag());
			System.out.println("Combined? " + e.getStatus());
			System.out.println();
		}
		
		//TADA :D
		
	}

}

Ausgabe
Code:
ID: 1
Eintrag: 1
Combined? Uncombined Element

ID: 2
Eintrag: 2
Combined? ID 2 combined with ID 3

ID: 5
Eintrag: 10
Combined? ID 5 combined with ID 4

ID: 6
Eintrag: 1
Combined? Uncombined Element

wenn das nicht hilft und total daneben ist, beschreib mir nochmal was du genau vor hast bzw was du da genau benutzt


Edit: wo sich mir auch nocht die frage stellt, was ist, wenn eintrag 1 und 2 ein flag haben, gibts dann ne 3er kopplung oder kann sowas nicht vorkommen?
 
Zuletzt bearbeitet: