/
LogicSchematic.class.php
195 lines (155 loc) · 6.78 KB
/
LogicSchematic.class.php
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
194
195
<?php
class InvalidSchematicException extends exception {}
class LogicSchematic
{
/**
* Stores a list of gate objects instatiated in the schematic.
*/
private $gates;
private $wires;
/**
*
*/
public function __construct($gates, $wires)
{
$this->gates = $gates;
$this->wires = $wires;
//TODO: abstract to class / static /whatever
$gate_defaults = array('in' => 2, 'out' => 1, 'prefix' => '', 'infix'=>'', 'postfix' => '', 'input' => false, 'output' => false);
$this->defs = array
(
//inputs
'IN_A' => (object)array_merge($gate_defaults, array('infix'=>'a', 'input'=> true)),
'IN_B' => (object)array_merge($gate_defaults, array('infix'=>'b', 'input'=> true)),
'IN_C' => (object)array_merge($gate_defaults, array('infix'=>'c', 'input'=> true)),
'IN_D' => (object)array_merge($gate_defaults, array('infix'=>'d', 'input'=> true)),
'IN_E' => (object)array_merge($gate_defaults, array('infix'=>'e', 'input'=> true)),
'IN_F' => (object)array_merge($gate_defaults, array('infix'=>'f', 'input'=> true)),
//outputs
'OUT_Q' => (object)array_merge($gate_defaults, array('output'=> true, 'in' => 1)),
//basic gates
'AND' => (object)array_merge($gate_defaults, array('infix' => '*')),
'OR' => (object)array_merge($gate_defaults, array('infix' => '+')),
'NOT' => (object)array_merge($gate_defaults, array('in' => 1, 'prefix' => '!')),
//advanced gates
'XOR' => (object)array_merge($gate_defaults, array('infix' => '^')),
'XNOR' => (object)array_merge($gate_defaults, array('prefix' => '!', 'infix' => '^')),
'NAND' => (object)array_merge($gate_defaults, array('prefix' => '!', 'infix' => '*')),
'NOR' => (object)array_merge($gate_defaults, array('prefix' => '!', 'infix' => '+')),
);
//run some basic sanity checks
$this->sanity_checks();
}
/**
*
* $as_object : If true, the result will be returned as a LogicExpression object; if not, it will be returned as a string.
*/
public function to_expression($as_object = true)
{
//convert the object to an expression, recursively
$expr = $this->eval_recurse($this->get_output());
//convert the string into a LogicExpression object, and return it
if($as_object)
return new LogicExpression($expr);
else
return $expr;
}
private function sanity_checks()
{
$outputs = 0;
//check 1: ensure the circuit only has one output
foreach($this->gates as $id => $gate)
{
$def = $this->get_definition($id);
if($def->output)
++$outputs;
}
if($outputs != 1)
throw new InvalidSchematicException('Improper number of (identical) outputs!');
}
/**
* Returns the gate ID for the gate which connects to the given schematic's output.
*/
private function get_output()
{
//for each gate in the schematic
foreach($this->gates as $id => $gate)
{
//get the gate's definition
$def = $this->get_definition($id);
//if this gate is /the/ output
if($def->output)
{
//return the wire connected to it
$inputs = $this->get_input_gates($id);
if(count($inputs)==0)
throw new InvalidSchematicException("Nothing connected to the output!");
return $inputs[0];
}
}
throw new InvalidSchematicException("Schematic lacks an output!");
}
/**
* Returns a list of gate IDs which feed the given gate.
*/
private function get_input_gates($gate_id)
{
$gates = array();
//for each wire in the schematic
foreach($this->wires as $wire)
{
//if the wire is attached to the input of the given gate, on either end, add it to our list of input wires
//case 1: gate is attached to the wire's source
if($wire->src->moduleId==$gate_id && (strpos($wire->src->terminal, '_INPUT')===0))
$gates[] = $wire->tgt->moduleId;
//case 2: gate is attached to the wire's target
if($wire->tgt->moduleId==$gate_id && (strpos($wire->tgt->terminal, '_INPUT')===0))
$gates[] = $wire->src->moduleId;
}
//if we have the wrong number of inputs for the gate type, throw an exception
if(count($gates) != $this->get_definition($gate_id)->in)
throw new InvalidSchematicException('Inputs missing from one or more gates!');
//return the matched wires
return $gates;
}
/**
* Performa a recursive descent down the abstract syntax (sub)tree rooted at target gate,
* and returns the logical expression represented.
*
* Should not be called with the output gate.
*/
private function eval_recurse($target)
{
//base case: the object in an input
if($this->get_definition($target)->input)
{
//return its name
return $this->get_definition($target)->infix;
}
//recursive case: the object is a gate
//(We know the gate isn't an input from above,
//and we assume we're never going to be called with the output gate.)
//get the defintion for the given gate
$def = $this->get_definition($target);
//and get a list of gates which feed this one
$input_gates = $this->get_input_gates($target);
//recurse for each of the input gates
$subexprs = array_map(array($this, 'eval_recurse'), $input_gates);
//and merge the given subexpressions into one expression
return $def->prefix .'('. implode($def->infix, $subexprs) .')' . $def->postfix;
}
private function get_definition($gate_id)
{
return $this->defs[$this->gates[$gate_id]->name];
}
public static function from_JSON($json_string)
{
//decode the given schematic
$schema = json_decode($json_string);
//test for bad schematic
if($schema == false)
throw new InvalidSchematicException('Did not receive a valid schematic response.');
//create a new schematic from the list of modules (gates) and wires
return new LogicSchematic((array)$schema->working->modules, (array)$schema->working->wires);
}
}