001    /* EVolve - an Extensible Software Visualization Framework
002     * Copyright (C) 2001-2002 Qin Wang
003     *
004     * This library is free software; you can redistribute it and/or
005     * modify it under the terms of the GNU Library General Public
006     * License as published by the Free Software Foundation; either
007     * version 2 of the License, or (at your option) any later version.
008     *
009     * This library is distributed in the hope that it will be useful,
010     * but WITHOUT ANY WARRANTY; without even the implied warranty of
011     * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
012     * Library General Public License for more details.
013     *
014     * You should have received a copy of the GNU Library General Public
015     * License along with this library; if not, write to the
016     * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017     * Boston, MA 02111-1307, USA.
018     */
019    
020    /*
021     * EVolve is distributed at http://www.sable.mcgill.ca/EVolve/
022     */
023    
024    package EVolve.util;
025    
026    import EVolve.data.Entity;
027    import EVolve.data.EntityComparator;
028    
029    
030    public class Sorter implements Cloneable{
031        private int[] source, target;
032        private EntityComparator comparator;
033    
034        public Sorter(Entity[] array, EntityComparator comparator) {
035            this.comparator = comparator;
036    
037            int size = array.length;
038            Entity[] arr = new Entity[size];
039    
040            source = new int[size];
041            target = new int[size];
042    
043            for (int i = 0; i < size; i++) {
044                arr[i] = array[i];
045                source[i] = i;
046            }
047    
048            mergesort(arr);
049    
050            for (int i = 0; i < size; i++) {
051                target[source[i]] = i;
052            }
053        }
054    
055        public int getTarget(int source) {
056            if ((source >= target.length) || (source < 0))
057                return -1;
058            else
059                return target[source];
060        }
061    
062        public int getSource(int target) {
063            if ((target >= source.length) || (target < 0))
064                return -1;
065            else
066                return source[target];
067        }
068    
069        private void mergesort(Entity[] array) {
070            Entity[] temp = new Entity[array.length];
071            int[] tempSource = new int[array.length];
072    
073            int step = 1;
074            while (step<array.length) {
075                int L1=0, L2, H1, H2, k=0;
076                while (L1+step<array.length) {
077                    L2 = L1 + step;
078                    H1 = L2 - 1;
079                    if (L2+step-1>=array.length)
080                        H2 = array.length-1;
081                    else
082                        H2 = L2+step-1;
083                    k = mergepass(temp,array,tempSource,L1,L2,H1,H2,k);
084                    L1 = H2 + 1;
085                }
086                int i = L1;
087                while ((k < array.length)&&(i<array.length)) {
088                    temp[k] = array[i];
089                    tempSource[k] = source[i];
090                    i++; k++;
091                }
092                for (i=0; i<array.length; i++) {
093                    array[i] = temp[i];
094                    source[i] = tempSource[i];
095                }
096                step = step * 2;
097            }
098        }
099    
100        private int mergepass(Entity[] temp, Entity[] array, int[] tempSource, int L1, int L2, int H1, int H2, int k) {
101            int i = L1, j = L2;
102            while ((i<=H1)&&(j<=H2)) {
103                if (comparator.compare(array[i], array[j]) < 0) {
104                    tempSource[k] = source[i];
105                    temp[k] = array[i];
106                    i++;
107                } else {
108                    tempSource[k] = source[j];
109                    temp[k] = array[j];
110                    j++;
111                }
112                k++;
113            }
114            while (i<=H1) {
115                temp[k] = array[i];
116                tempSource[k] = source[i];
117                i++; k++;
118            }
119            while (j<=H2) {
120                temp[k] = array[j];
121                tempSource[k] = source[j];
122                j++; k++;
123            }
124            return k;
125        }
126    
127        public Object clone() {
128            Sorter o = null;
129            try {
130                o = (Sorter)super.clone();
131            } catch (CloneNotSupportedException e) {
132                e.printStackTrace();
133            }
134    
135            o.source = new int[source.length];
136            for (int i=0; i<source.length; i++)
137                o.source[i] = source[i];
138    
139            o.target = new int[target.length];
140            for (int i=0; i<target.length; i++)
141                o.target[i] = target[i];
142    
143            o.comparator = (EntityComparator)comparator.clone();
144            return o;
145        }
146    }