
Thanks, David, I'm going to take a break, and enjoy what's left of the day here at GMT + 7, and then think about your comments, and Luc's comments, tonight, or early am tomorrow.
I feel pretty clear that I want to implement something with both a 'verbose' form for development and testing, and a 'meanlean' form for final use. So any further thoughts about what would be the form(s) you'd like to see would be welcome.
I am a devotee of the cult of making generic dictionaries with keyvalue pairs whose keys are whatever and whose values are executable code: I'll have to see if I can bootleg that in here
best, Bill
"In the River of Delights, Panic has not failed me." Jorge Luis Borges





For mean and lean I'd definitely go for the Single Big Switch, it will be compiled to a jump table so it's constant time and without the oftenmispredicted branches that the Tree Of If's would have.
As for a dictionary with executable values, yes that'll work.. you could just make it an array though, because the key would just be an integer in the range 0  2^k without holes.
I don't expect that to be any faster than the Single Big Switch though because it's essentially doing the same thing, only the switch has less overhead because the jump table would contain the address directly rather than references to objects that contain the address (as in an array of delegates)





Hi David,
... edit #1 ...
An hour of reading on the web about what happens when switch statements get turned into IL turned out to be fascinating: in some cases ifthenelse statements are generated ... in other cases jumptables of the form you might expect when a continuous series of values are used as selector ... in other cases generic dictionaries may be generated and used as a lookup based solution, and even hashtables !
... end edit #1 ...
I took a look at the IL code generated by a switch statement with an integer selector, and I see code like this:
IL_003e: switch (IL_00c4, IL_00d8, IL_00ec, IL_0100, IL_0114, IL_0128, IL_0309, IL_013c, IL_0150, IL_0165, IL_017a, IL_018f, IL_01a4, IL_01b9, IL_01ce, IL_01e3, IL_01f8, IL_020d, IL_0222, IL_0237, IL_024c, IL_0261, IL_0276, IL_0309, IL_028b, IL_029d, IL_02af, IL_02c1, IL_02d3, IL_02e5, IL_02f7)
IL_00bf: br IL_0309
IL_00c4: ldloc.1
IL_00c5: ldloc.1
IL_00c6: ldc.i4.1
IL_00c7: ldc.i4.1
IL_00c8: ldstr "!DCBAE"
IL_00cd: callvirt instance class Test5Parameters/BigSwitchBoolIntString Test5Parameters/BigSwitchBoolIntString::SetValue(class Test5Parameters/BigSwitchBoolIntString, bool, int32, string)
IL_00d2: stloc.2
IL_00d3: br IL_0314
...
all the other cases
...
Seems reasonable to assume the IL instruction 'switch' is turned into a jumptable by the JITcompiler, but are you certain of this ? It's beyond my abilities to view/grok what's produced by JIT.
thanks, Bill
"In the River of Delights, Panic has not failed me." Jorge Luis Borges
modified on Thursday, August 25, 2011 9:27 AM





assuming your number of bools is limited to 32 (or 64) I would pack them in an uint (or ulong), then work with that. So it could look like:
uint v=0;
if (Is_A) v=0x00000001;
if (Is_B) v=0x00000002;
...
followed by your decision tree, possibly a sequence of ifs:
if (v==someValue1) {
} else if (v==someValue2) {
}...
BTW1: the first code block could possibly be avoided altogether, either by using v everywhere, or by constructing an union/overlap structure (which is slightly harder in C# than it is in C/C++).
BTW2: the second code block could possibly be avoided also: when all your cases are so similar, you could simply write something like Console.WriteLine("Test"+v+" passed");





Thanks, Luc, good to see your 'light' shining in/on CP again ! Will look forward to thinking about your ideas.
I like the idea of a dual 'logic compiler' which can create either verbose or succinct output as desired.
best, Bill
"In the River of Delights, Panic has not failed me." Jorge Luis Borges





Turns out creating an autogenerator for the 'bigswitch' form of the logictest class, as suggested by David1987, was really pretty easy.
Here's a link to a usable sample of its output[^], which I'd appreciate suggestions on in terms of code, format, style, etc.
In comments in the file is code which will test the complete matrix of logical possibilities for a three condition case.
thanks, Bill
"In the River of Delights, Panic has not failed me." Jorge Luis Borges





Hi Bill,
I had a play with this tonight and thought I'd post it for what it's worth. If the code generator needs to support a various number of boolean values, it may be of some use.
void Start()
{
bool[] bools = new bool[] { true, false, true};
string testCase = "Test case " + FindTestCase(bools);
}
int FindTestCase(bool[] bools)
{
string arrayCode = BoolArrayToBinaryString(bools);
foreach (string code in BoolArrayToBinaryStringPermuations(bools.Length))
if (code == arrayCode)
return Convert.ToInt32(code, 2);
return 1;
}
string BoolArrayToBinaryString(bool[] bools)
{
StringBuilder sb = new StringBuilder();
foreach (bool b in bools)
sb.Append(Convert.ToInt32(b));
return sb.ToString();
}
IEnumerable BoolArrayToBinaryStringPermuations(int count)
{
double max = Math.Pow(2, count);
for (int i = 0; i < max; i++)
yield return Convert.ToString(i, 2).PadLeft(count, '0');
}
[modified] took into account David's comments but decided against << due to readablity. Changed code and assigned a max variable so I was only killing the kitten once instead of at every iteration
"You get that on the big jobs."
modified on Friday, August 19, 2011 1:37 PM





RobCroll wrote: Math.Pow(2, count)
Please no. Every time you do that, a kitten dies.
Use this instead: 1 << count





I've never liked cat's anyway but wow I never knew about <<, I thought it was c syntax. Can you provide a link, google isn't play ball with "<<".
"You get that on the big jobs."






Hi Rob,
thanks, I'll look forward to studying your code tomorrow (GMT + 7 here).
Right now the prototype is coming along nicely, and here's what the current calling convention looks like for generating a 5 element matrix of boolean combinations
List<string> ExcludedCases = new List<string> {"DCBAE", "!D!C!BAE", "DCB!A!E"};
List<string> t = PermutationsManager.MakeBigSwitch
(
IsVerboseOutput: true,
IsExcludesAsComments: true,
PriorityStr: "DCBAE",
ClassTitle: "Test5Params",
Excludes: ExcludedCases
);
0. ExcludedCases List<string>: cases to be either skipped or written out as comments: here defined separately for debugging, but could just as well have been written 'inline' as the last argument to 'MakeBigSwitch.
1. IsVerboseOutput bool: controls whether output is minimal or fully commented.
2. IsExcludesAsComments bool: controls whether excluded cases are written as comments or skipped.
3. PriorityStr string: contains the order in which to write out 'switch 'case statements.
4. ClassTitle string: will be written into the generated class
5. Excludes is the List<string> of excluded cases
Given the input above, the output now looks something like this (excerpt):
using System;
using BigSwitch_0_0;
public static class Test5Params
{
public static BigSwitchBoolIntString BigSwitch3(bool D, bool C, bool B, bool A, bool E)
{
int intSelector = (D ? 0 : 16) + (C ? 0 : 8) + (B ? 0 : 4) + (A ? 0 : 2) + (E ? 0 : 1);
BigSwitchBoolIntString resultData = new BigSwitchBoolIntString();
resultData.IsSuccess = false;
switch (intSelector)
{
case 1:
return resultData.SetValue(true, 1, "!DCBAE");
break;
case 31:
return resultData.SetValue(true, 31, "!D!C!B!A!E : All Values False");
break;
default:
throw new BigSwitchFailException("Error In: Test5 parameters : DCBAE : DateTime: ");
}
}
}
The Type 'BigSwitchBoolIntString' is a helper class ... not shown here ... designed to 'package' the result of an evaluation. And 'BigSwitchFailException' ... not shown here ... is a custom Exception ... just in case demons strike.
In about another halfday, I should have all you see above fully implemented.
Appreciate any thoughts, ideas, you may have.
best, Bill
"In the River of Delights, Panic has not failed me." Jorge Luis Borges
modified on Friday, August 19, 2011 12:57 PM





I may have missed the point of what you are trying to achieve but:
taking 0 = false and 1 = true, all true/false combinations for n variables would be the numbers 0 to (2^n)1 in binary read as an array of binary flags
e.g.
n = 2
2^n = 4
0 = 00 = false, false
1 = 01 = false, true
2 = 10 = true, false
3 = 11 = true, true
it should be, therefore, possible to devise a simple algorithm that runs a for loop of i = 0 to 2^n1 and, at each iteration, deriving an array of bools from the binary representation of i
Pedis ex oris





Hi,
I am looking for an algorithm that given:
1. a bounding box 'bb => [x, y, width, height]
2. List<rectangle> 'ra => a set of rectangles r#1 ... r#n, all of which are guaranteed to be fully contained in bounding box 'bb, and all of which are guaranteed not to overlap any other rectangle
3. List





I don't know of any good way to solve it.
The way I do know, you're not going to like.
Branch & bound, where every "step" represents "extending a line in one of 3 directions (except back) by 1 unit" and the "cost" is the number of intersections. Finished when all lines have reached their targets (or when the previous best cost is exceeded, obviously).
It only works if the lines can only change direction on integer coordinates.
Bonus: expand lines in "likely good" directions first (ie. not immediately intersecting, roughly towards their goal)
Pro: it will give the right result.
Con: it will take all eternity to run.
Bonus 2: first estimate an upper bound for the cost this way:
For every pair of things that need to be connected, use A* to find the shortest path among the possible ways to connect them (A* is trivially extended that way  put all starting points on the Open list, test for "done" at all end points). Add extra cost at intersections (since the cost is positive, that will not affect the optimality of A*).
The result will be bad, but it will give a better initial bound at very little cost and thus save time.
It will still take all eternity to run.





Thanks, David, for the response.
I think you are right to (wittily) imply that this problem leads to runawayrecursion ! But I do see a parallel to this problem in algorithms used in the phototypesetting business that arrange a variablesized number of pagerectangles in a way that optimizes use of the space in each printingplate generated, and I think it must be similar to some spreadsheet financial solutions that use multiple recursive "solvers."
Here's my working pseudocode for a more practical approach:
1. for all the pairs of rectanglestobeconnected, generate the set of the shortest rectangleconnections.
2. generate the set of intersections of the possible connections, ordered by rectanglepairs with the highest number of intersections.
3. evaluate the set of intersections for each rectanglepair with intersections > #someLimit, and then reevaluate the complete set of connection points, compile the new set of intersections, and see if the number of intersections has increased or decreased: if increased return to the original set, if decreased use the new set of intersections.
4. and so on ...
I notice my eternitys are getting shorter these days.
best, Bill
p.s. Jonathan Swift: "A flea hath fleas that on him prey, and so on 'til infinity."
"In the River of Delights, Panic has not failed me." Jorge Luis Borges





Hm.. is that optimal? It doesn't seem optimal, unless I'm missing something..





Hi,
Yes, it's not optimal: both the hypothetical plan, and the shortening of eternitys
If I clearly knew what was optimal in this case, I would be busy implementing the algorithm, instead of here, humbly seeking your advice, and opinion.
best, Bill
"In the River of Delights, Panic has not failed me." Jorge Luis Borges





For starting, I think you ignore the connection point issue, that's UI, and really a lot of Graph Theory isn't concerned with physical layout. Stick with points
Your issue is intersecting paths/edges.
I used ForceBased positioning for mine...which does seem to reduce the number of overlaps, but this is more by fluke rather than design, as no part of the algo cares about the route of the edge.
But maybe you could use it to get a layout, then find any intersects, and 'shove' the lesser connected node out (randomly). That's a first thought, and there is likely to be better math out there! You'd need to tell the forcebased algo that some nodes are fixed, most I've seen don't consider that.
Your going to need some cyclic path checking I think as well, as there will be a relation between the number of cyclic paths and the ability to position the nodes with no overlap, more cycles must decrease that ability.
I've got this edge layout:
public static GraphicsPath StraightPath(Point from, Point to, Rectangle fromRect, Rectangle toRect)
{
GraphicsPath path = new GraphicsPath();
if (PointDistance(from, to) < 40)
{
path.AddLine(from, to);
return path;
}
List<Point> outputPoints = new List<Point>(6);
outputPoints.Add(from);
List<Point> inputPoints = new List<Point>(6);
inputPoints.Add(to);
bool isReversed = from.X > to.X;
int direction = from.Y >= to.Y ? fromRect.Top : fromRect.Bottom;
if (LineRectangleIntersection(fromRect, outputPoints[outputPoints.Count  1], inputPoints[inputPoints.Count  1]))
outputPoints.Add(new Point(outputPoints[outputPoints.Count  1].X, direction));
direction = from.Y <= to.Y ? toRect.Top : toRect.Bottom;
if (LineRectangleIntersection(toRect, outputPoints[outputPoints.Count  1], inputPoints[inputPoints.Count  1]))
inputPoints.Add(new Point(inputPoints[inputPoints.Count  1].X, direction));
inputPoints.Reverse();
outputPoints.AddRange(inputPoints);
path.AddLines(outputPoints.ToArray());
return path;
}
public static bool LineRectangleIntersection(Rectangle rect, Point p1, Point p2)
{
if (LineSegmentIntersection(p1, p2, new Point(rect.Left, rect.Top), new Point(rect.Right, rect.Top)))
{
return true;
}
if (LineSegmentIntersection(p1, p2, new Point(rect.Left, rect.Bottom), new Point(rect.Right, rect.Bottom)))
{
return true;
}
if (LineSegmentIntersection(p1, p2, new Point(rect.Left, rect.Top), new Point(rect.Left, rect.Bottom)))
{
return true;
}
if (LineSegmentIntersection(p1, p2, new Point(rect.Right, rect.Top), new Point(rect.Right, rect.Bottom)))
{
return true;
}
return false;
}
internal static bool LineSegmentIntersection(
float Ax, float Ay,
float Bx, float By,
float Cx, float Cy,
float Dx, float Dy)
{
float distAB, theCos, theSin, newX, ABpos;
if (Ax == Bx && Ay == By  Cx == Dx && Cy == Dy)
return false;
Bx = Ax;
By = Ay;
Cx = Ax;
Cy = Ay;
Dx = Ax;
Dy = Ay;
distAB = (float) Math.Sqrt(Bx * Bx + By * By);
theCos = Bx / distAB;
theSin = By / distAB;
newX = Cx * theCos + Cy * theSin;
Cy = Cy * theCos  Cx * theSin;
Cx = newX;
newX = Dx * theCos + Dy * theSin;
Dy = Dy * theCos  Dx * theSin;
Dx = newX;
if (Cy < 0f && Dy < 0f  Cy >= 0f && Dy >= 0f)
return false;
ABpos = Dx + (Cx  Dx) * Dy / (Dy  Cy);
if (ABpos < 0f  ABpos > distAB)
return false;
return true;
}
Which for a single node pair and edge will draw the edge without touching either node...it basically juts to outside the bounds of each node then a direct line. Looks nice though.
Forgot to say, I was thinking more of laying out the rectangles so that overlapping edges don't occur...you could just layout the rects any old way, and route the edges using something like an A* algo. But you could end up with very long windy edges...that's one issue I've got at the mo.





Thanks, CJB110, for your response ! I am going to study your code and think about it for a few days, and I am sure it will help me refine the strategy to pursue.
best, Bill
"In the River of Delights, Panic has not failed me." Jorge Luis Borges





Bill,
I have some questions about this problem.
BillWoodruff wrote: 3. List
What determines whether you have 1, 2, or 3 line segments for a rectangle pair?
Do the connections have to be made from top to top, left to left, or just in any order between the rectangle pairs, and can a point on one rectangle of the pair connect to more than one point on the other rectangle of the pair?
BillWoodruff wrote: Simplest case would be a straight line: two points; then three points for a path with one rightangle turn; and, finally four points for a path with two rightangle turns.
What do you mean "a straight line" ... "for a path with xxx rightangle turns"?
BillWoodruff wrote: Where: intersections of lines are minimized.
I am assuming that the lines are the rectangle pair connection lines from all of the pairs in the set.
Dave.





bw: "set of rectangle pairs => all in rectangle array 'ra, which need to be 'connected' by 13 line segments.">
Dave: "What determines whether you have 1, 2, or 3 line segments for a rectangle pair?"
Their position:
1. two rectangles of the same size that share either a common left, or top, can be connected with one line.
2. two rectangles, not the same size, if they share a common horizontal center, or vertical center, can be connected with one line.
3. two rectangles of same size, or variant size, which do not overlap each others bounds in such a way that two lines cannot join a centerpoint to the other rectangle's centerpoint, and that do not meet conditions 1,2 can be connected by two lines, with one 90 degree 'joint.'
4. the necessity for three lines is perhaps best expressed by an example: imagine you have r1 { 200, 200, 200, 200 } and r2 { 275, 500, 200, 200 }:
a. the shortest possible connecting line from the midpoint of the bottom of r1 to the midpoint of the top of r2 will take three lines (four points) to achieve with two 90 degree turns.
b. but, you may say, what about going from the right centerpoint of r1 and just drawing a first line out perpendicular to the r1's right, and then a line down so it falls on top of r2's right side. Nope, that's out, no overlapping like that allowed.
Dave: "Do the connections have to be made from top to top, left to left, or just in any order between the rectangle pairs, and can a point on one rectangle of the pair connect to more than one point on the other rectangle of the pair?"
1. No two rectangles can be connected by more than one line between them, but every rectangle can be connected to all other rectangles it has not already connected to.
2. all connection lines must originate from a midpoint on left, top, bottom, or right sides, and connect to a midpoint on the other rectangle's left, top, bottom, sides. Corners are out.
bw: "Simplest case would be a straight line: two points; then three points for a path with one rightangle turn; and, finally four points for a path with two rightangle turns."
Dave: "What do you mean "a straight line" ... 'for a path with xxx rightangle turns'?"
I mean that each linesegment of a connection can only be along a line parallel with either the horizontal or vertical axis of the graphics space, so segments can only be joined by a 90 degree rotation. Two points = straight line. Three points = two lines one of which will be at rightangles to the other. Four points = three lines, two of which will be at rightangles to each other.
bw: "Where: intersections of lines are minimized."
Dave: "I am assuming that the lines are the rectangle pair connection lines from all of the pairs in the set."
The 'set of connecting lines' I think of as a collection; each element of the collection contains 24 points that map to 13 linesegments, and some identifying information to be determined. Something like this:
// will compile .NET 4.0 Client
// rough sketch for Line 'primitive'
Public class ConnectingLine
{
public Rectangle sourceRectangle { get; set; }
public Rectangle sinkRectangle { get; set; }
public List<Point> cPoints { get; set; }
}
// will compile .NET 4.0 Client
// rough sketch for Line Manager Class
public static class ConnectingLines
{
// Line Collection
static internal List<ConnectingLine> ConnectingLineList = new List<ConnectingLine>();
// using automatic property initializers
public static void Add(Rectangle r1, Rectangle r2, List<Point> lPts)
{
ConnectingLineList.Add(new ConnectingLine
{
sourceRectangle = r1, sinkRectangle = r2, cPoints = lPts
});
}
}
// 'hardcoded' simulation of a call to add a new connection ...
// case where a connection requires 4 points that define 3 lines
// stick this in a method and call it
// will compile .NET 4.0 Client. Execute in a method body and inspect results
ConnectingLines.Add
(
new Rectangle (200, 200, 200, 200),
new Rectangle (275, 500, 200, 200),
new List<Point> {new Point (300,400), new Point(300,450), new Point(375, 450), new Point(375,500)}
); In the 'solution' there would be, of course, some 'engine' analyzing the Rectangles selected to be joined, and generating the appropriate calls to ConnectingLines.Add.
Whether that 'connection engine' would make a first pass to figure out the shortest possible connection for each pair of connected rectangles, and then iterate over the complete result of the first pass, to try and identify the maximum number of overlapping connections, and then try to reduce them ... or, whether the engine would, as it created each new connection, then 'backtrack' over all the previous connections and perhaps make change them, and then compute a different choice for the current connection ... well, that's beyond my 'computer science' capacity
Many thanks for your detailed response !
best, Bill
"In the River of Delights, Panic has not failed me." Jorge Luis Borges
modified on Sunday, August 7, 2011 8:48 PM





Bill,
Thank you for the detailed reply.
Comes the dawn! Multilayer circuit board design.
Dave.





Bill,
As Columbo would say "just one more thing".
BillWoodruff wrote: 1. No two rectangles can be connected by more than one line between them, but every rectangle can be connected to all other rectangles it has not already connected to.
Can one rectangle connect to more than 4 other rectangles? If so, then there can be more than one connection at any midpoint, correct?
Are there any data sets to play around with that define the bounding box, the rectangles, and the connectto list of rectangle pairs?
And, circuit board is massively too big, you are talking about chip design, right?
Dave.





Hi Dave,
Dave: Can one rectangle connect to more than 4 other rectangles? If so, then there can be more than one connection at any midpoint, correct?
Yes, a given rectangle, could have many other rectangles connecting to any of its sides midpoints.
Dave: Are there any data sets to play around with that define the bounding box, the rectangles, and the connectto list of rectangle pairs?
For right now, I'm assuming the following conditions, in addition to the ones I've described previously:
1. the bounding box of the container in which all rectangles are shown is known.
2. the location of each rectangle is known within the container.
3. the connections are made visually, at runtime, by the enduser. Of course they can be saved as a set, and saved sets can be loaded in: a set loaded in can have its connections added to connections already made after, perhaps, being filtered to exclude duplicates
Dave: And, circuit board is massively too big, you are talking about chip design, right?
No, this has nothing to do with hardware, it's more in the area of wanting to show complex interconnections between multiple hierarchical data sets. A form of "metacataloging," if you will. But I ... instinctively ... feel that the same issues must arise in printed circuitboard design, and algorithms that create mazes, etc.
Again, thanks for your time, and response. I am going to "take my head out of this problemspace for a few days" (no deadline pending here), and think about the points you and CJB110 have raised.
best, Bill
"In the River of Delights, Panic has not failed me." Jorge Luis Borges





Bill,
"just one more thing". A connection between two rectangles has 1, 2, or 3 segments with right angle turns. This I understand. I also understand that the connections must be made to and from a midpoint on a rectangle edge. Is there also a restriction that the pathway between the two rectangles must be open, i.e. that there can not be another rectangle that blocks the way (you cannot zig zag around the obstacle with a limitation of two right turns in the path)? Or, can the connections be determined solely on the basis of the two rectangles themselves and the chosen path (segmented or not), disregarding all other rectangles for the moment (maybe hyperspace connections). This is not too far fetched. I have envisioned a computer architecture in the form of a silo, where the CPUs and IO controllers communicate via IR signals (no front or back bus, just the ether), and all of the MMUs examine the request and all ignore the request except the MMU holding the address, and the returned data is sent back by the same method, and all CPUs and IO controllers examine all memory data and all ignore the returned data except the requester.
Another thing. Consider a neat layout of rows and columns for the rectangles. It appears that with the connection specifications as stated, a center rectangle can potentially connect to ANY other rectangle in its row or column or connect to ANY other rectangle in the rows or columns adjacent to its row or column, (3 possible paths for the four immediately horizontally or vertically adjacent rectangles, 2 paths for other rectangles in the same row or column, only 1 path for rectangles in adjacent rows or columns), and that there are no other possible connections for that center rectangle. Is this correct?
Dave.




