Board index » delphi » Independent Type Algorithm (Eg: Sorting)

Independent Type Algorithm (Eg: Sorting)

Hi all,

What I would like to do is a generic algorithm to take care of the data
regardless of the data type.A good example is a sorting algorithm.
Imagine I want to sort strings instead of integers, or sort records by a
specific field...

Have a look at this code:

Procedure Sort(Var Data: TDataArray; NumItems: Integer);
Var
 i, j: Integer;

 Procedure Swap(Var A, B: TDataType);
 Var
  Temp:TDataType;
  Begin
   Temp:=A;
   A:=B;
   B:=Temp;
  End;

 Begin
  For i:=1 To NumItems Do
   Begin
    Pos:=i;
    For j:=Succ(i) To NumItems Do
     If Data[j].SomeField>Data[pos].SomeField Then
      Pos:=j;
    Swap(Data[i], Data[Pos])
   End.
 End;

 I know this isn't the best sorting method but it's quite simple to
implement and very good for my needs.
 First question:
   How can I pass different data types to my sort algorithm ? I mean...How
will I tell TP in runtime what array type I want to pass ? I think this is
possible with some clever use of pointers, can someone give me ideas on that
?
   Second, and this one I think it's not possible... Is there any way to
know the fields of any record ? I mean... Is there a generic way to identify
them like Record.Field[i] (I'm not talking about arrays as a field...I'm
talking about a ordinal way to identify fields...).
As I said, I think this is not possible, in this case, how could we made a
generic sorting algorithm for any field I would like ? Can we pass the field
as a parameter to the sort procedure ? (I also think not..but perhaps there
are some clever tricks with memory to do this).

   I think this is an interesting subject for us to discuss.All ideas will
be appreciated :-)

  Regards,

Jose Santos

Jose Carlos Almeida Santos

WebPage: http://codpro.home.ml.org
E-Mail : jcsan...@iname.com
ICQ UIN: 5826000

 

Re:Independent Type Algorithm (Eg: Sorting)


Quote
Jose Santos wrote:
>    How can I pass different data types to my sort algorithm ? I mean...How
> will I tell TP in runtime what array type I want to pass ? I think this is
> possible with some clever use of pointers, can someone give me ideas on that
> ?

It would be possible to pass different types to a function or procedure by
using pointers to pass the addresses of both variables and additionally pass
their size as a third parameter. This way you could e.g. swap two variables of
any kind.
But there's another problem: You cannot find out, how the data has to be
interpreted. So you can't compare. Strings are compared completely different
than integer values, for example. Maybe this can be solved with heavy coding
tricks (like passing the type of data in a further parameter and implementing
different comparison routines), but I don't think it's worth the work.

        Bye,
          Ingo

Re:Independent Type Algorithm (Eg: Sorting)


{question skipped}

The easiest way I know is to write a comparison procedure and pass it into
your sorting procedure.  You will have to have a comparison procedure for
each type of data you will ever want to sort (i.e. one for integers, one for
records compared by certain field, one for strings, etc. etc. etc.).  Then
when you want to sort, just pass the array (or whatever you store your data
in) and the comparison procedure to the procedure responsible for the
sorting.  Inside the sorting procedure instead of the ">" and "<" you use
the comparison procedure.

Hope this helps.  Nikita.

Re:Independent Type Algorithm (Eg: Sorting)


On Thu, 17 Dec 1998 22:33:11 -0800, "Jose Santos" <jcsan...@iname.com>
wrote:

Quote
> Hi all,

> What I would like to do is a generic algorithm to take care of the data
> regardless of the data type.A good example is a sorting algorithm.
> Imagine I want to sort strings instead of integers, or sort records by a
> specific field...

A generic sorting routine could be structured like this:

type
  sfunc:function(var a,b):integer;

procedure sort(var a;size,num:word;f:sfunc);

If sorting will be applied to an array of myrec

type myrec = record
               i:integer;
               s:string;
             end;

you have to define an order function depending on your sort key like

function mysfunc(var a,b);
begin
  if myrec(a).s<myrec(b).s then mysfunc:=-1
  else if myrec(a).s>myrec(b).s then mysfunc:=1
  else mysfunc:=0
end;

Inside the sort function you treat 'a' as a virtual array of blocks of
size num

procedure sort(var a;size,num:word;f:sfunc);
var
  bytes:array[0..$FFF7] of byte absolute a;
begin

A 'var' reference to a virtual array element i (0<=i<num) is
identified by

        bytes[i*num];

(the byte is never evaluated. It only serves as a handle which will be
passed to f and to the swap function which will be implemented as

        procedure swap(var a,b;size:word);
        { swap two memory chunks 'a' and 'b' of size 'size'}

A comparison is performed by

        if f(bytes[i*num],bytes[j*num]) < 0 then ...
           { means; if array[i] < array [j] }

Actual call

var
  m:array[0..9] of tmyrec;

sort(m, sizeof(tmyrec),10,mysfunc);

Regards
Horst

Re:Independent Type Algorithm (Eg: Sorting)


Quote
Jose Santos wrote:
> What I would like to do is a generic algorithm to take care of the data
> regardless of the data type.A good example is a sorting algorithm.

I would use objects, inheritance, and virtual methods.  Define an
object class "ThingToBeSorted" and write code for sorting a linked
list of them.  Its only field variable would be a pointer to the next
ThingToBeSorted in the list.

Then each data type can be a subclass of ThingToBeSorted, so it
inherits the sorting methods, but you can add your own as well.

Good luck.

     - Rich

Re:Independent Type Algorithm (Eg: Sorting)


In article <75c0nn$n0...@duke.telepac.pt>,

Quote
Jose Santos <jcsan...@iname.com> wrote:
>Hi all,

>What I would like to do is a generic algorithm to take care of the data
>regardless of the data type.A good example is a sorting algorithm.
>Imagine I want to sort strings instead of integers, or sort records by a
>specific field...

>Have a look at this code:

>Procedure Sort(Var Data: TDataArray; NumItems: Integer);
>Var
> i, j: Integer;

> Procedure Swap(Var A, B: TDataType);
> Var
>  Temp:TDataType;
>  Begin
>   Temp:=A;
>   A:=B;
>   B:=Temp;
>  End;

> Begin
>  For i:=1 To NumItems Do
>   Begin
>    Pos:=i;
>    For j:=Succ(i) To NumItems Do
>     If Data[j].SomeField>Data[pos].SomeField Then
>      Pos:=j;
>    Swap(Data[i], Data[Pos])
>   End.
> End;

> I know this isn't the best sorting method but it's quite simple to
>implement and very good for my needs.
> First question:
>   How can I pass different data types to my sort algorithm ? I mean...How
>will I tell TP in runtime what array type I want to pass ? I think this is
>possible with some clever use of pointers, can someone give me ideas on that
>?

A good way is to use procedure/function parameters:

Type CompareFunc=Function(i,j:integer):Boolean;
     SwapProc=Procedure(i,j:integer);

Procedure ShellSort(first,n:integer;InOrder:CompareFunc; Swap:SwapProc);
var i,j,incr,last:integer;
Begin
  incr:=longint(n)*10 div 17;
  last:=n-1+first;

  while incr>0 do begin
    for i:=first to last-incr do begin
      j:=i;
      while (j>=first) and Not InOrder(j,j+incr) do begin   { Short circuit! }
          Swap(j,j+Incr);
          dec(j,incr);
      End
    End;
    incr:=longint(incr)*10 div 17;
  End;
End;

Now you can write sort and compare routines for the type that you use and
pass them as parameter, like:

var A:TdataArray;
...

 Procedure Swap(i,j:integer); far;
 Var
  Temp:TDataType;
 Begin
   Temp:=A[i];
   A[i]:=A[j];
   A[j]:=Temp;
  End;

Quote
>   Second, and this one I think it's not possible... Is there any way to
>know the fields of any record ? I mean... Is there a generic way to identify
>them like Record.Field[i] (I'm not talking about arrays as a field...I'm
>talking about a ordinal way to identify fields...).

No, you could pass the offset within the field but there still would be
the type to consider and things would get really ugly. Use procedure
parameters.

Osmo

Re:Independent Type Algorithm (Eg: Sorting)


Quote
Jose Santos wrote in message <75c0nn$n0...@duke.telepac.pt>...
>Hi all,

>What I would like to do is a generic algorithm to take care of the data
>regardless of the data type.A good example is a sorting algorithm.

The TSortedCollection (in the Turbo Vision/OWL unit - Objects.pas) will be
of interest. Add TVISION.TPH to your IDE help files list and Alt-F1 on
"TSortedCollection".

Jay
--

Jason Burgon - author of Graphic Vision
g...@jayman.demon.co.uk
http://www.jayman.demon.co.uk

Re:Independent Type Algorithm (Eg: Sorting)


On 18 Dec 1998 17:30:16 +0200, ronka...@cc.helsinki.fi (Osmo Ronkanen)
wrote:

Quote
>In article <75c0nn$n0...@duke.telepac.pt>,
>Jose Santos <jcsan...@iname.com> wrote:
>>Hi all,

>>What I would like to do is a generic algorithm to take care of the data
>>regardless of the data type.A good example is a sorting algorithm.
>>Imagine I want to sort strings instead of integers, or sort records by a
>>specific field...
>A good way is to use procedure/function parameters:

>Type CompareFunc=Function(i,j:integer):Boolean;
>     SwapProc=Procedure(i,j:integer);

>Procedure ShellSort(first,n:integer;InOrder:CompareFunc; Swap:SwapProc);
....
>Now you can write sort and compare routines for the type that you use and
>pass them as parameter, like:

>var A:TdataArray;
>...
> Procedure Swap(i,j:integer); far;
> Var
>  Temp:TDataType;
> Begin
>   Temp:=A[i];
>   A[i]:=A[j];
>   A[j]:=Temp;
>  End;

>Osmo

I have a problem with this method of programming :
Your variable A can be local :
Look this code :

Procedure Example;
var A:TdataArray;

 Procedure Swap(i,j:integer); far;
 Begin
 ...
 End;
 Function Compare(i,j:integer):Boolean;far;
 Begin
 ...
 End;

Begin
ShellSort(first,n,:Compare, Swap);
.....
End;

Tp7 doesn't compile this.

If you don't want to have the variable A in global, how do you make ??

Re:Independent Type Algorithm (Eg: Sorting)


Quote
In article <36815c85.5775...@news.club-internet.fr>,  <syba...@chez.com> wrote:

...

Quote

>I have a problem with this method of programming :
>Your variable A can be local :
>Look this code :

>Procedure Example;
>var A:TdataArray;

> Procedure Swap(i,j:integer); far;
> Begin
> ...
> End;
> Function Compare(i,j:integer):Boolean;far;
> Begin
> ...
> End;

>Begin
>ShellSort(first,n,:Compare, Swap);
>.....
>End;

>Tp7 doesn't compile this.

>If you don't want to have the variable A in global, how do you make ??

You need to define a global pointer variable and make it point the
actual array. The procedures used as procedure parameters have to be at
the first level. Of course one could also pass the pointer to  Shellsort
which in turn would pass it to compare and swap but that would be one
step away from being truly general purpose. Note that if one passed
the pointer and also data size to shellsort then the swapping could be
done internally but this also would be a step away from general purpose
routine. (it would not work on implementations that split the array into
subarrays by using pointers)

Osmo

Re:Independent Type Algorithm (Eg: Sorting)


Quote
syba...@chez.com wrote:
>On 18 Dec 1998 17:30:16 +0200, ronka...@cc.helsinki.fi (Osmo Ronkanen)
>wrote:
>>In article <75c0nn$n0...@duke.telepac.pt>,
>>Jose Santos <jcsan...@iname.com> wrote:
>>>Hi all,

>>>What I would like to do is a generic algorithm to take care of the data
>>>regardless of the data type.A good example is a sorting algorithm.
>>>Imagine I want to sort strings instead of integers, or sort records by a
>>>specific field...

>>A good way is to use procedure/function parameters:

>>Type CompareFunc=Function(i,j:integer):Boolean;
>>     SwapProc=Procedure(i,j:integer);

>>Procedure ShellSort(first,n:integer;InOrder:CompareFunc; Swap:SwapProc);
>....
>>Now you can write sort and compare routines for the type that you use and
>>pass them as parameter, like:

>>var A:TdataArray;
>>...
>> Procedure Swap(i,j:integer); far;
>> Var
>>  Temp:TDataType;
>> Begin
>>   Temp:=A[i];
>>   A[i]:=A[j];
>>   A[j]:=Temp;
>>  End;

>>Osmo

>I have a problem with this method of programming :
>Your variable A can be local :
>Look this code :

>Procedure Example;
>var A:TdataArray;

> Procedure Swap(i,j:integer); far;
> Begin
> ...
> End;
> Function Compare(i,j:integer):Boolean;far;
> Begin
> ...
> End;

>Begin
>ShellSort(first,n,:Compare, Swap);
>.....
>End;

>Tp7 doesn't compile this.

>If you don't want to have the variable A in global, how do you make ??

The easiest solution would be to pass the array as an untyped
VAR parameter.  Of course that would mean you would have to pass
array elements as untyped VAR parameters rather than simply pass
subscripts to the compare and swap procedures.  Of course you
could pass three parameters - array and subscripts.

 Procedure Swap(VAR i,j); far;
 Begin
   ...
 End;
 Function Compare(VAR i,j):Boolean; far;
 Begin
   ...
 End;

PROCEDURE Sort(VAR List; first,n,:Compare, Swap);
  ...
End;

Another solution would be to design the sort procedure to
receive sub-procedures as parameters, as done for a collection's
iterator (ForNext, FirstThat, ...).  To call a sub-procedure
you have to have the caller pass a "hidden" parameter.  It's
like the "self" passed to an object's method, except in this
case it is the parent procedure's stack frame.

We're getting a little technical here, so let's cover a little
background first.  Upon entering a procedure, the TP/BP compiler
generates code to construct a standard stack-frame.  This is
simply the code that saves the current value of BP, then loads
BP with the current value of the stack.  After the current
position of the stack is obtained, SP is adjusted so as to
allocate space for local variables, intermediate string results,
etc.  The stack relative to BP is called the stack frame.  Since
BP is static throughout the life of the procedure's instance, it
provides a base from which it can access it's parameters and
local variables.

When a sub-procedure is called, the parent procedure's stack
frame is passed as the "last" parameter.  If the calling
procedure is the parent, this means the current value of BP is
pushed to the stack.  If one sub-procedure calls another
sub-procedure at the same level, then the calling procedure is
the parent of both.  Therefore the value of the caller's
"hidden" parameter is pushed to the stack.  Just remember that
it is the stack frame of the called sub-procedure's parent that
is pushed to the stack.

Okay, now let's look at building a sort that expects to receive
a procedure parameter that is a FAR sub-procedure of the CALLER!
Like a collection, the caller *MUST* be the parent procedure.

Osmo already indicated that the first step would be to move the
compare and swap functions out of the sort procedure.   You
might find it easier to understand if we did this a step at a
time.  If we begin with by using a sub-procedure, the outline
for a typical sort might be --

procedure Sort(n: integer);

   Function Compare(i,j: Integer): Boolean; FAR;
   Begin
     ...
   End;

VAR i,j: Integer;
Begin
   ...
      If compare(i,j) Then
             ...
   ...
End;

The above "If compare" would generate something like
  push [BP+nn] { value of i }
  push [BP+nn] { value of j }
  push BP      { parent's stack frame }
  push CS      { fake far call }
  call sort    { near call     }

When compare is a parameter procedure, then the code looks
something like -
  push [BP+nn] { value of i }
  push [BP+nn] { value of j }
  push CS      { fake far call }
  call sort    { near call     }

The trick, if you call it such, is to be able to not only pass i
and j, but to push the stack frame of the procedure that called
the sort procedure.  The call would then look like a normal call
to a sub-procedure and the compare function would be able to
access its parent's parameters and local variables.

One solution would be to use BASM to pass all parameters and
make the call.  But this wouldn't work for anyone using
something earlier than TP 6.0.  If we create a more generic
solution using a local "inline" compare function and a "local"
inline swap procedure as stepping stones, our sort becomes ---

Type CompFunc=Function(i,j:integer):Boolean;
     SwapProc=Procedure(i,j:integer);

Procedure ShellSort(n:integer;InOrder: CompFunc; Swap:SwapProc);

  Function Comp(x,y: Integer): Boolean;
  INLINE(  { integer parameters are all ready on the stack }
           { need push caller's stack frame and call compare }
  INLINE(
      $FF/$76/$00           { push BP[0] }
     /$FF/$5E/<compare  { call FAR PTR Compare (byte offset)}
  );

  Function Switch(x,y: Integer): Boolean;
  INLINE(  { integer parameters are all ready on the stack }
           { need push caller's stack frame and call swap }
  INLINE(
      $FF/$76/$00           { push BP[0] }
     /$FF/$5E/<swap     { call FAR PTR Swap (byte offset)}
  );

BEGIN{sort}
   { refer to Comp and Switch and NOT InOrder or Swap! }

   If Comp(i,j) Then
      ...
END;

If the main sort is a sub-procedure, as is the usual case in a
quicksort, the nested sub-procedure will need to load it's
parent's frame in order to access the original caller's stack
frame and the local parent's compare and swap parameters.

IIRC, in BASM this becomes:
      mov  BX,BP[0]   { get local parent's stack frame }
      push SS:[BX+0]  { push original caller's stack frame }
      call FAR PTR SS:[BX+OFFSET InOrder]

If you have any problems understanding any of this, I suggest
you stick with passing the array as an untyped parameter.  But
you're welcome to write and I'll do my best to help you with any
problems you're having.

Happy holiday every one!

    ...red

Re:Independent Type Algorithm (Eg: Sorting)


In article <36824270.806...@news.leading.net>,

Quote
R.E.Donais <rdon...@leading.net> wrote:

>The easiest solution would be to pass the array as an untyped
>VAR parameter.  Of course that would mean you would have to pass
>array elements as untyped VAR parameters rather than simply pass
>subscripts to the compare and swap procedures.  Of course you
>could pass three parameters - array and subscripts.

> Procedure Swap(VAR i,j); far;
> Begin
>   ...
> End;
> Function Compare(VAR i,j):Boolean; far;
> Begin
>   ...
> End;

>PROCEDURE Sort(VAR List; first,n,:Compare, Swap);
>  ...
>End;

You also would need to pass the size of the element. Also this would
not be a general purpose algorithm anymore as the whole array should
have to be in same segment.

....

- Show quoted text -

Quote

>One solution would be to use BASM to pass all parameters and
>make the call.  But this wouldn't work for anyone using
>something earlier than TP 6.0.  If we create a more generic
>solution using a local "inline" compare function and a "local"
>inline swap procedure as stepping stones, our sort becomes ---

>Type CompFunc=Function(i,j:integer):Boolean;
>     SwapProc=Procedure(i,j:integer);

>Procedure ShellSort(n:integer;InOrder: CompFunc; Swap:SwapProc);

>  Function Comp(x,y: Integer): Boolean;
>  INLINE(  { integer parameters are all ready on the stack }
>           { need push caller's stack frame and call compare }
>  INLINE(
>      $FF/$76/$00       { push BP[0] }
>     /$FF/$5E/<compare  { call FAR PTR Compare (byte offset)}
>  );

Why two inlines?

Quote
>  Function Switch(x,y: Integer): Boolean;
>  INLINE(  { integer parameters are all ready on the stack }
>           { need push caller's stack frame and call swap }
>  INLINE(
>      $FF/$76/$00       { push BP[0] }
>     /$FF/$5E/<swap     { call FAR PTR Swap (byte offset)}
>  );

>BEGIN{sort}
>   { refer to Comp and Switch and NOT InOrder or Swap! }

>   If Comp(i,j) Then
>      ...
>END;

This is really really dirty.

Osmo

Re:Independent Type Algorithm (Eg: Sorting)


The problem i have with Function/Procedure parameter is this :
I have found an usefull proc in the swag (File_Find).
This procedure searchs in the directory source all the files and
continues in sub-directories....
Every time a file is found, this procedure call FileDoer with the
complete name of the file in parameter.
Here is the interface of this procedure.

Type  TRecurseProc = Procedure (FileName:String);

Procedure File_Find(Source:String; FileDoer:TRecurseProc);
Begin
.....
End;

For example :
Procedure Display(S:String);
Begin
Writeln(S);
End;

Begin
File_Find('c:\*.*',Display)
End.

This code will display all the files in the drive c:

{----------------}

Now i write this code :

{Set the archive/read-only.... attributes of one file}
Procedure Attrib(FileName:String;Attr:Word);Far;
Begin
......
End;

{Set attributes for all a directory and sub-directories}
Procedure XAttrib(Path:String;Attr:Word);

 Procedure AttrProc(FileName:String);Far;
 Begin
 Attrib(FileName,Attr);
 End;

Begin
File_Find(Path,AttrProc);
End;

Tp7 doesn't want to compile this...
{----------------}
The solution i found is :

Var GlobalAttr:Word;

Procedure AttrProc(FileName:String);Far;
Begin
Attrib(FileName,GlobalAttr);
End;

Procedure XAttrib(Path:String;Attr:Word);
Begin
GlobalAttr:=Attr;
File_Find(Path,AttrProc);
End;

I think the solution is ugly :-)
do you have a best solution ??
{----------------}
I have the same problem when i wrote this code :

Procedure CopyFile(SourceFN,TargetFN:String);Far;
Begin
.....
End;

Procedure XCopy(Source,Target:String);
 Procedure CopyFileProc(FileName:String);Far;
 Begin
 CopyFile(FileName,Target);
 End;

Begin
File_Find(Source,CopyFileProc);
End;

Tp7 doesn't want to compile this :-)

If i use the same solution i will have to put 2 strings in global.
If i continue i will have to put a lot of variables in global ...

SomeOne has a good solution ??

Re:Independent Type Algorithm (Eg: Sorting)


On 24 Dec 1998 17:55:48 +0200, ronka...@cc.helsinki.fi (Osmo Ronkanen)
wrote:

Quote
>You need to define a global pointer variable and make it point the
>actual array. The procedures used as procedure parameters have to be at
>the first level. Of course one could also pass the pointer to  Shellsort
>which in turn would pass it to compare and swap but that would be one
>step away from being truly general purpose. Note that if one passed
>the pointer and also data size to shellsort then the swapping could be
>done internally but this also would be a step away from general purpose
>routine. (it would not work on implementations that split the array into
>subarrays by using pointers)

>Osmo

Ok, i agree except about define a global pointer variable :
You can define the array in local and pass the pointer in parameter...

Procedure a(P:Pointer);
Begin
End;

Procedure b;
Var T:Array[1..5] of byte;
Begin
a(@T);
End;

Begin
b;
End.

Re:Independent Type Algorithm (Eg: Sorting)


On Thu, 24 Dec 1998 16:32:57 GMT, rdon...@leading.net (R.E.Donais)
wrote:

Quote

>Another solution would be to design the sort procedure to
>receive sub-procedures as parameters, as done for a collection's
>iterator (ForNext, FirstThat, ...).  To call a sub-procedure
>you have to have the caller pass a "hidden" parameter.  It's
>like the "self" passed to an object's method, except in this
>case it is the parent procedure's stack frame.

I have difficulties to understand you :
What is the relation between object and the stack frame ??
What is collection's iterator ??

Quote
>We're getting a little technical here, so let's cover a little
>background first.  Upon entering a procedure, the TP/BP compiler
>generates code to construct a standard stack-frame.  This is
>simply the code that saves the current value of BP, then loads
>BP with the current value of the stack.  After the current
>position of the stack is obtained, SP is adjusted so as to
>allocate space for local variables, intermediate string results,
>etc.  The stack relative to BP is called the stack frame.  Since
>BP is static throughout the life of the procedure's instance, it
>provides a base from which it can access it's parameters and
>local variables.

>When a sub-procedure is called, the parent procedure's stack
>frame is passed as the "last" parameter.  If the calling
>procedure is the parent, this means the current value of BP is
>pushed to the stack.  If one sub-procedure calls another
>sub-procedure at the same level, then the calling procedure is
>the parent of both.  Therefore the value of the caller's
>"hidden" parameter is pushed to the stack.  Just remember that
>it is the stack frame of the called sub-procedure's parent that
>is pushed to the stack.

>Okay, now let's look at building a sort that expects to receive
>a procedure parameter that is a FAR sub-procedure of the CALLER!
>Like a collection, the caller *MUST* be the parent procedure.

>Osmo already indicated that the first step would be to move the
>compare and swap functions out of the sort procedure.   You
>might find it easier to understand if we did this a step at a
>time.  If we begin with by using a sub-procedure, the outline
>for a typical sort might be --

>procedure Sort(n: integer);

>   Function Compare(i,j: Integer): Boolean; FAR;
>   Begin
>     ...
>   End;

>VAR i,j: Integer;
>Begin
>   ...
>      If compare(i,j) Then
>         ...
>   ...
>End;

>The above "If compare" would generate something like
>  push [BP+nn] { value of i }
>  push [BP+nn] { value of j }
>  push BP      { parent's stack frame }
>  push CS      { fake far call }
>  call sort    { near call     }

If i understand you explain me this :
In the following code, proc b knows 2 stack frame one from the caller
(proc a) and it own stack frame (proc b).
To know the caller frame, proc a push bp, i agree with you...

{$S-}
Procedure a;
 Var i:integer;
 Procedure b;
 Var j:integer;
 begin
 i:=1;
 j:=2;
 end;

begin
b;
End;

begin
a;
End.

Quote
>When compare is a parameter procedure, then the code looks
>something like -
>  push [BP+nn] { value of i }
>  push [BP+nn] { value of j }
>  push CS      { fake far call }
>  call sort    { near call     }

Ok, i agree too.

Quote
>The trick, if you call it such, is to be able to not only pass i
>and j, but to push the stack frame of the procedure that called
>the sort procedure.  The call would then look like a normal call
>to a sub-procedure and the compare function would be able to
>access its parent's parameters and local variables.

>One solution would be to use BASM to pass all parameters and
>make the call.  But this wouldn't work for anyone using
>something earlier than TP 6.0.  If we create a more generic
>solution using a local "inline" compare function and a "local"
>inline swap procedure as stepping stones, our sort becomes ---

Here i don't understand : What is the interest to force the push of BP
??

- Show quoted text -

Quote
>Type CompFunc=Function(i,j:integer):Boolean;
>     SwapProc=Procedure(i,j:integer);

>Procedure ShellSort(n:integer;InOrder: CompFunc; Swap:SwapProc);

>  Function Comp(x,y: Integer): Boolean;
>  INLINE(  { integer parameters are all ready on the stack }
>           { need push caller's stack frame and call compare }
>  INLINE(
>      $FF/$76/$00       { push BP[0] }
>     /$FF/$5E/<compare  { call FAR PTR Compare (byte offset)}
>  );

>  Function Switch(x,y: Integer): Boolean;
>  INLINE(  { integer parameters are all ready on the stack }
>           { need push caller's stack frame and call swap }
>  INLINE(
>      $FF/$76/$00       { push BP[0] }
>     /$FF/$5E/<swap     { call FAR PTR Swap (byte offset)}
>  );

>BEGIN{sort}
>   { refer to Comp and Switch and NOT InOrder or Swap! }

>   If Comp(i,j) Then
>      ...
>END;

I don't understand what is the interest to call switch instead calling
swap...

- Show quoted text -

Quote

>If the main sort is a sub-procedure, as is the usual case in a
>quicksort, the nested sub-procedure will need to load it's
>parent's frame in order to access the original caller's stack
>frame and the local parent's compare and swap parameters.

>IIRC, in BASM this becomes:
>      mov  BX,BP[0]   { get local parent's stack frame }
>      push SS:[BX+0]  { push original caller's stack frame }
>      call FAR PTR SS:[BX+OFFSET InOrder]

>If you have any problems understanding any of this, I suggest
>you stick with passing the array as an untyped parameter.  But
>you're welcome to write and I'll do my best to help you with any
>problems you're having.

>Happy holiday every one!

>    ...red

Re:Independent Type Algorithm (Eg: Sorting)


Quote
In article <3682b3c3.8991...@news.club-internet.fr>,  <syba...@chez.com> wrote:

...

Quote

>Now i write this code :

>{Set the archive/read-only.... attributes of one file}
>Procedure Attrib(FileName:String;Attr:Word);Far;
>Begin
>......
>End;

Why is this far?????

Quote

>{Set attributes for all a directory and sub-directories}
>Procedure XAttrib(Path:String;Attr:Word);

> Procedure AttrProc(FileName:String);Far;
> Begin
> Attrib(FileName,Attr);
> End;

>Begin
>File_Find(Path,AttrProc);
>End;

>Tp7 doesn't want to compile this...

Of course not as the attr is not defined.

Quote
>{----------------}
>The solution i found is :

>Var GlobalAttr:Word;

>Procedure AttrProc(FileName:String);Far;
>Begin
>Attrib(FileName,GlobalAttr);
>End;

>Procedure XAttrib(Path:String;Attr:Word);
>Begin
>GlobalAttr:=Attr;
>File_Find(Path,AttrProc);
>End;

>I think the solution is ugly :-)

I do not agree. There is nothing wrong with using global variables in
this kind of a situation. The whole point is that as the procedure
parameter has a very general interface then all the specific cases
cannot be passes as parameter.

Quote
>do you have a best solution ??
>{----------------}
>I have the same problem when i wrote this code :

>Procedure CopyFile(SourceFN,TargetFN:String);Far;
>Begin
>.....
>End;

Why far?

Quote

>Procedure XCopy(Source,Target:String);
> Procedure CopyFileProc(FileName:String);Far;
> Begin
> CopyFile(FileName,Target);
> End;

Setting nested procedures far does not make any sense as they can be
only called from the same unit. (well using overlays is an exception but
then one should use $F+.

Quote
>Begin
>File_Find(Source,CopyFileProc);
>End;

>Tp7 doesn't want to compile this :-)

>If i use the same solution i will have to put 2 strings in global.
>If i continue i will have to put a lot of variables in global ...

Well you could manage with one global pointer if you really needed to
spare data segment.

Quote
>SomeOne has a good solution ??

Osmo
Go to page: [1] [2]

Other Threads