0

If I have a class like:

class Node
{
    string id;
    const Node next;
}

How do I find, say, the id of the last Node in the linked list?

string lastID(const Node node)
{
    ???
}

2 Answers 2

3

I assume that your problem is that you need to loop but can't reset your variable, because it's const? If you want to have an object which refers to a const object but is re-assignable itself (i.e. it's tail-const), then use std.typecons.Rebindable. In this case, that gives you:

string lastID(const Node node)
{
    import std.typecons;
    Rebindable!(const Node) curr = node;

    while(curr.next)
        curr = curr.next;

    return curr.id;
}

I must say that I find it a bit odd though that you don't just ask about how to have a reference to a const object where the reference isn't const itself, since that's all I can see that you're really asking here, given how straightforward the loop itself is. As it stands, your question is a bit too much along the lines of asking someone to write your code for you rather than asking a question.

3
  • Yes, that was the exact problem -- I couldn't loop because it was const, and I couldn't break const because that would've been undefined behavior. Seems like Rebindable is the answer, I completely forgot about that struct; thanks.
    – user541686
    Commented Sep 20, 2012 at 5:59
  • @Mehrdad, Casting away const is not undefind. Commented Sep 20, 2012 at 10:54
  • It's casting away const and then mutating which is undefined. Commented Sep 20, 2012 at 10:59
2

You can also go fancy and use recursion:

string lastID(const Node node)
{
    if(node.next)
        return lastID(node.next);
    return node.id;
}

Do take in mind that it might cause a stack overflow if the list is very long(as far as I know D does not support tail call recursion optimization)

2
  • Yeah that's exactly why I didn't use recursion, it's not practical without a guarantee of tail recursion.
    – user541686
    Commented Sep 20, 2012 at 7:31
  • 1
    dmd currently optimizes tail recursion but not tail calls. Tail recursion == function calls itself as the last expression. Tail call == function issues a call to another function as the last expression. Without tail call optimization, mutual recursion will consume stack as you noted. digitalmars.com/pnews/…
    – jpf
    Commented Sep 22, 2012 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.