I'm trying to mimic the functionality of useful enums, since Java doesn't have them. The idea is to be able to turn a BNCS packet id in to an object and back. Normally, this wouldn't be difficult, but Java doesn't allow you to specify ordinals; it assigns them automatically, incrementally beginning with zero. Therefore, it would be possible to simply specify a constant for each unused packet id, but I don't like that solution too much.
Here's what I've got now; I don't like the fromId() method in its current state because it has to search - this could be replaced with a map of some kind, which could potentially drop the algo from O(n) to O(log(n)), or an array to drop it to O(1), which would be equivalent to mapping each unused constant.
Does anyone have a better solution, or ideas to improve upon what I've got? I may just switch to defining the unused IDs.
FWIW, I'm doing this because it's useful for logging, it simplifies my switch statements, and I like being type safe.
/**
* This file is distributed under the GPL
* $Id: BNCSCommandIDs.java 755 2007-10-15 05:43:55Z scotta $
*/
package net.bnubot.core.bncs;
import net.bnubot.core.EnumIdNotPresentException;
public enum BNCSCommandIDs {
SID_NULL(0x00),
SID_STOPADV(0x02),
SID_CLIENTID(0x05),
SID_STARTVERSIONING(0x06),
SID_REPORTVERSION(0x07),
SID_STARTADVEX(0x08),
SID_GETADVLISTEX(0x09),
SID_ENTERCHAT(0x0A),
SID_GETCHANNELLIST(0x0B),
SID_JOINCHANNEL(0x0C),
SID_CHATCOMMAND(0x0E),
SID_CHATEVENT(0x0F),
SID_LEAVECHAT(0x10),
SID_LOCALEINFO(0x12),
SID_FLOODDETECTED(0x13),
SID_UDPPINGRESPONSE(0x14),
SID_CHECKAD(0x15),
SID_CLICKAD(0x16),
SID_MESSAGEBOX(0x19),
SID_STARTADVEX3(0x1C),
SID_LOGONCHALLENGEEX(0x1D),
SID_CLIENTID2(0x1E),
SID_LEAVEGAME(0x1F),
SID_DISPLAYAD(0x21),
SID_NOTIFYJOIN(0x22),
SID_PING(0x25),
SID_READUSERDATA(0x26),
SID_WRITEUSERDATA(0x27),
SID_LOGONCHALLENGE(0x28),
SID_LOGONRESPONSE(0x29),
SID_CREATEACCOUNT(0x2A),
SID_GAMERESULT(0x2C),
SID_GETICONDATA(0x2D),
SID_GETLADDERDATA(0x2E),
SID_FINDLADDERUSER(0x2F),
SID_CDKEY(0x30),
SID_CHANGEPASSWORD(0x31),
SID_CHECKDATAFILE(0x32),
SID_GETFILETIME(0x33),
SID_QUERYREALMS(0x34),
SID_PROFILE(0x35),
SID_CDKEY2(0x36),
SID_LOGONRESPONSE2(0x3A),
SID_CHECKDATAFILE2(0x3C),
SID_CREATEACCOUNT2(0x3D),
SID_LOGONREALMEX(0x3E),
SID_STARTVERSIONING2(0x3F),
SID_QUERYREALMS2(0x40),
SID_QUERYADURL(0x41),
SID_WARCRAFTGENERAL(0x44),
SID_NETGAMEPORT(0x45),
SID_NEWS_INFO(0x46),
SID_OPTIONALWORK(0x4A),
SID_EXTRAWORK(0x4B),
SID_REQUIREDWORK(0x4C),
SID_AUTH_INFO(0x50),
SID_AUTH_CHECK(0x51),
SID_AUTH_ACCOUNTCREATE(0x52),
SID_AUTH_ACCOUNTLOGON(0x53),
SID_AUTH_ACCOUNTLOGONPROOF(0x54),
SID_AUTH_ACCOUNTCHANGE(0x55),
SID_AUTH_ACCOUNTCHANGEPROOF(0x56),
SID_AUTH_ACCOUNTUPGRADE(0x57),
SID_AUTH_ACCOUNTUPGRADEPROOF(0x58),
SID_SETEMAIL(0x59),
SID_RESETPASSWORD(0x5A),
SID_CHANGEEMAIL(0x5B),
SID_SWITCHPRODUCT(0x5C),
SID_GAMEPLAYERSEARCH(0x60),
SID_FRIENDSLIST(0x65),
SID_FRIENDSUPDATE(0x66),
SID_FRIENDSADD(0x67),
SID_FRIENDSREMOVE(0x68),
SID_FRIENDSPOSITION(0x69),
SID_CLANFINDCANDIDATES(0x70),
SID_CLANINVITEMULTIPLE(0x71),
SID_CLANCREATIONINVITATION(0x72),
SID_CLANDISBAND(0x73),
SID_CLANMAKECHIEFTAIN(0x74),
SID_CLANINFO(0x75),
SID_CLANQUITNOTIFY(0x76),
SID_CLANINVITATION(0x77),
SID_CLANREMOVEMEMBER(0x78),
SID_CLANINVITATIONRESPONSE(0x79),
SID_CLANRANKCHANGE(0x7A),
SID_CLANSETMOTD(0x7B),
SID_CLANMOTD(0x7C),
SID_CLANMEMBERLIST(0x7D),
SID_CLANMEMBERREMOVED(0x7E),
SID_CLANMEMBERSTATUSCHANGE(0x7F),
SID_CLANMEMBERRANKCHANGE(0x81),
SID_CLANMEMBERINFORMATION(0x82);
private final int id;
private BNCSCommandIDs(int id) {
this.id = id;
}
public int getId() {
return id;
}
public static BNCSCommandIDs fromId(int id) throws EnumIdNotPresentException {
// TODO: replace this with a map
for(BNCSCommandIDs command : values())
if(command.getId() == id)
return command;
throw new EnumIdNotPresentException(BNCSCommandIDs.class, id);
}
}
Quote from: Camel on October 15, 2007, 01:44:08 AM
...could potentially drop the algo from O(n) to O(log(n)), or an array to drop it to O(1),...
This is
totally off-topic, but could you please explain this concept to me? O(n), O(log(n)), etc.?
It's in my AP Computer Science review book, and it doesn't make any sense whatsoever.
When I get home from school, I'll post what it's called. I just know that in the first section I understood all the "review" but this since I've never encountered it.
Quote from: Newby on October 15, 2007, 10:02:11 AM
Quote from: Camel on October 15, 2007, 01:44:08 AM
...could potentially drop the algo from O(n) to O(log(n)), or an array to drop it to O(1),...
This is totally off-topic, but could you please explain this concept to me? O(n), O(log(n)), etc.?
It's in my AP Computer Science review book, and it doesn't make any sense whatsoever.
When I get home from school, I'll post what it's called. I just know that in the first section I understood all the "review" but this since I've never encountered it.
It's called Big-O notation. It looks pretty easy (it's basically the worst case time, where n is the number of elements). But it gets nasty fast with stuff like recursion.
O(n) means that the algorithm will loop n times in the worst case. O(log(n)) means it'll loop log(n) times in the worst case, etc.
Sounds easy, but it's not. :)
Quote from: Newby on October 15, 2007, 10:02:11 AM
This is totally off-topic, but could you please explain this concept to me? O(n), O(log(n)), etc.?
It's in my AP Computer Science review book, and it doesn't make any sense whatsoever.
When I get home from school, I'll post what it's called. I just know that in the first section I understood all the "review" but this since I've never encountered it.
To elaborate on what iago said, big-O notation is an asymptotic upper bound. It doesn't necessarily mean that the program will loop through n or log(n) times. It could loop through n/2+4log(n) times if it is O(n) or 10000000000000000000000*log(n) times if it is O(log(n)). To define it formally, there exists some C and k such that
(http://latex.sidoh.org/?render64=ZihuKSQgaXMgJE8oZyhuKSkkIGlmICRcZm9yYWxsIHggPiBrLCB8ZihuKXwgXGxlcSBDfGcobil8JA==)
However, it's rare that this definition is used. It's sort of like the definition of a limit. It's important to mathematically define it in a concise manner, but unnecessary to use said definition after it has been proven.
So, you basically find some k and C (called "witnesses") so that a function can be written in the form shown above. So, for example, if
(http://latex.sidoh.org/?render64=JGYobik9eF40K3heMyt4XGxvZ3t4fQ==)
Then you can see that (http://latex.sidoh.org/?render64=XGZvcmFsbCB4IFxnZXEgMQ==), (http://latex.sidoh.org/?render64=eF4zIFxsZXEgeF40) and (http://latex.sidoh.org/?render64=eFxsb2d7eH0gXGxlcSB4XjQ=). We then let (http://latex.sidoh.org/?render64=az0x). We can then write (http://latex.sidoh.org/?render64=ZyhuKT14XjQ=) and let (http://latex.sidoh.org/?render64=Qz0z).
To put it all into place (http://latex.sidoh.org/?render64=XGZvcmFsbCB4ID4gMSAkXHF1YWQkIHx4XjQreF4zK3hcbG9ne3h9fFxsZXEgM3heNCA=).
This means that (http://latex.sidoh.org/?render64=Zih4KSAkIGlzICQgTyh4XjQp).
You can see that the "algorithm" to find the big O of a function is to find the fastest growing term, ignore all of the other ones and drop any coefficients associated with the chosen term.
There are also other "bounding" functions that are more descriptive. You obviously lose a lot of that using big-O. Big-theta, which is a tighter asymptotic bound, is used when you don't want to lose that data. They're usually a bit harder to find, though.
Hope this helps.
And that's what I mean when I say "it gets complicated" :P
So no one has a better solution to java's inability to specify ordinals?
@Newby: I like to think of it as an approximation of a number proportional (ie, drop any constants) to the worst case run-time where n is the number of elements as it approaches infinity. If you haven't done anything with limits, this can still be useful if you just accept that the purpose of them in this case is to drop all of the things that are not of the highest order; consider:
int f = 0;
for(int i = 0; i < n; i++)
f++;
If you wanted to find out how many mathematical operations (compairsons, addition, subraction, et al) this algorithm did, you could re-write it to this:
int f = 0;
int i = 0;
loop:
if(i < n) {
f++;
i++;
goto loop;
}
So, now it's simpler to see how many operations are done: before the loop, there are 2, and inside of the loop there is one comparison and two increments. You could write the run-time as 2+3*n, but since we're looking for (http://latex.sidoh.org/?render64=XGxpbV97blx0b1xpbmZ0eX0gWyBydW50aW1lKGYobikpIF0gPSBrXHRpbWVzIE8oZihuKSkgXQ==), we see that O(f(n)) becomes 3*n/k, or just n; it's expressed O(n).
An example of O(log(n)) would be a quicksort, because the number of iterations increases linearly as n increases proportionally. That is to say, each time you double the size of the input array, the run-time increases by a constant amount.
HTH
Quote from: iago on October 15, 2007, 12:44:59 PM
And that's what I mean when I say "it gets complicated" :P
I know. Newby is more than capable of understanding everything I said, though, so I figured I'd put all of it out there.
I'm sure there are algorithms when it becomes sort of difficult to prove that they are O(f(n)), but I think most of them can be found intuitively pretty quickly, at least when compared to some of the other bounding notations.
Quote from: Camel on October 15, 2007, 01:04:40 PM
An example of O(log(n)) would be a quicksort, because the number of iterations increases linearly as n increases proportionally. That is to say, each time you double the size of the input array, the run-time increases by a constant amount.
Quicksort is (http://latex.sidoh.org/?render64=TyhuXGxvZ3tufSk=) in the average case, (http://latex.sidoh.org/?render64=TyhuXjIp) in the worse case (which occurs when the list is already sorted).
An example of a (http://latex.sidoh.org/?render64=TyhcbG9ne259KQ==) algorithm is binary search.
Oh, and for the record, in computer science when we're dealing with things like this (as Camel hinted at), we normally assume that (http://latex.sidoh.org/?render64=XGxvZ3syfT0x). That is to say, we use base-2 logarithms. I've seen it denoted as "lg(n)" before, but only in contexts where using "log(n)" might be ambiguous or if the professor or whoever wants to be really concise.
I'm sure Camel already knows this, but since we're talking big O, I might as well throw this out there. (http://latex.sidoh.org/?render64=TyhuXGxvZ3tufSk=) is the best we can do in the general-case for sorting algorithms. There exist specialized sorts (radix/bucket sort) that are (http://latex.sidoh.org/?render64=TyhuKQ==), but they require that you know something about the domain of the inputs in order to work. The classic class-example of this is a deck of cards. You know that there are four suits and 14 different types of cards. You create four buckets for the suits, and then fourteen buckets for each of the types of the cards and then you "merge" the buckets.
I don't know about the original problem, Camel. I suppose you could do binary search instead of a linear search, if you make sure everything is in ascending order? That's better than the O(n) you have there. I guess that's what you were hinting at, though. It's sort of an ugly problem, because you're going to have to muck something up. You either do a search, which seems silly, or add a bunch of filler elements, which also seems silly. I say you tell Java to fix the way enums work. :)
Make a hashmap of the enums, then it's O(1).
Nevermind, you said that in your post lol.
Quote from: Ender on October 15, 2007, 02:52:40 PM
Nevermind, you said that in your post lol.
Yeah, that's what I thought of right away until I saw what he wanted to use it for. It'd be way more hideous to use outside the class, but the class sure would look cleaner!
I can't think of anything off the top of my head that wouldn't add its own problems.
Newby, take an advanced Discrete Math or algorithm analysis class if you are interested in big O or big Omega/Theta
Quote from: Chavo on October 15, 2007, 03:00:28 PM
Newby, take an advanced Discrete Math or algorithm analysis class if you are interested in big O or big Omega/Theta
That's wholly unnecessary to understand what they are or how to find them. There are clearly quite a few little details that we all left out, but the posts in this thread should give him a damn good idea of what big O is, how to find some g(n) such that f(n) is O(g(n)) and why it's useful.
Yes, I know. That's why I stated "if you are interested" :) Consider it an aside, not a replacement for the explanations already given.
Quote from: Chavo on October 15, 2007, 03:08:29 PM
Yes, I know. That's why I stated "if you are interested" :) Consider it an aside, not a replacement for the explanations already given.
Ah, I see what you're saying.
Algorithms is an interesting section of computer science. So far, it's been my favorite (lol @ firefox telling me that favorite should be favourite). I haven't done much with many of the other big branches (AI, embedded systems, etc) yet, but I like how abstract algorithms is.
Quote from: Camel on October 15, 2007, 01:04:40 PM
So no one has a better solution to java's inability to specify ordinals?
Yes. Use C#. :P
Quote from: MyndFyrex86/64] link=topic=10474.msg132999#msg132999 date=1192477583]
Quote from: Camel on October 15, 2007, 01:04:40 PM
So no one has a better solution to java's inability to specify ordinals?
Yes. Use C#. :P
Quote from: Sidoh on October 15, 2007, 01:56:56 PM
Quote from: Camel on October 15, 2007, 01:04:40 PM
An example of O(log(n)) would be a quicksort, because the number of iterations increases linearly as n increases proportionally. That is to say, each time you double the size of the input array, the run-time increases by a constant amount.
Quicksort is (http://latex.sidoh.org/?render64=TyhuXGxvZ3tufSk=) in the average case, (http://latex.sidoh.org/?render64=TyhuXjIp) in the worse case (which occurs when the list is already sorted).
An example of a (http://latex.sidoh.org/?render64=TyhcbG9ne259KQ==) algorithm is binary search.
Oops! I edited my post, and forgot to proof read it.
Quote from: Sidoh on October 15, 2007, 01:56:56 PM
I don't know about the original problem, Camel. I suppose you could do binary search instead of a linear search, if you make sure everything is in ascending order? That's better than the O(n) you have there. I guess that's what you were hinting at, though. It's sort of an ugly problem, because you're going to have to muck something up. You either do a search, which seems silly, or add a bunch of filler elements, which also seems silly. I say you tell Java to fix the way enums work. :)
Since the packet IDs are mostly used, I will just fill in the gaps with SID_UNKNOWN_0x??s
Must... refrain... from making a big O joke.
If you must bump old topics, you should at least have something to contribute.