Collections Stack-Kapazität begrenzen

[Shadoka]

Abend miteinander,

ich habe eine Undo-Funktion implementiert, die mit einem Stack arbeitet.
Jetzt würde ich allerdings gerne die Kapazität des Stacks begrenzen, damit ich den Speicher nicht so sehr belaste. Allerdings scheint es da keine Lösung seitens Java für zu geben, oder?

Falls nicht, eine mögliche Vorgehensweise (auch wenn sie nicht dem Prinzip eines Stacks entspricht) wäre doch, wenn ich die Methoden von Vector nutze, von der Stack erbt.
Wenn einmal die gewünschte Kapazität erreicht ist, macht man bei einem push() einen neuen Stack auf, der alle Elemente des alten Stacks bis oldStack.size()-1 bekommt und das neue Element eben obendrauf.

Für elegantere Lösungen bin auch auch offen

 

[Gast2]

Ich würde dafür nen ring buffer implementieren der automatisch die letzten Einträge überschreibt wenn der puffer voll ist. Sollte sehr einfach zu machen sein.

 

[Shadoka]

Danke für den Tipp, habs mal nachgeschlagen, scheint eine gute Möglichkeit für mein Problem zu sein. Ich werds mal ausprobieren

 

[Shadoka]

Sorry für Doppelpost, aber ich habe die Edit-Funktion nicht gefunden :/

Hab ich das Prinzip des RingBuffers hier richtig verstanden?

public void add(Command c) {
		int length = buffer.length;
		if (buffer[length - 1] != null) {
			for (int i = 1; i < length; i++) {
				buffer[i] = buffer[i - 1];
			}
			buffer[0] = c;
		} else {
			for (int i = 0; i < length; i++) {
				if (buffer[i] != null) {
					buffer[i] = c;
				}
			}
		}
	}

"buffer" ist ein einfaches Array.

 

[Gast2]

Ne, hast du scheinbar nicht verstanden
Ein RingBuffer hat ne feste Größe, man kann also intern nen Array verwenden, das machst du ja bei dir auch schon. Dann hast du noch zwei Variablen. Eine enthält den Index der auf den aktuell "obersten" Eintrag zeigt, als zweites entweder die aktuelle Größe des Puffers, oder einen Zeiger auf den "untersten" Eintrag im Puffer.
Das Hinzufügen ist dann ganz einfach (current ist der Index des obersten Eintrags):
- Füge das Element an Position current+1 in das Array ein
- current um 1 erhöhen
- ggf. aktuelle Größe um 1 erhöhen
Stößt du ans Ende des Arrays musst du natürlich vorne weitermachen wenn neue Daten kommen, wie in nem Ring halt.

EDIT:
So in etwa könntest du das machen:

public class RingStack<T> {
	
	private final Object[] buffer;
	
	private int leader;
	private int size;
	
	public RingStack (int size) {
		this.buffer = new Object[size];
		
		this.size = 0;
		this.leader = 0;
	}
	
	public void push (T t) {
		leader = wrapIndex(leader + 1);
		
		buffer[leader] = t;
		
		if (size < buffer.length) size++;
	}
	
	public T pull() {
		if (size == 0) {
			throw new ArrayIndexOutOfBoundsException("the stack is empty");
		}
		
		@SuppressWarnings("unchecked")
		T element = (T) buffer[leader]; // this cast is safe
		
		leader = wrapIndex(leader - 1);
		size--;
		
		return element;
	}
	
	public int getSize() {
		return size;
	}
	
	public int getCapacity() {
		return buffer.length;
	}
	
	private int wrapIndex(int index) {
		return (index + getCapacity()) % getCapacity();
	}
}

 

[Shadoka]

Ah, ich glaube jetzt habe ich es verstanden. Ich habe jetzt noch 2 Variablen "put" und "get" angelegt.

	public void add(Command c) {
		buffer[put] = c;
		if (put == buffer.length-1) {
			put = 0;
			get++;
		} else {
			put++;
			if (put == get) {
				get++;
			}
		}
	}
	
	public Command get() {
		Command result = buffer[get];
		if (get == buffer.length-1) {
			get = 0;
		} else {
			get++;
		}
		return result;
	}

Gefällt mir auch besser, da man hier nicht mit null umgehen muss.

€: Danke, für das Beispiel, habe es erst nach meinem Post gesehen. Du hast du etwas wiederverwertbarer gehalten als ich, und im Gegensatz zu mir daran gedacht, was bei einem get() bei einem leeren Stack geschieht
Ich werde mir das morgen nochmal genauer anschauen, heute war ein langer Tag...danke nochmal!
€2:% anstelle von if-Abfragen ist natürlich auch schöner.

 

[Mujahiddin]

Deine Methode ist mMn unnötig umständlich... Guck mal hier:

    public void add(Command c) {
        buffer[put] = c;
        put = ++put % buffer.length;
        if( put == get ) get++;
    }
    
    public Command get() {
        if( put == -1 ) /* puffer leer */
            throw new NoSuchElementException(); /* oder return null; wobei dann buffer[get] auch null liefert */
        Command result = buffer[get];
        get = ++get % buffer.length;
        return result;
    }

Da es sich um einen Ringpuffer handelt, brauchst du keine if-Abfragne, du brauchst einfach nur eine Moduloanweisung.