Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members

out_common.cc

Go to the documentation of this file.
00001 /* ===========================================================================
00002  *        Filename:  out_common.cc
00003  *     Description:  common functions for output writers
00004  * 
00005  *         Version:  $Rev: 3 $
00006  *         Changed:  $Date: 2005-03-02 14:30:37 -0800 (Mi, 02 Mär 2005) $
00007  *         Licence:  GPL (read COPYING file for details)
00008  * 
00009  *          Author:  Erich Schubert (eS), erich@debian.org
00010  *                   Institut für Informatik, LMU München
00011  * ======================================================================== */
00012 #include "doc.h"
00013 #include <vector>
00014 #include <map>
00015 #include <libxml/tree.h>
00016 #include <iostream>
00017 
00018 using namespace SSD;
00019 namespace SSD {
00020 
00021 /* calculate the longest increasing subsequence
00022  * easier case of LCS, longest common subsequence */
00023 void calcLIS(vector<pair<xmlNodePtr, xmlNodePtr> >& p1, vector<xmlNodePtr>& p2, vector<pair<xmlNodePtr, xmlNodePtr> >& lcs) {
00024         vector<pair<xmlNodePtr, xmlNodePtr> >::iterator pos1;
00025         vector<xmlNodePtr>::iterator pos2;
00026         /* map node ptrs to pos */
00027         int l = 0;
00028         hash_map<xmlNodePtr, int, hash<void*> > m; /* local numbers */
00029         hash_map<xmlNodePtr, int, hash<void*> >::iterator mi;
00030         /* assign increasing sequence of numbers to nodes that might appear
00031          * in second chain as well */
00032         for (pos1 = p1.begin(); pos1 != p1.end(); pos1++) {
00033                 m[pos1->second] = l;
00034                 l++;
00035         }
00036         if (l==0) return;
00037         /* translate second chain to ints using the sequence made above */
00038         vector<int> list;
00039         for (pos2 = p2.begin(); pos2 != p2.end(); pos2++) {
00040                 mi = m.find(*pos2);
00041                 if (mi != m.end())
00042                         list.push_back(mi->second);
00043         }
00044         /* make lookup table */
00045         l = list.size();
00046         if (l<=0) return;
00047         vector<int> len(l,1);
00048         vector<int> next(l,-1);
00049         for (int k=l-2; k>=0; k--)
00050                 for (int n=l-1; n>k; n--)
00051                         if ( (list[n] > list[k]) && (len[n]+1 > len[k]) ) {
00052                                 len[k] = len[n] + 1;
00053                                 next[k] = n;
00054                         }
00055         /* read longest list */
00056         int end=0;
00057         int max=0;
00058         for (int k=0; k<l; k++)
00059                 if (len[k] > max) { end=k; max = len[k]; }
00060         /* extract longest list */
00061         for (int k=end; k>=0; k = next[k]) {
00062                 lcs.push_back(p1[list[k]]);
00063         }
00064 #if 0
00065         /* debug output */
00066         cout << "LCS: " << max << ": ";
00067         for (int k=end; k>=0; k = next[k]) {
00068                 cout << k << ":" << p1[list[k]].first->name << " ";
00069                 if (p1[list[k]].first->name && p1[list[k]].first->children)
00070                         cout << "(" << xmlNodeGetContent(p1[list[k]].first->children) << ") ";
00071         }
00072         cout << endl;
00073 #endif
00074 }
00075 
00076 } /* namespace end */

Generated on Thu Aug 4 17:57:12 2005 for SSDDiff by  doxygen 1.4.3-20050530