1/* 2 * RopeUtilities.java 3 * Copyright (C) 2007 Amin Ahmad. 4 * 5 * This file is part of Java Ropes. 6 * 7 * Java Ropes is free software: you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License as published by 9 * the Free Software Foundation, either version 3 of the License, or 10 * (at your option) any later version. 11 * 12 * Java Ropes is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with Java Ropes. If not, see <http://www.gnu.org/licenses/>. 19 * 20 * Amin Ahmad can be contacted at amin.ahmad@gmail.com or on the web at 21 * www.ahmadsoft.org. 22 */ 23package org.ahmadsoft.ropes.impl; 24 25import java.io.PrintStream; 26import java.util.ArrayDeque; 27import java.util.ArrayList; 28 29import org.ahmadsoft.ropes.Rope; 30 31/** 32 * Contains utlities for manipulating ropes. 33 * @author aahmad 34 */ 35class RopeUtilities { 36 37 private static final long[] FIBONACCI = { 0l, 1l, 1l, 2l, 3l, 5l, 8l, 13l, 21l, 34l, 55l, 89l, 144l, 233l, 377l, 610l, 987l, 1597l, 2584l, 4181l, 6765l, 10946l, 17711l, 28657l, 46368l, 75025l, 121393l, 196418l, 317811l, 514229l, 832040l, 1346269l, 2178309l, 3524578l, 5702887l, 9227465l, 14930352l, 24157817l, 39088169l, 63245986l, 102334155l, 165580141l, 267914296l, 433494437l, 701408733l, 1134903170l, 1836311903l, 2971215073l, 4807526976l, 7778742049l, 12586269025l, 20365011074l, 32951280099l, 53316291173l, 86267571272l, 139583862445l, 225851433717l, 365435296162l, 591286729879l, 956722026041l, 1548008755920l, 2504730781961l, 4052739537881l, 6557470319842l, 10610209857723l, 17167680177565l, 27777890035288l, 44945570212853l, 72723460248141l, 117669030460994l, 190392490709135l, 308061521170129l, 498454011879264l, 806515533049393l, 1304969544928657l, 2111485077978050l, 3416454622906707l, 5527939700884757l, 8944394323791464l, 14472334024676221l, 23416728348467685l, 37889062373143906l, 61305790721611591l, 99194853094755497l, 160500643816367088l, 259695496911122585l, 420196140727489673l, 679891637638612258l, 1100087778366101931l, 1779979416004714189l, 2880067194370816120l, 4660046610375530309l, 7540113804746346429l}; 38 private static final short MAX_ROPE_DEPTH = 96; 39 private static final String SPACES = " "; 40 41 public static RopeUtilities INSTANCE = new RopeUtilities(); 42 43 /** 44 * Rebalance a rope if the depth has exceeded MAX_ROPE_DEPTH. If the 45 * rope depth is less than MAX_ROPE_DEPTH or if the rope is of unknown 46 * type, no rebalancing will occur. 47 * @param r the rope to rebalance. 48 * @return a rebalanced copy of the specified rope. 49 */ 50 public Rope autoRebalance(final Rope r) { 51 if (r instanceof AbstractRope && ((AbstractRope) r).depth() > RopeUtilities.MAX_ROPE_DEPTH) { 52 return this.rebalance(r); 53 } else { 54 return r; 55 } 56 } 57 58 /** 59 * Concatenate two ropes. Implements all recommended optimizations in "Ropes: an 60 * Alternative to Strings". 61 * @param left the first rope. 62 * @param right the second rope. 63 * @return the concatenation of the specified ropes. 64 */ 65 Rope concatenate(final Rope left, final Rope right) { 66 if (left.length() == 0) 67 return right; 68 if (right.length() == 0) 69 return left; 70 if ((long) left.length() + right.length() > Integer.MAX_VALUE) 71 throw new IllegalArgumentException( 72 "Left length=" + left.length() + ", right length=" + right.length() 73 + ". Concatenation would overflow length field."); 74 final int combineLength = 17; 75 if (left.length() + right.length() < combineLength) { 76 return new FlatCharSequenceRope(left.toString() + right.toString()); 77 } 78 if (!(left instanceof ConcatenationRope)) { 79 if (right instanceof ConcatenationRope) { 80 final ConcatenationRope cRight = (ConcatenationRope) right; 81 if (left.length() + cRight.getLeft().length() < combineLength) 82 return this.autoRebalance(new ConcatenationRope(new FlatCharSequenceRope(left.toString() + cRight.getLeft().toString()), cRight.getRight())); 83 } 84 } 85 if (!(right instanceof ConcatenationRope)) { 86 if (left instanceof ConcatenationRope) { 87 final ConcatenationRope cLeft = (ConcatenationRope) left; 88 if (right.length() + cLeft.getRight().length() < combineLength) 89 return this.autoRebalance(new ConcatenationRope(cLeft.getLeft(), new FlatCharSequenceRope(cLeft.getRight().toString() + right.toString()))); 90 } 91 } 92 93 return this.autoRebalance(new ConcatenationRope(left, right)); 94 } 95 96 /** 97 * Returns the depth of the specified rope. 98 * @param r the rope. 99 * @return the depth of the specified rope. 100 */ 101 byte depth(final Rope r) { 102 if (r instanceof AbstractRope) { 103 return ((AbstractRope)r).depth(); 104 } else { 105 return 0; 106 //throw new IllegalArgumentException("Bad rope"); 107 } 108 } 109 110 boolean isBalanced(final Rope r) { 111 final byte depth = this.depth(r); 112 if (depth >= RopeUtilities.FIBONACCI.length - 2) 113 return false; 114 return (RopeUtilities.FIBONACCI[depth + 2] <= r.length()); // TODO: not necessarily valid w/e.g. padding char sequences. 115 } 116 public Rope rebalance(final Rope r) { 117 // get all the nodes into a list 118 119 final ArrayList<Rope> leafNodes = new ArrayList<Rope>(); 120 final ArrayDeque<Rope> toExamine = new ArrayDeque<Rope>(); 121 // begin a depth first loop. 122 toExamine.add(r); 123 while (toExamine.size() > 0) { 124 final Rope x = toExamine.pop(); 125 if (x instanceof ConcatenationRope) { 126 toExamine.push(((ConcatenationRope) x).getRight()); 127 toExamine.push(((ConcatenationRope) x).getLeft()); 128 continue; 129 } else { 130 leafNodes.add(x); 131 } 132 } 133 Rope result = merge(leafNodes, 0, leafNodes.size()); 134 return result; 135 } 136 private Rope merge(ArrayList<Rope> leafNodes, int start, int end) { 137 int range = end - start; 138 switch (range) { 139 case 1: 140 return leafNodes.get(start); 141 case 2: 142 return new ConcatenationRope(leafNodes.get(start), leafNodes.get(start + 1)); 143 default: 144 int middle = start + (range / 2); 145 return new ConcatenationRope(merge(leafNodes, start, middle), merge(leafNodes, middle, end)); 146 } 147 } 148 149 /** 150 * Visualize a rope. 151 * @param r 152 * @param out 153 */ 154 void visualize(final Rope r, final PrintStream out) { 155 this.visualize(r, out, (byte) 0); 156 } 157 158 public void visualize(final Rope r, final PrintStream out, final int depth) { 159 if (r instanceof FlatRope) { 160 out.print(RopeUtilities.SPACES.substring(0,depth*2)); 161 out.println("\"" + r + "\""); 162// out.println(r.length()); 163 } 164 if (r instanceof SubstringRope) { 165 out.print(RopeUtilities.SPACES.substring(0,depth*2)); 166 out.println("substring " + r.length() + " \"" + r + "\""); 167// this.visualize(((SubstringRope)r).getRope(), out, depth+1); 168 } 169 if (r instanceof ConcatenationRope) { 170 out.print(RopeUtilities.SPACES.substring(0,depth*2)); 171 out.println("concat[left]"); 172 this.visualize(((ConcatenationRope)r).getLeft(), out, depth+1); 173 out.print(RopeUtilities.SPACES.substring(0,depth*2)); 174 out.println("concat[right]"); 175 this.visualize(((ConcatenationRope)r).getRight(), out, depth+1); 176 } 177 } 178 179 public void stats(final Rope r, final PrintStream out) { 180 int nonLeaf=0; 181 final ArrayList<Rope> leafNodes = new ArrayList<Rope>(); 182 final ArrayDeque<Rope> toExamine = new ArrayDeque<Rope>(); 183 // begin a depth first loop. 184 toExamine.add(r); 185 while (toExamine.size() > 0) { 186 final Rope x = toExamine.pop(); 187 if (x instanceof ConcatenationRope) { 188 ++nonLeaf; 189 toExamine.push(((ConcatenationRope) x).getRight()); 190 toExamine.push(((ConcatenationRope) x).getLeft()); 191 } else { 192 leafNodes.add(x); 193 } 194 } 195 out.println("rope(length=" + r.length() + ", leaf nodes=" + leafNodes.size() + ", non-leaf nodes=" + nonLeaf + ", depth=" + RopeUtilities.INSTANCE.depth(r) + ")"); 196 } 197 198} 199