/* OrthoDepthSorter.java * * Copyright (c) 2002, Benja Fallenstein * * You may use and distribute under the terms of either the GNU Lesser * General Public License, either version 2 of the license or, * at your choice, any later version. Alternatively, you may use and * distribute under the terms of the XPL. * * See the LICENSE.lgpl and LICENSE.xpl files for the specific terms of * the licenses. * * This software is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the README * file for more details. * */ /* * Written by Benja Fallenstein */ package gzz.vob.impl; import gzz.vob.*; final class OrthoDepthSorter { OrthoCoordsys sys; int[] sorted; int nsorted; /** Helper array for the quicksort implementation */ private int[] helper; OrthoDepthSorter(OrthoCoordsys sys, int initialSize) { this.sys = sys; sorted = new int[initialSize]; helper = new int[initialSize]; nsorted = 0; } void clear() { nsorted = 0; } void sort() { if(nsorted < sys.nsys) { if(sorted.length < sys.nsys) { sorted = new int[sys.depth.length]; helper = new int[sys.depth.length]; } for(int i=nsorted; i sys.depth[cs2]) return 1; if(sys.depth[cs1] < sys.depth[cs2]) return -1; if(cs1 > cs2) return 1; else return -1; } else if(sys.nancestors[cs1] == sys.nancestors[cs2]) { return cmp(sys.parent[cs1], sys.parent[cs2]); } else if(sys.nancestors[cs1] > sys.nancestors[cs2]) { int ancestor = cs1; while(sys.nancestors[ancestor] > sys.nancestors[cs2]) ancestor = sys.parent[ancestor]; int cmp = cmp(ancestor, cs2); if(cmp == 0) return -1; else return cmp; } else { return 0 - cmp(cs2, cs1); } } /* OLD VERSION-- needed ancestor array per coordset, had clipping errors int cmp(int cs1, int cs2) { if(cs1 == cs2) return 0; if(cs2 == 0) return 1; if(cs1 == 0) return -1; int[] a1 = sys.ancestors[cs1]; int[] a2 = sys.ancestors[cs2]; int len = (a1.length < a2.length) ? a1.length : a2.length; for(int i=0; i sys.depth[s2]) return 1; if(s1 > s2) return 1; if(s1 < s2) return -1; throw new Error("Huh?"); } } if(a1.length < a2.length) return 1; if(a1.length > a2.length) return -1; if(sys.depth[cs1] < sys.depth[cs2]) return -1; if(sys.depth[cs1] > sys.depth[cs2]) return 1; if(cs1 > cs2) return 1; if(cs1 < cs2) return -1; throw new Error("Huh?"); } */ /** Sort part of the array, using quicksort. * @param start The start of the range to be sorted. * @param n The length of the range to be sorted. */ void quicksort(int start, int n) { if(n <= 1) return; if(n == 2) { if(cmp(sorted[start], sorted[start+1]) > 0) exchange(start, start+1); } int pivot = sorted[start + n/2]; int l = 0, r = n; for(int i=0; i 0) { r--; helper[r] = s; } } for(int i=l; i