Hi folks, I would like to write a set implementation for expressions, or borrow one, if it has already been written. I have several questions. 1. What C++ type is best suited to representing sets? 2. Is there a hash function implemented for GiNaC expressions? 3. Can GiNaC expressions be put into some kind of canonical form? 4. (Requirement.) The hash function should be such that e.g. a + b + c * (d + e) and b + (e + d) * c + a hash to the same value. Thanks! Marko Riedel +-------------------------------------------------------------+ | Marko Riedel, EDV Neue Arbeit gGmbH, mriedel@lsi.upc.edu | | http://www.geocities.com/markoriedelde/index.html | +-------------------------------------------------------------+
Dear Marko, On Mon, 18 Sep 2006, Marko Riedel wrote:
1. What C++ type is best suited to representing sets?
There is a class set defined in the standard library. I would go for that unless there is a good reason you cannot use it. You should use
2. Is there a hash function implemented for GiNaC expressions?
Yes there is. Call the method unsigned ex::gethash() to obtain the hash value. You should use std::set<ex, ex_is_less>.
3. Can GiNaC expressions be put into some kind of canonical form?
They are automatically put into some kind of canonical form. Of course one cannot guarantee that equal expressions will end up with the same canonical form, as "being equal" is generally not a decidable property.
4. (Requirement.) The hash function should be such that e.g.
a + b + c * (d + e)
and
b + (e + d) * c + a
hash to the same value.
Both multiplications and additions are put in a canonical order, so these two expressions will actually be turning themselves into identical expressions. The terms/factors will be sorted according to their hash values. This also implies that these two expressions will have the same hashvalue automatically. Good luck! Chris
Chris Dams writes:
Dear Marko,
On Mon, 18 Sep 2006, Marko Riedel wrote:
1. What C++ type is best suited to representing sets?
There is a class set defined in the standard library. I would go for that unless there is a good reason you cannot use it. You should use
2. Is there a hash function implemented for GiNaC expressions?
Yes there is. Call the method
unsigned ex::gethash()
to obtain the hash value. You should use std::set<ex, ex_is_less>.
Hi again, I have another very basic question. Suppose I have an ordinary C structure (I will use C in my example, rather than Objective C, to keep it simple) containing some fields e.g. typedef struct { int a, b; char *name; } mystruct; Now I want to add a field to it (at compile time, of course), containing a set of expressions, using std::set<ex, ex_is_less>, as you suggested. How would I declare this field? What headers do I need to import? Furthermore I have two functions, "make_instance" and "free_instance." The function "make_instance" calls "malloc" to allocate the structure, as in inst = (mystruct *)malloc(sizeof(mystruct)); inst->a = inst->b = 0; inst->name = NULL; What do I have to do to allocate and initialize a new set of expressions, e.g. what goes on the right side of inst->set = /* ??? */ The function "free_instance" frees the name field, the set, and the structure itself, as in if(inst->name!=NULL){ free(inst->name); } /* free inst->set */ free(inst); What do I need to put on the second line (the one that frees the set). Thank you for your patience with these extremely basic questions. I belong to the class of users that are not familiar with C++ but want to use GiNaC just the same. Best regards, Marko Riedel +-------------------------------------------------------------+ | Marko Riedel, EDV Neue Arbeit gGmbH, mriedel@lsi.upc.edu | | http://www.geocities.com/markoriedelde/index.html | +-------------------------------------------------------------+
Dear Marko, You wrote:
I have another very basic question. Suppose I have an ordinary C structure (I will use C in my example, rather than Objective C, to keep it simple) containing some fields e.g.
typedef struct { int a, b; char *name; } mystruct;
Now I want to add a field to it (at compile time, of course), containing a set of expressions, using std::set<ex, ex_is_less>, as you suggested. How would I declare this field? What headers do I need to import?
#include <ginac/ginac.h> typedef struct { int a, b; char *name; std::set<GiNaC::ex, GiNaC::ex_is_less> expressionset; } mystruct;
Furthermore I have two functions, "make_instance" and "free_instance." The function "make_instance" calls "malloc" to allocate the structure, as in
inst = (mystruct *)malloc(sizeof(mystruct)); inst->a = inst->b = 0; inst->name = NULL;
What do I have to do to allocate and initialize a new set of expressions, e.g. what goes on the right side of
inst->set = /* ??? */
Nothing. As recommended in an earlier email, use the placement new istead: new(inst) mystruct. This way, the set ctor will have initialized expressionset properly. Note, that the compiler has automatically equipped mystruct with a set of default ctors.
The function "free_instance" frees the name field, the set, and the structure itself, as in
if(inst->name!=NULL){ free(inst->name); } /* free inst->set */ free(inst);
What do I need to put on the second line (the one that frees the set).
Again, nothing. Since the object was allocated with placement new, you would have to explicitly call the dtor inst->~mystruct(). Again, the compiler has automatically equpped mystruct with a dtor. -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
Richard B. Kreckel writes:
Dear Marko,
You wrote:
I have another very basic question. Suppose I have an ordinary C structure (I will use C in my example, rather than Objective C, to keep it simple) containing some fields e.g.
typedef struct { int a, b; char *name; } mystruct;
Now I want to add a field to it (at compile time, of course), containing a set of expressions, using std::set<ex, ex_is_less>, as you suggested. How would I declare this field? What headers do I need to import?
#include <ginac/ginac.h>
typedef struct { int a, b; char *name; std::set<GiNaC::ex, GiNaC::ex_is_less> expressionset; } mystruct;
[...]
Nothing. As recommended in an earlier email, use the placement new istead: new(inst) mystruct. This way, the set ctor will have initialized expressionset properly. Note, that the compiler has automatically equipped mystruct with a set of default ctors.
Thank you for the reply and for your patience. I guess I'm not explaining myself well. Consider the following problem: Someone hands me a chunk of memory through a void pointer, like so: (void *)ptr. I want the memory pointed to by "ptr" to hold a newly initialized set of GiNaC expressions. How do I do this? How do I find out the number of bytes I will need? At some point in the future, someone will hand me that same pointer and I will want to free the set of expressions that it holds. Again, how do I do this? Thanks! Best regards, Marko Riedel +-------------------------------------------------------------+ | Marko Riedel, EDV Neue Arbeit gGmbH, mriedel@lsi.upc.edu | | http://www.geocities.com/markoriedelde/index.html | +-------------------------------------------------------------+
Dear Marko, Marko Riedel wrote:
Someone hands me a chunk of memory through a void pointer, like so:
(void *)ptr.
I want the memory pointed to by "ptr" to hold a newly initialized set of GiNaC expressions. How do I do this? How do I find out the number of bytes I will need? At some point in the future, someone will hand me that same pointer and I will want to free the set of expressions that it holds. Again, how do I do this?
Same as before. Don't let yourself be fooled by a funny long type name instead of a crisp "mystruct". I suppose that should work (I haven't actually tested it): typedef std::set<GiNaC::ex, GiNaC::ex_is_less> myset; // shorthand myset* inst; inst = (myset*)malloc(sizeof(myset)); // or get inst from elsewhere new(inst) myset; // do stuff to *inst here... inst->~myset(); delete inst; Again: this is dirty stuff. But you wanted to do some interfacing. So be it... Regards -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
Richard B. Kreckel writes:
Dear Marko,
Marko Riedel wrote:
Someone hands me a chunk of memory through a void pointer, like so:
(void *)ptr.
I want the memory pointed to by "ptr" to hold a newly initialized set of GiNaC expressions. How do I do this? How do I find out the number of bytes I will need? At some point in the future, someone will hand me that same pointer and I will want to free the set of expressions that it holds. Again, how do I do this?
Same as before. Don't let yourself be fooled by a funny long type name instead of a crisp "mystruct".
I suppose that should work (I haven't actually tested it):
typedef std::set<GiNaC::ex, GiNaC::ex_is_less> myset; // shorthand myset* inst; inst = (myset*)malloc(sizeof(myset)); // or get inst from elsewhere new(inst) myset; // do stuff to *inst here... inst->~myset(); delete inst;
Okay, one last remark: the malloc should be matched up with a free, right? Giving the sequence inst = (myset*)malloc(sizeof(myset)); // or get inst from elsewhere new(inst) myset; // do stuff to *inst here... inst->~myset(); free(inst); Best regards, Marko +-------------------------------------------------------------+ | Marko Riedel, EDV Neue Arbeit gGmbH, mriedel@lsi.upc.edu | | http://www.geocities.com/markoriedelde/index.html | +-------------------------------------------------------------+
Marko Riedel wrote:
Richard B. Kreckel writes:
I suppose that should work (I haven't actually tested it):
typedef std::set<GiNaC::ex, GiNaC::ex_is_less> myset; // shorthand myset* inst; inst = (myset*)malloc(sizeof(myset)); // or get inst from elsewhere new(inst) myset; // do stuff to *inst here... inst->~myset(); delete inst;
Okay, one last remark: the malloc should be matched up with a free, right? Giving the sequence
inst = (myset*)malloc(sizeof(myset)); // or get inst from elsewhere new(inst) myset; // do stuff to *inst here... inst->~myset(); free(inst);
Yes. The example I gave was in error. -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
participants (3)
-
Chris Dams
-
Marko Riedel
-
Richard B. Kreckel