Wie Iterator Remove implementieren?

[DisasterJava]

Hi,

Ich hab einen Binärbaum gemacht und eine Iterator-Klasse dazu. Soweit funktioniert das ganze. Allerdings weiß ich nicht wie man vom Interator das Remove Implementieren kann und ich finde auch keine ordentliche Beschreibung dazu. Es heißt ja es löscht das letzte Element welches mit Next zurück gegeben wurde.. aber wie kann man darauf zugreifen?

Danke für die Hilfe

 

[Cola_Colin]

Darauf zugreifen ?
Das Element sollte dein Iterator eben noch kennen, d.h. in einem Feld der Klasse sollte es abgespeichert sein.

 

[SlaterB]

oder es muss ein Index oder sonst etwas bekannt sein, sonst funktionieren ja auch die restlichen Funktionen nicht

 

[Asgar13]

???:L

element.remove();

Oracle:
Iterator (Java 2 Platform SE 5.0)

Beispiel:
Remove an element from Collection using Java Iterator Example | Java Examples - Java Program Sample Source Code

 

[Cola_Colin]

Er will glaub ich einen eigenen Iterator für seine eigene Binärbaumklasse schreiben.

 

[Asgar13]

Ich hab einen Binärbaum gemacht und eine Iterator-Klasse dazu. Soweit funktioniert das ganze. Allerdings weiß ich nicht wie man vom Interator das Remove Implementieren kann

Danach scheint er eine schon zu haben.

 

[Cola_Colin]

Allerdings weiß ich nicht wie man vom Interator das Remove Implementieren kann

Implementieren, nicht nur aufrufen.

 

[DisasterJava]

Hi,

mir geht es um die Implementation.

Ich habe eine Klasse BST und in dieser eine "private static class BSTIterator implements Iterator"

Dadurch muss ich ja einige Methoden implementieren und hier kann man auch Remove implementieren, weil wenn man das nicht macht nützt ja element.remove() gar nix.

So mein Problem ist ja nur ich kann im Iterator remove nicht meine remove Methode von BST aufrufen weil ich da ja gar nicht ran komme nur weil ich ein element (Node) von BST habe.

.. Hoffe das war verständlicher

 

[SlaterB]

wer erstellt wann wo warum welchen Iterator und welche anderen Programmzusammenhänge kannst du noch erzählen?
übergib den BST, was immer das ist, an den Iterator, z.B. im Konstruktor, schon kennt er ihn/es

 

[DisasterJava]

Also ich hab mal den Code angehängt..
Der Iterator wird so aufgerufen:

 final int NELEMS = 10000;
    SortedSet set = createSet();

    for (int i=1; i<=NELEMS; i++)
      set.add(i);
    
    Iterator<Integer> it = set.iterator();
    int i=0;
    while (it.hasNext()) {
      assertEquals(++i, it.next().intValue());
      it.remove();
      assertEquals(NELEMS-i, set.getSize());
    }

package collections;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

public class BSTSet implements SortedTreeSet {

	Node root;
	private int size; 
	private int height;

	/**
	 *This is a Node object.
	 *
	 */
	private static class Node {

		@SuppressWarnings("unchecked")
		Comparable val;

		Node left; // Referenz auf ein kleineres Objekt
		Node right; // Referenz auf ein groesseres Element
		Node parent; // Referenz auf den Parent

		/**
		 * Constructor of a new node object.
		 * @param val
		 * value of the node
		 * @param left
		 * left child node
		 * @param right
		 * right child node
		 * @param parent
		 * parent of the node
		 */
		@SuppressWarnings("unchecked")
		public Node(Comparable val, Node left, Node right, Node parent) {
			this.val = val;
			this.left = left;
			this.right = right;
			this.parent = parent;
		}

	}

	/**
	 * Iterator Class for BST
	 *
	 */
	@SuppressWarnings("unchecked")
	private static class BSTIterator implements Iterator {

		private Stack par;
	
		private BSTIterator(Node root) {
			par = new Stack();
			Node next = root;
			while (next != null) {
				par.push(next);
				next = next.left;
			} // while
		} // bst iterator

		public boolean hasNext() {
			return !par.empty();
		} // has next

		public Object next() {
			if (par.empty()) {
				throw new NoSuchElementException();
			} // if
			else {
				Node cur = (Node) par.pop();
				Node next = cur.right;
				while (next != null) {
					par.push(next);
					next = next.left;
				} // while
				return cur.val;
			} // else
		} // next

		public void remove() {
			
			throw new UnsupportedOperationException();
		} // remove

	} // iterator
	
	/**
	 * Start: Tree is Empty.
	 */
	public BSTSet() {
		root = null;
	}

	/**
	 * Retuns the height of the tree.
	 */
	@Override
	public int height() {
		return height;
	}
	
	/**
	 * Prints the the tree inOrder.
	 */
	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append("[");
		traverseInOrder(root, sb);
		sb.append("]");
		return sb.toString();
	} // to string

	/**
	 * Walk throw the tree and adds the values.
	 * @param t
	 * current Node
	 * @param sb
	 * StringBuffer object
	 */
	private void traverseInOrder(Node t, StringBuffer sb) {
		if (t != null) {
			traverseInOrder(t.left, sb);
			if (sb.length() > 1)
				sb.append(", ");
			sb.append(t.val);
			traverseInOrder(t.right, sb);
		} // if
	} // traverse
	
	/**
	 * Adds a new node in the Tree when the key isn't alredy in the tree.
	 */
	@SuppressWarnings("unchecked")
	@Override
	public boolean add(Comparable key) {
		Node x, current, parent;

		parent = null;
		current = root;

		// Till the end of the tree.
		while (current != null) {
			int cmpRes = key.compareTo(current.val);
			// Node is alredy in the tree => return false;
			if (cmpRes == 0)
				return false;

			parent = current;

			if (cmpRes < 0)
				current = current.left;
			else
				current = current.right;
			// if

		} // while

		// New node and initialize.

		x = new Node(key, null, null, parent);
		size++;
		
		// Set the new node at the right position or as root.
		if (parent != null) {
			int cmpRes = key.compareTo(parent.val);

			if (cmpRes < 0){
				parent.left = x;
				if(parent.right == null)
					height++;
			}
			else{
				parent.right = x;
				if(parent.left == null)
					height++;
			}
		} else{
			root = x;
			height++;
		}
		return true;
	} // add

	/**
	 * 	Searchs for a key in the tree.
	 */
	@Override
	@SuppressWarnings("unchecked")
	public boolean contains(Comparable key) {

		Node current = root;

		while (current != null) {
			int cmpRes = key.compareTo(current.val);
			// Node is alredy in the tree => return false;
			if (cmpRes == 0)
				return true;

			if (cmpRes < 0)
				current = current.left;
			else
				current = current.right;
		}

		return false;
	} // contains

	/**
	 * Returns the current size of the tree.
	 */
	@Override
	public int getSize() {
		return size;
	}

	/**
	 * Returns the BSTIterator for this tree;
	 */
	@SuppressWarnings("unchecked")
	@Override
	public Iterator iterator() {
		return new BSTIterator(root);
	}

	/**
	 * Removes a key from the tree.
	 */
	@SuppressWarnings("unchecked")
	@Override
	public boolean remove(Comparable key) {

		Node x, y, z;

		z = root;

		while (z != null) {
			int cmpRes = key.compareTo(z.val);

			if (cmpRes == 0)
				break;
			else if (cmpRes < 0)
				z = z.left;
			else
				z = z.right;
		} // while

		// Node is not in the tree.
		if (z == null)
			return false;

		if (z.left == null || z.right == null)
			y = z;
		else {
			y = z.right;

			while (y.left != null)
				y = y.left;
		}

		if (y.left != null)
			x = y.left;
		else
			x = y.right;

		if (x != null)
			x.parent = y.parent;

		if (y.parent != null)
			if (y == y.parent.left)
				y.parent.left = x;
			else
				y.parent.right = x;
		else
			root = x;

		if (y != z) {
			y.left = z.left;
			if (y.left != null)
				y.left.parent = y;
			// if

			y.right = z.right;
			if (y.right != null)
				y.right.parent = y;
			// if

			y.parent = z.parent;
			if (z.parent != null)
				if (z == z.parent.left)
					z.parent.left = y;
				else
					z.parent.right = y;
			// if
			else
				root = y;
		} // if

		size--;
		return true;
	} // remove

} // class BST

 

[Cola_Colin]

Übergebe dem Iterator statt der root den ganzen BSP-Tree und schon kannst du auf den Tree zugreifen.

 

[DisasterJava]

Super danke, manchmal ist man richtig blind... funktioniert natürlich. THX