RedBlackTreeSet.java

/*
 * Created by: Karol Sobczak (napewnotrafi@gmail.com)
 */
package org.adblocktv.tagsserver.utils.rbtree;

import java.util.Iterator;

/**
 * A simple implementation of a set using an underlying red-black tree.
 * @author Karol Sobczak
 */
public class RedBlackTreeSet<K extends Comparable>
        extends RedBlackTree<K, Object>
        implements Iterable<K> {

    /**
     * An iterator for the red-black tree set.
     */
    private class RedBlackTreeSetIterator implements Iterator<K> {

        private Iterator<Node> nodesIterator = nodesIterator();

        @Override
        public boolean hasNext() {
            return nodesIterator.hasNext();
        }

        @Override
        public K next() {
            return nodesIterator.next().getKey();
        }

        @Override
        public void remove() {
        }
    }

    /**
     * Adds a value to the set.
     * @param e a value to be added to the set
     */
    public void add(K e) {
        Node node = search(e);
        if (node == getNilNode()) {
            add(new Node(e, null));
        }
    }

    /**
     * Checks if the set contains a given value.
     * @param e a value to be checked for existence
     * @return true if the set contains a given value
     */
    public boolean contains(K e) {
        Node node = search(e);
        return node != getNilNode();
    }

    /**
     * Removes a given value from the set.
     * @param e a value to be removed from the set
     */
    public void remove(K e) {
        Node node = search(e);
        if (node != getNilNode()) {
            remove(node);
        }
    }

    /**
     * Returns an iterator for the set (ascending order).
     * @return an iterator for the set (ascending order)
     */
    @Override
    public Iterator<K> iterator() {
        return new RedBlackTreeSetIterator();
    }
}