[prev in list] [next in list] [prev in thread] [next in thread] 

List:       darcs-conflicts
Subject:    Re: [darcs-conflicts] permutivity,
From:       Ian Lynagh <igloo () earth ! li>
Date:       2005-10-31 20:04:05
Message-ID: 20051031200405.GA9815 () matrix ! chaos ! earth ! li
[Download RAW message or body]

On Mon, Oct 24, 2005 at 09:44:32AM -0400, David Roundy wrote:
> 
>                                 I'm going with a new notation for
> conflictors, which looks like
> 
> [A1:,A2:,A3:A2...|Pre:P:Post|:B1,:B2,B2:B3,...]

We haven't had a new conflictor definition for /far/ too long, so I'll
be using

[Es; {Pres}; PrePs:P:PostPs; {Posts}]

where Es is the effect, Pres and Posts are sets of conflicts (with pre
and post contexts respectively), P is the patch and PrePs/PostPs are
pre/post context of P. Simple, ain't it?  :-)

In Haskellish notation that is

Conflictor a c = Conflictor (PatchSeq a c)           -- Es
                            [PatchWithPreContext a]  -- Pres
                            (PatchSeq a x)           -- PrePs
                            Patch x z                -- P
                            (PatchSeq z c)           -- PostPs
                            [PatchWithPostContext c] -- Posts

PatchWithPreContext a = PatchWithPreContext (PatchSeq a b) (Patch b c)
PatchWithPostContext c = PatchWithPostContext (Patch a b) (PatchSeq b c)

Note that Es == simplify (PrePs P PostPs)

This is largely the same as yours but I hope with more useful contexts.

> At last... permutivity tells us that for a sequence of patches A1B1C1, all
> permutations can be represented by
> 
>      A1 B1 C1
> <->* B2 A2 C1
> <->* B2 C2 A3
> <->* C3 B3 A3
> <->* C3 A4 B4
> <->* A1 C4 B4

Or equivalently,

       A1 B1 C1
<-AB-> B2 A2 C1
<-AC-> B2 C2 A3
<-BC-> C3 B3 A3
<-BA-> C3 A4 B4
<-CA-> A1 C4 B4

> The simplest scenario is A1B1C1 == ABC, and none of these patches commute.
> In this case
> 
> A1 = A ~ A
> B1 = B ~ B
> C1 = C ~ C
> B2 = [A:|:B:|] ~ A
> A2 = [|:A:|:B] ~ B
> B4 = [|:B:|:C] ~ C
> C4 = [B:|:C:|] ~ B (easy so far)
> C3 = [A:B,B:|:C:|] ~ AB
> A3 = [|:A:|:B,B:C] ~ BC (these two are also old friends)
> A4 = [|:A:B|:C] ~ id (id means identity)
> C2 = [A:|B:C:|] ~ id (another pair of old friends)
> B3 = [A:|:B:|:C] ~ B^ (!!! this is Ian's conflictor, remember ^ is inverse)

Using the above patch effects gives me:

       ABC
<-AB-> [A; {}; A:B:B^; {A:}][B; {:B}; A^:A:B; {}]C
<-AC-> [A; {}; A:B:B^; {A:}][; {}; B:C:C^B^; {A:}][BC; {:B,B:C}; A^:A:BC; {}]
<-BC-> [AB;{};AB:C:C^;{A:B,B:}][B^;{:C};B^:B:B^;{A:}][BC;{:B,B:C};A^:A:BC;{}]
<-BA-> [AB; {}; AB:C:C^; {A:B,B:}][; {:C}; B^A^:A:B; {}][C; {:C}; B^:B:C; {}]
<-CA-> A[B; {}; B:C:C^; {B:}][C; {:C}; B^:B:C; {}]


This is straight off the top of my head so there may be errors, and I
haven't thought about the algorithm yet.


Thanks
Ian


_______________________________________________
darcs-conflicts mailing list
darcs-conflicts@darcs.net
http://www.abridgegame.org/cgi-bin/mailman/listinfo/darcs-conflicts
[prev in list] [next in list] [prev in thread] [next in thread]