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