Tuesday, September 05, 2006

C# object arrays BinarySearch, Sort and IComparer

This isn't so much a new or very difficult thing, but it's something I've happened to come across twice recently, and I've needed to dig up the example code both times, so thought I'd add it to my blog for future reference.

Basically, I'm getting much more interested in dealing with object arrays rather than DataSets even in smaller projects. I feel like I have more control over certain things with object arrays, like business logic and customising properties. Now one of my projects was .net 2.0 so I used the generic List<> which was quite nicely put together, but my other project is a 1.1 project, so needed a slightly more outdated method.

I'll explain that one here, and probably add a note about the List<> way to do the same (plus more) next time.

Setting up the object array
For a very basic example I've got a class with a couple of fields in it for an Mp3 list:
public class Mp3Class {
private string _Artist;
private string _Song;
private int _Ranking;
public string Artist { get { return _Artist;} set {_Artist = value;}}
public string Song { get { return _Song;} set {_Song = value;}}
public int Ranking { get { return _Ranking;} set {_Ranking = value;}}
public Mp3Class (string Artist, string Song, int Ranking)
{
_Artist = Artist; _Song = Song; _Ranking = Ranking;
}
}

A basic example to get some data into this would be:
Mp3Class[] mp3s = new Mp3Class[5];
mp3s[0] =
new Mp3Class("Cave", "Ship Song", 9);
mp3s[1] =
new Mp3Class("Nirvana", "Smells like teen spirit", 3);
mp3s[2] =
new Mp3Class("Sonic Youth", "100%", 1);
mp3s[3] =
new Mp3Class("Cave", "Red right hand", 4);
mp3s[4] =
new Mp3Class("Nirvana", "Heart shaped box", 7);

The Array class
So the thing you really need to get your head around working with arrays of objects is the Array class. It's very similar to working with List<>, but missing a few features. For simple arrays, things like IndexOf, Sort and even BinarySearch can be straight forward, but with object arrays a little more work is needed, but fortunately not too much.

Array.Sort
For sorting our class, there is one big thing that makes it more difficult. Which property do you sort on? In this case all are valid, as you may be ordering by artist, by ranking or even by song, but that means we need to implement another class to help us out. The IComparer interface gives us the ability to sort things how we wish using our objects. Basically, if we want to sort this list by Artist, we can implement an IComparer class which compares the Artist string, and Sort will do the rest, or if we want to sort by Ranking, we can compare the ranking numbers and Sort will do the rest. Here are those two examples:

public class ArtistCompareClass : IComparer
{
int IComparer.Compare(object x, object y)
{
int RetVal = String.Compare((x as Mp3Class).Artist, (y as Mp3Class).Artist, true);
return RetVal;
}
}

public class RankingCompareClass : IComparer
{
int IComparer.Compare(object x, object y)
{
int RetVal = (x as Mp3Class).Ranking - (x as Mp3Class).Ranking;
return RetVal;
}
}

The ArtistCompareClass cheats by using String.Compare (with case insensitivity). IComparer.Compare is simply looking for a negative if the first object should be ordered earlier, 0 if they are the same and a positive number if the 2nd object should be ordered earlier. Passing this object to Array.Sort will sort the array alphabetically by Artist.

The RankingCompareClass implements the same IComparer.Compare, so again, if the first Ranking is smaller it returns a negative, if they are the same a 0, if the 2nd Ranking is smaller a positive. This will order the object array by Ranking.

The call to sort the array will look like this:
Array.Sort(mp3s, new RankingCompareClass());

You now have the mp3s ordered by Ranking.

Array.BinarySearch
The BinarySearch as the name suggests searches the array using the same IComparer (or at least can do it this way). So again IComparer helps us search through an array of objects, when the language would otherwise have no idea of what it's searching for.

Note: Remember these key things when using a BinarySearch:

  • You must sort by the IComparer before using BinarySearch
  • It won't work (100%) if your "key" is not unique
  • If the result is negative, you can do a bitwise operation to see the closest match
  • If you are only searching a subset of the array, it will still return the item in the entire array that's a match.

Here are a couple of examples. I'll give you another IComparer which will help do "real" searches easier. In this case we'll send through the ranking as the 2nd parameter rather than a full object. As you can imagine if someone wanted to search for the song with ranking number 5, it's easier to pass through 5 than new Mp3Class("", "", 5):

public class RankingCompareValueClass : IComparer
{
int IComparer.Compare(object x, object y)
{
int RetVal = (x as Mp3Class).Ranking - (int)y;
return RetVal;

}

}

To find the object which matches a search with a ranking of 4 (MatchingObject is 2, which is the 3rd object in the array):
Array.Sort(mp3s, new RankingCompareClass());
int MatchingObject = Array.BinarySearch(mp3s, 5, new RankingCompareValueClass());
MessageBox.Show(mp3s[MatchingObject].Artist + " - " + mp3s[MatchingObject].Song);

If the user tried to search for a ranking of 5, we could take them to the next closest match (MatchingObject is 3, which is the 4th object in the array):
Array.Sort(mp3s, new RankingCompareClass());
int MatchingObject = Array.BinarySearch(mp3s, 5, new RankingCompareValueClass());
if (MatchingObject < matchingobject =" ~MatchingObject;">" - " + mp3s[MatchingObject].Song);

That's about it. It's worth pointing out that List<> does most of this stuff plus more, and is slightly easier to use, so I'd tend to use that for any 2.0+ projects.


kick it on DotNetKicks.com

24 comments:

Levi Watts said...

Thank you for the information. I needed a class array.

Anonymous said...

Hi thanks for the info, can you advice how can i make a get method for this class you explained?

Anonymous said...

Hi,
Thanks a lot for the information. Those ware really usefull for me

Anonymous said...

atlasandnetfinds.blogspot.com is very informative. The article is very professionally written. I enjoy reading atlasandnetfinds.blogspot.com every day.
guaranteed bad credit loans
payday advance

Anonymous said...

I'm the sort of guy who passions to try brand-new stuff. Presently I am manufacturing my own solar panels. I'm making it all by myself without the assistance of my staff. I'm utilizing the internet as the only path to acheive that. I stumbled upon a truly amazing website that explains how to create pv panels and wind generators. The web site explains all the steps involved in solar panel construction.

I am not exactly sure about how precise the info given there iz. If some people over here who had xp with these things can have a peak and give your feedback in the page it would be great and I would extremely value it, because I truly take an interest in [URL=http://apennootje.blogwogin.com/2009/11/10/solar-panel-construction-at-home]solar panel construction[/URL].

Tnx for reading this. You guys are the best.

Anonymous said...

This web site really has all the info I needed about this
subject and didn't know who to ask.
Here is my site ; click through the next post

Anonymous said...

I visit day-to-day some web pages and information sites to
read articles, but this weblog presents quality
based writing.
Visit my web-site ... Smith Mountain Lake Vacation Home Rentals

Anonymous said...

With havin so much content do you ever run
into any issues of plagorism or copyright infringement?
My site has a lot of unique content I've either created myself or outsourced but it looks like a lot of it is popping it up all over the internet without my authorization. Do you know any ways to help protect against content from being ripped off? I'd really appreciate it.
Feel free to surf my blog post ... free high preformance company assessment

Anonymous said...

A fascinating discussion is definitely worth comment. I believe that
you should write more about this subject, it may not be a taboo subject but typically folks don't speak about such subjects. To the next! Best wishes!!

My web blog ... quotes about fake people
my site: Executive dirtbag

Anonymous said...

Very shortly this web page will be famous among all blogging and site-building
people, due to it's good content

my page ... locksmith in salt lake city

Anonymous said...

Since the admin of this web site is working, no hesitation very soon it will be renowned, due to its
quality contents.

Feel free to surf to my webpage :: buy cheap gw2 gold
My web site > guild wars 2 gold

Anonymous said...

I love your blog.. very nice colors & theme.

Did you make this website yourself or did you hire someone to do it
for you? Plz respond as I'm looking to create my own blog and would like to know where u got this from. appreciate it

My homepage Summitt Energy
my website :: Summitt Energy

Anonymous said...

It is the best time to make some plans for the longer
term and it's time to be happy. I've learn this put up and if I may I want to recommend you few interesting
issues or tips. Perhaps you could write subsequent articles relating to this article.
I want to learn even more things approximately it!



Look into my web-site: 7 sultans casino

Anonymous said...

Thanks for sharing your thoughts. I truly appreciate your
efforts and I am waiting for your further write ups thanks once again.



Visit my website ... learning forex trading

Anonymous said...

I've read some excellent stuff here. Certainly price bookmarking for revisiting. I wonder how a lot attempt you place to make this kind of magnificent informative web site.

Look into my homepage; binary options demo

Anonymous said...

Hi, i think that i saw you visited my website so i came to “return the favor”.
I'm trying to find things to enhance my website!I suppose its ok to use some of your ideas!!

Also visit my webpage - http://www.youtube.com/watch?v=VMJkb-bhjiI

Anonymous said...

Usually I do not learn article on blogs, but I wish to say that this write-up very forced me to try
and do it! Your writing taste has been amazed me.
Thanks, quite great post.

Also visit my weblog - mzansi cleaners

Anonymous said...

My partner and I stumbled over here coming from a
different web page and thought I might check things out. I like what I see so
i am just following you. Look forward to looking over your
web page repeatedly.

my weblog - Manchester Health Clinic

Anonymous said...

I like the valuable info you supply in your articles.
I will bookmark your blog and check again right here regularly.

I am slightly sure I will be told lots of new stuff proper here!
Good luck for the next!

Also visit my blog Manchester Health Clinic

Anonymous said...

No matteг if ѕome one ѕearсhes fοr hiѕ vital thіng, thuѕ
he/shе wаnts to be available that in detail, so that thіng
is maintaіned over here.

my web-site :: raspberry ketone uk

Anonymous said...

If some one ωants eхpert vіew on the toрic of blogging and site-building afterward
i ѕuggest him/heг to ρay a visit this ωebѕitе, Kеep up the good job.


Also visit my blοg post ... moringa oleifera

Anonymous said...

I'm not sure exactly why but this web site is loading extremely slow for me. Is anyone else having this issue or is it a problem on my end? I'll
check back later on and see if the problem still exists.

My webpage ... zorporno.com

Anonymous said...

If you desire to take a good deal from this article then you have to apply these methods to your won weblog.


my homepage - www.69videosporno.net

Anonymous said...

I think this is among the such a lot significant information for me.
And i am glad studying your article. But wanna statement
on few normal issues, The web site style is wonderful, the articles is actually excellent :
D. Just right process, cheers

Stop by my web-site - http://www.xxxvideofix.
com (www.pinkparadize.net)