D.ershane Solutions Ddili.org

Pointers

  1. When parameters are value types like int, the arguments are copied to functions. The preferred way of defining reference parameters is to specify them as ref.

    Another way is to define the parameters as pointers that point at the actual variables. The parts of the program that have been changed are highlighted:

    void swap(int * lhs, int * rhs) {
        int temp = *lhs;
        *lhs = *rhs;
        *rhs = temp;
    }
    
    void main() {
        int i = 1;
        int j = 2;
    
        swap(&i, &j);
    
        assert(i == 2);
        assert(j == 1);
    }
    

    The checks at the end of the program now pass.

  2. Node and List have been written to work only with the int type. We can convert these types to struct templates by adding (T) after their names and replacing appropriate ints in their definitions by Ts:
    struct Node(T) {
        T element;
        Node * next;
    
        string toString() const {
            string result = to!string(element);
    
            if (next) {
                result ~= " -> " ~ to!string(*next);
            }
    
            return result;
        }
    }
    
    struct List(T) {
        Node!T * head;
    
        void insertAtHead(T element) {
            head = new Node!T(element, head);
        }
    
        string toString() const {
            return format("(%s)", head ? to!string(*head) : "");
        }
    }
    

    List can now be used with any type:

    import std.stdio;
    import std.conv;
    import std.string;
    
    // ...
    
    struct Point {
        double x;
        double y;
    
        string toString() const {
            return format("(%s,%s)", x, y);
        }
    }
    
    void main() {
        List!Point points;
    
        points.insertAtHead(Point(1.1, 2.2));
        points.insertAtHead(Point(3.3, 4.4));
        points.insertAtHead(Point(5.5, 6.6));
    
        writeln(points);
    }
    

    The output:

    ((5.5,6.6) -> (3.3,4.4) -> (1.1,2.2))
    
  3. In this case we need another pointer to point at the last node of the list. The new code is necessarily more complex in order to manage the new variable as well:
    struct List(T) {
        Node!T * head;
        Node!T * tail;
    
        void append(T element) {
            /* Since there is no node after the last one, we set
             * the new node's next pointer to 'null'. */
            auto newNode = new Node!T(element, null);
    
            if (!head) {
                /* The list has been empty. The new node becomes
                 * the head. */
                head = newNode;
            }
    
            if (tail) {
                /* We place this node after the current tail. */
                tail.next = newNode;
            }
    
            /* The new node becomes the new tail. */
            tail = newNode;
        }
    
        void insertAtHead(T element) {
            auto newNode = new Node!T(element, head);
    
            /* The new node becomes the new head. */
            head = newNode;
    
            if (!tail) {
                /* The list has been empty. The new node becomes
                 * the tail. */
                tail = newNode;
            }
        }
    
        string toString() const {
            return format("(%s)", head ? to!string(*head) : "");
        }
    }
    

    The new implementation of insertAtHead() can actually be shorter:

        void insertAtHead(T element) {
            head = new Node!T(element, head);
    
            if (!tail) {
                tail = head;
            }
        }
    

    The following program uses the new List to insert Point objects with odd values at the head and Point objects with even values at the end.

    void main() {
        List!Point points;
    
        foreach (i; 1 .. 7) {
            if (i % 2) {
                points.insertAtHead(Point(i, i));
    
            } else {
                points.append(Point(i, i));
            }
        }
    
        writeln(points);
    }
    

    The output:

    ((5,5) -> (3,3) -> (1,1) -> (2,2) -> (4,4) -> (6,6))