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 }