require "csim"
# This represents a compound of gates. It has an interface similar enough
# to Gate to be used in place of one, though it isn't derived from Gate.
# Ruby thinks this is just fine.
# To build compound circuits, you must create a Blueprint. To do so:
# 1. Create the Blueprint object.
# 2. Create the objects, and connect them to each other. Don't make
# any external connections.
# 3. As needed specify gates you create as input or output devices for
# the compund.
# 4. Call lock(). This completes the Bluprint and makes it ready to
# generate compounds.
# The resulting Blueprint is also a Compound. It can be connected and used
# like a Gate (though it is not derived from Gate). The another method
# of Blueprint creates a Compound, which can be used in a circuit, but
# lacks the building infrastructure. The Compound remembers its Blueprint,
# and its another method simply calls the one in Blueprint.
#
# You should not add the same component to multiple compounds.
class Compound
protected
# This is called only by Blueprint. Clients don't get to create
# Compounds themselves.
def initialize(ingates, outgates, blueprint)
@ingates = ingates # Initially array of input gates, replaced
# on each connect with a connection to it.
@conndex = -1 # Index for connecting to it.
@outgates = outgates # Array of output gates.
@joindex = -1 # Index for joining.
@blueprint = blueprint # Our blueprint object.
end
public
# Connect to a specific input port.
def portconn(port, v)
c = @ingates[port]
c.signal(v)
return Gate::LinkHandle.new(self,port)
end
# Connect to the next input port.
def connect(v)
return portconn(@conndex += 1, v)
end
# Join an output to another device. Outputs are joined in the order
# specified by outputs, or out(n) may be used to join to a specific output.
def out(n)
return @outgates[n]
end
def join(gate)
@outgates[@joindex += 1].join(gate)
end
# Handle inbound signals.
def signal(port, val)
Gate.activate
@ingates[port].signal(val)
Gate.deactivate
end
# All the links on the output list, except for internal connections.
def outlinks
ret = [ ]
for i in (0...@outgates.length)
outs = @outgates[i].outlinks
for j in (0...outs.length)
ret.push(outs[j]) if outs[j] && @blueprint.internmap[i][j] != 1
end
end
return ret
end
# This creates another one of us. This runs in the blueprint, which
# has more information.
def another
return @blueprint.another
end
# Create several others of us in an array.
def manyothers(n)
ret = []
n.times { ret.push(self.another) }
return ret
end
# For prettier printing.
def to_s
ret = self.class.to_s
st = @blueprint.subtype
ret += " [" + st + "]" if st
return ret + " " + self.object_id.to_s
end
end
# Class Blueprint is used to describe a component made of other components.
class Blueprint < Compound
# Note: Initialization is not really complete until the lock method is
# called.
def initialize(subtype = nil)
super([], [], self)
@allgates = [ ] # This is a list of connections to internal gates
# which represent the device inputs.
@allcons = [ ] # List of [src, sink] in proper connect order.
@internmap = [ ] # For each output gate, a mask of connections which
# are internal.
@subtype = subtype
end
# Specify gates as inputs to the circuits. You may specify any number of
# Gates or Compounds, or arrays thereof. Each input makes a connection to
# the specified gate in the order given; gates may be repeated when the
# they form more than one input. If input order matters, be careful to
# mix the specification of gates as inputs, and the joining of internal
# connections, in the correct order.
def inputs(*gates)
for g in flatten(gates)
@ingates.push(g.connect(false))
end
end
# This specifies some gates which are outputs. Gates, Compounds, or arrays
# thereof may be specified. Output connections are made to these gates
# in the order given. Gates may be repeated to supply multiple ouputs.
# It is also possible to use a specific output connection number to
# join multiple devices to the same port.
def outputs(*gates)
@outgates += flatten(gates)
end
# This closes the definition. It finds all the objects in the collection,
# and makes a list of pairs that can be used to reproduce all the connections
# preserving relative order at each end. This involves a topological sort.
# Yecccch.
def lock
# Create the initial pending list of all input gates, plus all the
# output gates (which should be redundant, but ...)
gset = { }
((@ingates.map { |c| c.sinkg }) + @outgates).each { |g| gset[g] = true }
pend = gset.keys
# Process pending gates for outlinks. Find all devices which are
# connected downstream from an input or output.
while g = pend.shift
# Scan the receiving gates. We take the list of outbound connections
# and extract the sink gates therein, and run through that.
for t in g.outlinks.map { |lnk| lnk.sinkg }
if ! gset.has_key?(t) then
# If not already in the set, add it to the set and the pending list.
pend.push(t)
gset[t] = true
end
end
end
# These are all the reachable gates; all the gates in the device.
@allgates = gset.keys
# Allocate graph nodes for each connection. This allocates a node for
# each connection between two contained gates. Each node is an array
# of the form
# [ srcnext, sinknext, predcnt, src, sink ]
# Where the first two point to nodes that come later in the order at
# the source or destination (respectively), predcnt is an integer number
# of nodes which must come before this one, and src and sink are the
# gates at the start and end of the connection. This loop allocates
# such nodes for each connection, adds links (only) for the source
# ordering, and places them in a hash so we can find them by destination.
nmap = { }
n = 0
for g in @allgates
lnode = nil # Previous node in source ordering.
for c in g.outlinks
# Create the node and store it in the hash.
key = [ c.sinkg, c.sinkp ]
node = [ nil, nil, (if lnode then 1 else 0 end), g, c.sinkg ]
nmap[key] = node
# Add a link here to the previous node.
lnode[0] = node if lnode
lnode = node
end
n += 1
end
# This adds more nodes to represent the array of input links. These
# nodes are like the above, except source position is nil.
lnode = nil
for c in @ingates do
key = [ c.sinkg, c.sinkp ]
node = [ nil, nil, (if lnode then 1 else 0 end), nil, c.sinkg ]
nmap[key] = node
lnode[0] = node if lnode
lnode = node
end
# Now we go through and add links representing the ordering at the
# destination.
for k in nmap.keys # Scan all node keys.
gate, port = k # Get the destination information
targ = [gate, port+1] # Get key of next node in destination order
if nmap.has_key?(targ) # See if such a node exists.
tnode = nmap[targ] # Get the sink successor from the hash.
tnode[2] += 1 # Increment its pred. count for source node.
nmap[k][1] = tnode # Add a link from source to sink node.
end
end
# Find all the roots (nodes without predecessors). This is the initial
# value of links which may be established, since all links which must
# appear earlier have been created.
ready = nmap.values.select { |n| n[2] == 0 }
# Traverse the graph obeyong all the constratints and produce a list
# of connections in an order which will preserve the order at each end.
# That preserves the creation order of the links in case it matters.
@allcons = [ ]
while n = ready.shift
# Extract the contents of the ready node and add the relevant information
# to the output order list.
srcnext, sinknext, count, source, sink, sinkp = n
@allcons.push([source, sink])
# Reduce the count of each successor, and add it each to the ready list
# if it has no more predecessors.
if srcnext then
srcnext[2] -= 1;
ready.push(srcnext) if srcnext[2] == 0
end
if sinknext then
sinknext[2] -= 1;
ready.push(sinknext) if sinknext[2] == 0
end
end
# This makes a record of all internal links outbound from output
# devices. These are not to be reported as connections out from the
# compound. They are recorded in an array parallel to @outgates.
# For each output gate, they contain a bitmap showing ones for each
# position occupied at this time.
@internmap = @outgates.map do |g|
ret = 0
bit = 1
g.outlinks.each { |c| if c then ret &= bit end; bit <<= 1; }
ret
end
# Whew!
end
# Make a Compound like this one.
def another
# Make copies of all the objects, and keep a map from the original to the
# copy, so we can copy the connections.
copymap = { }
@allgates.each { |g| copymap[g] = g.another }
# Reproduce all the connections on the new gates. Use the order computed
# by close which preserves order of connections at each end.
ingates = [ ]
for c in @allcons
if c[0] then
copymap[c[0]].join(copymap[c[1]])
else
# nil source indicates an input connection
ingates.push(copymap[c[1]].connect(false))
end
end
# Construct the new compound using the new gates.
return Compound.new(ingates, @outgates.map { |g| copymap[g] }, self)
end
attr_reader :internmap, :subtype
private
# This flattens an list by opening component arrays.
def flatten(a)
ret = []
a.each { |x| if x.is_a?(Array) then ret += x else ret.push(x) end }
return ret
end
end
Ruby Example Code
Circuit Test III