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 008// All Rights Reserved. 009*/ 010package mondrian.util; 011 012import mondrian.olap.Util; 013 014import java.util.*; 015 016/** 017 * List that generates the cartesian product of its component lists. 018 * 019 * @author jhyde 020 */ 021public class CartesianProductList<T> 022 extends AbstractList<List<T>> 023 implements RandomAccess 024{ 025 private final List<List<T>> lists; 026 027 public CartesianProductList(List<List<T>> lists) { 028 super(); 029 this.lists = lists; 030 } 031 032 @Override 033 public List<T> get(int index) { 034 final List<T> result = new ArrayList<T>(); 035 for (int i = lists.size(); --i >= 0;) { 036 final List<T> list = lists.get(i); 037 final int size = list.size(); 038 int y = index % size; 039 index /= size; 040 result.add(0, list.get(y)); 041 } 042 return result; 043 } 044 045 @Override 046 public int size() { 047 int n = 1; 048 for (List<T> list : lists) { 049 n *= list.size(); 050 } 051 return n; 052 } 053 054 public void getIntoArray(int index, Object[] a) { 055 int n = 0; 056 for (int i = lists.size(); --i >= 0;) { 057 final List<T> list = lists.get(i); 058 final int size = list.size(); 059 int y = index % size; 060 index /= size; 061 Object t = list.get(y); 062 if (t instanceof List) { 063 List tList = (List) t; 064 for (int j = tList.size(); --j >= 0;) { 065 a[n++] = tList.get(j); 066 } 067 } else { 068 a[n++] = t; 069 } 070 } 071 reverse(a, n); 072 } 073 074 private void reverse(Object[] a, int size) { 075 for (int i = 0, j = size - 1; i < j; ++i, --j) { 076 Object t = a[i]; 077 a[i] = a[j]; 078 a[j] = t; 079 } 080 } 081 082 @Override 083 public Iterator<List<T>> iterator() { 084 return new CartesianProductIterator(); 085 } 086 087 /** 088 * Iterator over a cartesian product list. It computes the list of elements 089 * incrementally, so is a more efficient at generating the whole cartesian 090 * product than calling {@link CartesianProductList#get} each time. 091 */ 092 private class CartesianProductIterator implements Iterator<List<T>> { 093 private final int[] offsets; 094 private final T[] elements; 095 private boolean hasNext; 096 097 public CartesianProductIterator() { 098 this.offsets = new int[lists.size()]; 099 //noinspection unchecked 100 this.elements = (T[]) new Object[lists.size()]; 101 hasNext = true; 102 for (int i = 0; i < lists.size(); i++) { 103 final List<T> list = lists.get(i); 104 if (list.isEmpty()) { 105 hasNext = false; 106 return; 107 } 108 elements[i] = list.get(0); 109 } 110 } 111 112 public boolean hasNext() { 113 return hasNext; 114 } 115 116 public List<T> next() { 117 @SuppressWarnings({"unchecked"}) 118 List<T> result = Util.flatListCopy(elements); 119 moveToNext(); 120 return result; 121 } 122 123 private void moveToNext() { 124 int ordinal = offsets.length; 125 while (ordinal > 0) { 126 --ordinal; 127 ++offsets[ordinal]; 128 final List<T> list = lists.get(ordinal); 129 if (offsets[ordinal] < list.size()) { 130 elements[ordinal] = list.get(offsets[ordinal]); 131 return; 132 } 133 offsets[ordinal] = 0; 134 elements[ordinal] = list.get(0); 135 } 136 hasNext = false; 137 } 138 139 public void remove() { 140 throw new UnsupportedOperationException(); 141 } 142 } 143} 144 145// End CartesianProductList.java