001: // ============================================================================
002: // $Id: FindRepeated.java,v 1.19 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.Iterator;
036: import net.sf.jga.fn.UnaryFunctor;
037: import net.sf.jga.fn.UnaryFunctor;
038: import net.sf.jga.fn.comparison.EqualTo;
039: import net.sf.jga.fn.comparison.Equality;
040: import net.sf.jga.util.EmptyIterator;
041: import net.sf.jga.util.LookAheadIterator;
042:
043: /**
044: * Locates runs of repeated values in an iteration.
045: * <p>
046: * Copyright © 2003-2005 David A. Hall
047: *
048: * @author <a href="mailto:davidahall@users.sf.net">David A. Hall</a>
049: * @deprecated
050: */
051:
052: public class FindRepeated<T> extends LookAheadFunctor<T> {
053:
054: static final long serialVersionUID = 2382887791885942503L;
055:
056: // the size of the run sought
057: private int _repeatCount;
058:
059: // functor used to determine if the element should be included in the run
060: private UnaryFunctor<T, Boolean> _eq;
061:
062: /**
063: * Builds a FindRepeated functor that will look for a run of the given size,
064: * using the equals() method.
065: */
066: public FindRepeated(int count, T value) {
067: this (count, new EqualTo<T>().bind2nd(value));
068: }
069:
070: /**
071: * Builds a FindRepeated functor that will look for a run of the given size,
072: * using the given equality functor.
073: */
074: public FindRepeated(int count, T value, Equality<T> eq) {
075: this (count, eq.bind2nd(value));
076: }
077:
078: /**
079: * Builds a FindRepeated functor that will look for a run of the given size,
080: * using the given functor. The functor is expected to return TRUE if the
081: * element should be included in the run.
082: */
083: public FindRepeated(int count, UnaryFunctor<T, Boolean> eq) {
084: if (count < 0)
085: throw new IllegalArgumentException("count < 0");
086:
087: _repeatCount = count;
088: _eq = eq;
089: }
090:
091: /**
092: * Returns the length of the run being sought
093: */
094: public int getRunLength() {
095: return _repeatCount;
096: }
097:
098: /**
099: * Returns the functor used to determine if the element should be included
100: * in the run
101: */
102: public UnaryFunctor<T, Boolean> getComparisonFn() {
103: return _eq;
104: }
105:
106: /**
107: * Locates the first/next run of the given length containing elements that
108: * meet the given criteria.
109: * @return an Iterator whose next() [if it hasNext()] points at the first
110: * element in the desired run. If no such run of elements exists, then the
111: * returned iterator's hasNext() will be false.
112: */
113: public LookAheadIterator<T> fn(Iterator<? extends T> iterator) {
114: // return early if the input iterator is already finished,
115: if (!iterator.hasNext() || _repeatCount == 0) {
116: return new LookAheadIterator<T>(iterator, 1);
117: }
118:
119: LookAheadIterator<T> lai = wrap(iterator, _repeatCount);
120:
121: OUTER: while (lai.hasNextPlus(_repeatCount)) {
122:
123: // ... examine the contents of the look ahead buffer ...
124: for (int i = 1; i <= _repeatCount; ++i) {
125: T arg = lai.peek(i);
126:
127: // ... and if we find something in the buffer that isn't
128: // 'equal', then we'll advance past that point in the iterator
129: // and try again
130: if (!_eq.fn(arg)) {
131: for (int j = i; j > 0; --j) {
132: lai.next();
133: }
134:
135: continue OUTER;
136: }
137: }
138:
139: // If we safely got off the end of the INNER loop, then we must
140: // have found the point we're looking for.
141: return lai;
142: }
143:
144: // didn't find anything, make an iterator that will return false.
145: return new LookAheadIterator<T>(new EmptyIterator<T>(), 1);
146: }
147:
148: /**
149: * Calls the Visitor's <code>visit(FindRepeated)</code> method, if it
150: * implements the nested Visitor interface.
151: */
152: public void accept(net.sf.jga.fn.Visitor v) {
153: if (v instanceof FindRepeated.Visitor)
154: ((FindRepeated.Visitor) v).visit(this );
155: else
156: v.visit(this );
157: }
158:
159: // Object overrides
160:
161: public String toString() {
162: return "FindRepeated[" + _eq + "]";
163: }
164:
165: // AcyclicVisitor
166:
167: /**
168: * Interface for classes that may interpret an <b>FindRepeated</b> functor.
169: */
170: public interface Visitor extends net.sf.jga.fn.Visitor {
171: public void visit(FindRepeated host);
172: }
173: }
|