Ссылки содержат ориентированный граф и нуждаются в рекурсии для обхода путей.
На шаге данных несколько дочерних элементов родительского объекта могут храниться в структуре Hash of Hashes, но рекурсия на шаге данных довольно неудобна (вам придется вручную поддерживать свой собственный стек и локальные переменные в еще одном хэше)
В Proc DS2 рекурсия гораздо более традиционна и очевидна, и доступна Package Hash. Однако хеширование Package Hash отличается от шага данных. Значения данных могут быть только скалярами, поэтому Hash of Hashes отсутствует: (.
Отсутствие хэша хэшей можно исправить, установив для хэша значение multidata. Каждые данные (дочерний элемент) ключа (родительского элемента) извлекаются с шаблоном find и циклом для has_next с find_next.
Другая проблема с хэшами в DS2 заключается в том, что они должны быть глобальными для шага data и одинаковыми для любых переменных хоста, используемых для ключей и данных. Это делает сложным управление переменными во время рекурсии. Код на глубине области N не может полагаться на глобальные переменные, которые могут быть изменены на уровне области N + 1.
К счастью, анонимный хеш может быть создан в любой области видимости, и его ссылка поддерживается локально ... но переменные ключа и данных должны быть глобальными; поэтому требуется более пристальное внимание.
Анонимный хеш используется для хранения мультиданных, полученных ключом; это необходимо, потому что рекурсия повлияет на операцию has_next get_next.
Пример кода. Требуется переменная rownum для предотвращения зацикливания, которое может произойти, если ребенку разрешено выступать в роли родителя в предыдущем ряду.
data have; rownum + 1;input
Pid cid;datalines;
1 2
2 3
2 5
3 6
4 8
5 12
6 2
8 9
9 4
12 1
12 2
12 14
13 15
14 20
14 21
14 21
15 1
run;
proc delete data=paths;
proc delete data=rows;
%let trace=;
proc ds2 libs=work;
data _null_ ;
declare double rownum pid cid id step pathid;
declare int hIndex;
declare package hash rows();
declare package hash links();
declare package hash path();
declare package hash paths();
method leaf(int _rootRow, int _step);
declare double _idLast _idLeaf;
&trace. put ' ';
&trace. put 'LEAF';
&trace. put ' ';
* no children, at a leaf -- output path;
rownum = _rootRow;
if _step < 2 then return;
* check if same as last one;
do step = 0 to _step;
paths.find(); _idLast = id;
path.find(); _idLeaf = id;
if _idLast ne _idLeaf then leave;
end;
if _idLast = _idLeaf then return;
pathid + 1;
do step = 0 to _step;
path.find();
paths.add();
end;
end;
method saveStep(int _step, int _id);
&trace. put 'PATH UPDATE' _step ',' _id ' <-------';
step = _step;
id = _id;
path.replace();
end;
method descend(int _rootRow, int _fromRow, int _id, int _step);
declare package hash h;
declare double _hIndex;
declare varchar(20) p;
if _step > 10 then return;
p = repeat (' ', _step-1);
&trace. put p 'DESCEND:' _rootRow= _fromRow= _id= _step=;
* given _id as parent, track in path and descend by child(ren);
* find links to children;
pid = _id;
&trace. put p 'PARENT KEY:' pid=;
if links.find() ne 0 then do;
&trace. put p 'NO KEY';
saveStep(_step, _id);
leaf(_rootRow, _step);
return;
end;
* convert multidata to hash, emulating hash of hash;
* if not, has_next / find_next multidata traversal would be
* corrupted by a find in the recursive use of descent;
* new hash reference in local variable;
h = _new_ hash ([hindex], [cid rownum], 0,'','ascending');
hIndex = 1;
&trace. put p 'CHILD' hIndex= cid= rownum=;
if rownum > _fromRow then h.add();
do while (links.has_next() = 0);
hIndex + 1;
links.find_next();
&trace. put p 'CHILD' hIndex= cid= rownum=;
if rownum > _fromRow then h.add();
end;
if h.num_items = 0 then do;
* no eligble (forward rowed) children links;
&trace. put p 'NO FORWARD CHILDREN';
leaf(_rootRow, _step-1);
return;
end;
* update data for path step;
saveStep (_step, _id);
* traverse hash that was from multidata;
* locally instantiated hash is protected from meddling outside current scope;
* hIndex is local variable;
do _hIndex = 1 to hIndex;
hIndex = _hIndex;
h.find();
&trace. put p 'TRAVERSE:' hIndex= cid= rownum= ;
descend(_rootRow, rownum, cid, _step+1);
end;
&trace. put p 'TRAVERSE DONE:' _step=;
end;
method init();
declare int index;
* data keyed by rownum;
rows.keys([rownum]);
rows.data([rownum pid cid]);
rows.ordered('A');
rows.defineDone();
* multidata keyed by pid;
links.keys([pid]);
links.data([cid rownum]);
links.multidata('yes');
links.defineDone();
* recursively discovered ids of path;
path.keys([step]);
path.data([step id]);
path.ordered('A');
path.defineDone();
* paths discovered;
paths.keys([pathid step]);
paths.data([pathid step id]);
paths.ordered('A');
paths.defineDone();
end;
method run();
set have;
rows.add();
links.add();
end;
method term();
declare package hiter rowsiter('rows');
declare int n;
do while (rowsiter.next() = 0);
step = 0;
saveStep (step, pid);
descend (rownum, rownum, cid, step+1);
end;
paths.output('paths');
rows.output('rows');
end;
run;
quit;
proc transpose data=paths prefix=ID_ out=paths_across(drop=_name_);
by pathid;
id step;
var id;
format id_: 4.;
run;