    001    /*
    002     * Licensed to the Apache Software Foundation (ASF) under one or more
    003     * contributor license agreements.  See the NOTICE file distributed with
    004     * this work for additional information regarding copyright ownership.
    005     * The ASF licenses this file to You under the Apache License, Version 2.0
    006     * (the "License"); you may not use this file except in compliance with
    007     * the License.  You may obtain a copy of the License at
    008     *
    009     *      http://www.apache.org/licenses/LICENSE-2.0
    010     *
    011     * Unless required by applicable law or agreed to in writing, software
    012     * distributed under the License is distributed on an "AS IS" BASIS,
    013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014     * See the License for the specific language governing permissions and
    015     * limitations under the License.
    016     */
    017    package org.apache.commons.math3.linear;
    018
    019    import java.io.Serializable;
    020    import java.lang.reflect.Array;
    021
    022    import org.apache.commons.math3.Field;
    023    import org.apache.commons.math3.FieldElement;
    024    import org.apache.commons.math3.exception.MathArithmeticException;
    025    import org.apache.commons.math3.exception.NotPositiveException;
    026    import org.apache.commons.math3.exception.NullArgumentException;
    027    import org.apache.commons.math3.exception.OutOfRangeException;
    028    import org.apache.commons.math3.exception.DimensionMismatchException;
    029    import org.apache.commons.math3.exception.util.LocalizedFormats;
    030    import org.apache.commons.math3.util.OpenIntToFieldHashMap;
    031
    032    /**
    033     * This class implements the {@link FieldVector} interface with a {@link OpenIntToFieldHashMap} backing store.
    034     * @param <T> the type of the field elements
    035     * @version $Id: SparseFieldVector.java 1416643 2012-12-03 19:37:14Z tn $
    036     * @since 2.0
    037     * @deprecated As of version 3.1, this class is deprecated, for reasons exposed
    038     * in this JIRA
    039     * <a href="https://issues.apache.org/jira/browse/MATH-870">ticket</a>. This
    040     * class will be removed in version 4.0.
    041     */
    042    @Deprecated
    043    public class SparseFieldVector<T extends FieldElement<T>> implements FieldVector<T>, Serializable {
    044        /**  Serialization identifier. */
    045        private static final long serialVersionUID = 7841233292190413362L;
    046        /** Field to which the elements belong. */
    047        private final Field<T> field;
    048        /** Entries of the vector. */
    049        private final OpenIntToFieldHashMap<T> entries;
    050        /** Dimension of the vector. */
    051        private final int virtualSize;
    052
    053        /**
    054         * Build a 0-length vector.
    055         * Zero-length vectors may be used to initialize construction of vectors
    056         * by data gathering. We start with zero-length and use either the {@link
    057         * #SparseFieldVector(SparseFieldVector, int)} constructor
    058         * or one of the {@code append} method ({@link #append(FieldVector)} or
    059         * {@link #append(SparseFieldVector)}) to gather data into this vector.
    060         *
    061         * @param field Field to which the elements belong.
    062         */
    063        public SparseFieldVector(Field<T> field) {
    064            this(field, 0);
    065        }
    066
    067
    068        /**
    069         * Construct a vector of zeroes.
    070         *
    071         * @param field Field to which the elements belong.
    072         * @param dimension Size of the vector.
    073         */
    074        public SparseFieldVector(Field<T> field, int dimension) {
    075            this.field = field;
    076            virtualSize = dimension;
    077            entries = new OpenIntToFieldHashMap<T>(field);
    078        }
    079
    080        /**
    081         * Build a resized vector, for use with append.
    082         *
    083         * @param v Original vector
    084         * @param resize Amount to add.
    085         */
    086        protected SparseFieldVector(SparseFieldVector<T> v, int resize) {
    087            field = v.field;
    088            virtualSize = v.getDimension() + resize;
    089            entries = new OpenIntToFieldHashMap<T>(v.entries);
    090        }
    091
    092
    093        /**
    094         * Build a vector with known the sparseness (for advanced use only).
    095         *
    096         * @param field Field to which the elements belong.
    097         * @param dimension Size of the vector.
    098         * @param expectedSize Expected number of non-zero entries.
    099         */
    100        public SparseFieldVector(Field<T> field, int dimension, int expectedSize) {
    101            this.field = field;
    102            virtualSize = dimension;
    103            entries = new OpenIntToFieldHashMap<T>(field,expectedSize);
    104        }
    105
    106        /**
    107         * Create from a Field array.
    108         * Only non-zero entries will be stored.
    109         *
    110         * @param field Field to which the elements belong.
    111         * @param values Set of values to create from.
    112         */
    113        public SparseFieldVector(Field<T> field, T[] values) {
    114            this.field = field;
    115            virtualSize = values.length;
    116            entries = new OpenIntToFieldHashMap<T>(field);
    117            for (int key = 0; key < values.length; key++) {
    118                T value = values[key];
    119                entries.put(key, value);
    120            }
    121        }
    122
    123        /**
    124         * Copy constructor.
    125         *
    126         * @param v Instance to copy.
    127         */
    128        public SparseFieldVector(SparseFieldVector<T> v) {
    129            field = v.field;
    130            virtualSize = v.getDimension();
    131            entries = new OpenIntToFieldHashMap<T>(v.getEntries());
    132        }
    133
    134        /**
    135         * Get the entries of this instance.
    136         *
    137         * @return the entries of this instance
    138         */
    139        private OpenIntToFieldHashMap<T> getEntries() {
    140            return entries;
    141        }
    142
    143        /**
    144         * Optimized method to add sparse vectors.
    145         *
    146         * @param v Vector to add.
    147         * @return {@code this + v}.
    148         * @throws DimensionMismatchException if {@code v} is not the same size as
    149         * {@code this}.
    150         */
    151        public FieldVector<T> add(SparseFieldVector<T> v)
    152            throws DimensionMismatchException {
    153            checkVectorDimensions(v.getDimension());
    154            SparseFieldVector<T> res = (SparseFieldVector<T>)copy();
    155            OpenIntToFieldHashMap<T>.Iterator iter = v.getEntries().iterator();
    156            while (iter.hasNext()) {
    157                iter.advance();
    158                int key = iter.key();
    159                T value = iter.value();
    160                if (entries.containsKey(key)) {
    161                    res.setEntry(key, entries.get(key).add(value));
    162                } else {
    163                    res.setEntry(key, value);
    164                }
    165            }
    166            return res;
    167
    168        }
    169
    170        /**
    171         * Construct a vector by appending a vector to this vector.
    172         *
    173         * @param v Vector to append to this one.
    174         * @return a new vector.
    175         */
    176        public FieldVector<T> append(SparseFieldVector<T> v) {
    177            SparseFieldVector<T> res = new SparseFieldVector<T>(this, v.getDimension());
    178            OpenIntToFieldHashMap<T>.Iterator iter = v.entries.iterator();
    179            while (iter.hasNext()) {
    180                iter.advance();
    181                res.setEntry(iter.key() + virtualSize, iter.value());
    182            }
    183            return res;
    184        }
    185
    186        /** {@inheritDoc} */
    187        public FieldVector<T> append(FieldVector<T> v) {
    188            if (v instanceof SparseFieldVector<?>) {
    189                return append((SparseFieldVector<T>) v);
    190            } else {
    191                final int n = v.getDimension();
    192                FieldVector<T> res = new SparseFieldVector<T>(this, n);
    193                for (int i = 0; i < n; i++) {
    194                    res.setEntry(i + virtualSize, v.getEntry(i));
    195                }
    196                return res;
    197            }
    198        }
    199
    200        /** {@inheritDoc} */
    201        public FieldVector<T> append(T d) {
    202            FieldVector<T> res = new SparseFieldVector<T>(this, 1);
    203            res.setEntry(virtualSize, d);
    204            return res;
    205         }
    206
    207        /** {@inheritDoc} */
    208        public FieldVector<T> copy() {
    209            return new SparseFieldVector<T>(this);
    210        }
    211
    212        /** {@inheritDoc} */
    213        public T dotProduct(FieldVector<T> v) throws DimensionMismatchException {
    214            checkVectorDimensions(v.getDimension());
    215            T res = field.getZero();
    216            OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
    217            while (iter.hasNext()) {
    218                iter.advance();
    219                res = res.add(v.getEntry(iter.key()).multiply(iter.value()));
    220            }
    221            return res;
    222        }
    223
    224        /** {@inheritDoc} */
    225        public FieldVector<T> ebeDivide(FieldVector<T> v)
    226            throws DimensionMismatchException, MathArithmeticException {
    227            checkVectorDimensions(v.getDimension());
    228            SparseFieldVector<T> res = new SparseFieldVector<T>(this);
    229            OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator();
    230            while (iter.hasNext()) {
    231                iter.advance();
    232                res.setEntry(iter.key(), iter.value().divide(v.getEntry(iter.key())));
    233            }
    234            return res;
    235        }
    236
    237        /** {@inheritDoc} */
    238        public FieldVector<T> ebeMultiply(FieldVector<T> v)
    239            throws DimensionMismatchException {
    240            checkVectorDimensions(v.getDimension());
    241            SparseFieldVector<T> res = new SparseFieldVector<T>(this);
    242            OpenIntToFieldHashMap<T>.Iterator iter = res.entries.iterator();
    243            while (iter.hasNext()) {
    244                iter.advance();
    245                res.setEntry(iter.key(), iter.value().multiply(v.getEntry(iter.key())));
    246            }
    247            return res;
    248        }
    249
    250        /**
    251         * {@inheritDoc}
    252         *
    253         * @deprecated as of 3.1, to be removed in 4.0. Please use the {@link #toArray()} method instead.
    254         */
    255        @Deprecated
    256        public T[] getData() {
    257            return toArray();
    258        }
    259
    260        /** {@inheritDoc} */
    261        public int getDimension() {
    262            return virtualSize;
    263        }
    264
    265        /** {@inheritDoc} */
    266        public T getEntry(int index) throws OutOfRangeException {
    267            checkIndex(index);
    268            return entries.get(index);
    269       }
    270
    271        /** {@inheritDoc} */
    272        public Field<T> getField() {
    273            return field;
    274        }
    275
    276        /** {@inheritDoc} */
    277        public FieldVector<T> getSubVector(int index, int n)
    278            throws OutOfRangeException, NotPositiveException {
    279            if (n < 0) {
    280                throw new NotPositiveException(LocalizedFormats.NUMBER_OF_ELEMENTS_SHOULD_BE_POSITIVE, n);
    281            }
    282            checkIndex(index);
    283            checkIndex(index + n - 1);
    284            SparseFieldVector<T> res = new SparseFieldVector<T>(field,n);
    285            int end = index + n;
    286            OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
    287            while (iter.hasNext()) {
    288                iter.advance();
    289                int key = iter.key();
    290                if (key >= index && key < end) {
    291                    res.setEntry(key - index, iter.value());
    292                }
    293            }
    294            return res;
    295        }
    296
    297        /** {@inheritDoc} */
    298        public FieldVector<T> mapAdd(T d) throws NullArgumentException {
    299            return copy().mapAddToSelf(d);
    300        }
    301
    302        /** {@inheritDoc} */
    303        public FieldVector<T> mapAddToSelf(T d) throws NullArgumentException {
    304            for (int i = 0; i < virtualSize; i++) {
    305                setEntry(i, getEntry(i).add(d));
    306            }
    307            return this;
    308        }
    309
    310        /** {@inheritDoc} */
    311        public FieldVector<T> mapDivide(T d)
    312            throws NullArgumentException, MathArithmeticException {
    313            return copy().mapDivideToSelf(d);
    314        }
    315
    316        /** {@inheritDoc} */
    317        public FieldVector<T> mapDivideToSelf(T d)
    318            throws NullArgumentException, MathArithmeticException {
    319            OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
    320            while (iter.hasNext()) {
    321                iter.advance();
    322                entries.put(iter.key(), iter.value().divide(d));
    323            }
    324            return this;
    325        }
    326
    327        /** {@inheritDoc} */
    328        public FieldVector<T> mapInv() throws MathArithmeticException {
    329            return copy().mapInvToSelf();
    330        }
    331
    332        /** {@inheritDoc} */
    333        public FieldVector<T> mapInvToSelf() throws MathArithmeticException {
    334            for (int i = 0; i < virtualSize; i++) {
    335                setEntry(i, field.getOne().divide(getEntry(i)));
    336            }
    337            return this;
    338        }
    339
    340        /** {@inheritDoc} */
    341        public FieldVector<T> mapMultiply(T d) throws NullArgumentException {
    342            return copy().mapMultiplyToSelf(d);
    343        }
    344
    345        /** {@inheritDoc} */
    346        public FieldVector<T> mapMultiplyToSelf(T d) throws NullArgumentException {
    347            OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
    348            while (iter.hasNext()) {
    349                iter.advance();
    350                entries.put(iter.key(), iter.value().multiply(d));
    351            }
    352            return this;
    353        }
    354
    355        /** {@inheritDoc} */
    356        public FieldVector<T> mapSubtract(T d) throws NullArgumentException {
    357            return copy().mapSubtractToSelf(d);
    358        }
    359
    360        /** {@inheritDoc} */
    361        public FieldVector<T> mapSubtractToSelf(T d) throws NullArgumentException {
    362            return mapAddToSelf(field.getZero().subtract(d));
    363        }
    364
    365        /**
    366         * Optimized method to compute outer product when both vectors are sparse.
    367         * @param v vector with which outer product should be computed
    368         * @return the matrix outer product between instance and v
    369         */
    370        public FieldMatrix<T> outerProduct(SparseFieldVector<T> v) {
    371            final int n = v.getDimension();
    372            SparseFieldMatrix<T> res = new SparseFieldMatrix<T>(field, virtualSize, n);
    373            OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
    374            while (iter.hasNext()) {
    375                iter.advance();
    376                OpenIntToFieldHashMap<T>.Iterator iter2 = v.entries.iterator();
    377                while (iter2.hasNext()) {
    378                    iter2.advance();
    379                    res.setEntry(iter.key(), iter2.key(), iter.value().multiply(iter2.value()));
    380                }
    381            }
    382            return res;
    383        }
    384
    385        /** {@inheritDoc} */
    386        public FieldMatrix<T> outerProduct(FieldVector<T> v) {
    387            if (v instanceof SparseFieldVector<?>) {
    388                return outerProduct((SparseFieldVector<T>)v);
    389            } else {
    390                final int n = v.getDimension();
    391                FieldMatrix<T> res = new SparseFieldMatrix<T>(field, virtualSize, n);
    392                OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
    393                while (iter.hasNext()) {
    394                    iter.advance();
    395                    int row = iter.key();
    396                    FieldElement<T>value = iter.value();
    397                    for (int col = 0; col < n; col++) {
    398                        res.setEntry(row, col, value.multiply(v.getEntry(col)));
    399                    }
    400                }
    401                return res;
    402            }
    403        }
    404
    405        /** {@inheritDoc} */
    406        public FieldVector<T> projection(FieldVector<T> v)
    407            throws DimensionMismatchException, MathArithmeticException {
    408            checkVectorDimensions(v.getDimension());
    409            return v.mapMultiply(dotProduct(v).divide(v.dotProduct(v)));
    410        }
    411
    412        /** {@inheritDoc} */
    413        public void set(T value) {
    414            for (int i = 0; i < virtualSize; i++) {
    415                setEntry(i, value);
    416            }
    417        }
    418
    419        /** {@inheritDoc} */
    420        public void setEntry(int index, T value) throws OutOfRangeException {
    421            checkIndex(index);
    422            entries.put(index, value);
    423        }
    424
    425        /** {@inheritDoc} */
    426        public void setSubVector(int index, FieldVector<T> v)
    427            throws OutOfRangeException {
    428            checkIndex(index);
    429            checkIndex(index + v.getDimension() - 1);
    430            final int n = v.getDimension();
    431            for (int i = 0; i < n; i++) {
    432                setEntry(i + index, v.getEntry(i));
    433            }
    434        }
    435
    436        /**
    437         * Optimized method to compute {@code this} minus {@code v}.
    438         * @param v vector to be subtracted
    439         * @return {@code this - v}
    440         * @throws DimensionMismatchException if {@code v} is not the same size as
    441         * {@code this}.
    442         */
    443        public SparseFieldVector<T> subtract(SparseFieldVector<T> v)
    444            throws DimensionMismatchException {
    445            checkVectorDimensions(v.getDimension());
    446            SparseFieldVector<T> res = (SparseFieldVector<T>)copy();
    447            OpenIntToFieldHashMap<T>.Iterator iter = v.getEntries().iterator();
    448            while (iter.hasNext()) {
    449                iter.advance();
    450                int key = iter.key();
    451                if (entries.containsKey(key)) {
    452                    res.setEntry(key, entries.get(key).subtract(iter.value()));
    453                } else {
    454                    res.setEntry(key, field.getZero().subtract(iter.value()));
    455                }
    456            }
    457            return res;
    458        }
    459
    460        /** {@inheritDoc} */
    461        public FieldVector<T> subtract(FieldVector<T> v)
    462            throws DimensionMismatchException {
    463            if (v instanceof SparseFieldVector<?>) {
    464                return subtract((SparseFieldVector<T>)v);
    465            } else {
    466                final int n = v.getDimension();
    467                checkVectorDimensions(n);
    468                SparseFieldVector<T> res = new SparseFieldVector<T>(this);
    469                for (int i = 0; i < n; i++) {
    470                    if (entries.containsKey(i)) {
    471                        res.setEntry(i, entries.get(i).subtract(v.getEntry(i)));
    472                    } else {
    473                        res.setEntry(i, field.getZero().subtract(v.getEntry(i)));
    474                    }
    475                }
    476                return res;
    477            }
    478        }
    479
    480        /** {@inheritDoc} */
    481        public T[] toArray() {
    482            T[] res = buildArray(virtualSize);
    483            OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
    484            while (iter.hasNext()) {
    485                iter.advance();
    486                res[iter.key()] = iter.value();
    487            }
    488            return res;
    489        }
    490
    491        /**
    492         * Check whether an index is valid.
    493         *
    494         * @param index Index to check.
    495         * @throws OutOfRangeException if the index is not valid.
    496         */
    497        private void checkIndex(final int index) throws OutOfRangeException {
    498            if (index < 0 || index >= getDimension()) {
    499                throw new OutOfRangeException(index, 0, getDimension() - 1);
    500            }
    501        }
    502
    503        /**
    504         * Check if instance dimension is equal to some expected value.
    505         *
    506         * @param n Expected dimension.
    507         * @throws DimensionMismatchException if the dimensions do not match.
    508         */
    509        protected void checkVectorDimensions(int n)
    510            throws DimensionMismatchException {
    511            if (getDimension() != n) {
    512                throw new DimensionMismatchException(getDimension(), n);
    513            }
    514        }
    515
    516        /** {@inheritDoc} */
    517        public FieldVector<T> add(FieldVector<T> v) throws DimensionMismatchException {
    518            if (v instanceof SparseFieldVector<?>) {
    519                return add((SparseFieldVector<T>) v);
    520            } else {
    521                final int n = v.getDimension();
    522                checkVectorDimensions(n);
    523                SparseFieldVector<T> res = new SparseFieldVector<T>(field,
    524                                                                    getDimension());
    525                for (int i = 0; i < n; i++) {
    526                    res.setEntry(i, v.getEntry(i).add(getEntry(i)));
    527                }
    528                return res;
    529            }
    530        }
    531
    532        /**
    533         * Build an array of elements.
    534         *
    535         * @param length Size of the array to build.
    536         * @return a new array.
    537         */
    538        @SuppressWarnings("unchecked") // field is type T
    539        private T[] buildArray(final int length) {
    540            return (T[]) Array.newInstance(field.getRuntimeClass(), length);
    541        }
    542
    543
    544        /** {@inheritDoc} */
    545        @Override
    546        public int hashCode() {
    547            final int prime = 31;
    548            int result = 1;
    549            result = prime * result + ((field == null) ? 0 : field.hashCode());
    550            result = prime * result + virtualSize;
    551            OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
    552            while (iter.hasNext()) {
    553                iter.advance();
    554                int temp = iter.value().hashCode();
    555                result = prime * result + temp;
    556            }
    557            return result;
    558        }
    559
    560
    561        /** {@inheritDoc} */
    562        @Override
    563        public boolean equals(Object obj) {
    564
    565            if (this == obj) {
    566                return true;
    567            }
    568
    569            if (!(obj instanceof SparseFieldVector<?>)) {
    570                return false;
    571            }
    572
    573            @SuppressWarnings("unchecked") // OK, because "else if" check below ensures that
    574                                           // other must be the same type as this
    575            SparseFieldVector<T> other = (SparseFieldVector<T>) obj;
    576            if (field == null) {
    577                if (other.field != null) {
    578                    return false;
    579                }
    580            } else if (!field.equals(other.field)) {
    581                return false;
    582            }
    583            if (virtualSize != other.virtualSize) {
    584                return false;
    585            }
    586
    587            OpenIntToFieldHashMap<T>.Iterator iter = entries.iterator();
    588            while (iter.hasNext()) {
    589                iter.advance();
    590                T test = other.getEntry(iter.key());
    591                if (!test.equals(iter.value())) {
    592                    return false;
    593                }
    594            }
    595            iter = other.getEntries().iterator();
    596            while (iter.hasNext()) {
    597                iter.advance();
    598                T test = iter.value();
    599                if (!test.equals(getEntry(iter.key()))) {
    600                    return false;
    601                }
    602            }
    603            return true;
    604        }
    605    }