Data model, cyclic references

Question

I have the following data structure for storing meridians and parallels.

Each cartographic point stores:
A] geographic and spatial coordinates, cartographic distortions, etc.
B] pointer to north/south/east/west node.

It allows to store relationships between points, first of all their affiliation to the meridian/parallel...

 class Node2DCart 
 { 
     protected: 
             //Coordinates of the point 
             double lat; 
             double lon; 
             double lattrans; 
             double lontrans; 
             double x; 
             double y; 
 ..... 
             //Pointers to adjacent points in geographic network 
             Node2DCart *left; 
             Node2DCart *right; 
             Node2DCart *top; 
             Node2DCart *bottom; 
 ..... 
 }; 

Data structure for meridian stores longitude of the meridian, start point and end point of the meridian and number of points.

 class Meridian 
 { 
     private: 
             unsigned int points_count; 
             double longitude; 
             Node2DCart *start; 
             Node2DCart *end; 
 .... 
 }; 

All points are stored in nodes list:

typedef std::vector<Node2DCart*> TNodes2DCartList; 

class Node2DCartList 
{ 
     protected: 

             TNodes2DCartList nodes; 

     ... 
}; 

But there is a big problem writing copy constructor for Node2DList. There is a cyclic dependency between Meridian/Parallel and Node2Dlist.

Copy constructor uses std::map and replaces old points and links with new, it is not an implementation problem... However pointers start/end from class Meridian point to points from old Node2DList... Node2DList copy constructor should have to notify all meridians pointed to old Node2DList points and change all pointers to new Node2DList points. This model does not allow it.

The possible solution would be adding two pointers pointing to meridian and parallel point belongs to:

 class Node2DCart 
 { 
     protected: 
             //Coordinates of the point 
             double lat; 
             double lon; 
             double lattrans; 
             double lontrans; 
             double x; 
             double y; 
 ..... 
             //Pointers to adjacent points in geographic network 
             Node2DCart *left; 
             Node2DCart *right; 
             Node2DCart *top; 
             Node2DCart *bottom; 
 ..... 
             Meridian *m;
             Parallel *p;
 };

I am afraid that this proposed model is not good. There are still cycling references between two classes... Would someone help me to improve it? Thanks...

Answer 1

Would someone help me to improve it?

In such cases I generally resort to something like this:

 typedef int node_id_t;
 enum { NODE_NULL = 0 };
 // or enum node_id_t { NODE_NULL=0 }; for strict typing.

 class Node2DCart 
 { 
     protected:
             node_id_t id;    // id of the node
             //Coordinates of the point 
             double lat; 
             double lon; 
             double lattrans; 
             double lontrans; 
             double x; 
             double y; 
 ..... 
             //Pointers to adjacent points in geographic network 
             node_id_t left;
             node_id_t right; 
             node_id_t top; 
             node_id_t bottom; 
 ..... 
 };

 class Meridian
 {
     private:
             unsigned int points_count;
             double longitude;
             node_id_t start;
             node_id_t end;
 .... 
 };

 /* ... */

 std::vector<Node2DCart *> node_registry;

 // during initialization:
 node_registry.push_back( NULL );
 // to reserve 0th element to denote the NULL pointer

 Node2DCart *
 GetNode(node_id_t id)
 {
    // placeholder of the id range check
    return node_registry[id];
 };

 node_id_t
 AddNode(Node2DCart *n)
 {
    node_registry.push_back(n);
    return node_id_t(node_registry.size()-1);
 };

And then use the numeric node_id_t instead of Node2DCart *. One can also throw in a std::set (or std::map, updated/tested in the AddNode()) to ensure that all the Node2DCart objects are unique and if not reuse id of the existing object.

Essentially an addressing scheme, providing each node with a unique global identifier. Not the nicest/easiest solution, with a global container, but helped me more than once. Especially to avoid memory leaks and to ensure clean destruction of the whole hierarchy of interdependent objects.

Instead of typedef int node_id_t one can also use struct node_id_t { int id; }; and overload conversion operators to simplify node id lookups.

Answer 2

In my opininon, the solution replacing pointers with indices in some cases will be slow.

• If we do not delete any point, point_id will represent index of he point, eg. nodes[poin_id], it is ok.

• But if we delete any point of the list, point_id will not represent its index in the list. We will have to use std::find and get point_id of the found point. This significantly reduces the speed of the code...

• If we delete any point we can reindex list of points to avoid problems mentioned above. But we do not have to forget to reindex all meridinans start / end indices... But it takes some time and does the same as the copy constructor in the question. And I think, that affecting the data of some class by another class using copy constructor represents not very suitable proposal of the data structure...