Kirk Rader  1.0-SNAPSHOT
Expression.java
Go to the documentation of this file.
1 /*
2  * Copyright 2016 Kirk Rader
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package us.rader.tt.formula;
18 
19 import java.io.BufferedReader;
20 import java.io.ByteArrayInputStream;
21 import java.io.ByteArrayOutputStream;
22 import java.io.IOException;
23 import java.io.InputStream;
24 import java.io.InputStreamReader;
25 import java.io.PrintStream;
26 import java.lang.reflect.Constructor;
27 import java.util.Set;
28 
29 /**
30  * Objects with unique Graphviz node names.
31  */
32 public abstract class Expression implements Graphable {
33 
34  /**
35  * Exception thrown when a syntax error is detected while parsing an
36  * {@link Expression}.
37  *
38  * This only extends IOException as a work-around for an ill-advised
39  * SonarQube rule.
40  */
41  public static class SyntaxError extends IOException {
42 
43  /**
44  * Serialization version number.
45  */
46  private static final long serialVersionUID = 1L;
47 
48  /**
49  * @param message
50  * The exception message
51  */
52  public SyntaxError(final String message) {
53 
54  super(message);
55 
56  }
57 
58  }
59 
60  /**
61  * Character encoding for file and streams.
62  */
63  private static final String ENCODING = "UTF-8";
64 
65  /**
66  * Make {@link #nodeName} unique per instance.
67  *
68  * Using a sequential counter rather than, for example, a hash allows
69  * {@link #nodeName} to be used for sorting columns in a truth table.
70  *
71  * @see #Expression
72  * @see Formula#toTruthTable
73  */
74  private static long counter;
75 
76  static {
77 
78  counter = 0;
79 
80  }
81 
82  /**
83  * Graphviz digraph node name.
84  *
85  * Also used to sort columns in a truth table.
86  *
87  * @see #Expression
88  * @see Formula#toTruthTable
89  */
90  protected String nodeName;
91 
92  /**
93  * Initialize {@link #nodeName}.
94  *
95  * Note that the combination of `counter` and the depth-first, left-to-right
96  * traversal of the nodes while parsing an expression results in
97  * monotonically increasing values for {@link #nodeName} that can then be
98  * used to sort the columns in a truth table.
99  *
100  * @see Formula#toTruthTable
101  */
102  protected Expression() {
103 
104  synchronized (Expression.class) {
105 
106  nodeName = "node" + ++counter;
107 
108  }
109  }
110 
111  /**
112  * Parse the next {@link Expression} from the given buffered input stream.
113  *
114  * @param reader
115  * The buffered input stream.
116  *
117  * @return The {@link Expression}
118  *
119  * @throws IOException
120  * Thrown if an I/O error occurs.
121  */
122  public static Expression parseFactor(final BufferedReader reader) throws IOException {
123 
124  final int c = skipWhitespace(reader);
125 
126  if (c == -1) {
127 
128  throw new SyntaxError("unexpected end of input parsing factor");
129 
130  }
131 
132  if (c == ':') {
133 
134  return parseVariableBindingOperator(reader, Description.class, ':');
135 
136  }
137 
138  if (Character.isLowerCase(c)) {
139 
140  return new Variable(Character.toString((char) c));
141 
142  }
143 
144  throw new SyntaxError(String.format("Expression expected, got '%s'", Character.toString((char) c)));
145 
146  }
147 
148  /**
149  * Parse the next {@link Expression} from the given buffered input stream.
150  *
151  * @param stream
152  * The input stream.
153  *
154  * @return The {@link Expression}
155  *
156  * @throws IOException
157  * Thrown if an I/O error occurs.
158  */
159  public static Expression parseFactor(final InputStream stream) throws IOException {
160 
161  try (InputStreamReader streamReader = new InputStreamReader(stream, ENCODING)) {
162 
163  try (BufferedReader reader = new BufferedReader(streamReader)) {
164 
165  return parseFactor(reader);
166 
167  }
168  }
169  }
170 
171  /**
172  * Parse the next {@link Expression} from the given buffered input stream.
173  *
174  * @param factor
175  * The string representation of the {@link Expression} to parse.
176  *
177  * @return The {@link Expression}
178  *
179  * @throws IOException
180  * Thrown if an I/O error occurs.
181  */
182  public static Expression parseFactor(final String factor) throws IOException {
183 
184  try (ByteArrayInputStream stream = new ByteArrayInputStream(factor.getBytes(ENCODING))) {
185 
186  return parseFactor(stream);
187 
188  }
189  }
190 
191  /**
192  * Parse the next {@link VariableBindingOperator} or {@link Description}
193  * from the given buffered input stream.
194  *
195  * @param reader
196  * The buffered input stream.
197  *
198  * @param type
199  * The type of {@link VariableBindingOperator} to create.
200  *
201  * @param terminator
202  * The terminator symbol for the operator.
203  *
204  * @return The {@link Connective}
205  *
206  * @throws IOException
207  * Thrown if an I/O error occurs.
208  */
209  protected static Expression parseVariableBindingOperator(final BufferedReader reader,
210  final Class<? extends VariableBindingOperator> type, final char terminator) throws IOException {
211 
212  try {
213 
214  int c = skipWhitespace(reader);
215 
216  if (c == -1) {
217 
218  throw new SyntaxError(String.format("unexpected end of input parsing %s", type.getName()));
219 
220  }
221 
222  final String v = Character.toString((char) c);
223 
224  if (!Character.isLowerCase(c)) {
225 
226  reader.reset();
227  throw new SyntaxError(String.format("expected a variable, got \"%s\"", v));
228 
229  }
230 
231  c = skipWhitespace(reader);
232 
233  if (c != terminator) {
234 
235  reader.reset();
236  throw new SyntaxError(String.format("expected \"%s\", got \"%s\"", Character.toString(terminator), v));
237 
238  }
239 
240  final Expression operand = Formula.parseFormula(reader);
241  final Constructor<?> constructor = type.getConstructor(Variable.class, Formula.class);
242  return (Expression) constructor.newInstance(new Variable(v), operand);
243 
244  } catch (ReflectiveOperationException | SecurityException e) {
245 
246  throw new IllegalStateException(e);
247 
248  }
249 
250  }
251 
252  /**
253  * Print the specified number of spaces to the given stream.
254  *
255  * @param stream
256  * The output stream.
257  *
258  * @param indent
259  * The number of characters to print.
260  */
261  protected static void printIndentation(final PrintStream stream, final int indent) {
262 
263  for (int i = 0; i < indent; ++i) {
264 
265  stream.print(' ');
266 
267  }
268  }
269 
270  /**
271  * Discard white space from the given buffered input stream.
272  *
273  * @param reader
274  * The buffered input stream.
275  *
276  * @return The next non-whitespace character or -1.
277  *
278  * @throws IOException
279  * Thrown if an I/O error occurs.
280  */
281  protected static int skipWhitespace(final BufferedReader reader) throws IOException {
282 
283  int c;
284 
285  do {
286 
287  reader.mark(1);
288  c = reader.read();
289 
290  } while (c != -1 && Character.isWhitespace(c));
291 
292  return c;
293 
294  }
295 
296  /**
297  * Base equality on the string representation of a formula.
298  *
299  * @see #hashCode
300  */
301  @Override
302  public final boolean equals(final Object obj) {
303 
304  if (obj == null) {
305 
306  return false;
307 
308  }
309 
310  if (!(obj instanceof Expression)) {
311 
312  return false;
313 
314  }
315 
316  return toString().equals(obj.toString());
317 
318  }
319 
320  /**
321  * @return The set of nodes for this formula (i.e. the columns of its truth
322  * table).
323  */
324  public abstract Set<Expression> getNodes();
325 
326  /**
327  * @return The set of primitive terms in this formula.
328  */
329  public abstract Set<Expression> getTerminalNodes();
330 
331  /**
332  * Base the hash code on the string representation of a formula.
333  *
334  * @see #equals
335  */
336  @Override
337  public final int hashCode() {
338 
339  return toString().hashCode();
340 
341  }
342 
343  /**
344  * Replace `boundVariable` with `factor` everywhere in this
345  * {@link Expression}.
346  *
347  * @param boundVariable
348  * The variable to replace.
349  *
350  * @param factor
351  * The new free value.
352  *
353  * @return The new {@link Expression}.
354  */
355  public abstract Expression replaceVariable(Variable boundVariable, Expression factor);
356 
357  /**
358  * @return The LaTeX representation of this object
359  *
360  * @throws IOException
361  * Throw if an I/O error occurs.
362  */
363  public final String toLaTeX() throws IOException {
364 
365  try (ByteArrayOutputStream stream = new ByteArrayOutputStream()) {
366 
367  try (PrintStream printStream = new PrintStream(stream, false, ENCODING)) {
368 
369  toLaTeX(printStream);
370  printStream.flush();
371  return new String(stream.toByteArray(), ENCODING);
372 
373  }
374  }
375  }
376 
377  /**
378  * Print the LaTeX representation of this object to the given stream.
379  *
380  * @param stream
381  * The output stream.
382  */
383  public abstract void toLaTeX(PrintStream stream);
384 
385 }
static final String ENCODING
Character encoding for file and streams.
Definition: Expression.java:63
final int hashCode()
Base the hash code on the string representation of a formula.
Expression()
Initialize nodeName.
String nodeName
Graphviz digraph node name.
Definition: Expression.java:90
Definite description (reverse iota).
static Expression parseFactor(final InputStream stream)
Parse the next Expression from the given buffered input stream.
static int skipWhitespace(final BufferedReader reader)
Discard white space from the given buffered input stream.
static long counter
Make nodeName unique per instance.
Definition: Expression.java:74
Objects that can render themselves as Graphviz digraphs.
Definition: Graphable.java:25
static Expression parseFactor(final BufferedReader reader)
Parse the next Expression from the given buffered input stream.
abstract Set< Expression > getNodes()
A variable (lower-case alphabetic character) of the monadic predicate calculus.
Definition: Variable.java:27
final boolean equals(final Object obj)
Base equality on the string representation of a formula.
static Formula parseFormula(final BufferedReader reader)
Parse the next Formula from the given buffered input stream.
Definition: Formula.java:112
static final long serialVersionUID
Serialization version number.
Definition: Expression.java:46
Objects with unique Graphviz node names.
Definition: Expression.java:32
abstract Expression replaceVariable(Variable boundVariable, Expression factor)
Replace boundVariable with factor everywhere in this Expression.
static Expression parseVariableBindingOperator(final BufferedReader reader, final Class<? extends VariableBindingOperator > type, final char terminator)
Parse the next VariableBindingOperator or Description from the given buffered input stream...
Exception thrown when a syntax error is detected while parsing an Expression.
Definition: Expression.java:41
A formula of the monadic predicate calculus.
Definition: Formula.java:51
static void printIndentation(final PrintStream stream, final int indent)
Print the specified number of spaces to the given stream.
static Expression parseFactor(final String factor)
Parse the next Expression from the given buffered input stream.
abstract Set< Expression > getTerminalNodes()