Re: Growing ordered set

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Charles Greathouse [2014-11-20 19:42]:
> Fairly often I have a problem of the type 'generate a number by a given
> process, and repeat until a duplicate is found'. I also have the related
> problem 'generate a number by a given process, and repeat until some limit,
> recording the number of distinct elements at each step'.
> 
> What's a good way to go about this in GP?

I don't see any generic way in GP. I'd throw the required 3 lines in
a C file using our generic hashtables and install it with a simple wrapper...

  // generic hash table of initial size 100, allocated on stack; keys are GENs
  hashtable *h = hash_create(100, &hash_GEN, &gidentical, 1);

  // if key k not present, insert (arbitrary) NULL as associated value
  if (!hash_search(h, (void*)k))
    hash_insert(h, (void*)k, NULL);

(can be made more efficient by implementing a trivial routine fusing the
last two steps)


There are three main reasons we can't export this in GP without major
nightmares :

1) struct hashtable is not a GEN, and neither are its components; it
doesn't fit the memory model (gerepile, etc.).

2) there'd be no way to handle this in a "safe" way in GP without deep
copies all around, making the mechanism much less efficient than it
should. The current implementation uses only pointers and assumes 
keys/values are permanent.

3) GP2C


Cheers,

    K.B.

P.S. The way I usually work around such problems is by having a global
variable in a C file corresponding to the unique instance of the C
struct I want to handle, and add simple GP-friendly methods with GEN
arguments / return values, which are allowed to manipulate that private data.

I have a working interface to IBM/Ilog CPLEX for instance:
2 globals CPXENVptr / CPXLPptr, and a few exported methods
init/add_constraint/add_objective, minimize/maximize, set variable type
[real/integer], etc. The whole thing is about 230 lines of C code
and allows me to drive huge linear programs through GP.

If you want multiple instances of that foreign class, then you store
then in a table, thereby indexing them by small integers, and pass the
integer key as an extra argument (specifying the affected instance)
via your GP functions.

And of course you must make everything orthogonal to GP/PARI stack and
garbage collections !

--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`