Finish 2000-03-27 00:00:00 UTC

GFDASH

by Steve LeFever

Status: Failed
Results: []

Based on: GFD5.1a (diff)
Basis for: GFDASH2 (diff)

Comments
Please login or create a profile.
Code
function Sequence = GFD4(Segments) % MARCHE ENCORE ?

[nSegs, lSegs] = size(Segments);

hashkey = rand(lSegs,1);
[SortedHash Order]  = sort(Segments * hashkey)  ;
Segments = Segments(Order(diff([SortedHash ; 0]) ~= 0), :);
[nSegs, lSegs] = size(Segments);

theSegments = cell(nSegs, 1);
theSegs = 1:nSegs;
for index = theSegs,
   theSegments{index} = Segments(index, :);
end
copySegments = theSegments;
riteSegments = Segments;
maxkey=fix(1000*(char(84*ones(1,lSegs))*hashkey));

matchLength = lSegs-1;
while matchLength > 0
   Segments(:, 1) = [];
   riteSegments(:,end)=[];
   hashkey(1) = [];
   keyIntoTable = fix(1000*Segments*hashkey);
   tableEntries = fix(1000*riteSegments*hashkey);
   hashtable = sparse(tableEntries,ones(nSegs,1),(1:nSegs)',maxkey,1);

   for leftSeg = theSegs
      Match = hashtable(keyIntoTable(leftSeg),1);
      %Match = find(strncmp(Segments(leftSeg, :), copySegments, matchLength));
      if Match
         Select = Match(1);
         rightSeg = theSegs(Select);
         if rightSeg == leftSeg 
            if length(Match) > 1 % Rare case
               temp = Match(Match ~= Select);
               Select = temp(1);
               rightSeg = theSegs(Select); 
               
               theSegments{rightSeg} = [theSegments{leftSeg} theSegments{rightSeg}(1+matchLength:end)];
               i = find(theSegs == leftSeg);
               theSegs(i) = [];
               if length(theSegs) == 1 
                  Sequence = [theSegments{theSegs}];
                  return;
               end
               copySegments(Select) = copySegments(i);
               copySegments(i) = [];
               riteSegments(Select,:) = riteSegments(i,:);
               riteSegments(i,:) = [];
            	hashtable(tableEntries(Select),1)= 0;
            	tableEntries(Select) = tableEntries(i);
            	tableEntries(i) = [];
            	nSegs = nSegs - 1;
            	hashtable(tableEntries,1) = (1:nSegs)';
               end
         else
            theSegments{rightSeg} = [theSegments{leftSeg} theSegments{rightSeg}(1+matchLength:end)];
            i = find(theSegs == leftSeg);
            theSegs(i) = [];
            if length(theSegs) == 1 
               Sequence = [theSegments{theSegs}];
               return;
            end
            copySegments(Select) = copySegments(i);
            copySegments(i) = [];
            riteSegments(Select,:) = riteSegments(i,:);
            riteSegments(i,:) = [];
            hashtable(tableEntries(Select),1)= 0;
            tableEntries(Select) = tableEntries(i);
            tableEntries(i) = [];
            nSegs = nSegs - 1;
            hashtable(tableEntries,1) = (1:nSegs)';
         end
      end
   end
   matchLength = matchLength - 1;
end
Sequence = [theSegments{theSegs}];