/
GradientRegex.java
193 lines (148 loc) · 4.33 KB
/
GradientRegex.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
package com.delta2.examples;
import java.awt.Point;
import java.util.Set;
import com.delta2.colours.Colour;
import com.delta2.colours.colourspace.ColourSpace;
import com.delta2.colours.generation.Generator;
import dk.brics.automaton.Automaton;
import dk.brics.automaton.RegExp;
/**
* Assign a unique String to each point in the canvas and supply a regular expression to the generator.
* The points will then be colored based on the Hamming distance from the String to any string the language defined by the regular expression.
* @author ssodelta
*
*/
public final class GradientRegex extends Generator {
private int len, SIZE;
private Set<String> matches;
/**
* Constructs a Gradient Regex generator.
* @param regex The regular expression to use.
* @param len The depth of the images. A depth of n will create an image with resolution [2^n, 2^n]
*/
public GradientRegex(String regex, int len){
super((int)Math.pow(2, len),(int)Math.pow(2, len));
this.len = len;
SIZE = (int)Math.pow(2, len);
constructMatches(regex);
}
private void constructMatches(String regex){
//Construct automaton from RegExp
Automaton aut = getAutomaton(regex);
//Construct DFA from NFA
aut.determinize();
//Get the automaton that accepts all strings of length n
Automaton length_n = getAutomaton("0|1|2|3").repeat(len);
//Get the complement automaton
Automaton complement = aut.complement().intersection(length_n);
complement.determinize();
//Get the automaton that accepts the language, and has a length of n
Automaton lang_n = aut.intersection(length_n);
System.out.println("Computing language...");
matches = lang_n.getStrings(len);
if(matches.size()==0){
System.out.println("Error: Empty language detected. Aborting...");
return;
}
}
/**
* Computes the hamming distance between some string k, and the set of matches.
* @param k The string
* @return
*/
private int getDistance(String k){
int dist = Integer.MAX_VALUE;
for(String s : matches){
int d = hammingDistance(s,k);
if(d==1)return 1;
if(d<dist)dist=d;
}
return dist;
}
@Override
protected Colour generate(double x, double y, double t) {
String regexPos = getRegexPos(x,y);
int d = getDistance(regexPos);
Colour c = Colour.fromColourSpace(ColourSpace.HSV, new double[]{t*d/20.0,1.0/Math.sqrt(Math.sqrt(Math.sqrt(d))),1.0/Math.sqrt(Math.sqrt(Math.sqrt(d)))});
return c;
}
private String getRegexPos(double x, double y){
return getRegexPos((int)(x*SIZE),(int)(y*SIZE));
}
private String getRegexPos(int x, int y){
String s = getRegexPos(new Point(x,y));
return s;
}
private String getRegexPos(Point p){
return regexFromPoint(p, SIZE, SIZE, len);
}
private static final String regexFromPoint(Point p, int width, int height, int len){
if(len==0)return "";
StringBuilder sb = new StringBuilder();
int hw = width / 2,
hh = height / 2;
if(p.x <= hw){ //Left side
if(p.y <= hh){ //Upper left quadrant
sb.append(0);
sb.append(regexFromPoint(
p,
hw,
hh,
len-1
));
} else { //Lower left quadrant
sb.append(2);
sb.append(regexFromPoint(
new Point(p.x,
p.y-hh),
hw,
hh,
len-1
));
}
} else { //Right side
if(p.y <= hh){ //Upper right side
sb.append(1);
sb.append(regexFromPoint(
new Point(p.x-hw,
p.y),
hw,
hh,
len-1
));
} else {
sb.append(3);
sb.append(regexFromPoint(
new Point(p.x-hw,
p.y-hh),
hw,
hh,
len-1
));
}
}
return sb.toString();
}
/**
* Converts a regex-string to an Automaton-object.
* @param regex The string representation of the regular expression.
* @return An Automaton-object representing the regular expression.
*/
private static final Automaton getAutomaton(String regex){
RegExp r = new RegExp(regex);
return r.toAutomaton(true);
}
/**
* Computes the hamming distance between two strings of equal length.
* @param s0
* @param s1
* @return
*/
private static final int hammingDistance (String s0, String s1) {
int dist = 0;
for(int i=0; i<s0.length(); i++){
if(s0.charAt(i) != s1.charAt(i))dist++;
}
return dist;
}
}