001    /*
002     * Copyright (c) 1998-2014 ChemAxon Ltd. All Rights Reserved.
003     *
004     * This software is the confidential and proprietary information of
005     * ChemAxon. You shall not disclose such Confidential Information
006     * and shall use it only in accordance with the terms of the agreements
007     * you entered into with ChemAxon.
008     *
009     */
010    package com.chemaxon.overlap.bruteforce;
011    
012    import com.chemaxon.overlap.SimilarityResultImpl;
013    import com.chemaxon.overlap.SimilarityResultNode;
014    import com.google.common.collect.ImmutableList;
015    import java.util.Arrays;
016    
017    /**
018     * Multiple dissimilarity result values.
019     *
020     * <p>
021     * This class represents multiple dissimilarity result values with associated IDs. The values can be interpreted as
022     * best values for multiple queries or top-n best values for a single query.</p>
023     */
024    class Dissimilarities {
025        /**
026         * Represented target IDs.
027         */
028        protected final int[] idArray;
029        /**
030         * Dissimilarity values for the IDs;
031         */
032        protected final double[] dissimArray;
033    
034        /**
035         * Initialize with invalid values.
036         *
037         * @param size Number of queries stored.
038         */
039        Dissimilarities(int size) {
040            this.idArray = new int[size];
041            this.dissimArray = new double[size];
042            Arrays.fill(this.idArray, -1);
043            Arrays.fill(this.dissimArray, Double.MAX_VALUE);
044        }
045    
046        /**
047         * Best IDs array.
048         *
049         * @return Best IDs array
050         */
051        int[] getIdArray() {
052            return this.idArray;
053        }
054    
055        /**
056         * Best dissimilarities array.
057         *
058         * @return Best dissimilarities array
059         */
060        double[] getDissimArray() {
061            return this.dissimArray;
062        }
063    
064        /**
065         * Merge another instance with.
066         *
067         * <p>
068         * Merged instance is left intact; this will be updated according to the best dissimilarity values for each
069         * index
070         * position.</p>
071         *
072         * <p>
073         * Both array must have the same size.</p>
074         *
075         * @param another Another instance to merge
076         */
077        void mergeDistinct(Dissimilarities another) {
078            if (this.idArray.length != another.idArray.length) {
079                throw new IllegalArgumentException("Expected size " + this.idArray.length + "; got "
080                        + another.idArray.length);
081            }
082            for (int i = 0; i < this.idArray.length; i++) {
083                if (another.dissimArray[i] < this.dissimArray[i]) {
084                    this.dissimArray[i] = another.dissimArray[i];
085                    this.idArray[i] = another.idArray[i];
086                }
087            }
088        }
089    
090        /**
091         * Merge another ID/dissimilarity value into sorted.
092         *
093         * @param dissim Dissimilarity value to merge
094         * @param id Associated ID
095         */
096        public void insertSorted(double dissim, int id) {
097            // quick check if merge actually needed
098            if (dissim >= this.dissimArray[this.dissimArray.length - 1]) {
099                // no merge needed, return
100                return;
101            }
102            // The last element from this will go
103            // invariant: new element is better than the one at insertPos and later
104            int insertPos = this.dissimArray.length - 1;
105            while (insertPos > 0 && this.dissimArray[insertPos - 1] > dissim) {
106                // advance insertpos
107                this.dissimArray[insertPos] = this.dissimArray[insertPos - 1];
108                this.idArray[insertPos] = this.idArray[insertPos - 1];
109                insertPos--;
110            }
111            this.dissimArray[insertPos] = dissim;
112            this.idArray[insertPos] = id;
113        }
114    
115        /**
116         * Merge another instance.
117         *
118         * <p>
119         * Merged instance is left intact; this will be updated.</p>
120         *
121         * <p>
122         * Size of this instance is not changed; this instance will contain best dissimilarities of the union of the two
123         * merged instances.</p>
124         *
125         * @param another Another instance to merge
126         */
127        public void mergeSorted(Dissimilarities another) {
128            mergeSorted(another, 0);
129        }
130    
131        /**
132         * Merge another instance.
133         *
134         * <p>
135         * Merged instance is left intact; this will be updated.</p>
136         *
137         * <p>
138         * Size of this instance is not changed; this instance will contain best dissimilarities of the union of the two
139         * merged instances.</p>
140         *
141         *
142         *
143         * @param another Another instance to merge
144         * @param shiftAnotherIds Add value to IDs from another array
145         */
146        public void mergeSorted(Dissimilarities another, int shiftAnotherIds) {
147            // quick check if merge actually needed
148            // if the best of another is not better than the worse of this then no merge needed
149            if (another.dissimArray[0] >= this.dissimArray[this.dissimArray.length - 1]) {
150                // no merge needed, return
151                return;
152            }
153            final int[] newIdArray = new int[this.idArray.length];
154            final double[] newDissimArray = new double[this.dissimArray.length];
155            int nextThis = 0;
156            int nextOther = 0;
157            for (int nextMerged = 0; nextMerged < newIdArray.length; nextMerged++) {
158                if (nextThis == this.idArray.length || (nextOther < another.idArray.length && this.dissimArray[nextThis] > another.dissimArray[nextOther])) {
159                    // Merge from another if this ran out
160                    // Or both present and this is worse
161                    newIdArray[nextMerged] = another.idArray[nextOther];
162                    newDissimArray[nextMerged] = another.dissimArray[nextOther];
163                    nextOther++;
164                } else {
165                    // This not ran out and
166                    // another ran out OR another is worse
167                    newIdArray[nextMerged] = this.idArray[nextThis];
168                    newDissimArray[nextMerged] = this.dissimArray[nextThis];
169                    nextThis++;
170                }
171            }
172            System.arraycopy(newIdArray, 0, this.idArray, 0, this.idArray.length);
173            System.arraycopy(newDissimArray, 0, this.dissimArray, 0, this.dissimArray.length);
174        }
175    
176        /**
177         * Create list representation.
178         *
179         * @return list representation
180         */
181        public ImmutableList<SimilarityResultNode> toList() {
182            final ImmutableList.Builder<SimilarityResultNode> ret = new ImmutableList.Builder<SimilarityResultNode>();
183            for (int i = 0; i < this.idArray.length; i++) {
184                ret.add(new SimilarityResultImpl(this.idArray[i], this.dissimArray[i]));
185            }
186            return ret.build();
187        }
188    
189    }