Riešenia testu č. 5

Úloha č. 1

package trees;

import java.util.function.*;

public class BinaryNode<T> extends Node<T> {

    // ...

    @Override
    public T evaluate() {
        return operator.apply(left.evaluate(), right.evaluate());
    }
}

package trees;

import java.util.function.*;

public class UnaryNode<T> extends Node<T> {

    // ...

    @Override
    public T evaluate() {
        return operator.apply(child.evaluate());
    }

}

package trees;

public class NullaryNode<T> extends Node<T> {

    // ...

    @Override
    public T evaluate() {
        return value;
    }

}

package trees;

public class Plus extends BinaryNode<Integer> {

    public Plus(Node<Integer> left, Node<Integer> right) {
        super((a, b) -> a + b, left, right);
    }

}

package trees;

public class Times extends BinaryNode<Integer> {

    public Times(Node<Integer> left, Node<Integer> right) {
        super((a, b) -> a * b, left, right);
    }

}

package trees;

public class UnaryMinus extends UnaryNode<Integer> {

    public UnaryMinus(Node<Integer> child) {
        super(a -> -a, child);
    }

}

Úloha č. 2

package graphs;

import java.util.*;

public class Bridges {
    private UndirectedGraph g;
    private int n;
    private Set<UndirectedEdge> bridges;

    public Bridges(UndirectedGraph g) {
        this.g = g;
        n = g.getVertexCount();
        bridges = new HashSet<>();
        for (int u = 0; u <= n - 1; u++) {
            for (int v = u + 1; v <= n - 1; v++) {
                if (isBridge(u, v)) {
                    bridges.add(new UndirectedEdge(u, v));
                }
            }
        }
    }

    private boolean isBridge(int u, int v) {
        if (u == v || !g.hasEdge(u, v)) {
            return false;
        }
        ArrayList<Boolean> visited = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i <= n - 1; i++) {
            visited.add(false);
        }
        visited.set(u, true);
        visited.set(v, true);
        queue.add(u);
        while (!queue.isEmpty()) {
            int vertex = queue.remove();
            for (int successor : g.outgoingEdgesDestinations(vertex)) {
                if (vertex != u && successor == v) {
                    return false;
                }
                if (!visited.get(successor)) {
                    visited.set(successor, true);
                    queue.add(successor);
                }
            }
        }
        return true;
    }

    public int bridgeCount() {
        return bridges.size();
    }

    public Set<UndirectedEdge> getBridges() {
        return Collections.unmodifiableSet(bridges);
    }

}

Úloha č. 3

import java.util.*;

public class CombinationsIterator<T> implements Iterator<Set<T>> {
    private ArrayList<T> elements;
    private int n;
    private int k;
    private ArrayList<Integer> nextIndices;

    public CombinationsIterator(Set<T> set, int k) {
        elements = new ArrayList<>(set);
        n = set.size();
        this.k = k;
        if (k <= n) {
            nextIndices = new ArrayList<>();
            for (int i = 0; i <= k - 1; i++) {
                nextIndices.add(i);
            }
        }
    }

    private void findNextIndices() {
        for (int i = k - 1; i >= 0; i--) {
            if (nextIndices.get(i) <= n - k + i - 1) {
                nextIndices.set(i, nextIndices.get(i) + 1);
                for (int j = i + 1; j <= k - 1; j++) {
                    nextIndices.set(j, nextIndices.get(i) + j - i);
                }
                return;
            }
        }
        nextIndices = null;
    }

    @Override
    public boolean hasNext() {
        return nextIndices != null;
    }

    @Override
    public Set<T> next() {
        if (hasNext()) {
            Set<T> result = new HashSet<>();
            for (int i : nextIndices) {
                result.add(elements.get(i));
            }
            findNextIndices();
            return result;
        }
        throw new NoSuchElementException();
    }
}