From 0131be32be17cadb31c8d52dabc1f9598f310606 Mon Sep 17 00:00:00 2001 From: megacz Date: Fri, 30 Jan 2004 07:42:12 +0000 Subject: [PATCH] 2003/11/27 05:10:32 darcs-hash:20040130074212-2ba56-85ea2a96322821bf545f2629f48e4d13d6d68a6c.gz --- src/org/xwt/util/BalancedTree.java | 22 ++++++++++++++-------- 1 file changed, 14 insertions(+), 8 deletions(-) diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java index 99ec34f..3f78424 100644 --- a/src/org/xwt/util/BalancedTree.java +++ b/src/org/xwt/util/BalancedTree.java @@ -5,6 +5,7 @@ package org.xwt.util; // FEATURE: private void union() { } // FEATURE: private void subset() { } // FEATURE: grow if we run out of slots +// FEATURE: finalizer /** a weight-balanced tree with fake leaves */ public class BalancedTree { @@ -130,6 +131,7 @@ public class BalancedTree { // a d < == > b e // / \ / \ // c e a c + // FIXME might be doing too much work here private void rotate(boolean toTheLeft, int b, int parent) { int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right; int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left; @@ -137,19 +139,19 @@ public class BalancedTree { int c = left[d]; left[d] = b; right[b] = c; - size[b] = size(left[b]) + size(c); - size[d] = size[b] + size(right[d]); if (parent == 0) root = d; else if (left[parent] == b) left[parent] = d; else if (right[parent] == b) right[parent] = d; else throw new Error("rotate called with invalid parent"); + size[b] = 1 + size(left[b]) + size(right[b]); + balance(b, d); + size[d] = 1 + size(left[d]) + size(right[d]); + balance(d, parent); } private void balance(int slot, int parent) { - /* if (size(left[slot]) - 1 > 2 * size(right[slot])) rotate(false, slot, parent); else if (size(left[slot]) * 2 < size(right[slot]) - 1) rotate(true, slot, parent); - */ size[slot] = 1 + size(left[slot]) + size(right[slot]); } @@ -182,10 +184,14 @@ public class BalancedTree { left[arg] = left[slot]; // steal slot's left subtree left[slot] = -1 * arg; right[arg] = slot; // make slot our right subtree - if (slot == root) root = arg; - (left[parent] == slot ? left : right)[parent] = arg; - balance(slot, arg); - balance(arg, parent); + if (slot == root) { + root = arg; + balance(slot, arg); + } else { + (left[parent] == slot ? left : right)[parent] = arg; + balance(slot, arg); + balance(arg, parent); + } } } -- 1.7.10.4