Open arrays - can it be done? 
Author Message
 Open arrays - can it be done?


There's a very good article as to how this can be done in Delphi, November 1995 EXE magazine.

Mike

Quote:

>I understand that it is possible to have a definition of a function
>that does not set a maximum number of parameters, i.e.:

>function blah(params : array of const);

>but it seems to me that I cannot define a variable of type array with
>an undefined array size.  I have been searching and the best I can
>come up with is:

>var
>  blah : array[char] of string;
>(for example)

>but this is not really an open array, because there is a limited
>number of characters.  Also if I try something like this I seem to be
>getting a stack overflow when I run the program.

>Regardless of the pros and cons of having an array[char], it is not
>what I am after.  I want something that has no defined size and can
>deal with any number of parameters I give it.  So my question is, can
>this be done, or was I correct in my conclusion (after scouring books
>and help) that it cannot?  Also, I don't want to have a huge array
>because I would most likely only be using between one and, I don't
>know, less than one hundred items, but I would like there to be the
>ability to have any number.

>Ta,

>Jo.
>____________________________




Wed, 18 Jun 1902 08:00:00 GMT  
 Open arrays - can it be done?

: >
: >I understand that it is possible to have a definition of a function
: >that does not set a maximum number of parameters, i.e.:
: >
: >function blah(params : array of const);
: >
: >but it seems to me that I cannot define a variable of type array with
: >an undefined array size.  I have been searching and the best I can
: >come up with is:

        You could always use a linked list.  It shouldn't be hard to find
out how...even my old Apple Pascal textbook at school explains it.
Basically, instead of passing a set of values to the procedure, you pass a
memory address of a record.  The record contains a piece of data and the
memory address for another record of the same type.
        Implementation is harder than an array, but it would solve your
problem...
--
[) /-\ \/ ][ [)                I just say what I feel,
/-\ ~|~ |< ][ |\| $ () |\|     And I can't help what I feel.



Wed, 18 Jun 1902 08:00:00 GMT  
 Open arrays - can it be done?
Quote:

> Kilian) says:

>I understand that it is possible to have a definition of a function
>that does not set a maximum number of parameters, i.e.:

>function blah(params : array of const);

>but it seems to me that I cannot define a variable of type array with
>an undefined array size.  I have been searching and the best I can
>come up with is:

[chop!]

Hi Joanne,  It's one of those nights where I can't get to sleep.  Do you
think it might have something to do with the nap I took this afternoon? <g>  
So I thought I'd spend the time constructively and explain one method of
constructing variable sized arrays at runtine.  Actually I was tinkering with
the explaination last night, writing to everyone. Its just now that I'm ready
to attach the message that I find its in response to your question about open
arrays.

The explaination tends to ramble a bit, touchs on pointers, hints on writing
optimal code, and keeps an eye open for possible bugs.  At times it is pretty
simple. Maybe so simple that you might think I patronizing.  I'm not I just
tried to present it so that some aspiring beginner might be able to follow
what's happening. Maybe even screem eureka!, Yes! or what have you.  I would
appreciate some feed-back.  Send it in email, there's no need to burden the
group with such tripe.

Before we begin, I'd like everyone to read the following help:

 Open Parameters
 ---------------
 When Open parameters is not selected, Open parameters are disabled.

When Open parameters is selected, a variable parameter declared using the
string keyword is an open string parameter.

The actual parameter of an open string parameter can be a variable of any
string type, and within the procedure or function, the size attribute
(maximum length) of the formal parameter will be the same as that of the
actual parameter.

Open string parameters behave exactly as variable parameters of a string
type, except that they cannot be passed as regular variable parameters to
other procedures and functions.

Open parameters is equivalent to {$P}.

Seems that open parameters == variable length string declarations.  This
is a far cry from having open arrays of any type. Sorry folks, but we
can't get there from here.

Okay, so how do we get there?

The typical solution is to define a type of array that has a maximum
number of elements.  To save a little heart ache later (when you try to
circumvent type checking), it is often best to define a pointer to this
structure and use the pointer type in the list of parameters when defining
a function. So we have something like:

      TYPE  tpVector = ^Vector;
            tVector  = Array[1..$FFF0 div Sizeof(Longint)] of Longint;

So far so good.  So how do we actually build the arrays?

There are only two things that the compiler does - Allocate storage and
generate code.  Both of which evaluate to a constant. The magic is what it
does in order to resolve thos constants <g>. There is no way that a compiler
can allocate storage for an open-ended array. The compiler could
be made to handle something like

        const A: Array[] of integer = (1, 2, 3, 4);

because even though the [] makes the array appear undefined the four
entries in parentheses says the array has four elements.  But what would be
the bounds of such an array?  Simple, Zero to three!  That is what "C" does.
In "C", all arrays are zero based.  In other words you couldn't declare an
array of [1..4] or ['a'..'z'] elements.

Pascal programmers enjoy the ability of being able to establish the bounds of
their arrays. The price we pay is having to do a little extra computational
work when defining the bounds of an initialized array.  So in Pascal
initialized arrays have to be declared as something like:

        const A: Array[ 0..3] of longint = (1, 2, 3, 4);
        const B: Array[-3..3] of longint = (1, 2, 3, 4, 5, 6, 7);
        const C: Array[ 1..3] of longint = (1, 2, 3);

I know you understand this. What might have fell through the cracks is that
all of these arrays can be passed to a routine like the following:

        Procedure SomeProc(v: tpVector; Count: Integer);
        VAR i: Integer;
        Begin
            For i := 1 to Count Do Begin
               --- access elements in the array using ---
               --- v^[i] := v^[i]; ---
            End;
        End;


following techniques:



Ah, small glimmer of light!  But you knew this too.  What you want is to
determine the size of the array at runtime.  How do I build an array of
optimal size when I won't know the optimal size until after the program is
running?  The key here is that at runtime you _will_ know the size of the
array.  So at compile time we declare a pointer variable that we'll use at
runtime to reference our array.  The compiler is happy because it knows
how much to set aside in the data segment (or allocate on the stack for
local variables) and we are happy because we can bind it to an array at
runtime.  So we add:

      VAR Vector: tpVector;
          Vcount: Integer;

Now you promised that somewhere along the way you would know how big an
array you needed.  Well, that time has come, so put the number of elements
you need in Vcount.  Finally we add something like the following:

        { Allocate the array }
        Getmem(Vector, Longint(Vcount) * Sizeof(Vector^[1]));

        --- now stuff the thing with values, or whatever ---
        --- address elements like Vector^[1] := 1, etc.  ---

        SomeProc(Vector, Vcount);

        --- do anything else you need to do ---

        { Deallocate the array }
        Freemem(Vector, Longint(Vcount) * Sizeof(Vector^[1]));

In the above, Vector is a pointer. It was declared as a tpVector
(type pointer to vector).  Hence we allocate and deallocate the pointer
using GetMem(Vector, ... and FreeMem(Vector, ...

Why was Vcount cast to a Longint?

We could have made Vcount a word or longint, but I wanted emphasize the
fact that if the expression is not taken outside the bounds of an
integer, then the computed size of the array is going to fail when the
size of the array becomes larger than 32767 bytes.  In the example we've
used, that won't happen until the array is larger than 8191 elements.

If you are certain that the array will never be larger 32767 div
Sizeof(Element), fine, do nothing. However, if there is even the
slightest possibility that it will, then if you don't bring the
expression out of an integer's domain you have a latent bug that is
going to rear up and grab you some day. Anyone that's been bitten when a
collection tried to expand beyond 8191 elements, or by a similar
situation, can appreciate what I'm saying.  In this example the target. or
desired result is a word, so make sure you don't cut your throat by
limiting the expression to an integer's domain.  

If you think the program would ever attempt to crate an array larger than
65520 bytes, you might want to let you program stay in control by adding
someting like:

        If Vcount > High(Vector^) Then Begin
           --- error handling stuff ---
      End Else Begin
         --- continue with what we were doing ---
      End;      

Those with something earlier than BP 7.0 will have to reword the If statement
to be something like:

        If Vcount > SizeOf(Vector^) div Sizeof(Vector^[1]) Then Begin
           ---

Hint: "Sizeof() div Size()" equates to a constant that will be resolved at
compile time.  This is preferebe to coding a variable explression that can
only be resolved at runtime.

The notation Vector^ is called dereferencing a pointer. To dereference a
pointer means *not* to use the pointer, but use what it is pointing at.
If Vector is my hand, then Vector^ is my hand "pointing". If I hold out
my hand you can look at it and are able to put things into it and take
thinks out of it (same as Vector).  But when I point at something you
ignore my hand and follow where the finger is pointing (as in Vector^).

I hope this has helped some novice gain a better understanding for one
use of pointers, helped some grasp the fundimental technique of sizing
arrays at runtime.  Maybe even save someone from getting burned by a
subtle little bug!

Feel free to use any portion of this in a FAQ or tutorial.

May all your code run correctly, the _first_ time!

            ...red



Wed, 18 Jun 1902 08:00:00 GMT  
 Open arrays - can it be done?

Quote:

>>I understand that it is possible to have a definition of a function
>>that does not set a maximum number of parameters, i.e.:

>>function blah(params : array of const);

>>but it seems to me that I cannot define a variable of type array with
>>an undefined array size.  I have been searching and the best I can
>>come up with is:

>>var
>>  blah : array[char] of string;
>>(for example)

>>but this is not really an open array, because there is a limited
>>number of characters.  Also if I try something like this I seem to be
>>getting a stack overflow when I run the program.

>>Regardless of the pros and cons of having an array[char], it is not
>>what I am after.  I want something that has no defined size and can
>>deal with any number of parameters I give it.  So my question is, can
>>this be done, or was I correct in my conclusion (after scouring books
>>and help) that it cannot?  Also, I don't want to have a huge array
>>because I would most likely only be using between one and, I don't
>>know, less than one hundred items, but I would like there to be the
>>ability to have any number.

You cannot use a traditional array-type for this purpose; but you CAN use a
class-type such as appears in Delphi.  This is, in fact, how "open arrays" are
implemented in systems like Visual Basic, which made them popular.

A Pascal array-type is a fixed block of storage to which the compiler can
generate direct references.  You can't do that with what you are wanting to do
because (a) you want the size to grow dynamically; and (b) you probably don't
want "empty" elements to appear.

The Pascal array-type is very simple and very efficient; it is therefore
limited in its application.

A class will substitute a subroutine-call for each reference to an array
element, calling your code to check the index, grow the array if needed, and
to make a long story short, to come up with or to put-away the value.  In your
source-code the reference appears to be an ordinary array-reference.

/mr/



Wed, 18 Jun 1902 08:00:00 GMT  
 Open arrays - can it be done?

Quote:

>>>function blah(params : array of const);

>>>but it seems to me that I cannot define a variable of type array with
>>>an undefined array size.  I have been searching and the best I can
>>>come up with is:
>>>Regardless of the pros and cons of having an array[char], it is not
>>>what I am after.  I want something that has no defined size and can
>>>deal with any number of parameters I give it.  So my question is, can
>>>this be done, or was I correct in my conclusion (after scouring books
>>>and help) that it cannot?  Also, I don't want to have a huge array
>>>because I would most likely only be using between one and, I don't
>>>know, less than one hundred items, but I would like there to be the
>>>ability to have any number.

I don't have  source for it anymore, but I have seen a method of doing
this.  The method is not very clean, obviously because it is kind of
cheating.  But what you do is turn off  range checking in your
compiler options, then declare a type like this:

type PDynArray:^DynArray;
        DynArray:Array[0..0] of word;
var Dyn:PDynArray;

Then in the code, you can ask the user to enter the number of words to
be in the array, then use memory allocation to get the memory.(Sorry,
its been years sense I actually wrote any programs, so I'm very rusty,
but it would look kind of like

var DynSize:word;     {need this so you don't go out of bounds, since
                         pascal can't check}

begin
    Readln(DynSize);
    New(Dyn, DynSize*2);
        {Do whatever you want now, your array is 0..DynSize-1 <?>}
    Dispose(Dyn);
end.

Just make sure to get rid of the memory when you are done, and during
the program execution you must make sure you stay in the bounds of the
array.  The "DynSize*2" is *2 in this case because a word is 2 bytes,
you would declare this best actually by a SizeOf statement, so if you
change the array to longint or something it automatically updates
itself.  Also, I've never tried this code, so sorry if it doesn't work
very well, I saw it on a bulletin board several years ago.....

Chris Shaffer  



Wed, 18 Jun 1902 08:00:00 GMT  
 Open arrays - can it be done?
And If you don't have Delphi, then read up on linked lists.
Their messy and a pain to implement, but they are far more powerfull than
normal arrays.

I use them extensivly on my 3D engine, where I found they are better than
open arrays. Admitidly I am quite new to the concept of open arrays.

Good luck anyway. If you need any help on Linked lists then gimme a
shout.

{*filter*}vampyre         - At Liverpool John Moores University



Wed, 18 Jun 1902 08:00:00 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. Open arrays - can it be done?

2. Open arrays - can it be done?

3. Open arrays - can it be done?

4. Open arrays - can it be done?

5. What am I doing wrong...

6. What am I doing wrong

7. what am I doing wrong

8. What am I doing wrong?

9. What am I doing wrong?

10. TDBGrid onvalidate - what am i doing wrong

11. HELP : "Invalid Paramater", when doing Tquery.Open, seems to not release resources

12. It's not bad canned meat...

 

 
Powered by phpBB® Forum Software