001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 1997-1999 Raja Vallee-Rai
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 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: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser 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: package soot.jbco.util;
021:
022: /**
023: * @author Michael Batchelder
024: *
025: * Created on 30-Mar-2006
026: */
027: public class StringTrie {
028:
029: private char[] startChars = new char[0];
030: private StringTrie[] tries = new StringTrie[0];
031:
032: public StringTrie() {
033: super ();
034: }
035:
036: public void add(char[] chars, int index) {
037: if (chars.length == index)
038: return;
039: if (startChars.length == 0) {
040: startChars = new char[1];
041: startChars[0] = chars[0];
042: tries = new StringTrie[1];
043: tries[0].add(chars, index++);
044: } else {
045: int i = findStart(chars[index], 0, startChars.length - 1);
046: if (i >= 0) {
047: tries[i].add(chars, index++);
048: } else {
049: i = addChar(chars[index]);
050: tries[i].add(chars, index++);
051: }
052: }
053: }
054:
055: private int addChar(char c) {
056: int oldLength = startChars.length;
057:
058: int i = findSpot(c, 0, oldLength - 1);
059:
060: char tmp[] = startChars.clone();
061: StringTrie t[] = tries.clone();
062:
063: startChars = new char[oldLength + 1];
064: tries = new StringTrie[oldLength + 1];
065:
066: if (i > 0) {
067: System.arraycopy(tmp, 0, startChars, 0, i);
068: System.arraycopy(t, 0, tries, 0, i);
069: }
070: if (i < oldLength) {
071: System.arraycopy(tmp, i, startChars, i + 1, oldLength - i);
072: System.arraycopy(t, i, tries, i + 1, oldLength - i);
073: }
074:
075: startChars[i] = c;
076: tries[i] = new StringTrie();
077:
078: return i;
079: }
080:
081: private int findSpot(char c, int first, int last) {
082: int diff = last - first;
083: if (diff == 1)
084: return c < startChars[first] ? first
085: : c < startChars[last] ? last : last + 1;
086:
087: diff /= 2;
088: if (startChars[first + diff] < c)
089: return findSpot(c, first + diff, last);
090: else
091: return findSpot(c, first, last - diff);
092: }
093:
094: public boolean contains(char[] chars, int index) {
095: if (chars.length == index)
096: return true;
097: else if (startChars.length == 0)
098: return false;
099:
100: int i = findStart(chars[index], 0, startChars.length - 1);
101: if (i >= 0) {
102: return tries[i].contains(chars, index++);
103: }
104: return false;
105: }
106:
107: private int findStart(char c, int first, int last) {
108: int diff = last - first;
109: if (diff <= 1)
110: return c == startChars[first] ? first
111: : c == startChars[last] ? last : -1;
112:
113: diff /= 2;
114: if (startChars[first + diff] <= c)
115: return findStart(c, first + diff, last);
116: else
117: return findStart(c, first, last - diff);
118: }
119: }
|