Solved

Comparing arrays with arrays

Posted on 2000-02-25
14
887 Views
Last Modified: 2010-04-04
I need a way to compare arrays with other arrays.  These are generally arrays of ordinal values.  I'd like to add arrays to arrays, compare to see if all items in first array are in second, and remove items from an array from an array.  I've looked at SETS and it looks like it has some of what I need, but lacks the ability to add and remove items.

function InArray(A:array of Byte; B:array of Byte) : Boolean;

returning true if all items in array A are in B.  Note: There can be duplicates of the same value and if there are, there has to be atleast that many in array B to return TRUE.

function AddArray(A:array of Byte; B : Array of Byte): array of byte;

function SubtractArray(A:array of Byte;B:array of byte): array of bytw

I could generally write these myself, but I was wondering if there was a package out there that was already written that could do this.

It could be done either using dynamic/variant arrays or Tlist, it don't matter, but I need a way to COUNT the members in the array and access the data so I can save it to a stream.  It should also not require too much CPU resources because it is going to be called many times.

If someone can point me to a link that will help me I'll give 200 points, if someone goes thru the trouble and writes it themselves or posts/emails me the exact functions I need, I'll give 400+ points.  I have 1200 available.

This is for an online game that is similiar to a MUD, but it is graphical.  It is for the slots system to keep track of how many of each bodypart are not equipping anything.

If you want to help out, with the game project.  Let me know.  We need graphics artists and programmers.  We curretnly have 4 people on it.
0
Comment
Question by:arcrotty
  • 6
  • 6
  • 2
14 Comments
 
LVL 13

Expert Comment

by:Epsylon
ID: 2560276
Look in the Delphi help (index tab) for 'set operators'. Maybe that opens a whole new world for you.
0
 
LVL 13

Expert Comment

by:Epsylon
ID: 2560283
The only problem when using sets are duplicate values...
0
 

Author Comment

by:arcrotty
ID: 2560305
Duplicate values are a big thing.  Is there an undocumented method of checking all the values in the set?  Or is it prolly stored in a bit array of boolean or something.

basically I need to compare things like:
 
[1,1,1] in [1,1,1,2,2] = true;
[1,1,1] in [1,2,2,2] = false;
[1,1,2] + [1,2,3,4] = [1,1,1,2,2,3,4]
[1,2,2,3,4] - [2,3] = [1,2,4]

not necessarily in any specific order... but can be.  All the values will be an ordinal value.  An easy way to do this would be to have an array and make each dimension of it a count of each value, but this would use up a lot of memory (256 bytes) and there is going to be a lot of objects using these arrays in the order of prolly 1000's and would require a for 0..255 loop during each check even if there is only one item in the list.

In the program I'm writing, there prolly won't be more then 16 different ordinal values and generally the max will be about 4 of each.  They will represent body parts of types of creatures.  A human has 2 legs, minotours have 4, etc.  It basically is used to keep track of what slots are available to armor.  If a helmet is to be worn, it checks to see if there is a S_HEAD slot available, and if so, removes that slot from the list.  When it is taken off, it puts it back on the availability list.  Some weapons require 2 hands and would require 2 S_HAND slots.


0
 

Author Comment

by:arcrotty
ID: 2560353
I just had a thought...

If I set hard limits ...

S_HAND = 1;       // 0000000000000001
S_HAND_SHIFT = 0; // 0000000000000111
S_HAND_MAX = 7 SHL S_HAND_SHIFT;

S_ARM = 8;        // 0000000000001000
S_ARM_SHIFT = 3;  // 0000000000111000
S_ARM_MAX = 7 SHL S_ARM_SHIFT;

S_HEAD = 64;      // 0000000001000000
S_HEAD_SHIFT = 6; // 0000000011000000
S_HEAD_MAX = 3 SHL S_HEAD_SHIFT;

S_TWO_HANDS := S_HAND+S_HAND;

This method looks like it works well except for the fact that I will run out of bits fast.  Is there a way to shift a multi-byte block of data?  A 64 bit number *might* be big enough for my purposes.  I'm just thinking on the fly.

SlotsReq := S_HAND + S_ARM;
SlotsAvail := S_HAND + S_HAND + S_ARM + S_ARM + S_HEAD + etc...

NumHands = (SlotsAvail AND S_HAND_MAX) SHR S_HAND_SHIFT;

If SlotsReq OR SlotsAvail = SlotsAvail then; // there is enough slots.

This looks like an effient way of doing it, but I need a way to shift possible a 128-bit number if it exists.
0
 
LVL 20

Expert Comment

by:Madshi
ID: 2560537
I've not the time to write this completely for you, but I've some hints for you:

I recommend using dynamic arrays (only possible in D4 and D5). Sets are quite limited, because they can't hold the same value twice.

First of all, declare an array type like this:

type
  TYourOrdinalArray = array of integer;

Now the functions should look like this:

function InArray(const A, B: TYourOrdinalArray) : boolean;
var i1 : integer;
begin
  if length(A) <= length(B) then begin
    // here comes the big loop test
  end else
    result := false;
end;


function AddArray(const A, B: TYourOrdinalArray) : TYourOrdinalArray;
var i1, i2, i3 : integer;
begin
  i1 := Length(A);
  i2 := Length(B);
  SetLength(result, i1 + i2);
  for i3 := 0 to i1 - 1 do
    result[i3] := A[i3];
  for i3 := 0 to i2 - 1 do
    result[i1 + i3] := B[i3];
end;

function SubstractArray(const A, B: TYourOrdinalArray) : TYourOrdinalArray;
begin
  // ...
end;

Saving to a stream works like this:

  stream.Write(pointer(arr)^, Length(arr) * 4);  // *4 for integer; *1 for byte

Regards, Madshi.
0
 
LVL 20

Expert Comment

by:Madshi
ID: 2560541
P.S: AddArray should be complete.
0
 
LVL 13

Expert Comment

by:Epsylon
ID: 2560865
1) When looking at this definition you gave us in your question, who do you tell the function how many element the arrays have?

function AddArray(A:array of Byte; B : Array of Byte): array of byte


2) Array of byte means that the array can contain values from 0 to 255. Is it possible to use 0 for special purposes, e.g. a sentinel?
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 13

Accepted Solution

by:
Epsylon earned 375 total points
ID: 2561142
I think I have a perfect solution for you:

http://www3.ewebcity.com/joep/arraysets.zip
0
 
LVL 13

Expert Comment

by:Epsylon
ID: 2561827
0
 

Author Comment

by:arcrotty
ID: 2566284
Adjusted points to 375
0
 

Author Comment

by:arcrotty
ID: 2566286
Madshi,

You examples were real good, but epsilon's was a bit more complete.  I wish I could split the points, but...


Epsilon,

I was looking for a more memory efficient way of doing things, but you made up for it in detail.  I've increased the points to 375 for your help.
0
 

Author Comment

by:arcrotty
ID: 2566386
Epsilon,

Looking at the code more closely I noticed that I'd need to create your Tarrayset for each array.  I really needed to compare generic arrays, not a new Tarrayset.  I'll see if I can do that for you.  If you want to make it more complete for yourself, you should add clear() to it.  I'm going to be making these changes myself, if you want me to send you my changes, let me know.
0
 
LVL 13

Expert Comment

by:Epsylon
ID: 2566675
>Looking at the code more closely I noticed that I'd need to create your Tarrayset for each array.

You can do that if you want but you can choose only to create them when you need them. This way it uses much less memory of course.

Btw: when handling large or unsorted arrays, TArraySet is very fast...


>I'm going to be making these changes myself, if you want me to send you my changes, let me know.

Please do  :o)


Cheers,

Epsylon.

0
 

Author Comment

by:arcrotty
ID: 2566713
I may still have your email address somewhere from the last time you helped me.  But incase I don't, email me at smorales@twinlab.com.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Creating an auto free TStringList The TStringList is a basic and frequently used object in Delphi. On many occasions, you may want to create a temporary list, process some items in the list and be done with the list. In such cases, you have to…
In my programming career I have only very rarely run into situations where operator overloading would be of any use in my work.  Normally those situations involved math with either overly large numbers (hundreds of thousands of digits or accuracy re…
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.

948 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now