<meta name="description" content="Sync client and server" />
<title>s2g-sync</title>
<link rel="stylesheet" href="style.css">
<script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.2.13/angular.min.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/lodash.js/2.4.1/lodash.js" ></script>
<script src="script.js"></script>
<body ng-app="SyncApp">
<div>
<h1 id="syncing-lists-from-multiple-users-using-set-algebra.">Syncing lists from multiple users using set algebra.</h1>
<h3 id="use-case">use case</h3>
<p>In an app in which multiple people create and edit the same list, How to sync them together?</p>
<p>An app needs to be able to function to a certain extent even when not connected to the internet. How do you synchronize with other users who may have changed the list while you were making offline changes?</p>
<h3 id="setup">setup</h3>
<p>The app keeps two lists in local storage. One is the Current(C) list which reflects what the app screen shows. The second is the Prior(P) list which reflects the list as it existed after the last update. It has a timestamp.</p>
<p>The Server(S) has the shared list with its own timestamp.</p>
<h3 id="update">update</h3>
<p>Local updates when offline only change the Current list.</p>
<p>When the app is online it checks with the server. There are two possibilities for state. <br>
<dt>1. The Server has not changed since the last update (S.timestamp <= P.timestamp) </dt>
<dd>Update by copying the current list to server and to prior, and update timestamps </dd>
<dt>2. The Server has changed since the last update (somebody else changed the list)(S.timestamp > P.timestamp) </dt>
<dd>Synch the lists by merging current, prior and server.</dd></p>
<h3 id="problem">problem</h3>
<p>Figure out a slick way to sych, merging the current, prior and server lists. It looks like a set algebra problem. As you can see from the table below… Since the last update the user has added anise and frog legs but has gotten the dog-food. Meanwhile somebody got the apples and the fennel and added diapers fish sticks and gerkins to the list.</p>
<p>So the updated list should include the things added by the other user, but delete the things the other user got. It should also reflect the things added by the user and delete things they got.</p>
<div ng-controller="SyncCtrl">
<br>
<table>
<caption><b>sync clients with server</b> M=(C\(P\S))U(S\(P\C)) <br>
<small>(B\A) = the set of elements in B, but not in A.</small></caption>
<thead>
<tr>
<th width="15" valign="top">P <br>prior on client</th>
<th width="15" valign="top">C <br>current on client</th>
<th width="15" valign="top">S <br>server updated by other clients </th>
<th width="15" valign="top">(P\C) <br>relative complement (P-C) </th>
<th width="15" valign="top">(P\S) <br>relative complement (P-S) </th>
<th width="15" valign="top">(S\(P\C) <br>relative complement (S-(P-C)) </th>
<th width="15" valign="top">(C\(P\S)) <br>relative complement (C-(P-S)</th>
<th width="15" valign="top"> (C\(P\S)) U (S\(P\C))<br>union (S-(P-C) U (C-(P-S)</th>
<th width="15" valign="top"> combined <br>union: done true and false</th>
</tr>
</thead>
<tbody>
<tr>
<td><ul id="thePList">
<li ng-repeat="pi in p2">{{pi.product}} </li>
</ul></td>
<td><ul id="theCList">
<li ng-repeat="ci in c2">{{ci.product}} </li>
</ul></td>
<td><ul id="theSList">
<li ng-repeat="si in s2">{{si.product}} </li>
</ul></td>
<td><ul id="thePCList">
<li ng-repeat="pci in pc">{{pci.product}} </li>
</ul></td>
<td><ul id="thePSList">
<li ng-repeat="psi in ps">{{psi.product}} </li>
</ul></td>
<td><ul id="theSPCList">
<li ng-repeat="spci in spc">{{spci.product}} </li>
</ul></td>
<td><ul id="theCPSList">
<li ng-repeat="cpsi in cps">{{cpsi.product}} </li>
</ul></td>
<td><ul id="theMO2List">
<li ng-repeat="mo2i in mo2">{{mo2i.product}} </li>
</ul></td>
<td><ul id="theCombinedList">
<li ng-repeat="comi in com">{{comi.product}} {{comi.done}} </li>
</ul></td>
</tr>
</tbody>
</table>
<h3 id="solution">solution</h3>
<p>In short: the merged list M=(C\(P\S))U(S\(P\C)) where <br> Pis the relative complement of P in C<br> P= items contained in P that are not in C</p>
<pre><code> difference: function(array){
// difference(op,s2, 'product'
var prop =arguments[2];//product
var rest = arguments[1];//s2
var containsEquals = function(obj, target) {
// used on each value of the array being filtered(op),
// compares product name to each element in obj(s2)
if (obj == null) return false;
return _.any(obj, function(value) {
return value[prop] === target[prop];
});
};
// filter with the containsEquals function
// include only those array(op) elements not in the rest(s2) array
return _.filter(array, function(value){
return ! containsEquals(rest, value);
});
},</code></pre>
<p>First I took the current list and just kept operating on them with union, intersection, and relative complement operations until I got to the merge list I was after. Then I took that page of relations and intersecting circles and reduced them using set algebra rules.</p>
<h4>refs</h4>
<a href="http://www.cs.umd.edu/class/fall2005/cmsc250/exam/ex1/node5.html">http://www.cs.umd.edu/class/fall2005/cmsc250/exam/ex1/node5.html</a><br>
<a href="http://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement">http://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement</a><br>
<a href="http://stackoverflow.com/questions/18383636/compare-2-arrays-of-objects-with-underscore-to-find-the-differnce">http://stackoverflow.com/questions/18383636/compare-2-arrays-of-objects-with-underscore-to-find-the-differnce by Jonathan Naguin</a><br>
<a href="http://stackoverflow.com/questions/7146217/merge-2-arrays-of-objects">http://stackoverflow.com/questions/7146217/merge-2-arrays-of-objects by Guya</a>
<pre>
{{op}} <br>
{{c2}} <br>
{{s2}} <br>
{{jmo2}}
</pre>
</div>
</div>
</body>
/*
Write an algorithm that will find the first duplicate in a list on the page.
For example we would return 4, for the list above.
*/
var app = angular.module("SyncApp", []);
app.controller("SyncCtrl", function($scope, SyncService){
var c = $scope.c = SyncService.c() ;
var c2 = $scope.c2 = SyncService.c2() ;
//console.log( c2);
var s = $scope.s = SyncService.s() ;
var s2 = $scope.s2 = SyncService.s2() ;
var p2 = $scope.p2 = SyncService.p2() ;
var p = $scope.p = SyncService.p() ;
//var m = $scope.m = SyncService.merge(p,c,s);
//console.log(m)
var oc = $scope.oc = SyncService.a2o(c)
var os = $scope.os = SyncService.a2o(s)
var op = $scope.op = SyncService.a2o(p)
var ps = $scope.ps = SyncService.difference(op,s2, 'product');
var pc = $scope.pc = SyncService.difference(op,c2, 'product');
var spc = $scope.spc = SyncService.difference(s2,pc, 'product');
var cps = $scope.cps = SyncService.difference(c2, ps, 'product');
var mo2 = $scope.mo2 = SyncService.mergeObjs(op, c2, s2);
$scope.jmo2 = JSON.stringify(mo2, undefined, 2);
});
app.factory("SyncService", function(){
return {
s2: function(){
return [{"product":"bananas", "done" : false},
{"product":"cantelope", "done" : false},
{"product":"daipers", "done" : false},
{"product":"dog food",
"done" : false,
"tags" : [
"produce"
],
"amt" : {
"qty" : 3,
"unit" : "3lb bag"
}
},
{"product":"fish sticks", "done" : false},
{"product":"gerkins", "done" : false}]
},
c2: function(){
return [{"product":"anise", "done" : false},
{"product":"apples", "done" : false},
{"product":"bananas",
"done" : false,
"tags" : [
"produce"
],
"amt" : {
"qty" : 3,
"unit" : "3lb bag"
}
},
{"product":"cauliflower", "done" : false},
{"product":"fennel", "done" : false},
{"product":"frogs legs", "done" : false}]
},
c: function(){
return ['anise',
'apples',
'bananas',
'cauliflower',
'fennel',
'frogs legs',
]
},
p2: function(){
return [{"product":"apples", "done" : false},
{"product":"bananas", "done" : false},
{"product":"cantelope", "done" : false},
{"product":"dog food", "done" : false},
{"product":"fennel", "done" : false}
]
},
p: function(){
return ['apples',
'bananas',
'cantelope',
'dog food',
'fennel'
]
},
s: function(){
return ['bananas',
'cantelope',
'daipers',
'dog food',
'fish sticks',
'gerkins'
]
},
merge: function(p,c,s){
// (C\(P\S))U(S\(P\C))
var ps = _.difference(p,s);
var pc = _.difference(p,c);
var cps = _.difference(c,ps);
var spc = _.difference(s,pc);
var u = _.union(cps, spc);
return u
},
a2o: function(arr){
var obj = _.map(arr, function(x){
return {product: x, done: false}
})
return obj
},
difference: function(array){
// difference(op,s2, 'product'
var prop =arguments[2];//product
var rest = arguments[1];//s2
var containsEquals = function(obj, target) {
// used on each value of the array being filtered(op),
// compares product name to each element in obj(s2)
if (obj == null) return false;
return _.any(obj, function(value) {
return value[prop] === target[prop];
});
};
// filter with the containsEquals function
// include only those array(op) elements not in the rest(s2) array
return _.filter(array, function(value){
return ! containsEquals(rest, value);
});
},
union: function (arr1, arr2, prop) {
_.each(arr2, function(arr2obj) {
var arr1obj = _.find(arr1, function(arr1obj) {
return arr1obj[prop] === arr2obj[prop];
});
arr1obj ? _.extend(arr1obj, arr2obj) : arr1.push(arr2obj);
});
},
mergeObjs: function(p,c,s){
// (C\(P\S))U(S\(P\C))
var ps = this.difference(p,s, 'product');
var pc = this.difference(p,c, 'product' );
var cps = this.difference(c,ps, 'product');
var spc = this.difference(s,pc, 'product');
this.union(spc, cps, 'product');
return spc
}
}
})
/* Styles go here */
div {
margin:40px;
padding:6px;
color:blue;
}
#Syncing lists from multiple users using set algebra.
###use case
In an app in which multiple people create and edit the same list, How to sync them together?
An app needs to be able to function to a certain extent even when not connected to the internet. How do you synchronize with other users who may have changed the list while you were making offline changes?
###setup
The app keeps two lists in local storage. One is the Current(C) list which reflects what the app screen shows. The second is the Prior(P) list which reflects the list as it existed after the last update. It has a timestamp.
The Server(S) has the shared list with its own timestamp.
###update
Local updates when offline only change the Current list.
When the app is online it checks with the server. There are two possibilities for state.
1. The Server has not changed since the last update (S.timestamp <= P.timestamp)
* Update by copying the current list to server and to prior, and update timestamps
2. The Server has changed since the last update (somebody else changed the list)(S.timestamp > P.timestamp)
* Synch the lists by merging current, prior and server.
###problem
Figure out a slick way to sych, merging the current, prior and server lists. It looks like a set algebra problem. As you can see from the table below...
Since the last update the user has added anise and frog legs but has gotten the dog-food. Meanwhile somebody got the apples and the fennel and added diapers fish sticks and gerkins to the list.
So the updated list should include the things added by the other user, but delete the things the other user got. It should also reflect the things added by the user and delete things they got.
###solution
In short: the merged list M=(C\(P\S))U(S\(P\C)) where <br>
P\C is the relative complement of P in C<br>
P\C = items contained in P that are not in C
difference: function(array){
// difference(op,s2, 'product'
var prop =arguments[2];//product
var rest = arguments[1];//s2
var containsEquals = function(obj, target) {
// used on each value of the array being filtered(op),
// compares product name to each element in obj(s2)
if (obj == null) return false;
return _.any(obj, function(value) {
return value[prop] === target[prop];
});
};
// filter with the containsEquals function
// include only those array(op) elements not in the rest(s2) array
return _.filter(array, function(value){
return ! containsEquals(rest, value);
});
},
First I took the current list and just kept operating on them with union, intersection, and relative complement operations until I got to the merge list I was after. Then I took that page of relations and intersecting circles and reduced them using set algebra rules.
<a href="http://johnmacfarlane.net/pandoc/try/" title="">http://johnmacfarlane.net/pandoc/try/</a>