001: /*
002: * CharIntMap.java
003: *
004: * Created on 13.11.2003.
005: *
006: * eaio: StringSearch - high-performance pattern matching algorithms in Java
007: * Copyright (c) 2003, 2004 Johann Burkard (jb@eaio.com) http://eaio.com
008: *
009: * Permission is hereby granted, free of charge, to any person obtaining a copy
010: * of this software and associated documentation files (the "Software"), to deal
011: * in the Software without restriction, including without limitation the rights
012: * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
013: * copies of the Software, and to permit persons to whom the Software is
014: * furnished to do so, subject to the following conditions:
015: *
016: * The above copyright notice and this permission notice shall be included in
017: * all copies or substantial portions of the Software.
018: *
019: * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
020: * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
021: * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
022: * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
023: * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
024: * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
025: * SOFTWARE.
026: *
027: */
028: package com.eaio.stringsearch;
029:
030: import java.io.Externalizable;
031: import java.io.IOException;
032: import java.io.ObjectInput;
033: import java.io.ObjectOutput;
034:
035: /**
036: * The CharIntMap is a collection to save <code>char</code> to <code>int</code>
037: * mappings in. The CharIntMap is destined to provide fast access to skip tables
038: * while being both Unicode-safe and more RAM-effective than a naive
039: * <code>int</code> array.
040: * <br><br>
041: * The CharIntMap is initialized by specifying the extent between the lowest and
042: * the highest occuring character and the lowest occuring character. Only an
043: * array of size <code>highest - lowest + 1</code> is constructed.
044: * <br><br>
045: * There's usually no need to construct a CharIntMap yourself, it is done
046: * automatically for you in the pre-processing methods.
047: *
048: * @author <a href="mailto:jb@eaio.com">Johann Burkard</a>
049: * @version 1.2
050: */
051: public class CharIntMap implements Externalizable, Cloneable {
052:
053: static final long serialVersionUID = 1351686633123489568L;
054:
055: private int[] array;
056: private char lowest;
057: private int defaultValue;
058:
059: /**
060: * Constructor for CharIntMap. Required for Serialization.
061: */
062: public CharIntMap() {
063: }
064:
065: /**
066: * Constructor for CharIntMap.
067: *
068: * @param extent the extent of the text
069: * @param lowest the lowest occuring character
070: */
071: public CharIntMap(int extent, char lowest) {
072: this (extent, lowest, 0);
073: }
074:
075: /**
076: * Constructor for CharIntMap.
077: *
078: * @param extent the extent of the text
079: * @param lowest the lowest occuring character
080: * @param defaultValue a default value to initialize the underlying
081: * <code>int</code> array with
082: */
083:
084: public CharIntMap(int extent, char lowest, int defaultValue) {
085: array = new int[extent];
086: this .lowest = lowest;
087: if (defaultValue != 0) {
088: for (int i = 0; i < array.length; i++) {
089: array[i] = defaultValue;
090: }
091: this .defaultValue = defaultValue;
092: }
093: }
094:
095: /**
096: * Returns a deep clone of this CharIntMap.
097: *
098: * @return an CharIntMap containing the same mappings
099: */
100: public Object clone() {
101: CharIntMap out = new CharIntMap();
102: out.lowest = lowest;
103: out.defaultValue = defaultValue;
104: if (array != null) {
105: out.array = new int[array.length];
106: System.arraycopy(array, 0, out.array, 0, array.length);
107: }
108: return out;
109: }
110:
111: /**
112: * Returns the stored value for the given <code>char</code>.
113: *
114: * @param c the <code>char</code>
115: * @return the stored value
116: */
117: public int get(char c) {
118:
119: /*
120: * For the Sun VM, the char version accelerates some algorithms by 5 to 10 %,
121: * in the IBM VM, there is no difference.
122: */
123:
124: // int x = c - lowest;
125: // if (x < 0 || x >= array.length) {
126: // return defaultValue;
127: // }
128: char x = (char) (c - lowest);
129: if (x >= array.length) {
130: return defaultValue;
131: }
132: return array[x];
133: }
134:
135: /**
136: * Sets the stored value for the given <code>char</code>.
137: *
138: * @param c the <code>char</code>
139: * @param val the new value
140: */
141: public void set(char c, int val) {
142:
143: /*
144: * For the Sun VM, the char version accelerates some algorithms by 5 to 10 %,
145: * in the IBM VM, there is no difference.
146: */
147:
148: // int x = c - lowest;
149: // if (x < 0 || x >= array.length) {
150: // return;
151: // }
152: char x = (char) (c - lowest);
153: if (x >= array.length) {
154: return;
155: }
156: array[x] = val;
157: }
158:
159: /**
160: * Returns the extent of the actual <code>char</code> array.
161: *
162: * @return the extent
163: */
164: public int getExtent() {
165: return array.length;
166: }
167:
168: /**
169: * Returns the lowest char that mappings can be saved for.
170: *
171: * @return a <code>char</code>
172: */
173: public char getLowest() {
174: return lowest;
175: }
176:
177: /**
178: * Returns the highest char that mappings can be saved for.
179: * @return char
180: */
181: public char getHighest() {
182: return (char) (lowest + array.length);
183: }
184:
185: /**
186: * Returns if this Object is equal to another Object.
187: *
188: * @param obj the other Object
189: * @return if this Object is equal
190: * @see java.lang.Object#equals(Object)
191: */
192: public boolean equals(Object obj) {
193: if (this == obj) {
194: return true;
195: }
196: if (!(obj instanceof CharIntMap)) {
197: return false;
198: }
199: CharIntMap m = (CharIntMap) obj;
200: if (lowest != m.lowest) {
201: return false;
202: }
203: if (defaultValue != m.defaultValue) {
204: return false;
205: }
206: if (array == null && m.array == null) {
207: return true;
208: } else if (array != null && m.array == null) {
209: return false;
210: } else if (array == null && m.array != null) {
211: return false;
212: }
213: for (int i = 0; i < array.length; i++) {
214: if (array[i] != m.array[i]) {
215: return false;
216: }
217: }
218: return true;
219: }
220:
221: /**
222: * Returns the hashCode of this Object.
223: *
224: * @return the hashCode
225: * @see java.lang.Object#hashCode()
226: */
227: public int hashCode() {
228: int out = getClass().getName().hashCode();
229: out ^= lowest;
230: out ^= defaultValue;
231: if (array != null) {
232: for (int i = 0; i < array.length; i++) {
233: out ^= array[i];
234: }
235: }
236: return out;
237: }
238:
239: /**
240: * Returns a String representation of this Object.
241: *
242: * @return a String
243: * @see java.lang.Object#toString()
244: */
245: public String toString() {
246: StringBuffer out = new StringBuffer(128);
247: out.append("{ CharIntMap: lowest = ");
248: out.append(lowest);
249: out.append(", defaultValue = ");
250: out.append(defaultValue);
251: if (array != null) {
252: out.append(", array = ");
253: for (int i = 0; i < array.length; i++) {
254: if (array[i] != 0) {
255: out.append(i);
256: out.append(": ");
257: out.append(array[i]);
258: }
259: }
260: }
261: out.append(" }");
262: return out.toString();
263: }
264:
265: /**
266: * @see java.io.Externalizable#writeExternal(java.io.ObjectOutput)
267: */
268: public void writeExternal(ObjectOutput out) throws IOException {
269: if (array == null) {
270: out.writeInt(0);
271: } else {
272: out.writeInt(array.length);
273: for (int i = 0; i < array.length; i++) {
274: out.writeInt(array[i]);
275: }
276: }
277: out.writeChar(lowest);
278: out.writeInt(defaultValue);
279: }
280:
281: /**
282: * @see java.io.Externalizable#readExternal(java.io.ObjectInput)
283: */
284: public void readExternal(ObjectInput in) throws IOException,
285: ClassNotFoundException {
286: int l = in.readInt();
287: if (l > 0) {
288: array = new int[l];
289: for (int i = 0; i < array.length; i++) {
290: array[i] = in.readInt();
291: }
292: }
293: lowest = in.readChar();
294: defaultValue = in.readInt();
295: }
296:
297: }
|