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