KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > sf > jga > fn > algorithm > FindSequence


1 // ============================================================================
2
// $Id: FindSequence.java,v 1.16 2006/12/05 04:52:38 davidahall Exp $
3
// Copyright (c) 2003-2005 David A. Hall
4
// ============================================================================
5
// The contents of this file are subject to the Common Development and
6
// Distribution License (CDDL), Version 1.0 (the License); you may not use this
7
// file except in compliance with the License. You should have received a copy
8
// of the the License along with this file: if not, a copy of the License is
9
// available from Sun Microsystems, Inc.
10
//
11
// http://www.sun.com/cddl/cddl.html
12
//
13
// From time to time, the license steward (initially Sun Microsystems, Inc.) may
14
// publish revised and/or new versions of the License. You may not use,
15
// distribute, or otherwise make this file available under subsequent versions
16
// of the License.
17
//
18
// Alternatively, the contents of this file may be used under the terms of the
19
// GNU Lesser General Public License Version 2.1 or later (the "LGPL"), in which
20
// case the provisions of the LGPL are applicable instead of those above. If you
21
// wish to allow use of your version of this file only under the terms of the
22
// LGPL, and not to allow others to use your version of this file under the
23
// terms of the CDDL, indicate your decision by deleting the provisions above
24
// and replace them with the notice and other provisions required by the LGPL.
25
// If you do not delete the provisions above, a recipient may use your version
26
// of this file under the terms of either the CDDL or the LGPL.
27
//
28
// This library is distributed in the hope that it will be useful,
29
// but WITHOUT ANY WARRANTY; without even the implied warranty of
30
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
31
// ============================================================================
32

33 package net.sf.jga.fn.algorithm;
34
35 import java.util.ArrayList JavaDoc;
36 import java.util.Collection JavaDoc;
37 import java.util.Collections JavaDoc;
38 import net.sf.jga.fn.BinaryFunctor;
39 import net.sf.jga.fn.UnaryFunctor;
40 import net.sf.jga.fn.comparison.EqualTo;
41 import net.sf.jga.util.EmptyIterator;
42 import net.sf.jga.util.LookAheadIterator;
43 import java.util.Iterator JavaDoc;
44
45 /**
46  * Locates a sequence that matches the given pattern.
47  * <p>
48  * To Serialize a FindSequence, the generic parameter T must be serializable.
49  * <p>
50  * Copyright &copy; 2003-2005 David A. Hall
51  *
52  * @author <a HREF="mailto:davidahall@users.sourceforge.net">David A. Hall</a>
53  * @deprecated
54  **/

55
56 public class FindSequence<T> extends LookAheadFunctor<T> {
57
58     static final long serialVersionUID = 5277671793270812331L;
59
60     // the pattern to be located
61
private Collection JavaDoc<? extends T> _pattern;
62
63     // functor used to compare elements in the iteration and the pattern
64
private BinaryFunctor<T,T,Boolean JavaDoc> _eq;
65
66     // the length of the pattern
67
private int _length;
68
69     /**
70      * Builds a FindSequence functor that locates the given pattern using the
71      * equals() method to compare elements.
72      */

73     public FindSequence(Collection JavaDoc<? extends T> pattern) {
74         this(pattern, new EqualTo<T>());
75     }
76
77     /**
78      * Builds a FindSequence functor that locates the given pattern using
79      * given functor to compare elements. If the pattern is null, then an
80      * arbitrary empty collection will be used.
81      * @throws IllegalArgumentException if the functor is null.
82      */

83     public FindSequence(Collection JavaDoc<? extends T> pattern,
84                         BinaryFunctor<T,T,Boolean JavaDoc> eq )
85     {
86         if (eq == null)
87             throw new IllegalArgumentException JavaDoc();
88         
89         _eq = eq;
90         _pattern = (pattern != null) ? pattern : new ArrayList JavaDoc<T>();
91
92         // can't be 0, as the minimum size of a LookAhead is 1
93
_length = Math.max(pattern.size(), 1);
94     }
95
96     /**
97      * Returns the pattern being sought
98      */

99     public Collection JavaDoc<? extends T> getPattern() {
100         return Collections.unmodifiableCollection(_pattern);
101     }
102
103     /**
104      * Returns the functor used to compare elements in the iteration and
105      * the pattern.
106      */

107     public BinaryFunctor<T,T,Boolean JavaDoc> getComparisonFn() {
108         return _eq;
109     }
110
111     // UnaryFunctor Interface
112

113     /**
114      * Locates a sequence that matches the given pattern.
115      * @return an iterator whose next() [if it hasNext()] points to the
116      * beginning of a sequence in the iteration that matches the given pattern.
117      * If no such sequence exists, then the returned interator's hasNext() will
118      * be false.
119      */

120     public LookAheadIterator<T> fn(Iterator<? extends T> iterator) {
121         // return early if the input iterator is already finished,
122
if (!iterator.hasNext() || _length == 0) {
123             return wrap(iterator, 1);
124         }
125         
126         LookAheadIterator<T> lai = wrap(iterator, _length);
127         
128         // So long as the LookAhead has enough room for the repeat count to
129
// possibly fit, ...
130

131     OUTER:
132         while (lai.hasNextPlus(_length)) {
133             int idx = 1;
134             
135             // ... examine the contents of the look ahead buffer ...
136
for (T obj : _pattern) {
137 // Iterator<? extends T> patternIter = _pattern.iterator();
138
// while (patternIter.hasNext()) {
139
// T obj = patternIter.next();
140
// ... and if we find something in the buffer that isn't
141
// 'equal', then advance the look ahead
142
if (!_eq.fn(obj, lai.peek(idx))) {
143                     lai.next();
144                     continue OUTER;
145                 }
146
147                 ++idx;
148             }
149             
150             // If we safely got off the end of the INNER loop, then we must
151
// have found the point we're looking for.
152
return lai;
153         }
154
155         // didn't find anything, make an iterator that will return false.
156
return new LookAheadIterator<T>(new EmptyIterator<T>(), 1);
157     }
158
159     /**
160      * Calls the Visitor's <code>visit(FindSequence)</code> method, if it
161      * implements the nested Visitor interface.
162      */

163     public void accept(net.sf.jga.fn.Visitor v) {
164         if (v instanceof FindSequence.Visitor)
165             ((FindSequence.Visitor)v).visit(this);
166         else
167             v.visit(this);
168     }
169     
170     // Object overrides
171

172     public String JavaDoc toString() {
173         return "FindSequence";
174     }
175     
176     // AcyclicVisitor
177

178     /**
179      * Interface for classes that may interpret a <b>FindSequence</b>
180      * functor
181      */

182     public interface Visitor extends net.sf.jga.fn.Visitor {
183         public void visit(FindSequence host);
184     }
185
186 }
187
Popular Tags