what is the best method of coding a decision tree with options that have three states and all options are additive?

clarification: i have a situation with 5 (at this time) options and all 5 are three state... each option can be paired with all other options' states but may NOT be paired with its own other states...

eg:
optionA : min/max, min, max
optionB : min/max, min, max
optionC : min/max, min, max
optionD : min/max, min, max
optionE : min/max, min, max

optionA can be used as :
optionA:min/max
optionA:min only
optionA:max only
optionA:min/max AND optionB:min/max
optionA:min/max AND optionB:min only
optionA:min/max AND optionB:max only
optionA:min only AND optionB:min/max
optionA:min only AND optionB:min only
optionA:min only AND optionB:max only
optionA:max only AND optionB:min/max
optionA:max only AND optionB:min only
optionA:max only AND optionB:max only
optionA:min/max AND optionC:min/max
optionA:min/max AND optionC:min only
optionA:min/max AND optionC:max only
optionA:min only AND optionC:min/max
optionA:min only AND optionC:min only
optionA:min only AND optionC:max only
optionA:max only AND optionC:min/max
optionA:max only AND optionC:min only
optionA:max only AND optionC:max only
optionA:min/max AND optionD:min/max
optionA:min/max AND optionD:min only
optionA:min/max AND optionD:max only
optionA:min only AND optionD:min/max
optionA:min only AND optionD:min only
optionA:min only AND optionD:max only
optionA:max only AND optionD:min/max
optionA:max only AND optionD:min only
optionA:max only AND optionD:max only
optionA:min/max AND optionE:min/max
optionA:min/max AND optionE:min only
optionA:min/max AND optionE:max only
optionA:min only AND optionE:min/max
optionA:min only AND optionE:min only
optionA:min only AND optionE:max only
optionA:max only AND optionE:min/max
optionA:max only AND optionE:min only
optionA:max only AND optionE:max only

and so on with each additional options and its three states... as you can see, the sheer number of combinations is huge!

in my original attempt i started with if/then/else but that got very hard to follow very fast... so i decided to implement all the options in a bitmap so i could more easily use a case statement and simply list the decimal value of the valid bit patterns as the selection option... that is much easier to follow but can easily get confused...

it has been many years since i've had to code such a decision tree and my (20+ year) old code is not available for me to dig out and (try to) follow... so i'm asking how you would handle this situation so as to make it easy to implement, easy to grok, easy to follow when reading the code AND easy to expand or shrink if/when necessary...

[...]

no one has any ideas or thoughts on this?

i can be contacted offlist about this if one prefers ;)

Maybe I don't understand the question. The 5 options with each 3 states sounds like an array[1..5] of TRedGreenBlue.
What do you mean with "additive" and why a decision tree?

i can be contacted offlist about this if one prefers ;)

Mattias

that's quite possible... it took me a while to write it the way i did after starting over numerous times... i may have also used the wrong terms for what i was trying to describe as well as not giving enough examples but the example list was getting too large at that point anyway ;)

The 5 options with each 3 states sounds like an array[1..5] of TRedGreenBlue.

a lot of stuff i googled up related to 3states came up with similar... to me that reads as to be used for graphics and this is a console app with no graphics involved... i'm only using the bits to denote the combinations available... they select which IF statement is used in the actual filter code described below...

originally i had thought of using an array but i didn't know the size of it and each grouping varies with the number of options...

What do you mean with "additive"

logical AND with some combinations being invalid...

eg:
optionA:min/max {solitary}
optionB:max only AND optionE:min only {two ANDed together} optionA:min only AND optionB:min/max AND optionC:max only {three ANDed together}

optionA:min/max AND optionA:min only {invalid}
optionA:min/max AND optionA:max only {invalid}
optionA:min only AND optionA:max only {invalid}

and why a decision tree?

because it is used as the (right now) output filter ("tree" of "decisions" to be made) determining what gets written to the resulting file from the (currently) 30000+ entries loaded in a sorted, no-dupes collection... there are also plans to implement the exact same thing as an input filter to limit the data being loaded into the collection...

eg:
case foo of

   0 : writeoutput;
   1 : begin
         if (rec^.optionA >= optionA_min) and (rec^.optionA <= optionA_max) then
           writeoutput;
       end;
   2 : begin
         if (rec^.optionA >= optionA_min) then
           writeoutput;
       end;
   3 : begin {invalid} end;
   4 : begin
         if (rec^.optionA >= optionA_max) then
           writeoutput;
       end;

[...]
1316 : begin
if (rec^.optionA >= optionA_min) AND
(rec^.optionB >= optionB_min) AND
(rec^.optionC >= optionC_min) AND
{optionD not used in this one}
(rec^.optionE >= optionE_min) then

              writeoutput;
          end;

[...]
18506 : begin
if (rec^.optionA <= optionA_max) AND
(rec^.optionB >= optionB_min) and (rec^.optionB <= optionB_max) AND (rec^.optionC >= optionC_min) and (rec^.optionC <= optionC_max) AND (rec^.optionD >= optionD_min) AND
(rec^.optionE >= optionE_min) then

               writeoutput;
           end;

the current idea is to use a bit for each "state" and then use a case statement for the "decision tree" (as shown above) so as to simply walk thru the integers that the bit patterns make for the valid combinations...

^This

and ^this
[...]

the current idea is to use a bit for each "state" and then use a case statement for the "decision tree" (as shown above) so as to simply walk thru the integers that the bit patterns make for the valid combinations...>

^and this...
looks like a (good?) use for a dynamic array of TMinMaxState = [mmNone, mmMin, mmMinMax, mmMax]; (then var Options = array[static or dynamic] of TMinMaxState;)

This assumes options have a fixed position in the array however... but the bitwise code was assuming this anyway.

And yes, 4 states - one of them being mmNone - for the case when you don't want to use certain option.

If there is a lot of options, but not always consecutive - so there would be a lot more of mmNone's than significant states (IOW the data is sparse) - maybe do

TOption = record
  Index : [whatever type would suffice here];
  State : TMinMaxState; // [which could then be 3 state not 4]
end;

and use a dynamic array to hold the TOption(s).

Excuse my lameness please :) as I am not a programmer by trade.

-L.

On 1/22/2014 3:52 AM, Lukasz Sokol wrote:
[...]

ok so basically converting 16 bits storage into an array? currently only 15 bits are being used and i don't know that any more will be added... but i'm not seeing how to add (logical AND) them together for

optionA:mmMin AND optionC:mmMinMax

and similar up to all five basic ones as

A:mmMin AND B:mmMax AND C:mmMinMax AND D:mmMax AND E:mmMin

And yes, 4 states - one of them being mmNone - for the case when you don't want to use certain option.

yes, i've basically been ignoring mmNone because all the bits are off so we just skip over it in the ANDing code

If there is a lot of options, but not always consecutive - so there would be a lot more of mmNone's than significant states (IOW the data is sparse) -

yes, with what i have done, there are 1023 valid combination... 1024 if we count all options off (or mmNone)... that's out of 32767 combinations where the majority are invalid... it is no wonder, with 1023 combinations, that i got lost/confused with my first attempt using if/then/else and while trying to manually implement the bitmap CASE code...

as above, i'm not seeing how to AND each valid set together for later use in the filtering code :?

Excuse my lameness please :) as I am not a programmer by trade.

no problems... i'm looking for ideas and input for handling items like this... i appreciate any input on this...

it would seem that things like this would come up a lot and that there would already be a class or possibly an object that one could feed the settings array to with the options that hold each array and then to be able to walk thru like one can do with TStringsList

eg: fooList:TStringsList;
     [...]
     fooList[i]:='blah';
     [...]
     writeln(fooList[i]);

i actually did look at the TBits class but didn't see an easy way of walking it like one can do with TStringsList... my finding and looking at TBits was after some 12+ hours of manually coding if/then/else, getting lost in the details and starting over numerous times...

what i finally did with my current attempt using a bitmapped word was to write a tool to generate all the code for the case statement... with this i was able to

1] find out how many valid combinations there are (1023) 2] have the ANDs all written in the proper order for each valid bitmask 3] generate a file that is easily included {$I bitcase.inc}

any changes to the ordering need only a small rewrite to the generating tool to create the new CASE code for the filter... the resulting include file is only (!) 392353 bytes at 7932 lines with no comment lines... that's ~3x the size of the program's .pas file of 119151 bytes at 3157 lines with a few hundred comment lines...

this current implementation is used for output filtering... there's going to be an exact duplicate used for input selection with the only difference between the two CASE code blocks being the routine called on a match...

eg:
case FilterBits of
   0 : writeoutput;
   1 : begin
         if (rec^.optionA >= optionA_min) and (rec^.optionA <= optionA_max) then
           writeoutput;
       end;
   2 : begin
         if (rec^.optionA >= optionA_min) then
           writeoutput;
       end;
   3 : begin {invalid} end;
   4 : begin
         if (rec^.optionA >= optionA_max) then
           writeoutput;
       end;
[...]
case SelectBits of
   0 : addItem;
   1 : begin
         if (rec^.optionA >= optionA_min) and (rec^.optionA <= optionA_max) then
           addItem;
       end;
   2 : begin
         if (rec^.optionA >= optionA_min) then
           addItem;
       end;
   3 : begin {invalid} end;
   4 : begin
         if (rec^.optionA >= optionA_max) then
           addItem;
       end;
[...]

i think i should be able to use one routine for both input selection and output filtering... done by pass the bitmap and the routine to be used... that'll save having to worry about editing in more than one place when things change... i just gotta figure out how to pass the routine to use...

would something like:

   procedure runCase(var bitMap:word; whichProcedure: pointer);

called with

   runCase(SelectBits,@addItem);
   runCase(FilterBits,@writeoutput);

be the way to do this??

sometimes my linear procedural mind really gets in the way :/

If you insist on using bits.... define them:

const
  OptionAmmMin = $0001;
  OptionAmmMinMax = $0002;
  OptionAmmMax = $0004; // and so on

then do

if Options and (OptionAmmMin and ... ) then

?

I would have thought, that having an array of TOption like I wrote, would ensure the exclusivity.
And having the array dynamic, you can check for its size, then write some clever code to use it ;)

If you count permutations (so combinations not repeating) you'd have 120 valid ones...? http://easycalculation.com/statistics/permutation-combination.php do I understand that correctly?

Huh, well a lot of micro-management goes on here;

What if you did it like:

- define the valid bit masks (permutations?) at the start, dynamically
- associate the procedures (their pointers) to jump to with the valid bit masks in a new data type (- do you REALLY have that many procedures ? Or are they somewhat repeating themselves ?)
- then just walk the array of [bit mask, proc pointer] records and jump to pointers supplied if matching?

No ifs, no buts, treat the Options as a bitmask if such is its purpose?

Just a thought,
-L.

On 1/22/2014 12:12 PM, Lukasz Sokol wrote:
[...]

If you insist on using bits.... define them:

it isn't that i'm insisting on using them... more the way that my linear mind sees them... i'm trying to change this if it affords me better code that is easier to read, understand and modify...

const OptionAmmMin = $0001; OptionAmmMinMax = $0002; OptionAmmMax = $0004; // and so on

this is pretty much already being done by the code using SetBIT and GetBIT

then do if Options and (OptionAmmMin and ... ) then

this is where the CASE "decision tree" comes in with each CASE having the necessary if/then filtering of the data record at hand...

I would have thought, that having an array of TOption like I wrote, would ensure the exclusivity. And having the array dynamic, you can check for its size, then write some clever code to use it ;)

it may very well but as i wrote, i cannot visualize it in my mind's eye :(

there are 1023 permutations of the 32767 possible... that means that i have to have 1023 (1024 counting no options set) case selectors... each with their specific if/then to check the current data record for a match...

possibly ;) but i don't know...

What if you did it like: - define the valid bit masks (permutations?) at the start, dynamically

humm... my tool that generates the CASE statement does something like this... i might be able to adapt it... /BUT/ i still have to match the data records with the current permutation selected when the program is executed... don't i??

eg:
myprogram --optionA=-1,145 --optionD=30,40

on execution, GetOption('optionA') loads the values from the optionA command line parameter... any value less than zero means to ignore that "slot"... all other numbers are valid...

the above "--optionA=-1,145" results in the optionA_MAX bit being set (00000000
00000010) and storing the value of 145 in optA_MAX...

the above "--optionD=30,40" results in the optionD_MINMAX bit (00000010 00000000), storing the value of 30 in optD_MIN, and storing the value of 40 in optD_MAX...

ANDing the bitmasks together we have 00000010 00000010 which is 514 in decimal... this is the case selector value used later for output filtering (and future input selecting)...

then the program loads all of the data records it finds in all of the default files... currently this is some 30000 records from some 80+ files updated nightly... as the data is loaded, it is merged and updated so there are no duplicates records and all records have the most current, by date and time, information in them...

after all the merging and updating, we start with the first record and run through all of them writing them to the output file... if there are no options specified on the command line, then all the records are written... in this example, only the records matching the values given for the two options will be written to the output file... currently, that's

    514 : begin // 00000010 00000010
            if (Rec^.optA <= optA_MAX) and
               (Rec^.optD >= optD_MIN) and (Rec^.optD <= optD_MAX) then
              writeoutput;
          end;

if you can explain to me how using the arrays would work so that i can visualize it like the above, then i can try to implement it... however, i can't see any way to bypass the huge CASE statement and its IF comparisons of the data in each record... how would using the arrays allow me to do that?

- associate the procedures (their pointers) to jump to with the valid bit masks in a new data type (- do you REALLY have that many procedures ? Or are they somewhat repeating themselves ?)

it will be only two procedures IF i can do it like that... it should be easier to use one CASE procedure of the existing ~8000 lines for both (future) input selection of matching data records and for (current) output filtering of matching data records...

so what i was actually asking is if using a pointer is the proper item for passing the procedure to use and is @procA how i would specify that in the call to the procedure...

i really am trying to visualize your suggested methods ;)

On 22/01/14 21:23, waldo kitty wrote:
[...]

Maybe Something like: (but this is with type TOptionMinMax = [mmNone, mmMin,mmMinMax, mmMax])

//then
type
TOptionsArray = array[0..4] of TOptionMinMax;
var
OptionsArray : TOptionsArray;
//then you process all the options and do some kind of score to them :
function JumpTo(AOptionsArray : TOptionsArray): TProcedure;
var Score : integer;
begin
for i := 0 to 4 do // walk the array one by one
  begin
    case AOptionsArray[i].Option of
      mmMin : ;   //
      mmMinMax : ;// here gather the 'score' of the particular set of options
      mmMax : ;   // depending on 'i' and these 4 cases - if there is a well-defined formula detecting this
      else        //
    end; // case
  end; // for
//then the actual detection of score to actual procedures
if Score < something1 then Result := AddressOf(Procedure1); end;  // pseudo-code ;)
if Score >= someting1 and Score < something2 then ... end;
...
...
end;
// converting the above to dynamic array of Options :
type
TOptionMinMax = [mmMin, mmMinMax, mmMax];
TOption = record
  OptionIndex : integer;
  OptionMinMax : TOptionMinMax;
end;
TOptionsArray = array of TOption;
function JumpTo(AOptionsArray : TOptionsArray): TProcedure;
var Score : integer;
begin
for i := 0 to SizeOf(AOptionsArray)-1 do
  begin
    case AOptionsArray[i].Option of
      mmMin : ;   //
      mmMinMax : ;// here gather the 'score' of the particular set of options
      mmMax : ;   // depending on 'OptionIndex'(!) and these 3 cases - if there is a well-defined formula detecting this
                  // no mmNone because it's only to say the option is not in the set
    end; // case
  end; // for
//then the actual detection of score to procedure(s)
if Score < something1 then Result := AddressOf(Procedure1); end;  // pseudo-code ;)
if Score >= someting1 and Score < something2 then ... end;
...
...
end;
// score detection to procedures could be also automated:
type TJumpToScoreProcedure = record
   MinScore : integer;
   MaxScore : integer;
   JumpTo : TProcedure;
end;
// declare the above statically / or dynamically somewhere in an array:
const JumpToArray = [(MinScore : 10; MaxScore : 20 ; JumpTo : @Procedure1), ... ];
// and the actual detection in the JumpTo function above ^^^
for j  := 0 to SizeOf(JumpToArray)-1 do
  if (Score > JumpToArray[j].MinScore) and (Score < JumpToArray.MaxScore) then
    Result := JumpToArray[j].JumpTo;
// usage in both cases would be:
@Procedure := JumpTo(OptionsArray);
if Assigned(Procedure) then Procedure(); // in case we did not get a valid pointer from all that or
there was an error

Is this what you meant ?

-L.

Lukasz Sokol wrote

Maybe Something like: (but this is with type TOptionMinMax = [mmNone, mmMin,mmMinMax, mmMax])

i wanted to thank you, lukasz, for your input... it has made me take another look while rewriting to implement your ideas...

during this process i had an epiphany... that being that i don't need three individual states for each option since one of those states is ANDing two of those states... since i'm ANDing all valid possibilities anyway, this will free up 5 'bits' or 'scores' leaving room for more options if needed in the future... it will also lessen the complexity of the CASE "decision tree" but not by very much...

with the above epiphany and some other information i have acquired, i'm now in the process of rewriting the app... i suspect it will take me a day or two to get to the point i was at previously with the operational and in-use code but i still wanted to say thanks to you and others who provided ideas, insights and information ;) :)

Glad to hear that not all I thought of is a brain fart ;)

However I'm still curious : why use bits directly, when you can have a set/'enum' of possible choice(s), guaranteed to be distinct - so you can't physically set OptionA twice, by definition, and then make the Options be an array of the options? Yes it may be using Sizeof(set) x num options (1 byte per option?) but then it's not for you to worry any more about the bits - the compiler will care for that and you can go rethink the logic ;) and also readability and maintainability +100 ;)
But IMHO of course and YMMV ;)

Kind Regards,
-L. ;)

definitely not a brain fart... it was very helpful ;)

However I'm still curious : why use bits directly, when you can have a set/'enum' of possible choice(s), guaranteed to be distinct - so you can't physically set OptionA twice, by definition, and then make the Options be an array of the options?

well, i can't set any option more than once, anyway... not unless i make a code error and set or clear the wrong bit but that will be noticed very quickly during testing ;) for readability, i find setting the bits and then running down a simple CASE statement much easier to follow... especially since i wrote my code generator tool that creates the CASE statement and all of its valid selections ;)

Yes it may be using Sizeof(set) x num options (1 byte per option?)

yeah, i don't know... i'm very old school and like to keep things as tight as possible... being able to store all the options we've been discussing in one 16bit "device" is a good thing... that i can also simply use that "device" as a decimal number for the selectors in a CASE statement is a major good thing... no matter what i do, i can't get away from the CASE statement... well, i could by using a use tree of if/then/else but that's what i started with and it was not readable at all... the CASE statement "decision tree" is nice but i can't see how to use it with the sets of enums in an easy way...

but then it's not for you to worry any more about the bits - the compiler will care for that and you can go rethink the logic ;) and also readability and maintainability +100 ;)

once i get finished, this will be pretty much done and then i can move on to the larger application that this will eventually be a part of... i'm debating as to whether to keep this part as a separate binary or to build it all into one large monolithic app with the other parts... eventually i will be doing something with graphics which is going to be a whole new world for me to make mistakes in... and it is planned for all of this to by multi-platform, was well... data retrieval built-in along with the current merging and list output capabilities and then actually drawing the output on one of two graphical screens... one looking down at earth and the other looking up from earth... i should probably quit while i'm a head :LOL:

But IMHO of course and YMMV ;)

very true :)

waldo kitty wrote

well, i can't set any option more than once, anyway... not unless i make a code error and set or clear the wrong bit but that will be noticed very quickly during testing ;) for readability, i find setting the bits and then running down a simple CASE statement much easier to follow... especially since i wrote my code generator tool that creates the CASE statement and all of its valid selections ;)

I recently had a similar problem and solved it this way: With

-----------------------------------
type FlagType = (FlagA,
FlagB,
FlagC,
FlagD,
FlagE,

                   FlagF);
      FlagSetType = set of FlagType;

var FlagSet : FlagSetType;
-----------------------------------

I get a compact bit array (a set) where I can give each bit an individual name. Then these sets

-----------------------------------
[FlagA,FlagB,FlagC,FlagD,FlagE,FlagF]
[FlagA, FlagC,FlagD,FlagE,FlagF]
[FlagA,FlagB,FlagC,FlagD,FlagE,FlagF]
[FlagA, FlagD,FlagE,FlagF]
[FlagA,FlagB, FlagE,FlagF]
[FlagA,FlagB,FlagC,FlagD,FlagE ]
-----------------------------------

select one "number" (which it internaly is) and

-----------------------------------
byte([FlagA,FlagB,FlagC,FlagD,FlagE,FlagF])
byte([FlagA, FlagC,FlagD,FlagE,FlagF])
byte([FlagA,FlagB,FlagC,FlagD,FlagE,FlagF])
byte([FlagA, FlagD,FlagE,FlagF])
byte([FlagA,FlagB, FlagE,FlagF])
byte([FlagA,FlagB,FlagC,FlagD,FlagE ])
-----------------------------------

can be used to convert them to real (integer) numbers in a case statement:

-----------------------------------
case byte(FlagSet) of
    byte([FlagA,FlagB,FlagC,FlagD,FlagE,FlagF]) : begin .. end;
    byte([FlagA,      FlagC,FlagD,FlagE,FlagF]) : begin .. end;
    byte([FlagA,FlagB,FlagC,FlagD,FlagE,FlagF]) : begin .. end;
    byte([FlagA,            FlagD,FlagE,FlagF]) : begin .. end;
    byte([FlagA,FlagB,            FlagE,FlagF]) : begin .. end;
    byte([FlagA,FlagB,FlagC,FlagD,FlagE      ]) : begin .. end;
    end; // of case
-----------------------------------

and still I can use the set as a usual set:

-----------------------------------
include(FlagSet,FlagD);
...
if FlagA in Flagset then..
...
etc.
-----------------------------------

I even use an array which is indexed with the set variable:

-----------------------------------
type FlagSetArrayType = array[0..(1 shl (ord(High(FlagSetType))+1))-1] of any_other_type; // 0..2^n-1 -----------------------------------

which holds information for all 2^n possible flag combination in the set. Then I can use the set variable to index the array like this:

-----------------------------------
var FlagSetArray = FlagSetArrayType;
...

any_other_type_variable := FlagSetArray[ byte([FlagA,FlagB,FlagC,FlagD,FlagE,FlagF])   ];
-----------------------------------

(I hope there is no typo in the above code)

Hello Jürgen,

On 27/01/14 17:50, Jürgen Hestermann wrote:
[...]

I thought about this too, but this means waldo's use case would be

type TOptions = [FlagAMin, FlagAMinMax, FlagAMax, ... FlagFMin, FlagFMinMax, FlagFMax]

which would allow a nice usage of

if FlagAMin in Options then ...

but which he'd have to marshall (to disallow FlagA* set more than once) same way as he does now, bit by bit, only more verbose... whereas the 'array of set' would be more readable [IMHO] and did that 'automatically'.

Since we need a way to group the flag values so that one flagset option can be one of 3 states [4 still be a better choice, being a power of 2 and uses same number of bits anyway ] and distinctly read/set the value of an option, my array idea was (I think) closest...

I also thought of

type TFlag = [FlagNone, FlagMin, FlagMinMax, FlagMax];
type TOptions = packed record
   FlagA : TFlag;
   FlagB : TFlag;
   ...
end;

but that is more awkward and ultimately the array is easier to expand.or to turn to dynamic.

A nice touch would be if

TFlag = [FlagNone, FlagMin, FlagMinMax, FlagMax];
TFlags = set of TFlag;
TOptions = set of TFlags; // which would still pack into available 'set' type of variable,
// allowing constructs like byte(Options) to be used
but how would we then access individual options  in TOptions? AFAIK the above is impossible anyway;

Another I thought of was

type
TFlag = [FlagMin, FlagMinMax, FlagMax];
TFlagA = TFlag; TFlagB = TFlag; ... TFlagF = TFlag;
TOptions = [FlagA : TFlagA, ... FlagF : TFlagF];
// which ultimately is no different than the array approach
// but still less flexible
// and probaby impossible the way I wrote it above too.

Other ideas included having the flags use bitwise constants so that pushing/pulling it out of the set would ensure the state of any Option be always of distinct choice, best if not having to think about clearing the remnants of other states by hand... but I failed to materialize this vision :)

The only way I could visualize was to have the distinct Options values declared as Flags shifted two bits to the left each, and then yes using bitwise AND; this however limits number of options to bitsizeof(Byte) div 2 = 4 ... or bitsize(Word) div 2 = 8. and requiring bitwise AND masks and then shift, for use with the rest of the Options value to read the value... messy.

Whereas with array of set this all happens beyond our influence...

All in all, IMHO and YMMV, again ;)

-L