001: // ============================================================================
002: // $Id: FindSequence.java,v 1.16 2006/12/05 04:52:38 davidahall Exp $
003: // Copyright (c) 2003-2005 David A. Hall
004: // ============================================================================
005: // The contents of this file are subject to the Common Development and
006: // Distribution License (CDDL), Version 1.0 (the License); you may not use this
007: // file except in compliance with the License. You should have received a copy
008: // of the the License along with this file: if not, a copy of the License is
009: // available from Sun Microsystems, Inc.
010: //
011: // http://www.sun.com/cddl/cddl.html
012: //
013: // From time to time, the license steward (initially Sun Microsystems, Inc.) may
014: // publish revised and/or new versions of the License. You may not use,
015: // distribute, or otherwise make this file available under subsequent versions
016: // of the License.
017: //
018: // Alternatively, the contents of this file may be used under the terms of the
019: // GNU Lesser General Public License Version 2.1 or later (the "LGPL"), in which
020: // case the provisions of the LGPL are applicable instead of those above. If you
021: // wish to allow use of your version of this file only under the terms of the
022: // LGPL, and not to allow others to use your version of this file under the
023: // terms of the CDDL, indicate your decision by deleting the provisions above
024: // and replace them with the notice and other provisions required by the LGPL.
025: // If you do not delete the provisions above, a recipient may use your version
026: // of this file under the terms of either the CDDL or the LGPL.
027: //
028: // This library is distributed in the hope that it will be useful,
029: // but WITHOUT ANY WARRANTY; without even the implied warranty of
030: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
031: // ============================================================================
032:
033: package net.sf.jga.fn.algorithm;
034:
035: import java.util.ArrayList;
036: import java.util.Collection;
037: import java.util.Collections;
038: import net.sf.jga.fn.BinaryFunctor;
039: import net.sf.jga.fn.UnaryFunctor;
040: import net.sf.jga.fn.comparison.EqualTo;
041: import net.sf.jga.util.EmptyIterator;
042: import net.sf.jga.util.LookAheadIterator;
043: import java.util.Iterator;
044:
045: /**
046: * Locates a sequence that matches the given pattern.
047: * <p>
048: * To Serialize a FindSequence, the generic parameter T must be serializable.
049: * <p>
050: * Copyright © 2003-2005 David A. Hall
051: *
052: * @author <a href="mailto:davidahall@users.sourceforge.net">David A. Hall</a>
053: * @deprecated
054: **/
055:
056: public class FindSequence<T> extends LookAheadFunctor<T> {
057:
058: static final long serialVersionUID = 5277671793270812331L;
059:
060: // the pattern to be located
061: private Collection<? extends T> _pattern;
062:
063: // functor used to compare elements in the iteration and the pattern
064: private BinaryFunctor<T, T, Boolean> _eq;
065:
066: // the length of the pattern
067: private int _length;
068:
069: /**
070: * Builds a FindSequence functor that locates the given pattern using the
071: * equals() method to compare elements.
072: */
073: public FindSequence(Collection<? extends T> pattern) {
074: this (pattern, new EqualTo<T>());
075: }
076:
077: /**
078: * Builds a FindSequence functor that locates the given pattern using
079: * given functor to compare elements. If the pattern is null, then an
080: * arbitrary empty collection will be used.
081: * @throws IllegalArgumentException if the functor is null.
082: */
083: public FindSequence(Collection<? extends T> pattern,
084: BinaryFunctor<T, T, Boolean> eq) {
085: if (eq == null)
086: throw new IllegalArgumentException();
087:
088: _eq = eq;
089: _pattern = (pattern != null) ? pattern : new ArrayList<T>();
090:
091: // can't be 0, as the minimum size of a LookAhead is 1
092: _length = Math.max(pattern.size(), 1);
093: }
094:
095: /**
096: * Returns the pattern being sought
097: */
098: public Collection<? extends T> getPattern() {
099: return Collections.unmodifiableCollection(_pattern);
100: }
101:
102: /**
103: * Returns the functor used to compare elements in the iteration and
104: * the pattern.
105: */
106: public BinaryFunctor<T, T, Boolean> getComparisonFn() {
107: return _eq;
108: }
109:
110: // UnaryFunctor Interface
111:
112: /**
113: * Locates a sequence that matches the given pattern.
114: * @return an iterator whose next() [if it hasNext()] points to the
115: * beginning of a sequence in the iteration that matches the given pattern.
116: * If no such sequence exists, then the returned interator's hasNext() will
117: * be false.
118: */
119: public LookAheadIterator<T> fn(Iterator<? extends T> iterator) {
120: // return early if the input iterator is already finished,
121: if (!iterator.hasNext() || _length == 0) {
122: return wrap(iterator, 1);
123: }
124:
125: LookAheadIterator<T> lai = wrap(iterator, _length);
126:
127: // So long as the LookAhead has enough room for the repeat count to
128: // possibly fit, ...
129:
130: OUTER: while (lai.hasNextPlus(_length)) {
131: int idx = 1;
132:
133: // ... examine the contents of the look ahead buffer ...
134: for (T obj : _pattern) {
135: // Iterator<? extends T> patternIter = _pattern.iterator();
136: // while (patternIter.hasNext()) {
137: // T obj = patternIter.next();
138: // ... and if we find something in the buffer that isn't
139: // 'equal', then advance the look ahead
140: if (!_eq.fn(obj, lai.peek(idx))) {
141: lai.next();
142: continue OUTER;
143: }
144:
145: ++idx;
146: }
147:
148: // If we safely got off the end of the INNER loop, then we must
149: // have found the point we're looking for.
150: return lai;
151: }
152:
153: // didn't find anything, make an iterator that will return false.
154: return new LookAheadIterator<T>(new EmptyIterator<T>(), 1);
155: }
156:
157: /**
158: * Calls the Visitor's <code>visit(FindSequence)</code> method, if it
159: * implements the nested Visitor interface.
160: */
161: public void accept(net.sf.jga.fn.Visitor v) {
162: if (v instanceof FindSequence.Visitor)
163: ((FindSequence.Visitor) v).visit(this );
164: else
165: v.visit(this );
166: }
167:
168: // Object overrides
169:
170: public String toString() {
171: return "FindSequence";
172: }
173:
174: // AcyclicVisitor
175:
176: /**
177: * Interface for classes that may interpret a <b>FindSequence</b>
178: * functor
179: */
180: public interface Visitor extends net.sf.jga.fn.Visitor {
181: public void visit(FindSequence host);
182: }
183:
184: }
|