Push_front push_back

[Ultramann]

Hallo,

ich sitze an einem etwas größeren Problem: Ich möchte auch gar nicht großartig um den heißen Brei reden:
Ich muss eine Präsentation morgen halten zu einem Programm von dem ich so gut wie keine Ahnung habe. Ich weiß ungefähr was dahintersteckt, mehr aber auch nicht. Ich hoffe, dass das nicht ganz zu dreist rüberkommt...

Die Aufgabenstellung war:

Modifizieren Sie Ihre Implementierung aus Aufgabe 1 derart, dass bei der
push_front Methode die gleiche Reallokationsstrategie wie bei push_back
angewandt wird. Testen Sie, ob nach mehreren push_front Aufrufen der
Methodenaufruf get(0) das letzte mit push_front eingefügte Element
zurückliefert.


Die "Lösung" hatte er schonmal veröffentlicht:

class OutOfBoundsException extends Exception{}


interface SimpleCollection <T>{
	int size();
	void push_back(T arg);
	void push_front (T arg);
	T get(int i) throws OutOfBoundsException;
	void set(int i, T arg) throws OutOfBoundsException;
	void delete(int i) throws OutOfBoundsException ;
}



class MyVector<T> implements SimpleCollection <T>{

	int free_next;
	int increment;
	Object []obj;


	MyVector(int size, int realloc) {
		obj = new Object[size];
		increment = realloc;
		free_next=0;
	}
	MyVector(int size){
		this(size,0);
	}
	MyVector(){
		this(1);
	}

	public void resize(){
		Object []tmp_obj;
		if(increment==0){
			tmp_obj=new Object[obj.length*2];
		}
		else
			tmp_obj=new Object[obj.length+increment];
		obj=tmp_obj;
	}

	public int size(){
		return free_next;
	}

	public void push_front (T arg){
		if(free_next>=obj.length){
			resize();
		}
		Object tmp_obj[] = new Object[obj.length+1];
		for(int i=0;i<obj.length;++i){
			tmp_obj[i+1]=obj[i];
		}
		tmp_obj[0]=arg;
		++free_next;
		obj=tmp_obj;
	}
	public void push_back (T arg){
		if(free_next>=obj.length){
			resize();
		}
		obj[free_next++]=arg;
	}
	public T get(int i) throws OutOfBoundsException{
		if(i<=free_next && i>=0){
			return (T)obj[i];
		}
		else
			throw new OutOfBoundsException();
	}
	public void set(int i, Object arg) throws OutOfBoundsException{
		if(i<=free_next && i>=0){
			obj[i]=arg;
		}
		else
			throw new OutOfBoundsException();
	}
	public void delete(int i) throws OutOfBoundsException {
		if(i<=free_next && i>=0){
			Object tmp_obj[] = new Object[free_next-1];
			for(int j=0;j<i;++j){
				tmp_obj[j]=obj[j];
			}
			for(int k=i+1;k<tmp_obj.length;++k){
				tmp_obj[k]=obj[k];
			}
		}
		else
			throw new OutOfBoundsException();
	}
	public void print() throws OutOfBoundsException{
		try{
		for(int i=0;i<size();++i)
			System.out.print(get(i) + "\t");
		}catch(OutOfBoundsException e){
			System.out.println("zu weit");
		}
	}
}



public class uebung1_1 {

    public static void main(String[] args) {
    	try{
	    	MyVector<Integer> m = new MyVector<Integer>(2,5);
	    	for(int i=0;i<76;++i){
	    		m.push_front(i);
	    	}
	    	System.out.println(m.get(0));
	    	m.print();
    	}
    	catch(OutOfBoundsException e){
    		System.out.println("zu weit");
    	}
    }
}

Also, wichtig für mich ist der Teil mit der push-front und push-back methode. Was passiert da genau mit dem Vektor? Und was hat es mit der Ausgabe an sich?

Ich weiß, dass das vielleicht etwas dreist rüberkommt, ich habe aber nicht vor Programmierer zu werden, muss aber leider 3x eine Übung vorstellen um die CP zu erhalten.

Vielen Dank und Sorry nochmal!

 

[pro2]

Da war ein C++ Programmierer am Werk..

In der pushBack Methode wird einfach nur geschaut, ob der nächste freie Platz größer/gleich ist als das vorhandene Array, wenn ja dann wird die Größe erhöht, wenn nein nicht und anschließend wird das Objekt dem Array hinzugefügt. Außerdem wird die Variable für den nächsten freien Platz inkrementiert danach.

Bei der pushFront Methode passiert nichts groß anderes, außer dass hier natürlich am Anfang eingefügt werden soll. Also werden im "Zwischenspeicher" alle Objekte im Array um eins nach rechts verschoben und dann wird hinzugefügt.

Ja und die Ausgabe.. ka erklärt sich von selbst. Alle Objekte werden durchlaufen bzw. aus der Liste geholt und dann deren toString() Methode ausgegeben.

 

[Ultramann]

Vielen Dank! Das hilft mir weiter.


Wo im Quelltext wird sichergestellt, dass nach den push_front Aufrufen der
Methodenaufruf get(0) das letzte mit push_front eingefügte Element
zurückliefert?

 

[pro2]

Zeile 56 und 58. In 56 wird dein Objekt, was hinzugefügt werden soll, an Stelle 0 des temporären Arrays gesetzt und in 58 wird dein altes Array durch dein neues quasi ersetzt!

 

[Ultramann]

Oh, verdammt. Ich sehe gerade ich habe die Lösung von Aufgabe 1 gepostet.

Ziel war es ja diesselbe Reallokationsstrategie bei push_front wie bei push_back anzuwenden.


Das ist die Lösung zu der Aufgabe2:

class OutOfBoundsException extends Exception{}


interface SimpleCollection <T>{
	int size();
	void push_back(T arg);
	void push_front (T arg);
	T get(int i) throws OutOfBoundsException;
	void set(int i, T arg) throws OutOfBoundsException;
	void delete(int i) throws OutOfBoundsException ;
} 



class MyVector<T> implements SimpleCollection <T>{
	int free_prev;
	int free_next;
	int increment;
	Object []obj;
	
	
	MyVector(int size, int realloc) {
		obj = new Object[size];
		increment = realloc;
		free_next=0;
		free_prev=0;
	}
	MyVector(int size){
		this(size,0);
	}
	MyVector(){
		this(1);
	}
	

	
	public int size(){
		return free_next; 
	}
	
	public void push_front (T arg){
		if(free_prev<0){
			push_front_resize();
		}
		obj[free_prev--]=arg;
	}
	public void push_front_resize(){
		int more;
		int newSize; 
		if(increment == 0)
			more=obj.length;
		else
			more=increment;
		newSize=more+obj.length;
		Object[] tmp = new Object[newSize];
		for(int i = 0;i < obj.length;++i) {
			tmp[i+more] = obj[i];			
		}
		free_next+=more;
		free_prev+=more;
		obj = tmp;	
	}
	public void push_back (T arg){
		if(free_next>=obj.length){
			push_back_resize();
		}
		obj[free_next++]=arg;
	}
	public void push_back_resize(){
		int newSize;
		if(increment == 0)
			newSize=obj.length*2;
		else
			newSize=obj.length+increment;
		Object[] tmp = new Object[newSize];	
		for(int i=0;i<obj.length;++i){
			tmp[i]=obj[i];
		}
		obj=tmp;	
	}
	public T get(int i) throws OutOfBoundsException{
		if(i<=free_next && i>=0){
			return (T)obj[i];
		}
		else
			throw new OutOfBoundsException();
	}		
	public void set(int i, Object arg) throws OutOfBoundsException{
		if(i<=free_next && i>=0){
			obj[i]=arg;
		}
		else
			throw new OutOfBoundsException();
	}
	public void delete(int i) throws OutOfBoundsException {
		if(i<=free_next && i>=0){
			Object tmp_obj[] = new Object[free_next-1];
			for(int j=0;j<i;++j){
				tmp_obj[j]=obj[j];
			}
			for(int k=i+1;k<tmp_obj.length;++k){
				tmp_obj[k]=obj[k];
			}
		}
		else
			throw new OutOfBoundsException();
	}
	public void print() throws OutOfBoundsException{
		try{
		for(int i=0;i<size();++i)
			System.out.print(get(i) + "\t");
		}catch(OutOfBoundsException e){
			System.out.println("zu weit");
		}	
	}
}


 
public class uebung1_2 {
    
    public static void main(String[] args) {
    	try{
	    	MyVector<Integer> m = new MyVector<Integer>(2,5);
	    	for(int i=0;i<2;++i){
	    		m.push_front(i);
	    	}
	    	for(int j=0;j<5;++j){
	    		m.push_back(j);
	    	}	
	    	System.out.println(m.get(0));
	    	m.print();
    	}
    	catch(OutOfBoundsException e){
    		System.out.println("zu weit");
    	}	
    }
}

Bei dem zuvor geposteten Programm verstehe ich die Ausgabe. Bei dem hier nicht. Der Compiler gibt mir folgendes aus:

null
null null null null 1 0 1 2 3 4



Was genau hat es mit dem "null" auf sich?
Und nochmal meine Frage von vorhin:
Wo im Quelltext wird sichergestellt, dass nach den push_front Aufrufen der
Methodenaufruf get(0) das letzte mit push_front eingefügte Element
zurückliefert?

Das wären so die zwei wichtigsten Dinge, die ich wissen müsste.

Vielen Dank im Voraus!!