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.*;
027    import EVolve.data.*;
028    
029    public class Sorter {
030        private int[] source, target;
031        private EntityComparator comparator;
032    
033        public Sorter(Entity[] array, EntityComparator comparator) {
034            this.comparator = comparator;
035    
036            int size = array.length;
037            Entity[] arr = new Entity[size];
038    
039            source = new int[size];
040            target = new int[size];
041    
042            for (int i = 0; i < size; i++) {
043                arr[i] = array[i];
044                source[i] = i;
045            }
046    
047            quicksort(arr, 0, size - 1);
048    
049            for (int i = 0; i < size; i++) {
050                target[source[i]] = i;
051            }
052        }
053    
054        private void quicksort(Entity[] array, int start, int end) {
055            if (start < end) {
056                int pos = partition(array, start, end);
057                quicksort(array, start, pos - 1);
058                quicksort(array, pos + 1, end);
059            }
060        }
061    
062        private int partition(Entity[] array, int start, int end) {
063            Entity x = array[end];
064            int i = start - 1;
065            for (int j = start; j < end; j++) {
066                if (comparator.compare(array[j], x) < 0) {
067                    i++;
068                    Entity temp = array[i];
069                    array[i] = array[j];
070                    array[j] = temp;
071    
072                    int k = source[i];
073                    source[i] = source[j];
074                    source[j] = k;
075                }
076            }
077    
078            Entity temp = array[i + 1];
079            array[i + 1] = array[end];
080            array[end] = temp;
081    
082            int k = source[i + 1];
083            source[i + 1] = source[end];
084            source[end] = k;
085    
086            return i + 1;
087        }
088    
089        public int getTarget(int source) {
090            if ((source >= target.length) || (source < 0))
091                return -1;
092            else
093                return target[source];
094        }
095    
096        public int getSource(int target) {
097            if ((target >= source.length) || (target < 0))
098                return -1;
099            else
100                return source[target];
101        }
102    }