Dynamische Bindung mit Interfaces und LinkedList

[Henrik79]

Hallo,

ich habe da eine Aufgabe (Ich erwarte keine Lösung nur einen Tipp in die richtige Richtung).

Also, ich habe eine LinkedList programmiert (Wir dürfen keine Generics verwenden), diese besteht aus ListNodes der Klassen IntegerListNode und StringListNode. ListNode ist dabei eine abstrakte Klasse und Integer- bzw. StringListNode deren Ausprägung.

Dabei verwalte der ListNode ein Element der Klasse Object und einen Verweis auf den nächsten ListNode. (Es handelt sich um eine einfach verkettete Liste).

Object wurde spezialisiert um Vergleiche zu ermöglichen und Daten des Types Integer bzw. String aufzunehmen.

Die Aufgabe ist nun die Folgende.

Ich soll anhand der Interfaces Queue und Stack ein Programm schreiben welches wahlweisen Zugriff auf Queue und Stack erlaubt, als auch die Option bietet alles mit einem Array zu verwalten (Im Falle von Queue als Ring Buffer).

Das heisst der User hat die Möglichkeit zu sagen, jetzt soll ein Wert in Queue, jetzt einer in Stack, jetzt mal in die Liste, jetzt mal in das Array.

Meine eigentliche Frage ist, wie würde ich das optimalerweise gestalten, dass coden ist kein Problem.

Brauche ich mehr als ein MyQueue oder MyStack, welches jeweils die passenden interfaces implementiert?

Kann ich irgendwie Methoden in der Superclass überschrieben obwohl sich der angegebene Rückgabetyp im Interface unterscheidet? (z.B. einmal soll bei empty() Stack zurückgegeben werden, aber empty() in LinkedList gibt LinkedList zurück.

Ein guter Tipp wird dankbar entgegen genommen.

Viele Grüße

Henrik79

 

[SlaterB]

für mich ist das Problem nicht klar, anfangs scheint es um Unterscheidung des Inhalts, String oder Integer zu gehen,
später dann auf einmal ob LinkedList oder MyStack oder sonstwas, haben die gemeinsame Node-Klassen oder wo genau gibts Probleme?

Interface wird noch genannt, gibt es ein gemeinsames (noch nicht genanntes) für den Node?, für die Gesamt-Collections (Stack, Queue, LinkedList) an sich oder worum genau gehts?
empty() liefert entweder per Generics das richtige zurück, was ausfällt, oder sonst die gemeinsame Basisklasse, z.B. SQL (Abkürzung Stack, Queue, LinkedList ),
der Aufrufer müsste dann jedesmal casten,
nicht gut? dann gibt es eben keine Gemeinsamkeit, wenn man mit einer LinkedList arbeiten will hilft einem überhaupt kein Interface welches nicht genau mit LinkedList zu tun hat,
jedenfalls nicht in gewissen Situationen wie beim Rückgabewert von empty()

 

[Henrik79]

Ok ich habe mich wohl ein wenig unklar ausgedrückt. Sorry.

Also vorhanden ist eine funktionierende lineare LinkedList (selbst geproggt) mit den üblichen Operationen. (addFirst, addLast, removeFirst, getFirst, GetLast, getIndex, empty, isEmpty usw.)

public class LinkedList  {
	
	protected ListNode head;
	
	private int elementType = -1;
	
	public boolean addFirst(Object element) {
		int actualElement = -1;
		
		if (this.elementType == -1) {
			if (element.getiValue() == null) {
				this.elementType = 1;
				this.head = new StringListNode(element);
			} else {
				this.elementType = 0;
				this.head = new IntListNode(element);
			}
		}
		
		if(element.getiValue() != null) {
			actualElement = 0;
		} else {
			actualElement = 1;
		} 
		
		if (actualElement == this.elementType) {
		
			 if (this.elementType == 0){
				ListNode nHead = new IntListNode(element);
				nHead.setNext(this.head);
				this.head = null;
				this.head = nHead;
			} else if (this.elementType == 1){
				ListNode nHead = new StringListNode(element);
				nHead.setNext(this.head);
				this.head = null;
				this.head = nHead;
			}
		}
		
		return contains(element); //later it has to be redirected to contains!
	}
	public boolean addLast(Object element) {
		int actualElement = -1;
		
		if (this.elementType == -1) {
			if (element.getiValue() == null) {
				this.elementType = 1;
				this.head = new StringListNode(element);
			} else {
				this.elementType = 0;
				this.head = new IntListNode(element);
			}
			
		}
		
		if(element.getiValue() != null) {
			actualElement = 0;
		} else {
			actualElement = 1;
		} 
		if(actualElement == this.elementType) {
			 if (this.elementType == 0) {
				ListNode nTail = new IntListNode(element);
				returnLastNode(this.head).setNext(nTail);
			} else if (this.elementType == 1) {
				ListNode nTail = new StringListNode(element);
				returnLastNode(this.head).setNext(nTail);
			}
		}
		return contains(element); //has to be redirected to contains!
	}
	
	
	public boolean removeFirst() {
		boolean removed = false;
		if(this.head.getNext() != null) {
			this.head = this.head.getNext();
			removed = true;
		}
		else {
			this.head = null;
			removed = true;
		}
		
		if(this.isEmpty()) {
			this.elementType = -1;
			this.head = null;
		}
		
		return removed;
		
		
			
	}
	
	public Object getFirst() {
		if (this.head != null && this.head.getElement() != null)
			return this.head.getElement();
		else
			return null;
	}
	public Object getLast() {
		
		if(returnLastNode(this.head) != null
				&& returnLastNode(this.head).getElement() != null)
			return returnLastNode(this.head).getElement();
		else 
			return null;
	}
	public boolean isEmpty() {
		boolean isEmpty = false;
		if (this.size() == 0)
			isEmpty = true;
		return isEmpty;
	}
	
	public LinkedList empty() {
		return new LinkedList();
	}
	
	public boolean contains(Object element) {
		boolean contains = false;
		ListNode iterationNode = this.head;
		
		if(this.head != null && iterationNode.getElement().equals(element))
			contains = true;
		else if (this.head != null) {
			while(iterationNode.getNext() != null 
					&& !iterationNode.getElement().equals(element)) {
				iterationNode = iterationNode.getNext();
				if(iterationNode.getElement().equals(element))
					contains = true;
			}
		}
		return contains;
	}
	public boolean clear() {
		if(this.head != null) {
			this.head = null;
			this.elementType = -1;
		}
		return isEmpty();
	}
	
	public int size() {
		int count = 0;
		if (head != null) {
			ListNode first = this.head;
			while (first.getNext() != null) {
				first = first.getNext();
				count++;
			}

		}
		return count;
		
	}
	public LinkedList clone() {
		return this;
	}
	
	public boolean delete(Object element) { // delete genau prüfen
		ListNode start = this.head;
		ListNode end   = returnLastNode(start);
		if(start.getElement().equals(element))
			removeFirst();
		else if (end.getElement().equals(element))
			prevNode(end).setNext(null);
		else{
			while(start != null && !start.getElement().equals(element))
				start = start.getNext();
			if(start != null && start.getElement().equals(element)){
				prevNode(start).setNext(start.getNext());
				start = null;		
			}
		}
		if(this.isEmpty()){
			this.elementType = -1;
			this.head = null;
		}
		
		return contains(element);	
			
		
	}
	public String toString() {
		String concat = "";
		ListNode iterationNode = this.head;
		for(int i = 0 ; i < this.size() ; i++) { // evt. size()-1
			if(this.elementType == 0)
				concat += iterationNode.getElement().getiValue() + ", ";
			else if (this.elementType == 1)
				concat += iterationNode.getElement().getsValue() + ", ";
			iterationNode = iterationNode.getNext();
				
		}
		return concat;
	}

	public Object get(int index) {
		Object object = getFirst();
		int i = 0;
		if (index == 0) {
			return object;
		} else if (index >= this.size()) {
			object = getLast();
		} else {
			ListNode node = this.head;
			while (i < index) {
				if (node.getNext() != null) {
					node = node.getNext();
				}
				object = node.getElement();
				i++;
			}
		}
		return object;
	}
	
	public Object[] toArray() {
		ListNode first = this.head;
		Object[] listArray = new Object[this.size()];
		for(int i = 0; i < this.size(); i++){ //evt. lauf bis size-1
			listArray[i] = first.getElement();
			first = first.getNext();
		}
		return listArray;
	}

	public LinkedList addAll(LinkedList list, LinkedList otherList){
		LinkedList concat = new LinkedList();
		concat = list.cloneDeep();
		ListNode oFirst = otherList.head;
		for(int i = 0; i < otherList.size(); i++) {
			concat.addLast(oFirst.getElement());
			oFirst = oFirst.getNext();
		}
		return concat;
	}
	public LinkedList cloneDeep() {
		LinkedList deepCopy = new LinkedList();
		ListNode first = this.head;

		for (int i = 0; i < this.size(); i++) { // evt. lauf bis size -1
			deepCopy.addLast(first.getElement());
				first = first.getNext();
		}

		return deepCopy;
	}
	public boolean add(int index, Object element){
		int actualElementType = -1;
		if(this.elementType == -1){
			if(element.getiValue() != null){
				this.elementType = 0;
				this.head = new IntListNode(element);
			} else {
				this.elementType = 1;
				this.head = new StringListNode(element);
			}
		} else {
			if (element.getiValue() != null) {
				actualElementType = 0;		
			}else {
				actualElementType = 1;
			}		
		}
		if(this.elementType == actualElementType) {
			if (index == 0) {
				addFirst(element);
			} else if (index >= this.size()) {
				addLast(element);
			} else {
				ListNode node = this.head;
				ListNode temp;
				int i = 0;
				if(this.elementType == 0)
					temp = new IntListNode(element);
				else
					temp = new StringListNode(element);
				while (i<index-1) {
					node = node.getNext();
					i++;
				}
				temp.setNext(node.getNext());
				node.setNext(temp);
			}
		}
		return contains(element);
	}
	
  /**
   * Private Helper Methods
   */
	private ListNode returnLastNode(ListNode node) {
		if (node.getNext()==null) {
			return node;
		} else {
			return returnLastNode(node.getNext());
		}
	}
	private ListNode prevNode(ListNode n) {
		ListNode start = this.head;
		while(!start.getNext().equals(n))
			start = start.getNext();
		return start;
	}

}

Diese operiert auf folgenden ListNodes

public abstract class ListNode {
	
	
	/**Personal I'm not sure if i should externalize this fields****/

	protected ListNode next    = null; // reference to the next listnode
	protected Object   element = null; // actual node element
	
	/**
	 * @return the element
	 */
	public Object getElement() {
		return element;
	}


	/**
	 * @param element the element to set
	 */
	public void setElement(Object element) {
		this.element = element;
	}


	abstract boolean isLessThan(ListNode n) ;
		
	
	abstract boolean isEqualTo(ListNode n) ;
			
	public  ListNode getNext() {
		return this.next;
	}
	public void setNext(ListNode next){
		this.next = next;
	}
}

Ich poste hier nun nicht den Code für IntListNode oder StringListNode, sondern nur das zugrunde liegende Object

public class Object {

	private Integer iValue = null ;
	private String  sValue = null ;
	
	public Object () {	
	}
	public Object (Integer iValue) {
		super();
		this.iValue = iValue;
	}
	public Object (String sValue) {
		super();
		this.sValue = sValue;
	}
	/**
	 * @return the iValue
	 */
	public Integer getiValue() {
		return iValue;
	}
	/**
	 * @param iValue the iValue to set 
	 */
	public void setiValue(Integer iValue) {
		this.iValue = iValue;
	}
	/**
	 * @return the sValue
	 */
	public String getsValue() {
		return sValue;
	}
	/**
	 * @param sValue the sValue to set
	 */
	public void setsValue(String sValue) {
		this.sValue = sValue;
	}
	
	public int hashCode() {
		int result = 0;
		
		if(iValue == null){
			final int prime = 31;
			result = 1;
			result = prime * result + ((sValue == null) ? 0 : 
				sValue.hashCode());
		} else {
			final int prime = 31;
			result = 1;
			result = prime * result +((iValue == null) ? 0 : 
				iValue.hashCode());
		}
		
		return result;
	}
    public boolean equals (Object obj) {
		boolean result = false;
		if (obj.getClass().equals(this.getClass())) {
			Object eq = (Object) obj;
			if (this.hashCode() == eq.hashCode()) {
				result = true;
			}
		}
		return result;
	}
	@Override public String toString(){
		if(iValue != null)
			return "[OBJECT-IVAL]: "+iValue;
		else
			return "[OBJECT-SVAL]: "+sValue;

	}
}

Das alles funktioniert recht Prima (Über Tipps freue ich mich jedoch)

Nun ist es so, dass ich diese List verwenden soll um ein Queue und einen Stack zu verwalten. Die benötigten Methoden befinden sich in gleichnamigen Interfaces.

Dazu benötige ich ja erstmal instantiierbare Klassen, welche die Methoden aus Stack bzw. Queue implementieren.

Nun soll das ganze jedoch so erweitert werden, dass die Operationen von Stack bzw. Queue nicht nur auf der Liste operieren, sondern auch auf einem entsprechenden Array (Object Array nehme ich an). Im Falle von Queue soll das Array als Ring Buffer fungieren. Stack und Queue sollen im Array Fall einen automatischen Resize (Verdoppelung und im Falle des Queue-Ring Buffers reorganisation) bei erreichen eines definierten Limits vornehmen (einmalig). Aber auch bei der Liste soll eine definierte Datenbeschränkung vorgenommen werden.

Mir geht es nun eigentlich nur um das möglich Design, anhand dynamischer Bindung (Abstrakten Klassen und Interfaces) und bestmöglicher Struktur (Effizienz & Logik).

Die Frage ist nun folgende:

a) Ich habe eine funktionierende LinkedList Klasse s.o. und z.B. ein Interface Stack mit den Methoden (boolean push(Object element), Object pop(), Object top() ... usw.)

Jetzt muss ich ja eine Klasse schreiben, welche das Interface implementiert und gegebenenfalls von LinkedList erbt (halte ich nicht für den richtigen Ansatz). Diese Klasse soll aber die gleichen Funktionalitäten (z.B. so das der User sagen kann, jetzt hole ich das Datum aus der LinkedList, jetzt ein anderes zuvor gespeichertes Datum aus dem Array usw.) für einen Stack mit der Datenstruktur LinkedList bzw. je nach Usereingabe für eine Datenstruktur Stack basierend auf einem Array bieten.

Das ganze soll also optimal polymorph sein.

Hierbei brauche ein ein wenig Interfaceanwendung und Vererbungshilfe. Die Grundbegriffe sind schon sehr klar.

MFG

Henrik79

 

[SlaterB]

zur Array-Implementierung hast du noch gar nichts gepostet, da schon über Interface nachzudenken..

wenn ich das jetzt verstanden habe, willst du am Ende eine Monsterklasse, die gleichzeitig sowohl A eine Queue ist, B ein Stack, C das ganze mit LinkedList implementiert und D auch noch per Array,
vielleicht ist A nur mit C verbunden statt mit D und B nur mit dem anderen oder andersrum,
dennoch wird das ein unendliches Monster, an deren Erschaffung ich eigentlich nicht beteiligt sein will,

bevor ich überhaupt überlege weiterzudenken: ich sehe doch alles falsch, richtig?

 

[Henrik79]

Also, ob es nur eine Monsterklasse sein soll, da bin ich mir eben nicht sicher :-(
Ich gehe mal eigentlich noch davon aus.

Ich denke eher es sollen folgende Codestücke werden:

public class ListStack implements Stack {

private LinkedList list = new LinkedList();

/**
Interfacecode der kram mit der List vornimmt
*/

}

Nun zum Queue

public class ListQueue implements Queue {

private LinkedList list = new LinkedList();

/**
Interfacecode aus <<Interface>> Queue der kram mit der List vornimmt
*/

}

nun zur Arrayimp.

public class ArrayStack implements Stack {

private Object[] oArray;

//Konstruktoren und Kram

/**
Interfacecode der kram mit dem vornimmt
*/

}

Das natürlich auch mir Queue

public class ArrayQueue implements Queue {

private Object[] oArray;

//Konstruktoren und Kram

/**
Interfacecode der kram mit der List vornimmt
*/

}

Das ganze würde in diesem Fall sagen wir durch irgendeine GUI oder Konsoleneingabe mit entspr. Referenzzuweisung zur entspr. Klasse verwaltet.

Ich würde nur gerne wissen ob das durch diverse Vererbungsstrukturen und Interfaceimplementierungen geschickter geht?

Achja im oben geposteten Fall, wären dann Implementierungen folgender Art z.B. vorzunehmen.

public class Test{

public static void main(String[]arguments) {
      
     Queue q1 = new ListQueue();
     Queue q2 = new ArrayQueue();
     Stack  s1 = new ListStack();
    
      //Und so weiter bzw. ich kann ja passend zuweisen. Aber geht es auch besser?

}

}

Danke im voraus.

Henrik79

 

[SlaterB]

du könntest zunächst eine Klasse ArrayList implementieren, und die wie LinkedList mehrfach verwenden,
das spart etwas doppelte Implementation wie Vergrößerung des Arrays bei Überlauf usw.,

ob Vererbung oder Aggregation, also die Liste intern als Attribut, das ist immer und überall die Frage,
probiere die Varianten aus,
genauso bei einer evtuellen Frage, ob man für Stack auf LinkedList X oder Array/ArrayList Y gemeinsamen Stack-Code hat, der in einer Klasse gehört, nur intern an wenigen Stellen auf X oder Y verweist,
programmiere doch erstmal laufende Varianten, eine oder gar zwei, dann kann man immer noch sehen ob es schlauer ist etwas zusammenzulegen,

wenn du ArrayList statt Array hast, mit gleichen Methoden wie LinkedList, also add, remove usw., dann bietet sich natürlich an,
ein gemeinsames Interface List zu definieren (ganz wie in der Collections-API) und den einzelnen Klassen Stack/ Queue nur ein List-Objekt zu übergeben, ob Linked- oder Array-

 

[Henrik79]

Also ich stelle mir das nun wie folgt vor.

Ich habe eine Klasse ListStack, der auf LinkedList operiert, eine Klasse ListQueue die auf List operiert, eine Klasse ArrayStack der auf dem ArrayList (noch zu implementieren mit den selben Funktionen wie LinkedList) operiert, eine Klasse ArrayQueue die auf dem Array operiert und das ganze per Referenzzeiger als Ringpuffer behandelt.

ListStack, ArrayStack implementieren das Interface Stack, ListQueue und ArrayQueue implementieren das Interface Queue.

Im Hauptprogramm kann ich dann dem Interface Stack & Queue jeweils die passende Klasse zuweisen um nach belieben wechseln zu können.

Wie klingt das?

Grüße

Henrik79

 

[SlaterB]

klingt gut