473,320 Members | 2,147 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

array inside a array!?

I was going through an Boyer-Moore-Horspool pattern match, I saw a
array inside a array, like the below,

skip[pat[i] ] = patlen - i - 1;

The array is decleared as

int skip[UCHAR_MAX+1];

unsigned char *pat;
I have seen function call inside the array such as calling strlen()
inside a array, but the above one is
strange and new to me as a beginner. Can anybody spend a little time to
explain the above.
BTW, if this a FAQ please refer the question number.

--
"Combination is the heart of chess"
A.Alekhine
Mail to:
sathyashrayan AT gmail DOT com
(AT = @ and DOT = .)
Nov 14 '05 #1
9 3351


sathya wrote:
I was going through an Boyer-Moore-Horspool pattern match, I saw a
array inside a array, like the below,

skip[pat[i] ] = patlen - i - 1;

The array is decleared as

int skip[UCHAR_MAX+1];

unsigned char *pat;

I have seen function call inside the array such as calling strlen()
inside a array, but the above one is
strange and new to me as a beginner. Can anybody spend a little time to
explain the above.
BTW, if this a FAQ please refer the question number.


Sorry I must be more precise in my question. The bellow properties is
well known with the array:

"In an array, LOGICAL ADJACENCY (B follows A) is modeled by
PHYSICAL ADJACENCY (B occurs just after A in memory.)"

As in the case of the above "array inside a array" I cannot figure out
the possibility of logical and
physical adjacency. And is the above kind of "array inside a array" is
UD in std?
--
"Combination is the heart of chess"
A.Alekhine
Mail to:
sathyashrayan AT gmail DOT com
(AT = @ and DOT = .)
Nov 14 '05 #2
sathya wrote:
I was going through an Boyer-Moore-Horspool pattern match, I saw a
array inside a array, like the below,

skip[pat[i] ] = patlen - i - 1;
This is NOT "an array inside an array". This is array indexing where
the index expression is itself an array indexing expression.
I have seen function call inside the array such as calling strlen()
inside a array, but the above one is
strange and new to me as a beginner.


Why? pat[i] is just as much an expression as f(j) or k+1.

--
Chris "electric hedgehog" Dollin
Nov 14 '05 #3
sathya wrote:
I was going through an Boyer-Moore-Horspool pattern match, I saw a
array inside a array, like the below,

skip[pat[i] ] = patlen - i - 1;


I'm not sure about the Boyer-Moore-Horspool pattern match algorithm.

But what the code seems to do is this:

skip[pat[i] ] = patlen - i - 1;

pat[i] gets the ASCII value of the char pointed to by ptr 'pat'.
Index in the array 'skip' to the element (pat[i]), which in this case
is for that particular character, and store whatever 'patlen-i-1' is.
So the ASCII value of that char is actually an index for the skip
array, just like skip[65], 65 ASCII for 'A', would be for char 'A'

pat[i] is actually a number/value which is used as index. The notation
looks like array in array but there's nothing like array in array in C.
Hope that Helps.

Regards,
Taran Tripathi

Nov 14 '05 #4
sathya <sa****@nomail.com> wrote:
I was going through an Boyer-Moore-Horspool pattern match, I saw a
array inside a array, like the below, skip[pat[i] ] = patlen - i - 1; The array is decleared as int skip[UCHAR_MAX+1]; unsigned char *pat;
I have seen function call inside the array such as calling strlen()
inside a array, but the above one is
strange and new to me as a beginner. Can anybody spend a little time to
explain the above.
BTW, if this a FAQ please refer the question number.


I don't think that this requires a FAQ entry. In the above line
"pat[i]" simply evaluates to a number that is used as the index
in the 'skip' array. That's not different from using the result
of a function call or computation as the index. It's basically
the same as writing e.g.

idx = pat[ i ];
skip[ idx ] = patlen - i - 1;

just shorter and does not require an extra variable.

Regards, Jens
--
\ Jens Thoms Toerring ___ Je***********@physik.fu-berlin.de
\__________________________ http://www.toerring.de
Nov 14 '05 #5
On Tue, 14 Dec 2004 17:25:56 +0530
sathya <sa****@nomail.com> wrote:
sathya wrote:
I was going through an Boyer-Moore-Horspool pattern match, I saw
a
array inside a array, like the below,

skip[pat[i] ] = patlen - i - 1;

The array is decleared as

int skip[UCHAR_MAX+1];

unsigned char *pat;

I have seen function call inside the array such as calling strlen()
inside a array, but the above one is
strange and new to me as a beginner. Can anybody spend a little time
to explain the above.
BTW, if this a FAQ please refer the question number.


Sorry I must be more precise in my question. The bellow properties
is well known with the array:

"In an array, LOGICAL ADJACENCY (B follows A) is modeled by
PHYSICAL ADJACENCY (B occurs just after A in memory.)"

As in the case of the above "array inside a array" I cannot figure
out the possibility of logical and
physical adjacency. And is the above kind of "array inside a array"
is UD in std?


It's simple. You do *not* have an array inside an array, you are just
looking in one array to find an index in to the other. It is basically
equivalent to:

int skip[UCHAR_MAX+1];
unsigned char *pat;
unsigned char tmp;

tmp = pat[i];
skip[ tmp ] = patlen - i - 1;

<pedantic>
C does not guarantee physical adjacency, only logical adjacency. For
example, on a system with paged memory one location in the array might
be in physical memory whilst the next location, on the other side of a
page boundary, might have been swapped out to disk and not exist in
physical memory at all.
</pedantic>

If you want to look at formal definitions with respect to C you really
need to look at the C standard in my opinion. Google for N869 to find
the publicly available last draft of the C99 standard.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.
Nov 14 '05 #6
On Tue, 14 Dec 2004 17:25:56 +0530, sathya wrote:


sathya wrote:
I was going through an Boyer-Moore-Horspool pattern match, I saw a
array inside a array, like the below,

skip[pat[i] ] = patlen - i - 1;
This is equivalent to

char tmp;

tmp = pat[i];
skip[tmp] = patlen - i - 1;
The array is decleared as

int skip[UCHAR_MAX+1];

unsigned char *pat;

I have seen function call inside the array such as calling strlen()
inside a array, but the above one is
strange and new to me as a beginner. Can anybody spend a little time to
explain the above.
The expression between the [] is just a number used to index the array.
There is no real sense that it is "inside" the array, this idea seems to
be more confusing than helpful. See the equivalent code where pat[i]
isn't "inside" anything.
BTW, if this a FAQ please refer the question number.

I doubt it, this is simple expression evaluation.
Sorry I must be more precise in my question. The bellow properties is
well known with the array:

"In an array, LOGICAL ADJACENCY (B follows A) is modeled by
PHYSICAL ADJACENCY (B occurs just after A in memory.)"
If you want a discussion of how the algorithm works a newsgroup like
comp.programming would be appropriate.
As in the case of the above "array inside a array" I cannot figure out
the possibility of logical and
physical adjacency. And is the above kind of "array inside a array" is
UD in std?


The code is perfectly well defined, assuming the variables involved have
sensible values and it is in a sensible context in the rest of the program.
Again, look at the equivalent code, there's nothing unusual happening here.

Lawrence

Nov 14 '05 #7
On 14 Dec 2004 04:07:40 -0800
"Taran" <ta************@honeywell.com> wrote:
sathya wrote:
I was going through an Boyer-Moore-Horspool pattern match, I saw a
array inside a array, like the below,

skip[pat[i] ] = patlen - i - 1;
I'm not sure about the Boyer-Moore-Horspool pattern match algorithm.

But what the code seems to do is this:

skip[pat[i] ] = patlen - i - 1;

pat[i] gets the ASCII value of the char pointed to by ptr 'pat'.


Stop right there. The C standard does NOT mandate ASCII, and C has been
implemented on a number of systems that are not ASCII. All pat[1] does
is get the number stored in pat[i] which may have been generated as
something to do with the execution character set, but it might also
just be being used as a byte array.
Index in the array 'skip' to the element (pat[i]), which in this case
is for that particular character,
What makes you think pat contains character rather than, for example,
bytes of a bitmap graphic?
and store whatever 'patlen-i-1' is.
So the ASCII value of that char is actually an index for the skip
array, just like skip[65], 65 ASCII for 'A', would be for char 'A'
Definitely not as mentioned above. Don't assume that all the world is a
PC not that text is the only thing stored in char arrays.
pat[i] is actually a number/value which is used as index. The notation
looks like array in array but there's nothing like array in array in
C. Hope that Helps.


That is correct.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.
Nov 14 '05 #8
In article <27************@brenda.flash-gordon.me.uk>,
Flash Gordon <sp**@flash-gordon.me.uk> wrote:
What makes you think pat contains character rather than, for example,
bytes of a bitmap graphic?


The fact that he's applying the Boyer-Moore algorithm to it?

Of course, you can apply it to any sequence, but it's common to think
of characters in this context.

-- Richard
Nov 14 '05 #9
On 14 Dec 2004 14:27:19 GMT
ri*****@cogsci.ed.ac.uk (Richard Tobin) wrote:
In article <27************@brenda.flash-gordon.me.uk>,
Flash Gordon <sp**@flash-gordon.me.uk> wrote:
What makes you think pat contains character rather than, for example,
bytes of a bitmap graphic?


The fact that he's applying the Boyer-Moore algorithm to it?

Of course, you can apply it to any sequence, but it's common to think
of characters in this context.


Well, this is comp.lang.c not an algorithms group and I happen not to
have needed to do pattern matching on text and I know that text
processing is not the only place one does pattern matching. Taran stated
that he did not know the Boyer-Moore-Horspool algorithm, therefor s/he
obviously had no way of knowing that it was likely to be a character,
and all the references to ASCII showed a lack of understanding of what a
char is in C.

So I stand by my question, how did Taran (not you or the OP) know that
pat contained characters?

I add the further question, how does anyone other than the OP know that
the execution character set is ASCII?
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.
Nov 14 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

15
by: Bob | last post by:
I've tried everything; and I can't seem to get past this VERY (seemingly) simply problem. I want to work with an array variable within a function(s). I can't get it to work; if I: 1) global...
8
by: Marco | last post by:
Hi all, I have a base class and some subclasses; I need to define an array of objects from these various subclasses. What I have is something like: { //I have a base class, something like:...
4
by: Mark Hannon | last post by:
I am trying to initialize an array only once so it can be seen & used by any functions that need it. As I understand it, if a variable is declared by itself outside of any functions, its scope is...
6
by: Abhishek Srivastava | last post by:
Hello All, In .Net Array is a reference type and an int is a value type. If I create an array of int, then will the items inside the array get boxed? If yes, it will be a terrible overhead. If...
9
by: shaun | last post by:
Dear all, I realized an error in a previous post, I reproduce it here because I'm still not sure how to solve it: I want to make a templated function which points to one-past-the-end of a...
7
by: Jim Carlock | last post by:
Looking for suggestions on how to handle bad words that might get passed in through $_GET variables. My first thoughts included using str_replace() to strip out such content, but then one ends...
8
by: dan.winsor | last post by:
Hi all, I'm trying to write through SOAPpy in python to a Java implemented API. The API for the method I want to use is as follows: boolean added = SoapService.addAttachmentsToIssue(token,...
3
by: Spoon | last post by:
Hello everyone, I want to create an array of objects at run-time. AFAIU, operator new will call the default constructor for each object in the array. In other words, the following program will...
1
by: remya1000 | last post by:
i'm using VB.net 2003 application program. i'm trying to convert a VB6 program to VB.NET. The VB6 code i'm trying to convert is shown below. declared g_Share() array in module and trying to add...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.