A old post, but interesting the one about find a value in an array, when I first look, in the first post, there for me is explained a diferent pblem, when start talking about the data base thing, the problem completely change is shape!!!!!


My solution for the database thing is, first create a list of available IDs, then extract each one for your element, if you delete a element, restore the ID, by the way, you dont specify how a element get its ID...., but I think can be changed for extract a ID from this list, in this way, you dont need search, only handle more the inuse/nouse of IDs.



About the problem in a array of x elements, find a number that is not in the array, suposing with the same ... mmm... "rules" that you provide, this is no is valid repeat an ID... ok, not say a ID, but a number, and the values of a dword. I have a solution in mind, dunno if is best than the ones posted before...., I will try do myself, if not get sucess..., but I think I will get sucess...



Have a nice day or night.
Posted on 2004-01-21 17:13:04 by rea
I you just need a unique number use this:
range 0 to MAX (MAX must be below 7FFFFFFFh)
in: last used unique number (edx)
out: new unique number (edx)


mov ecx,MAX
lea eax,[edx+7FFFFFFFh] ;just a high prime
xor edx,edx
div ecx

This will use all possible numbers from 0 to MAX before repeating
Posted on 2004-01-22 13:10:57 by Joshua
Why you don't use the capabilities of the underlaying DB ? I think on autoincremental counters or an index to the ID field. You let sort it by an ascending index on ID. Then you choose easily the last record ID +1 as new ID. Suppose you have inserted 2^16 nodes, means you overflow with this method, you have to re-compress the entire database. But this happens only after 2^16 insertions of new nodes. The remaining part is O(1).
I personaly would choose an 32 Bit Long as ID Field and let it be an autoincremental counter. 2^32 Nodes are very unlikely today and storage is cheap. Thus i have only to design the database in 2 minutes and the problem where solved by the database. This is far better in a world of multi user accesses on databases.

Hagen
Posted on 2004-01-22 19:29:59 by Hagen
@Joshua, hm why so complicated. If we have separately storred the last highest ID then we could easily use ID +1 as the next ID.

But in any Database scenario this is inpracticable, because multiple client applications access in same time the same database. Managing separte ID's are then complicated.

Hagen
Posted on 2004-01-22 19:36:00 by Hagen