001/*
002// This software is subject to the terms of the Eclipse Public License v1.0
003// Agreement, available at the following URL:
004// http://www.eclipse.org/legal/epl-v10.html.
005// You must accept the terms of that agreement to use this software.
006//
007// Copyright (C) 2011-2011 Pentaho and others
008// All Rights Reserved.
009*/
010package mondrian.util;
011
012import java.util.*;
013
014/**
015 * A list that, given a collection of elements, contains every possible
016 * combination of those objects (also known as the
017 * <a href="http://en.wikipedia.org/wiki/Power_set">power set</a> of those
018 * objects).
019 *
020 * @author LBoudreau
021 * @author jhyde
022 */
023public class CombiningGenerator<E> extends AbstractList<List<E>> {
024
025    private final E[] elements;
026    private final int size;
027
028    /**
029     * Creates a CombiningGenerator.
030     *
031     * @param elements Elements to iterate over
032     */
033    public CombiningGenerator(Collection<E> elements) {
034        //noinspection unchecked
035        this.elements = (E[]) elements.toArray(new Object[elements.size()]);
036        if (elements.size() > 31) {
037            // No point having a list with more than 2^31 elements; you can't
038            // address it using a java (signed) int value. I suppose you could
039            // have an iterator that is larger... but it would take a long time
040            // to iterate it.
041            throw new IllegalArgumentException("too many elements");
042        }
043        size = 1 << this.elements.length;
044    }
045
046    /**
047     * Creates a CombiningGenerator, inferring the type from the argument.
048     *
049     * @param elements Elements to iterate over
050     * @param <T> Element type
051     * @return Combing generator containing the power set
052     */
053    public static <T> CombiningGenerator<T> of(Collection<T> elements) {
054        return new CombiningGenerator<T>(elements);
055    }
056
057    @Override
058    public List<E> get(final int index) {
059        final int size = Integer.bitCount(index);
060        return new AbstractList<E>() {
061            public E get(int index1) {
062                if (index1 < 0 || index1 >= size) {
063                    throw new IndexOutOfBoundsException();
064                }
065                int i = nth(index1, index);
066                return elements[i];
067            }
068
069            public int size() {
070                return size;
071            }
072        };
073    }
074
075    /**
076     * Returns the position of the {@code seek}th bit set in {@code b}.
077     * For example,
078     * nth(0, 1) returns 0;
079     * nth(0, 2) returns 1;
080     * nth(0, 4) returns 2;
081     * nth(7, 255) returns 7.
082     *
083     * <p>Careful. If there are not that many bits set, this method never
084     * returns.</p>
085     *
086     * @param seek Bit to seek
087     * @param b Integer in which to seek bits
088     * @return Ordinal of the given set bit
089     */
090    private static int nth(int seek, int b) {
091        int i = 0, c = 0;
092        for (;;) {
093            if ((b & 1) == 1) {
094                if (c++ == seek) {
095                    return i;
096                }
097            }
098            ++i;
099            b >>= 1;
100        }
101    }
102
103    public int size() {
104        return size;
105    }
106
107    /**
108     * Ad hoc test. See also UtilTest.testCombiningGenerator.
109     *
110     * @param args ignored
111     */
112    public static void main(String[] args) {
113        List<String> seed = new ArrayList<String>();
114        for (int i = 0; i < 8; i++) {
115            seed.add(String.valueOf(i));
116        }
117        List<List<String>> result = new CombiningGenerator<String>(seed);
118        for (List<String> i : result) {
119            for (Object o : i) {
120                System.out.print("|");
121                System.out.print(String.valueOf(o));
122            }
123            System.out.println("|");
124        }
125    }
126}
127
128// End CombiningGenerator.java