Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.physics > #612073

My diffs now _perfectly match MicroSoft's WinMerge.

Cross-posted to 3 groups.

Show all headers | View raw

I wrote:
> My guide: " Dynamic Programming | Set 4 (Longest Common Subsequence) "
>   http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

As is turns out, the The Longest Common Sequence ( NonContiguous ) algorithm,
outlined above, works better than what I was using before.
It uses a table, not recursion; recursion overflows the stack.

My diffs now _perfectly match MicroSoft's WinMerge.
Now _any whitspace change, including blank lines, is flaged.
Now, certain odd cases produce smaller diffs, which is _nice.
Before, my sequence of LeftOlder diffs was slightly different from RightNewer.

The code:

  //  ScreenShot:  http://Jeff-Relf.Me/Diff.PNG
  //  Help/Settings:  http://Jeff-Relf.Me/X.HTM

  //  _FileCmp(), below, records thousands of matching lines ( text ),
  //  LeftOlder vs RightNewer, using the "LongestCommonSequence"
  //  ( shortest diffs ) algorithm.
  //  
  //  BB is a pointer to the start of 
  //  a dynamic array of ( contiguous ) pointers ( lines );
  //  PP points to the end of the array.
  //  
  //   BB and  PP are from the LeftOlder file.
  //  _BB and _PP are from the RightNewer file.

  _FileCmp( LnA BB, LnA _BB, LnA PP, LnA _PP, LnT &Ln ) { 

    int Rows = PP - BB + 1, Cols = _PP - _BB + 1 ;  u64 Row = Rows, Col = Cols ;

    //  Allocate a " LeftOlderLines * RightNewerLines " table of 32 bit integers
    //  to store all LongestCommonSequence Lengths.
 
    pInt _Table = (pInt)MallocTmp( Rows * Cols * szInt );
    { LoopRow( Rows ) { LoopCol( Cols ) { 

        if ( !Row || !Col ) { Table( Row, Col ) = 0 ;  continue ;  }
        if ( aMatch ) Table( Row, Col ) = Table( Row - 1, Col - 1 ) + 1 ; 
        else Table( Row, Col ) = ER( Table( Row, Col - 1 ), Table( Row - 1, Col ) );  } } }

    //  " Ln " is a dynamic array of thousands of ( contiguous ) 64 bit pointers,
    //  repurosed to store two 32 bit intergers ( Row and Col ) in a pointer.
    //  If both files are the same, with X Lines, it'll store X RowCol pairs.
    //  
    //  The first " StoreRowColumn ", below, stores the end of the files;
    //  the last is first, and vice versa; it's reversed.

    Zero( Ln ), StoreRowColumn;  
    while ( Row > 0 && Col > 0 ) 
      if ( aMatch ) StoreRowColumn ;
      else Table( Row, Col - 1 ) > Table( Row - 1, Col ) ? Col-- : Row-- ;  }


Near Globals:

  //  Access " _Table ", a One Dimensional array, as if it were Two Dimensional.
  #define  Table( i, j )  _Table[ ( j ) * Rows + i ]

  //  F[-1] is the ( 16 bit ) length of the leading whitespace.
  #define  aMatch  ( F = BB[ Row - 1 ], _F = _BB[ Col - 1 ], F[-1] == _F[-1] && Eq( F, _F ) )

  //  Store the matching lines as line numbers from LeftOlder and RightNewer 
  #define  StoreRowColumn  ( Inc( Ln ) = LnP( Row - 1 << 32 | Col - 1 ), Row--, Col-- )

  LnP  F, _F ;

Far Globals:

  #define  Zero( X )  memset( & X, 0, sizeof X )
  #define  Eq  !strCmp

  #define  LoopRows( N )  int  Row = -1, eRow = ( N ) - 1 ; while ( ++Row <= eRow )
  #define  LoopCols( N )  int  Col = -1, eCol = ( N ) - 1 ; while ( ++Col <= eCol )

  typedef wchar_t  wchar ;  typedef wchar  *LnP ;  typedef  LnP  *LnA ; 
  typedef int  *pInt ;  typedef void  *Void_P ;  typedef unsigned __int64  u64 ;
  const int  szInt = sizeof( int );

  struct  LnT { LnA  BB, PP, maxPP ;  };  LnT  Ln ;

  //  " Inc() ", below, dynamically allocates thousands of ( contiguous ) pointers.
  //  When diff is done, " Temp_Heap " is simply destroyed.

  template < typename TyT, typename TyA, typename TyP >
  TyP & Inc( TyT  & Xx, int N ) {  int I_PP, I_PP_New, I_maxPP, rv, Sz, Temp_Heap = N >= 0 ;  if ( !Temp_Heap ) N = 1 ;
    I_PP = !Xx.PP ? -1 : Xx.PP - Xx.BB, I_maxPP = !Xx.maxPP ? 0 : Xx.maxPP - Xx.BB, I_PP_New = I_PP + N ;  if( I_maxPP < 0 ) exit(1);
    if ( I_PP_New < I_maxPP ) {    OK:    return  Xx.PP = Xx.BB + I_PP_New, *Xx.PP ;  }
    rv = ER( 1024, 3 * I_PP_New ), Sz = 16 + rv * szPtr ; 
    Xx.maxPP = Xx.BB = TyA( Temp_Heap ? ReAllocTmp( Xx.BB, ++I_PP * szPtr, Sz ) : realloc( Xx.BB, Sz ) ), Xx.maxPP += rv ;
    if( !Xx.BB ) exit(1);  goto OK ;    }

  LnP &Inc( LnT &Ln ) { return Inc< LnT, LnA, LnP>( Ln,  1 ) ;  }

  LnP ReAllocTmp( Void_P B⁰, int Sz⁰, int Sz ) { Void_P  B = B⁰ ; if ( Sz > 0 && Sz > Sz⁰ ) B = MallocTmp( Sz );
    if ( B⁰ && Sz⁰ > 0 ) memmove( B, B⁰, Sz⁰ );  return LnP( B );  }

Back to sci.physics | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

#define came from God himself, it's sacred. Jeff-Relf.Me <@.> - 2017-01-01 23:51 -0800
  #define came from God himself, it's sacred. Jeff-Relf.Me <@..yep> - 2017-01-02 08:00 +0000
    Re: #define came from God himself, it's sacred. moroney@world.std.spaamtrap.com (Michael Moroney) - 2017-01-03 03:58 +0000
      I completely reWrote it, of course. Jeff-Relf.Me <@.> - 2017-01-03 00:46 -0800
        I completely reWrote it, of course. Jeff-Relf.Me <@..sour> - 2017-01-03 08:51 +0000
          Re: I completely reWrote it, of course. Double-A <double-a3@hush.com> - 2017-01-05 16:12 -0800
        Re: I completely reWrote it, of course. Peter Köhlmann <peter-koehlmann@t-online.de> - 2017-01-03 12:13 +0100
          Re: I completely reWrote it, of course. Melzzzzz <mel@zzzzz.com> - 2017-01-03 12:28 +0100
          Re: I completely reWrote it, of course. chrisv <chrisv@nospam.invalid> - 2017-01-03 07:32 -0600
            Ezekiel lives in your head RENT FREE!!  LOL!!! GreyCloud <mist@cumulus.com> - 2017-01-03 12:16 -0700
            With "warnings as errors", turn off these warnings. Jeff-Relf.Me <@.> - 2017-01-03 13:00 -0800
          Re: I completely reWrote it, of course. GreyCloud <mist@cumulus.com> - 2017-01-03 12:16 -0700
            Re: I completely reWrote it, of course. red floyd <dont.bother@its.invalid> - 2017-01-03 12:30 -0800
              If you're retarded then, yes, _Loop() is "undefined". Jeff-Relf.Me <@.> - 2017-01-16 11:06 -0800
            Re: I completely reWrote it, of course. scott@slp53.sl.home (Scott Lurndal) - 2017-01-04 13:33 +0000
              Re: I completely reWrote it, of course. chrisv <chrisv@nospam.invalid> - 2017-01-04 07:45 -0600
                Re: I completely reWrote it, of course. scott@slp53.sl.home (Scott Lurndal) - 2017-01-04 14:54 +0000
                The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). Jeff-Relf.Me <@.> - 2017-01-04 10:17 -0800
                Re: The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). Peter Köhlmann <peter-koehlmann@t-online.de> - 2017-01-04 19:19 +0100
                Re: The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). noTthaTguY <abu.kuanysh05@gmail.com> - 2017-01-04 16:33 -0800
                Re: The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). noTthaTguY <abu.kuanysh05@gmail.com> - 2017-01-09 16:23 -0800
                Re: The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). moroney@world.std.spaamtrap.com (Michael Moroney) - 2017-01-05 03:34 +0000
                The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). Jeff-Relf.Me <@.> - 2017-01-04 22:26 -0800
                Re: The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). Anonymous <anonymous@invalid.tld> - 2017-01-05 08:18 +0000
                Re: The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). Peter Köhlmann <peter-koehlmann@t-online.de> - 2017-01-05 09:24 +0100
                PostScript is my thing. Jeff-Relf.Me <@.> - 2017-01-05 01:08 -0800
                My diffs now _perfectly match MicroSoft's WinMerge. Jeff-Relf.Me <@.> - 2017-01-07 03:56 -0800
                Re: My diffs now _perfectly match MicroSoft's WinMerge. Peter Köhlmann <peter-koehlmann@t-online.de> - 2017-01-07 13:09 +0100
                Re: My diffs now _perfectly match MicroSoft's WinMerge. moroney@world.std.spaamtrap.com (Michael Moroney) - 2017-01-07 20:25 +0000
                Like a compiler that compiles itself, my Diff app diffs itself. Jeff-Relf.Me <@.> - 2017-01-07 17:53 -0800
                Re: My diffs now _perfectly match MicroSoft's WinMerge. Christian Gollwitzer <auriocus@gmx.de> - 2017-01-10 22:15 +0100
                Text file comparison is essential. Jeff-Relf.Me <@.> - 2017-01-16 11:23 -0800
                Re: Text file comparison is essential. noTthaTguY <abu.kuanysh05@gmail.com> - 2017-01-17 11:22 -0800
                Nothing to compare, left and right, old and new. Jeff-Relf.Me <@.> - 2017-01-19 04:12 -0800
                Re: The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). jmfbahciv <See.above@aol.com> - 2017-01-05 14:08 +0000
                Re: The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). Vir Campestris <vir.campestris@invalid.invalid> - 2017-01-05 21:09 +0000
                Re: The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). legalize+jeeves@mail.xmission.com (Richard) - 2017-01-05 21:19 +0000
                "Functional" programming is "Tree Crawling". Jeff-Relf.Me <@.> - 2017-01-05 14:53 -0800
                Re: The Longest Common Sequence ( NonContiguous ) algorithm ( recursive ). Lofty Goat <rlwatkins@gmail.com> - 2017-01-05 17:43 -0600
                Re: I completely reWrote it, of course. jmfbahciv <See.above@aol.com> - 2017-01-05 14:08 +0000
            What about you, GreyCloud ? Jeff-Relf.Me <@.> - 2017-01-16 11:02 -0800
              Re: What about you, GreyCloud ? GreyCloud <mist@cumulus.com> - 2017-01-16 19:46 -0700
                Health issues ? Jeff-Relf.Me <@.> - 2017-01-16 20:39 -0800
                Re: Health issues ? GreyCloud <mist@cumulus.com> - 2017-01-17 11:50 -0700
                Re: Health issues ? noTthaTguY <abu.kuanysh05@gmail.com> - 2017-01-17 14:19 -0800
                Re: Health issues ? noTthaTguY <abu.kuanysh05@gmail.com> - 2017-01-17 18:44 -0800
                Negative Interest Rates. Jeff-Relf.Me <@.> - 2017-01-19 04:25 -0800
                Re: Negative Interest Rates. GreyCloud <mist@cumulus.com> - 2017-01-19 11:47 -0700
                Negative Interest Rates "rips off" rich people, not the poor. Jeff-Relf.Me <@.> - 2017-01-19 19:23 -0800
                Re: Negative Interest Rates "rips off" rich people, not the poor. GreyCloud <mist@cumulus.com> - 2017-01-20 16:17 -0700
              Tons of people have reviewed the code, source and object. Jeff-Relf.Me <@.> - 2017-01-19 04:02 -0800
              Building a complex system can't be done when you're drunk and horny. Jeff-Relf.Me <@.> - 2017-01-19 04:17 -0800
                Re: Building a complex system can't be done when you're drunk and horny. David Brown <david.brown@hesbynett.no> - 2017-01-19 13:59 +0100
                No one is here to learn at your feet, sorry. Jeff-Relf.Me <@.> - 2017-01-19 05:30 -0800
                Re: Building a complex system can't be done when you're drunk and horny. chrisv <chrisv@nospam.invalid> - 2017-01-19 07:37 -0600
                Building a complex system can't be done when you're drunk and horny. Jeff-Relf.Me <@.> - 2017-01-19 05:43 -0800
                Re: Building a complex system can't be done when you're drunk and horny. noTthaTguY <abu.kuanysh05@gmail.com> - 2017-01-19 10:06 -0800
                Re: Building a complex system can't be done when you're drunk and horny. moroney@world.std.spaamtrap.com (Michael Moroney) - 2017-01-20 04:32 +0000
                Usenet isn't WikiPedia; here, it's all play and no work, anything goes. Jeff-Relf.Me <@.> - 2017-01-19 21:02 -0800
                yeah, you can always prefer your preferred header noTthaTguY <abu.kuanysh05@gmail.com> - 2017-01-19 21:22 -0800
        The "Least Longest" diffs. Jeff-Relf.Me <@.> - 2017-01-03 03:04 -0800

csiph-web