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

diff.h

Go to the documentation of this file.
00001 /* ===========================================================================
00002  *        Filename:  diff.h
00003  *     Description:  Diff classes
00004  * 
00005  *         Version:  $Rev: 8 $
00006  *         Changed:  $Date: 2005-08-04 15:05:09 -0400 (Do, 04 Aug 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 #ifndef SSD_DIFF_H
00013 #define SSD_DIFF_H
00014 #include "node.h"
00015 #include "doc.h"
00016 #include <vector>
00017 #include <map>
00018 #include <set>
00019 #include <fstream>
00020 
00021 using namespace std;
00022 using namespace __gnu_cxx;
00023 
00024 namespace SSD {
00025 
00027 class Diff {
00028 protected:
00030         Doc*    doc1;
00032         Doc*    doc2;
00033 public:
00037         Diff(Doc& eins, Doc& zwei) : doc1(&eins), doc2(&zwei) {};
00039         virtual ~Diff() {};
00042         virtual bool run() = NULL;
00043 };
00044 
00057 class NodeAssignments {
00058 public:
00060         Node* n1;
00062         Node* n2;
00064         NodeAssignments* next;
00066         int refcount;
00067 
00073         NodeAssignments(Node* nn1, Node* nn2, NodeAssignments* nnext);
00076         bool release();
00078         ~NodeAssignments();
00079 };
00080 
00085 class DiffDijkstraState {
00086 public:
00087 #ifdef VERBOSE_SEQCOUNT
00088 
00089         int seq;
00090 #endif
00091 
00092         int cost;
00096         int credits_used;
00098         int length;
00102         bool complete;
00103         /* FIXME: replace this by an interator over a vector of nodes.
00104          * Then we can reorder them and will not need the
00105          * "next" pointer in the Node structure either */
00108         NodeVec::const_iterator iter;
00110         NodeAssignments* ass;
00111 
00113         RelCount* credit;
00114 
00123         DiffDijkstraState(int c, int u, int l, NodeVec::const_iterator p, NodeAssignments* a, RelCount* cr) :
00124 #ifdef VERBOSE_SEQCOUNT
00125                 seq(0),
00126 #endif
00127                 cost(c), credits_used(u), length(l), complete(false), iter(p), ass(a), credit(cr) {};
00129         ~DiffDijkstraState() { if (ass && ass->release()) delete(ass); if (credit) delete(credit); }
00133         const NodeAssignments* findNodeAssignment1(Node* n1) const;
00137         const NodeAssignments* findNodeAssignment2(Node* n2) const;
00145         bool operator<(const DiffDijkstraState& other) const {
00146                 return (cost != other.cost) ? (cost < other.cost) :
00147                        (credits_used != other.credits_used) ? (credits_used < other.credits_used) :
00148                        (length > other.length);
00149         };
00150 };
00151 
00154 struct DiffDijkstraStateQueue {
00157         bool operator()(const DiffDijkstraState* s1, const DiffDijkstraState* s2) const {
00158                 return *s1 < *s2;
00159         }
00160 };
00161 
00164 class DiffDijkstra : public Diff {
00165 private:
00166 #ifdef VERBOSE_SEQCOUNT
00167 
00168         int seq;
00169 #endif
00170 
00171         int steps;
00173         multiset<DiffDijkstraState*, DiffDijkstraStateQueue >   worklist;
00176         bool                    step();
00181         DiffDijkstraState*      makeState(const DiffDijkstraState* state, NodeVec::const_iterator n1, Node* n2);
00182 
00184         NodeVec nodevec;
00185 
00186 #ifdef TRACING_ENABLED
00187 
00188         static std::ofstream*   searchTreeOutputStream;
00189 #endif
00190 public:
00192         static bool             fastApproximativeMode;
00194         DiffDijkstraState*      result;
00198         DiffDijkstra(Doc& eins, Doc& zwei);
00200         ~DiffDijkstra();
00203         bool run();
00204 #ifdef TRACING_ENABLED
00205 
00206         static void setSearchTreeOutput(char* filename);
00207 #endif
00208 };
00209 
00210 }
00211 #endif /* DIFF_H */

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