This page demonstrates the effectiveness of component level programming by showing off many of our ActiveX controls.

Traditionally, an introduction to components will show you a few user-interface widgets like radio knobs, flashing colored circles and other worthess junk. It's hard to gain an appreciation of component-level programming when all of the examples are worthless or silly.

The examples on this page are neither worthless nor silly.

We have included several highly-complex components that perform useful and interersting tasks. Just imagine what powerful applications you could create with tools like these!

The examples are divded into a number of different categories. The most useful examples are in the area of Design Automation of VLSI circuits, but there are many others.

Choose your favorites from the menu below.


VLSI Design Automation

The Schematic Capture Control

The following examples demonstrate a component called Schem32. The long name is "The Schematic Capture Control." This control enables you to draw gates and the wires that connect them. A shape library is used to draw the shapes. The shapes are initially created using vector graphics, so they can be resized without losing quality.

Tutorial On Logic Design
This example teaches elementary logic design using the schematic capture control. It also illustrates the background editing feature of the control, since some of the diagrams are drawn by the web-page scripts.

The Schematic Editor
This example shows the schematic capture control with a fully enabled set of controls. In addition, a background simulator is provided, which enables circuits to be simulated as they are created.

Logic Design Course--Preliminary pages
The purpose of this example is to demonstrate an "electronic textbook" than contains embedded active examples that the student can run, and change. The idea is that this textbook will provide all of the tools needed for study right on the textbook pages. Someday, I believe, it will be possible to print examples like this on ordinary paper, but this will require substantial improvements in the printing process to include things like electronic circuits, display cells, and batteries to be printed on a sheet of paper. (OK, so I'm nuts, but just you wait!)

Click Here for the schem32 source code.

The Cell Editor Control

Cell Editor (For Schematic Editor)
A cell-library is used to provide the gate shapes. In fact, the schematic capture control could be used to draw other sorts of schematics by providing a different shape library. This example shows how to create new shapes and shape libraries using the library editor control.

Help for Cell Editor
This set of web pages will tell you how to use the cell editor web page to create your own cell library, and will also tell you how to integrate the cell editor control into your own applications.

Click Here for the cell-editor source code.

Full-Featured Hardware Simulator

FHDL Simulator
The FHDL simulator provides a full-featured simulation system for hardware structures. Included in the simulation system are standard gates: AND, OR, NOT XOR, NAND, NOR, XNOR, and BUFFER. There is a complete collection of flip-flops, unclocked, clocked, and complementary-clocked. There are high-level structures such as ALUs, REGISTERs, MULTIPLEXERS, DEMULTIPLEXERS, and many others. There are basic specifications for ROMs, PLAs, Algorithmic State Machines, BLIF specifications, and high-level expressions. There are auxilliary design languages for enhancing the specification of ROMs and PLAs. There is a highly powerful macro language that can be used to add additional features not in the basic language. There are several different simulators, but the most full-featured one is the UNIT-DELAY simulator. The web-page does not support BLIF specifications or expressions, but there are downloads to fix this problem.

The functions implemented by this simulator are broken into several ActivX controls. You can download the source for most of these here. The tool-bar, menu and editing windows are provided by two commercial controls, ActiveBar for the menu and tool bars, and AllText for the editing windows. The Microsoft comdlg32.ocx control is used to provide dialog boxes. Obviously, we can't give you the source for these three, but everything else is available.

Click here for the source to VdalCdlg.ocx.
This control provides some additional dialog boxes.

Click here for the source to FhdlParser.ocx.
This parses a file or a string containing FHDL code and returns a pointer to a datastructure that can be inserted into a simulation control.

Click here for the source to cnetlist.lib.
This library describes the parsed structure of an FHDL circuit, and is required by several other components, including FhdlParser and UnitDelay.

Click here for the source to UnitDelay.ocx.
This control accepts a pointer from FhdlParser.ocx (or some other component) and simulates the circuit contained in the data structure. The component must be supplied with input vectors to perform the simulation. One or more output vectors are produced for each input vector supplied.

Click here for the source to LookCkt.ocx.
This control accepts a pointer from FhdlParser.ocx (or some other component) and provides a programmer interface to the internals of the data structure.

Click here for the source to FHDLWizard.ocx.
This control provides several sets of dialog boxes that implement the wizards provided by the user interface. There is a register wizard, a counter wizard, and an ALU wizard. Why don't you add more?

Click here for the source to FHDLROM.ocx.
This control contains the ROM preprocessor. It processes an FHDL file and replaces the ROM descriptions with native FHDL ROM specifications.

Click here for the source to FHDLPLA.ocx.
This control contains the PLA preprocessor. It processes an FHDL file and replaces the ROM descriptions with native FHDL PLA specifications.

Click here for the source to FHDLMacro.ocx.
This control contains the Macro preprocessor. It processes an FHDL file removes the Macro definitions and executes all macro calls.

Additional Components

I don't know the status of these components, but I'm placing the source code here because it may prove useful.

Generate VLDL from FHDL. Source Code

Parse BLIF code. Source Code

Zero Delay Simulator. Source Code

Multi-Delay Simulator. Source Code

Nominal Delay Simulator. Source Code

Quine-McClusky Minimizer. Source Code

I've also done some work on Boolean Expressions, but I don't think it ever got far enough to publish here.

Routing Demos

These examples implement well-known routing algorithms, but the output is not actually in layout form, so they are just demos. (OK, why don't you implement that part?)

Left Edge Channel Router -- Demo
The well-known left-edge algorithm. This algorithm uses the vertical constraint graph to do the routing, and is incapable of dealing with circular vertical constraints.

The left-edge router is broken into three components. A commercial control, AllText, is used to enter the channel data. The source for AllText is not available. The source for the other three components is available below.

Click here for the source code for FHDLButton.ocx.
I wanted to have a button that behaved like any other component, and this took about three seconds to create. You might as well have it.

Click here for the source code for ChanParse.ocx.
This control parses the input data and creates a data structure suitable for routing.

Click here for the source code for channelrouter.ocx.
This control performs the actual routing. It creates a data structure suitable for display.

Click here for the source code for channeldisplay.ocx.
This control accepts the routing data structure from ChannelRouter.ocx, and draws the channel using pretty colors. The colors are similar to those provided by the Magic editor.

Dogleg Channel Router -- Demo
This is more or less the Deutsch dogleg channel router. It actually uses the left edge algorithm to place the horizontal segments once they have been split using the Deutsch criterion. We don't use the both-ends-against-the-middle technique from the Deutsch paper because our experimental evidence suggests that this approach is inferior to the simple left-edge technique. (Contrary to claims made elsewhere.)

This router also uses several components, but only one is different from that of the left-edge demo

Click here for the source code for DogLeg.ocx.
This control performs the actual routing. It creates a data structure suitable for display.

Grid Routers -- Demo
This Example demonstrates several grid routers: The Lee Algorithm (breadth-first search), variations of the A-Star algorithm with different (but topologically equivalent) distance measures, line-probe routing, and the Lee algorithm using the both-ends-against-the-middle i.e. BEAM technique.

In this case the routing is performed by a single component, plus many buttons.

Click here for the griddef source code.
There are several OCX controls in this package.


Puzzles

Rubik's Cube

The quintessential mechanical puzzle. The animation here could use some work. Right now, the cube snaps from one position to another. Two or three intermediate positions would give a better sense of motion.

Click here to play with the puzzle.

Click here for the source code.

The Peg-Board Game

This peg-board game has been around for about a century and a half. Apparently it was first invented by a man in prison as a way to pass the time. In the 1960's it was marketed as a plastic puzzle called "Hi-Q," and you can still buy it under that name. At first it may seem that this puzzle can be solved by brute-force, since there don't seem to be that many available moves at each step. However, a brute-force trial-by-error technique would need to try over one sextillion (1,000,000,000,000,000,000,000) moves before finding the solution.

Interestingly enough, though, the puzzle can be solved quite simply by using the "Rubik's Cube" technique. In other words, the game must be partitioned into several sub-problems, each of which can be solved using a straightforward algorithm. See this page if you don't want to figure it out for yourself.

Click here to play with the puzzle.

Click here for the source code.
The source code contains an enhanced version of the control that has multi-colored pegs. The reason for the multi-colored pegs is to distinguish between the various classes of pegs. Not ever peg can be moved to every hole on the board. In fact, the number of positions for a specific peg is quite limited. In the enhanced version, if two pegs are the same color, that means they can both be moved to the same hole. If they are of differing colors, they cannot be moved to the same hole.

The Towers of Hanoi

This puzzle is frequently given as an assignment to students in early programming courses. It is an example of a problem that appears to be highly complex, but can be solved quite simply and efficiently using a recursive algorithm. The traditional version of this problem has 8 disks, but there can be any number. The ActiveX control supports an arbitrary number of disks. Using a larger-than-normal number of disks can be quite time consuming, however, since adding one disk doubles the amount of time necessary to solve the problem.

Legend has it that there is a Buhdist monastary somewhere in Asia where the monks are working on a 64-disk version of this puzzle. As the legend goes, the world will end when the puzzle is solved. The actual number of disk-moves necessary to solve a 64-disk puzzle is 18,446,744,073,709,551,615. At one move per second, this would require 584,542,046,088 years to solve the puzzle. Perhaps the legend is correct.

Click here to play with the puzzle.

Click here for the source code.

Lucky 15

This is the old sliding number game with 15 numbered squares that you slide around in a framework to put them in order. The puzzle was invented by Sam Loyd in the 1870's, who called it the 15 puzzle, or sometimes the 14-15 puzzle. The alternative name comes from a once-famous challenge which is to rearrange the pieces so the puzzle is solved, except for the 14 and 15, which are reversed. (There is no way to do this.) The puzzle was the "Rubik's Cube" of its time. I got one of these back in the 1950's when I was a child, and was delighted to find that I could solve it. (I also solved Rubik's Cube with no help, but that's another story.)

Click here to play the game.

Click here for the source code.

Pentominos

This is another mechanical puzzle I got when I was in 5th grade. There is no trick to solving this one, you just have to work at it. Despite the fact that is unbelievably difficult to solve, there are literally thousands of distinct solutions. We offer two different pentominos controls, one that uses Microsoft Foundation Classes (MFC) and one that uses the Active Template Library (ATL). The presentations are also somewhat different.

Click here to play with the MFC Version.
This is a "Watch only" version. If you want to try your hand at solving the puzzle yourself, try the ATL version.

Click here for the MFC source code.

Click here to play with the ATL version.
This version allows you to solve the puzzle yourself if you wish. You'll probably give up, but when you do, you can click on the "Solve" button and the computer will finish the job for you. Unlike the MFC version, which computes a single solution, clicking "Solve" repeatedly will produce successive distinct solutions to the puzzle. The same control is used to display both the game board and the individual pieces.

Click here for the ATL source code.

Card Games

I really wanted to have a couple of card games on this website, so I created the "cards" ActiveX control for this purpose. This control displays either a stack of cards or a single card and can be used in the background to shuffle cards. Several different decks can be used. The source code contains an enhanced version of the control that can be used to implement undos. A web page is included that shows how this feature can be used with Seahaven Towers. The two following card games are two of my favorites.

Seahaven Towers
Free Cell

Click here for the source code.

Once you're done here check this out: Puzzle Games resources - a directory of Puzzle Games related websites.


Visualizations

Visualization is a complex field in its own right, but using ActiveX controls we can start with some simple visualizations, and perhaps work up to others that are more complicated. There are many visualizations here, some are of algorithms, some are of mathematical structures. These examples just scratch the surface. Much more could be done in this area.

The Rose

Click Here for an illustration of The Rose
The Rose is a figure that is generated by discretely sampling the polar coordinate function T=sin(n*r) at discrete intervals and joining the points with straight lines. One can vary the frequency (n) the distance between sample points (d) and the number of sub-divisions of the circle (s). These parameters have a profound effect on the generated figure. If the parameter (d) divides (s) evenly, then there are several subsets of points called cosets. Our algorithm generates all cosets when there is more than one.

Click here if you already know about the rose but just want to play with the parameters.

Click here for the source code.

Polynomials and Rational Functions

Polynomial Visualizations
This component is capable of graphing any polynomial or any rational function at any level of resolution. There are a few pitiful examples embedded in the web page, but don't believe for an instant that this is all that is available. The component is also capable of differentiating any polynomial or rational function and drawing the tangent at any point of the curve. Areas under the curve can be swept out, and droplines can be dropped at any point. The web page animates some of these operations, but a static display is the norm.

Click here for the source code.

Graph Algorithm Animations

The graphs illustrated in these examples aren't necessarily the best. You can load other graphs if you wish, because the underlying framework is capable of accepting graph input and drawing it.

Depth First Search
The recursive algorithm. What are the important modification points of this algorithm? (First visited, backing up to, backing up from.)

Click here for the source code.

Breadth First Search
Change the stack to a queue and you've got Breadth First Search. In the first section of this page, we called this "The Lee Algorithm." The two are essentially the same.

Click here for the source code.

Connected Components
Identify the connected components of a graph, and number each vertex with the number of the component that contains it.

Click here for the source code.

Minimum Spanning Tree
Generate the minimum-cost tree that will keep the graph connected. This control illustrates the Dijkstra-Prim Algorithm.

Click here for the source code.

Kruskal MST
Generate the minimum-cost tree that will keep the graph connected. This control illustrates the Kruskal Algorithm.

Click here for the source code.

Shortest Path
Find the shortest (cheapest, fastest) path from vertex A to vertex B.

Click here for the source code.

Standard Sort Animations

These algorithms speak for themselves.

Bubble Sort
Source Code

Heap Sort 
Source Code 

Insert Sort
Source Code 

Quick Sort
Source Code 

Quick Sort Split
Source Code 

Radix Sort
Source Code 

Repeated Minimum Sort
Source Code 

Merge Sort
Source Code 

Bubble-Sort Enhancements

Plain Bubble unenhanced  bubble-sort with bars left red after termination for comparison with the other enhanced algorithms. Source Code

YoYo Bubble Bubble Sort with alternating direction of scans. (Erroneously called "cocktail shaker" by Knuth ) Source Code

Long Bubble Bubble Sort (YoYo) with single-pass preconditioning. List is scanned "both ends against the middle" and if two inverted keys are found, they are exchanged. Source Code

LSM1 Bubble Last-Swap-Minus-1 Bubble Sort. Full scans of keys are shortened by keeping track of the position of the last swap in each scan. When the scan reverses, it begins at the position of the last swap "minus 1". Source Code

Tree Bubble Enhanced bubble sort with log-n preconditioning steps. Both-Ends-Against-The-Middle swaps are done on the whole list, then on the first and second halves, then on the first, second, third, and fourth quarters, and so forth until pairwise exchanges are being done. Source Code

Shell Sorts

Shell Sort Standard Shell sort with key separations of n/2, n/4, n/8, ..., 1. (Integer division with loss of remainder.) Insert sort is the base sort. Source Code

Long Jump Sort Shell Sort with key separations same as above, but using bubble-sort as the base sort. Source Code

Enhanced Long Jump Shell sort with key separations as above, but using LSM1 Bubble sort (without preconditioning) as the base sort. Source Code

Strange Sorts

Reversed Sequence Sort Do a brute-force scan through the list looking for a descending sequence of keys. Reverse the keys doing a both-ends-against-the-middle swap. Continue until no descending sequence is found. This animation is "artificially enhanced" to make it seem faster than it really is. Source Code

Reversed Sequence Bubble Standard bubble sort with an reversed-sequence search. (Since we're going that way anyway.) Source Code

Reversed Sequence YoYo Same as above, but using yoyo scans. Source Code

Reversed Sequence Preconditioned YoYo Same as above, with single-pass preconditioning. Source Code


This page and its contents are Copyright 2000-2007, Peter M. Maurer.
For comments and complaints send mail to peter_maurer@baylor.edu.
Home pagehttp://cs.baylor.edu/~maurer>