Automatic Follower

bearophile bearophileHUGS at lycos.com
Sat May 18 07:35:29 PDT 2013


Some of you maybe remember the idea of the roles of variables:

http://en.wikibooks.org/wiki/A-level_Computing/AQA/Problem_Solving,_Programming,_Data_Representation_and_Practical_Exercise/Fundamentals_of_Programming/The_Role_of_Variables

http://www.cs.joensuu.fi/~saja/var_roles/role_list.html

The idea is that in a program many variables have roles that can 
be classified in few categories. Modern languages often offer 
ways to express explicitly some of such roles, this makes the 
code more readable and sometimes less bug prone.

One of the roles that isn't built-in in D is the Follower, that 
is variables that get their value by following another data 
entity. They are "used to keep check of a previous value of a 
variable, so that a new value can be compared."

This is a basic implementation of a Follower in D (based on 
std.typecons.Nullable), with an usage example on doubly linked 
lists:


struct WithFollower(T, size_t N) {
     private T[N] _items;

     this(T value) {
         _items[0] = value;
     }

     this(T value, T pred) {
         _items[0] = value;
         _items[1] = pred;
     }

     void opAssign(T value) {
         _items[1] = _items[0];
         _items[0] = value;
     }

     @property ref inout(T) get() inout {
         return _items[0];
     }

     alias get this;

     @property predecessor() {
         return _items[1];
     }
}

auto withFollower(T, size_t N)(T[N] items...)
if (N > 0 && N < 3) {
     static if (N == 1) {
         return WithFollower!(T, 2)(items[0], T.init);
     } else static if (N == 2) {
         return WithFollower!(T, 2)(items[0], items[1]);
     } else {
         assert(0);
     }
}

// --------------------------

struct Node(T) {
     T data;
     Node* prev, next;
}

void prepend(T)(ref Node!T* head, T item) {
     auto newNode = new Node!T(item, null, head);
     if (head)
         head.prev = newNode;
     head = newNode;
}

void main() {
     import std.stdio;

     Node!(char)* head;
     foreach (char c; "DCBA")
         head.prepend(c);

     // Usual way to keep the predecessor:
     auto last = head;
     for (auto p = head; p; p = p.next) {
         p.data.write;
         last = p;
     }
     writeln;

     for (auto p = last; p; p = p.prev)
         p.data.write;
     writeln;
     writeln;

     //---------------

     // Using a follower:
     auto pf = withFollower(head, head);
     for ( ; pf; pf = pf.next)
         pf.data.write;
     writeln;

     for (auto p = pf.predecessor; p; p = p.prev)
         p.data.write;
     writeln;
}


One way to extend WithFollower is to support a user-specified 
number of past values, that is how much long the memory is.

The point of using a WithFollower is that the follower gets 
updated automatically every time you change the current item. So 
in theory this can avoid some bugs caused by forgetting to update 
the precedent value in some cases.

Bye,
bearophile


More information about the Digitalmars-d mailing list