KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > ant > internal > ui > dtd > schema > Nfm


1 /*******************************************************************************
2  * Copyright (c) 2002, 2005 Object Factory Inc.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * Object Factory Inc. - Initial implementation
10  *******************************************************************************/
11 package org.eclipse.ant.internal.ui.dtd.schema;
12
13 import org.eclipse.ant.internal.ui.dtd.IAtom;
14 import org.eclipse.ant.internal.ui.dtd.util.Factory;
15 import org.eclipse.ant.internal.ui.dtd.util.FactoryObject;
16
17
18 /**
19  * Non-deterministic finite state machine.
20  * @author Bob Foster
21  */
22 public class Nfm implements FactoryObject {
23     private NfmNode start;
24     private NfmNode stop;
25     
26     public NfmNode getStart() {
27         return start;
28     }
29     
30     public NfmNode getStop() {
31         return stop;
32     }
33     
34     /**
35      * Construct an nfm such that:
36      * <pre>
37      * start stop
38      * | |
39      * +---+ +---+
40      * | s |->| |
41      * +---+ +---+
42      * </pre>
43      * In all pictures, boxes are NfmNodes.
44      */
45     private static Nfm nfm(IAtom s) {
46         Nfm nfm = free();
47         nfm.stop = NfmNode.nfmNode();
48         nfm.start = NfmNode.nfmNode(s, nfm.stop);
49         return nfm;
50     }
51     
52     /**
53      * Construct an nfm that "wraps" an existing nfm x such that:
54      * <pre>
55      * start stop
56      * | |
57      * +---+ +---------+ +---------+ +---+
58      * | |->| x start | | x stop |->| |
59      * +---+ +---------+ +---------+ +---+
60      * </pre>
61      */
62     private static Nfm nfm(Nfm x) {
63         Nfm nfm = free();
64         nfm.start = NfmNode.nfmNode(x.start);
65         nfm.stop = NfmNode.nfmNode();
66         x.stop.next1 = nfm.stop;
67         return nfm;
68     }
69     
70     private static Nfm nfm() {
71         Nfm nfm = free();
72         nfm.start = NfmNode.nfmNode();
73         nfm.stop = NfmNode.nfmNode();
74         return nfm;
75     }
76
77     public static Nfm getNfm(IAtom s) {
78         return nfm(s);
79     }
80     
81     /**
82      * "Star" an existing nfm x.
83      * <pre>
84      * start stop
85      * | |
86      * +---+ +---------+ +---------+ +---+
87      * | |->| x start | | x stop |->| |
88      * +---+ +---------+ +---------+ +---+
89      * | | | |
90      * | +-----<------+ |
91      * +------>-------------------------+
92      * </pre>
93      * Frees x.
94      */
95     public static Nfm getStar(Nfm x) {
96         // Make the back link
97 x.stop.next2 = x.start;
98         Nfm tmp = nfm(x);
99         // Make the forward link
100 tmp.start.next2 = tmp.stop;
101         free(x);
102         return tmp;
103     }
104     
105     /**
106      * "Question" an existing nfm x: x => x?
107      * <pre>
108      * start stop
109      * | |
110      * +---+ +---------+ +---------+ +---+
111      * | |->| x start | | x stop |->| |
112      * +---+ +---------+ +---------+ +---+
113      * | |
114      * +---------------->---------------+
115      * </pre>
116      * Frees x.
117      */
118     public static Nfm getQuestion(Nfm x) {
119         Nfm tmp = nfm(x);
120         // Make the forward link
121 tmp.start.next2 = tmp.stop;
122         free(x);
123         return tmp;
124     }
125
126     /**
127      * "Plus" an existing nfm x -> x+
128      * <pre>
129      * start stop
130      * | |
131      * +---+ +---------+ +---------+ +---+
132      * | |->| x start | | x stop |->| |
133      * +---+ +---------+ +---------+ +---+
134      * | |
135      * +-----<------+
136      * </pre>
137      * Frees x.
138      */
139     public static Nfm getPlus(Nfm x) {
140         // Make the back link
141 x.stop.next2 = x.start;
142         Nfm tmp = nfm(x);
143         free(x);
144         return tmp;
145     }
146     
147     /**
148      * "Or" two existing nfms x,y -> x|y
149      * <pre>
150      * start stop
151      * | |
152      * +---+ +---------+ +---------+ +---+
153      * | |->| x start | | x stop |->| |
154      * +---+ +---------+ +---------+ +---+
155      * | |
156      * | +---------+ +---------+ |
157      * +--->| y start | | y stop |-->-+
158      * +---------+ +---------+
159      * </pre>
160      * Frees x and y.
161      */
162     public static Nfm getOr(Nfm x, Nfm y) {
163         Nfm tmp = nfm();
164         tmp.start.next1 = x.start;
165         tmp.start.next2 = y.start;
166         x.stop.next1 = tmp.stop;
167         y.stop.next1 = tmp.stop;
168         free(x);
169         free(y);
170         return tmp;
171     }
172     
173     /**
174      * "Comma" two existing nfms x,y -> x,y
175      *
176      * <p>Re-uses x so that x.stop is first
177      * transformed to y.start and then
178      * x.stop is reset to y.stop.
179      * This is as efficient as possible.
180      * <pre>
181      * x start former x stop x stop
182      * | | |
183      * +---------+ +----------+ +--------+
184      * | x start | | y start |->| y stop |
185      * +---------+ +----------+ +--------+
186      * </pre>
187      * Frees y, returns x modified.
188      */
189     public static Nfm getComma(Nfm x, Nfm y) {
190         x.stop.next1 = y.start.next1;
191         x.stop.next2 = y.start.next2;
192         x.stop.symbol = y.start.symbol;
193         x.stop = y.stop;
194         free(y);
195         return x;
196     }
197     
198     /**
199      * "{min,*}" an existing nfm x -> x[0],x[1],...,x[min-1],x[min]*
200      * Frees x.
201      */
202     public static Nfm getUnbounded(Nfm x, int min) {
203         if (min == 0)
204             return getStar(x);
205         if (min == 1)
206             return getPlus(x);
207         Nfm last1 = nfm(x), last2 = nfm(x);
208         for (int i = 2; i < min; i++) {
209             last1 = getComma(last1, last2);
210             free(last2);
211             last2 = nfm(x);
212         }
213         free(x);
214         return getComma(last1, getStar(last2));
215     }
216     
217     /**
218      * "{min,max}" an existing nfm x -> x[0],x[1],...,x[min-1],x[min]?,...,x[max-1]?
219      * Frees or returns x.
220      */
221     public static Nfm getMinMax(Nfm x, int min, int max) {
222         if (max == Integer.MAX_VALUE)
223             return getUnbounded(x, min);
224         if (max == 0) {
225             free(x);
226             return nfm((IAtom)null);
227         }
228         if (max == 1) {
229             if (min == 0)
230                 return getQuestion(x);
231             return x;
232         }
233         Nfm last = null;
234         int i = 0;
235         for (; i < min; i++) {
236             if (last == null)
237                 last = nfm(x);
238             else {
239                 Nfm tmp = nfm(x);
240                 last = getComma(last, tmp);
241                 free(tmp);
242             }
243         }
244         for (; i < max; i++) {
245             if (last == null)
246                 last = getQuestion(x);
247             else {
248                 Nfm tmp = getQuestion(x);
249                 last = getComma(last, tmp);
250                 free(tmp);
251                 //??? this is inefficient since the first failure
252 // in a sequence of x?,x?,...,x? can skip to
253 // the end rather than keep trying to match x
254 }
255         }
256         free(x);
257         return last;
258     }
259     
260     // Below here is factory stuff
261
262     /* (non-Javadoc)
263      * @see org.eclipse.ant.internal.ui.dtd.util.FactoryObject#next()
264      */
265     public FactoryObject next() {
266         return fNext;
267     }
268     
269     /* (non-Javadoc)
270      * @see org.eclipse.ant.internal.ui.dtd.util.FactoryObject#next(org.eclipse.ant.internal.ui.dtd.util.FactoryObject)
271      */
272     public void next(FactoryObject obj) {
273         fNext = (Nfm) obj;
274     }
275     private Nfm fNext;
276     private static Factory fFactory = new Factory();
277     private static Nfm free() {
278         Nfm nfm = (Nfm) fFactory.getFree();
279         if (nfm == null)
280             return new Nfm();
281         return nfm;
282     }
283     public static void free(Nfm nfm) {
284         nfm.start = nfm.stop = null;
285         fFactory.setFree(nfm);
286     }
287     private Nfm() {
288     }
289 }
290
Popular Tags