Intervall-Implementierung mit selbstgebauter LinkedList

[Riedelinho]

Hallo

Ich hab folgendes Problem:

Zu realisieren sind Mengen auf Intervallen. Ein einfaches Intervall ist eine Menge von rationalen Zahlen die sowohl >= einer Untergrenze a sind und <= einer Obergrenze b. Die Untergrenze muss IMMER <= Obergrenze sein.

Ein Intervall I ist hierbei eine Menge von einfachen Intervallen. Eine eindeutige Darstellung erhalten wir, wenn die einzelnen einfachen Intervalle überlappungsfrei sind.

Ein Wert x ist in einem Intervall, wenn er in einem einfachen Intervall ist.

Ebenso kann man auf Intervalle verschiedene Operationen durchführen.

• Vereinigung (x|x € I v x € I')
• Schnittmenge (x|x € I ^ x € I')
• Differenz (x|x € I ^ x €/I#)

Vereinigung sowie Schnittmenge sind wieder Intervalle.

Jetzt zu meinem eigentlichen Problem:

Ein Interface wurde vorgegeben.

public interface Interval extends Iterable<Interval.SimpleInterval> {

	class SimpleInterval {
		BigDecimal from;
		BigDecimal to;
	}
	
	boolean contains(BigDecimal number);
	boolean isEmpty();
	
	Interval union(BigDecimal from, BigDecimal to);
	Interval union(Interval ival);	
	Interval intersect(Interval ival);
	Interval difference(Interval ival);

	Iterator<SimpleInterval> iterator();
}

Wir sollen nun eine klasse

LinkedIntervall

realisieren die diese Schnittstelle

Interval

implementiert. Als interne Datenstruktur sollen wir eine einfach verkettete Liste verwenden, in der jedes Listenelement ein einfaches Intervall repräsentiert. Allerdings sollen wir die LinkedList nicht aus der Java Bibliothek

java.util.*

verwenden, sondern die Knotenelemente selbst implementieren. Soweit so gut. Das hab ich soweit hoffentlich hingekriegt.

public class LinkedInterval implements Interval{
	Node first;
	Node last;
	
	private class Node {
		public Node(Object o) {
			
		}
		
		Node next;
		SimpleInterval si;
		
	}
	
	public void add(Object o){
		Node n = new Node(o);
		first.next = n;
		first = n;
	}

Jetz sollen ausserdem die Methoden

union()

für vereinigung und

intersect()

für Schnittmenge realisiert werden.

Allerdings fehlt mir hierfür komplett der ansatz. Eine

toString

Methode soll auch noch implementiert werden.

Danke schonmal im Vorraus für eure Hilfe.

LG

 

[XHelp]

Das gehört wohl eher in die Hausaufgaben!

Hast du deine verkettete Liste mal ausprobiert? Sieht nicht funktionsfähig aus. Du musst ja die Elemente immer ans Ende anfügen und dazu musst du erstmal bis zum Ende durchlaufen. Dann kannst du auch ggf "last" sparen, denn der letzte Knoten ist ein Knoten ohne Nachfolger (somit auch als solcher erkennbar)

Ansatz zur Vereinigung:
Gegeben:
- Menge von Intervallen
- neuer Intervall, der dazukommt [a,b]

Mögliche Fälle:
a und b sind nicht im gegebenen Intervall: also kommt [a,b] als neues Intervall hinzu
a ist im Intervall, b nicht: Das Intervall, wo sich a befindet wird bis auf "b" nach rechts ausgedehnt
a ist nicht im Intervall, b ist im Intervall: Das Intervall, wo sich b befindet wird bis auf "a" nach links ausgedehnt
a und b sind im Intervall: brauchst du nichts tun.

Nach ähnlichem Schema lässt sich auch die Schnittmenge abarbeiten.

Ansatz zu toString: du musst alle Teilintervalle durchgehen und "von"+"bis" ausgeben

 

[Riedelinho]

Vielleicht kanns ja nen Mod verschieben

also ich hab den Code mal bissl verändert, nach bissl googlen und so
sieht folgendermaßen aus:

public class LinkedInterval implements Interval{
	
	//Knoten erzeugen
	private class Node {
		public Node(Object o) {
		}
		//der Zeiger zeigt auf den naechsten Knoten
		Node next;
		//Die Daten des Knotens (einfaches Interval)
		SimpleInterval si;
		
	}
	
	//Kopf und Ende der Liste instanziieren um Bezugsadresse im Speicher zu haben
	Node first = new Node("first");
	Node last = new Node("last");
	
	//Konstruktor erstellt eine Liste, deren Kopf auf das Ende zeigt und das Ende
	//auf null
	public LinkedInterval() {
		first.next = last;
		last.next = null;
	}
	
	//Neues Objekt in die Kette einfuegen
	public void add(Object o){
		Node n = new Node(o);
		last.next = null;
		last = n;
	}
	
	public void print(){
		Node act = first;
		
		while (act != null){
			System.out.println(act.si);
			act = act.next;
		}
	}

Deine Tipps, hab ich schon soweit, mit einigen Testfällen aufgeschrieben und notiert. Die ganzen Überlegungen hab ichsoweit auch angestellt, mein Problem ist es eher, den KRam in Programmcode umzusetzen.

Hier mal meine union Methode

public Interval union(BigDecimal from, BigDecimal to) {
		
		//Wenn Liste leer ist
		if (first.next == null) {
			SimpleInterval si = new SimpleInterval();
			si.from = from;
			si.to = to;
			add(si);
		}
		return ;
	}

Was muss ich denn hier zurückgeben? Oder hab ich einen falschen Denkansatz?
Ist noch nicht die ganze union methode, nur der fall,dass znächst einmal die Liste leer ist.

 

[XHelp]

Wie gesagt, du musst die Elemete ans Ende anfügen. Das was du hast ist keine Liste, sondern nur 2 Elemente, wobei du immer das letzte überschreibst. Was du brauchst ist sowas wie:

public void add(Object o){
  if (first==null) {
    first = new Node(o);
  } else {
    Node current = first;
    while (current.next!=null) {
      current = current.next;
    }
    current.next = new Node(o);
  }
}

habe den Code allerdings nicht ausprobiert.

Bei den Mengenoperationen musst du eben das Resultat zurückgeben. D.h. deine Ursprüngliche Menge bleibt unverändert.

 

[Riedelinho]

okay das funzt alles soweit
hier mal der code

public Interval union(BigDecimal from, BigDecimal to) {
		
		//Wenn Liste leer ist
		if (first.next.next == null) {
			SimpleInterval si = new SimpleInterval();
			si.from = from;
			si.to = to;
			add(si);
		}
		return intervall;
	}

public void add(Object o){
		if (first == null){
			first = new Node(o);
		} else {
			Node current = first;
			while (current.next != null) {
				current = current.next;
			}
			current.next = new Node(o);
		}
	}

public void print(){
		Node act = first;
		
		while (act != null){
			System.out.println("[ " + act.test + "   "+ act.test + " ]");
			act = act.next;
		}
	}

Mein Problem ist jetz was muss ich bei act.test hinschreiben, damit er mir ober- bzw untergrenze ausgibt? also from und to von simpleintervall?
bisher gibt er mir nur referenzen aus

der aufruf sieht folgendermaßen aus...

public static void main(String[] args) {
		
		intervall.union(BigDecimal.valueOf(3.1), BigDecimal.valueOf(5.4));
		intervall.print();

	}

 

[Riedelinho]

ok hab meine intervall variable global deklariert und ind er main einfach einneues objekt erzeugt und kanndannbeim simpleintervall auf from bzw to zugreifen...

allerdings fliegt bei mir jetz eine nullpointerexception

public class LinkedInterval implements Interval{
	private static LinkedInterval intervall;
	//Knoten erzeugen
	private class Node {
		public Node(SimpleInterval o) {
			test = o;
		}
		//der Zeiger zeigt auf den naechsten Knoten
		public Node next;
		//Die Daten des Knotens (einfaches Interval)
		//SimpleInterval si;
		public SimpleInterval test;
	}
	
	//Kopf und Ende der Liste instanziieren um Bezugsadresse im Speicher zu haben
	public Node first = new Node(null);
	public Node last = new Node(null);
	
	//Konstruktor erstellt eine Liste, deren Kopf auf das Ende zeigt und das Ende
	//auf null
	public LinkedInterval() {
		first.next = last;
		last.next = null;
	}
	
	//Neues Objekt in die Kette einfuegen
	public void add(SimpleInterval o){
		if (first == null){
			first = new Node(o);
		} else {
			Node current = first;
			while (current.next != null) {
				current = current.next;
			}
			current.next = new Node(o);
		}
	}
	
	public void print(){
		Node act = first;
		
		while (act != null){
			System.out.println("[ " + act.test.from + "   " + act.test.to + " ]");
			act = act.next;
		}
	}
		
	@Override
	public boolean contains(BigDecimal number) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public Interval difference(Interval ival) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Interval intersect(Interval ival) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public Iterator<SimpleInterval> iterator() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Interval union(BigDecimal from, BigDecimal to) {
		
		//Wenn Liste leer ist
		if (first.next.next == null) {
			SimpleInterval si = new SimpleInterval();
			si.from = from;
			si.to = to;
			add(si);
		}
		return intervall;
	}
		
	@Override
	public Interval union(Interval ival) {
		
		return null;
	}

	public static LinkedInterval getIntervall() {
		return intervall;
	}

	public static void main(String[] args) {
		intervall = new LinkedInterval();
		intervall.union(BigDecimal.valueOf(3.1), BigDecimal.valueOf(5.4));
		intervall.print();

	}
}

Exception in thread "main" java.lang.NullPointerException
	at LinkedInterval.print(LinkedInterval.java:47)
	at LinkedInterval.main(LinkedInterval.java:108)

 

[Riedelinho]

okay hinzufügen von einem intervall funktioniert jetz soweit, aber wenn ich jetz neue hinzufügen will muss ich ja die liste durchlaufen, dafür haben wir ja die iterator klasse im code
allerdings sollen wir denauch selber realisieren und NICHT den aus der bib nehmen...

jmd ne idee wie ich da am besten vorgehe?

 

[XHelp]

Zunächst, solange du nicht all zu weit bist: vllt lohnt es sich eine verkettete Liste bzw. Node-Klasse von Object auf Intervall umstellen. Dann brauchst du auch nicht casten beim auslesen.
Dann solltest du vllt lieber mit getter und setter arbeiten, anstatt alles auf public zu setzen
Das was du selber umsetzen musstest war die verkettete Liste und das hast du auch mit der Klasse LinkedIntervall gemacht.

public interface Interval extends Iterable<Interval.SimpleInterval>

wurde vorgegeben, das heißt du kannst es auch so wie es ist verwenden.
Wie du durch die Liste durchgehst sieht ungefähr so aus:

for ( Interval.SimpleInterval singleInterval : objectOfLinkedIntervall ) {
  System.out.println(singleInterval);
}