Priority-Queue

[TChill]

Ich bins nochmal
wollte euch fragen, da ich circa ne stunde auf den code schaue und ihn nicht wirklich nachvollziehen kann. Ich hab 2 Interfaces und 2 Klassen

public interface IF_PrioDetermination {
	public int getPriority(int age, int prio);
}

die Klasse

public class CL_PrioObject {
	IF_PrioDetermination prioDet;
	private int age;
	private int prio;

	public CL_PrioObject(IF_PrioDetermination prioDet, int prio) {
		this.prioDet = prioDet;
		this.prio = prio;
		this.age = 0;
	}

	public int getPriority() {
		return prioDet.getPriority(age, prio);
	}

	public int getPrio() {
		return prio;

	}

	public int getAge() {
		return age;
	}
public void incrementAge(){
	this.age++;
}

mein anderes Interface

public interface IF_PriorityQueue {

	public CL_PrioObject dequeue();

	public void enqueue(CL_PrioObject neu);
}

bis hierhin kann ich noch alles nachvollziehen und bin auch selbst soweit gekommen
doch bei der folgenden Klasse versteh ich nur Bahnhof und hab keine ahnung was da vor sich geht ich hoffe jemand nimmt sich vllt doch die Zeit um mir das ein bisschen verständlich zu machen.
Die Aufgabe: Erstellen Sie eine Implementierung der Prioritätswarteschlange (ArrayList modifizieren)
a. Bei Dequeue: Zu jedem verbleibenden Objekt muss die Methode incrementAge() aufgerufen werden!

package priority_Queue;

import java.util.ArrayList;

public class CL_PriorityQueue implements IF_PriorityQueue {

	private ArrayList<CL_PrioObject> queue = new ArrayList<CL_PrioObject>(); //eine Arraylist wird erstellt, aber wieso ?

	@Override
	public CL_PrioObject dequeue() {     // seh ich das richtig wenn sich kein Objekt hier mehr                          /                                                       //befindet passiert gar nix und nichts wird returned ?
		if (queue.size() == 0) {
			return null;
		}
		CL_PrioObject tmp = queue.get(0);     //das ist mein Drehpunkt an dem ich gar nichts mehr wirklich verstehe wird hier ein Objekt names tmp erstellt ? Weil tmp kommt hier zum ersten mal vor und was wird den hier von dem queue rausgeholt ?
		for (CL_PrioObject i : queue) {                   //was soll diese Bezeichnung "i:queue" ?
			if (tmp.getPriority() < i.getPriority()) { // allgemein der ganze block ist so   /   /     u                                             //unverständlich für mich ich könnte tausende fragen hierzustellen 
				tmp = i;
			}
		}
		queue.remove(tmp);  //was wird hier entfernt ?
		for (CL_PrioObject i : queue) {
			i.incrementAge();
		}
		return tmp;
	}

	@Override
	public void enqueue(CL_PrioObject neu) {
		if (!queue.contains(neu)) {
			queue.add(neu);
		}

so vielen dank an diejenigen die sich die Zeit genommen haben, ich weiss es ist ein riesen Code, doch ich komme alleine hier null weiter ich hätte noch zig fragen stellen können ich hoffe jemand kann mir das einigermassen verständlich näher bringen, denn ich bin echt am verzweifeln grad...
VIELEN DANK !!!

 

[Adelhorst]

Hallo.
Erstmal liefert 'dequeue' null zurück, wenn das Array leer ist.
Danach wird im Code die Hauptaufgabe von 'dequeue' ausgeführt:
Das besteht darin, dass im Array das Objekt mit der höchsten Priorität gesucht wird.
Dazu wird in tmp einfach ein Verweis auf das erste Objekt im Array gesetzt, und dann werden alle Objekte im Array geprüft, ob deren Priorität höher ist als in tmp.
Tritt dieser Fall ein, dann erhält tmp den Verweis auf das Objekt mit der höheren Priorität, und die Suche geht weiter.
Am Ende steht in tmp ein Verweis auf das Objekt mit der höchsten vorhandenen Priorität.
Dieses Objekt wird mit remove aus dem Array entfernt, aber da tmp immer noch auf dieses Objekt zeigt, geht dieses Objekt durch den GC noch nicht verloren.
Bei den restlichen Objekte im Array wird das 'Alter/Age' nachgezogen, sprich deren age wird um 1 erhöht.
Am Ende der Methode wird dann tmp zurück gegeben.

 

[TChill]

okay hat mir ein bisschen weitergeholfen
aber was passiert den hier genau ?

PrioObject tmp = queue.get(0); // wird hier das objekt erzeugt den eigentlich erzeugt man das Objekt // //doch so  PrioObject tmp = new PrioObject();
		for (PrioObject i : queue) { // und was bedeutet diese vorschleife mit dem PrioObject i : //queue , normalerweise muss ich doch for (i = 0; i<PrioObject; i++) 
// was bedeutet  ":" hier ?

so danke schonmal gibts vllt hier ein youtube video oder iwo wo ich bisschen nachgucken kann damit das verständlicher wird, denn das ist ein riesen sprung für mich von unserer letzten Aufgabe ..

 

[stg]

zu 1. Da wird kein neues Objekt erzeugt, sondern nur eins aus dem Queue geholt.

zu 2. Das ist eine forEach-Schleife, die über den Iterator von queue alle Elemente von queue abarbeitet. Übersetzt: Für alle alle PrioObjecte in queue mache ...

 

[TChill]

okay danke nur damit ich das richtig verstehe ?

for (PrioObject i : queue)

steht das "i", für das array ? hätte ich auch nen anderen Buchstaben nehmen können ?
und der Doppelpunkt heisst das er für alle objekte in der Queue, blabla machen soll ...

sry steh grad echt auf dem schlauch ...
tausend dank euch :toll:

 

[fLooojava]

Das ist eine enhanced for-Schleife, die kannst du aber auch als ganz normale for-Schleife anschreiben, erspart dir so nur Code.

Guck dir mal folgenden Link an, da sieht man es recht gut :

enhanced for loops

lg flo

 

[stg]

Im darunter folgenden Code-Block kannst du nun über

i

das jeweilige

PrioObject

ansprechen.

In deinem Code

for (CL_PrioObject i : queue) {
       i.incrementAge();
}

Wird nacheinander auf jedes

CL_PrioObject

genau einmal zugegriffen. In jedem Schleifen-Durchlauf kannst du über die Variable

i

auf das aktuelle

CL_PrioObject

zugreifen. Es wird also nacheinander bei jedem

CL_PrioObject

die Funktion

incrementAge()

aufgerufen.

 

[TChill]

danke flo, genau das hat mir gefehlt, weil der Code ist von einem Kumpel der 3 Jahre schon programmiert, konnte es nicht nachvollziehen...
wenn ich den code umschreiben will, hab ich mir das so gedacht ...

for (int i = 0; i<queue.size();i++){
			//hier fehlt ja das PrioObject ... wie müsste ich das dann da noch reinschreiben ?
		
			if (tmp.getPriority() < queue[i].getPriority()) {
				tmp = queue[i];
			}
		}

Danke im vorraus
gruß tchill

EDIT:

	CL_PrioObject tmp = queue.get(0);
	for (int i = 0;i<queue.size();i++){
		if(tmp.getPriority()<queue.get(i).getPriority()){
			tmp = queue.get(i);
		}
	}
	queue.remove(tmp);
		for (int i = 0; i<queue.size();i++){
			queue.get(i).incrementAge();
		}
		return tmp;
	}

wäre dass so richtig ?

 

[fLooojava]

Ich würde sagen ja, kriegst du denn das richtige returned?

 

[TChill]

ja hat geklappt, hab ne vorgegebene testklasse und dann kam alles grün raus
Vielen Dank euch :toll::toll::toll: