I mean pointers in a purely functional implementation like my lisp
code. The only reason I can think that you'd actually implement with
no pointer mutation in C++ is to improve parallel access in a
mult-threaded system. Then you'd need garbage collection (like smart
pointers for example) to make it all work. It's more likely that you
have an implementation that just uses the _idea_ of the immutable
algorithm but in fact changes pointers.
BTW, a cons is just a node with two pointers car and cdr. You can use
them any way you want. The common convention is that car points to a
list item and cdr serves as the "next" pointer. Instead, I used them
like a record with two fields. Car (by my arbitrary choice) is the
"back" list and cdr is "front." Also BTW, I tested this code with gcl
and it works fine.
In C++ a "pure" immutable queue (with garbage collection not shown)
would look something like the code below. Sorry in advance for small
errors; I haven't written C++ in a while. Of course this is calling
"new" all over the place to allocate memory that is never freed.
That's fine in Lisp because the GC will clean up the mess. It doesn't
agree very well with the C++ style of coding.
Note below that no pointer is ever assigned a value after it is
initialized!
// a list cell
struct Cons {
void *car; Cons *cdr;
Cons(void *item = 0, Cons *next = 0) { car = item; cdr = next; }
};
// reverse a list of conses in a purely functional way
Cons* reverse(Cons *src, Cons *dest = 0)
{
return src ? reverse(src->cdr, new Cons(src->car, dest)) : dest;
}
struct Queue {
Cons *front, *back;
Queue(Cons* f = 0, Cons* b = 0) { front = f; back = b; }
};
Queue* enqueue(Queue* queue, void* item)
{
return new Queue(queue->front, new Cons(item, queue->back));
}
Queue* dequeue(Queue* queue, void* &item)
{
if (queue->front) {
item = queue->front->car;
return new Queue(queue->front->cdr, queue->back);
}
if (queue->back) return dequeue(new Queue(reverse(queue->back, 0)));
return 0; // attempt to dequeue from an empty queue
}
To build a list [1,2,3], you would say
Queue* my_queue = enqueue(enqueue(enqueue(new Queue(), new Int(1)), new
Int(2)), new Int(3));
Then you could say
void* item;
my_queue = dequeue(my_queue, item);
and item would then point to the node containing 1.
Cheers!
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
