|
Hi David, excellent feedback, thanks !
I did consider writing out the nested form as you present here, but, given I was just getting into the arcane world of *.tt file editing in VS Studio, and T4 syntax (coming to it without a background in ASP.NET content/code escape syntax conventions), decided it was easier to write the more 'linear' output first. Nested 'style' is coming.
Yes, I like your idea of using integers for the conditions in a switch statement: I'm already using those values in the bit-shifting I'm doing in the code-generator, anyway. See any downside in nested switch statements ?
If the code-generator writes out a comment in each clause documenting implicit meaning of the integer in terms of the boolean variables, that's enough for code maintenance ?
I kind of like the idea of dual approach: perhaps during development and testing using the 'linear form' expression might be productive, while using the 'compiled-to-switch denser' form for possible greater execution speed ?
best, Bill
"In the River of Delights, Panic has not failed me." Jorge Luis Borges
|
|
|
|
|
Nothing like writing out by hand an example of what you want, and testing it against all possible inputs, to make you aware of issues you'll face in generating it auto-magically ... 
Wish I had the IL skills to look at how the compiler renders this and evaluate for efficiency. Is falling through to the 'default case' of a switch statement exactly the same as skipping over an 'if clause that has a 'return inside it ? I'd guess so.
Some obvious refactoring 'cries out' to be done in the 'brute force' example included here: mmm ... dare I utter the forbidden name: 'G*T*' ?
Would you really want to have beasts like this at large in your applications:
public static class NestedSwitch
{
public static string Test4(bool A, bool B, bool C, bool D)
{
int intSelectorA = A ? 8 : 0;
int intSelectorB = B ? 4 : 0;
int intSelectorC = C ? 2 : 0;
int intSelectorD = D ? 1 : 0;
switch (intSelectorA)
{
case 8:
switch (intSelectorB)
{
case 4:
switch (intSelectorC)
{
case 2:
switch (intSelectorD)
{
case 1:
return "ABCD";
default:
return "ABC!D";
}
default:
switch (intSelectorD)
{
case 1:
return "AB!CD";
default:
return "AB!C!D";
}
}
default:
switch (intSelectorC)
{
case 2:
switch (intSelectorD)
{
case 1:
return "A!BCD";
default:
return "A!BC!D";
}
default:
switch (intSelectorD)
{
case 1:
return "A!B!CD";
default:
return "A!B!C!D";
}
}
}
default:
switch (intSelectorB)
{
case 4:
switch (intSelectorC)
{
case 2:
switch (intSelectorD)
{
case 1:
return "!ABCD";
default:
return "!ABC!D";
}
default:
switch (intSelectorD)
{
case 1:
return "!AB!CD";
default:
return "!AB!C!D";
}
}
default:
switch (intSelectorC)
{
case 2:
switch (intSelectorD)
{
case 1:
return "!A!BCD";
default:
return "!A!BC!D";
}
default:
switch (intSelectorD)
{
case 1:
return "!A!B!CD";
default:
return "!A!B!C!D";
}
}
}
}
}
}
"In the River of Delights, Panic has not failed me." Jorge Luis Borges
|
|
|
|
|
I'm pretty sure the compiler is going to be silly about it and not optimize it (edit: that is to say, the nested switches) at all, but I would suggest this:
int all = intSelectorA | intSelectorB | intSelectorC | intSelectorD;
switch (all)
{
case 0:
return "!A!B!C!D";
....
case 15:
return "ABCD";
}
|
|
|
|
|
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 'mean-lean' 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 often-mispredicted 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 if-then-else statements are generated ... in other cases jump-tables 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 look-up 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 jump-table by the JIT-compiler, 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 auto-generator for the 'big-switch' form of the logic-test 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 'in-line' 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 half-day, 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^n-1 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 runaway-recursion ! But I do see a parallel to this problem in algorithms used in the photo-typesetting business that arrange a variable-sized number of page-rectangles in a way that optimizes use of the space in each printing-plate generated, and I think it must be similar to some spreadsheet financial solutions that use multiple recursive "solvers."
Here's my working pseudo-code for a more practical approach:
1. for all the pairs of rectangles-to-be-connected, generate the set of the shortest rectangle-connections.
2. generate the set of intersections of the possible connections, ordered by rectangle-pairs with the highest number of intersections.
3. evaluate the set of intersections for each rectangle-pair with intersections > #someLimit, and then re-evaluate 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
|
|
|
|
|
Your issue is intersecting paths/edges.
I used Force-Based 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 force-based 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 right-angle turn; and, finally four points for a path with two right-angle turns.
What do you mean "a straight line" ... "for a path with xxx right-angle 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 1-3 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 center-point to the other rectangle's center-point, 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 mid-point of the bottom of r1 to the mid-point 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 center-point 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 mid-point on left, top, bottom, or right sides, and connect to a mid-point 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 right-angle turn; and, finally four points for a path with two right-angle turns."
Dave: "What do you mean "a straight line" ... 'for a path with xxx right-angle turns'?"
I mean that each line-segment 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 right-angles to the other. Four points = three lines, two of which will be at right-angles 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 2-4 points that map to 1-3 line-segments, 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
});
}
}
// 'hard-coded' 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! Multi-layer circuit board design.
Dave.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
