1 /*
  2 Copyright (c) 2009 Simon Veith <simon@jinfinote.com>
  3 
  4 Permission is hereby granted, free of charge, to any person obtaining a copy
  5 of this software and associated documentation files (the "Software"), to deal
  6 in the Software without restriction, including without limitation the rights
  7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  8 copies of the Software, and to permit persons to whom the Software is
  9 furnished to do so, subject to the following conditions:
 10 
 11 The above copyright notice and this permission notice shall be included in
 12 all copies or substantial portions of the Software.
 13 
 14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 20 THE SOFTWARE.
 21 */
 22 
 23 /** Initializes a new DoRequest object.
 24  *  @class Represents a request made by an user at a certain time.
 25  *  @param {Number} user The user that issued the request
 26  *  @param {Vector} vector The time at which the request was issued
 27  *  @param {Operation} operation
 28  */
 29 function DoRequest(user, vector, operation) {
 30 	this.user = user;
 31 	this.vector = vector;
 32 	this.operation = operation;
 33 }
 34 
 35 DoRequest.prototype.toString = function() {
 36 	return "DoRequest(" + 
 37 		[this.user, this.vector, this.operation].join(", ") + ")";
 38 };
 39 
 40 DoRequest.prototype.toHTML = function() {
 41 	return "DoRequest(" + 
 42 		[this.user, this.vector.toHTML(), this.operation.toHTML()].join(", ")
 43 		+ ")";
 44 };
 45 
 46 DoRequest.prototype.copy = function() {
 47 	return new DoRequest(this.user, this.vector, this.operation);
 48 };
 49 
 50 /** Applies the request to a State.
 51  *  @param {State} state The state to which the request should be applied.
 52  */
 53 DoRequest.prototype.execute = function(state) {
 54 	if(state.vector[this.user] == undefined)
 55 		state.vector[this.user] = 0;
 56 	
 57 	this.operation.apply(state.buffer);
 58 	
 59 	state.vector[this.user] += 1;
 60 	
 61 	return this;
 62 };
 63 
 64 /** Transforms this request against another request.
 65  *  @param {DoRequest} other
 66  *  @param {DoRequest} [cid] The concurrency ID of the two requests. This is
 67  *  the request that is to be transformed in case of conflicting operations.
 68  *  @type DoRequest
 69  */
 70 DoRequest.prototype.transform = function(other, cid) {
 71 	if(this.operation instanceof Operations.NoOp)
 72 		var newOperation = new Operations.NoOp();
 73 	else {
 74 		var op_cid;
 75 		if(cid == this)
 76 			op_cid = this.operation;
 77 		if(cid == other)
 78 			op_cid = other.operation;
 79 		
 80 		var newOperation = this.operation.transform(other.operation, op_cid);
 81 	}
 82 	
 83 	return new DoRequest(this.user, this.vector.incr(other.user),
 84 		newOperation);
 85 };
 86 
 87 /** Mirrors the request. This inverts the operation and increases the issuer's
 88  *  component of the request time by the given amount.
 89  *  @param {Number} [amount] The amount by which the request time is
 90  *  increased. Defaults to 1.
 91  *  @type DoRequest
 92  */
 93 DoRequest.prototype.mirror = function(amount) {
 94 	if(typeof(amount) != "number")
 95 		amount = 1;
 96 	return new DoRequest(this.user, this.vector.incr(this.user, amount),
 97 		this.operation.mirror());
 98 };
 99 
100 /** Folds the request along another user's axis. This increases that user's
101  *  component by the given amount, which must be a multiple of 2.
102  *  @type DoRequest
103  */
104 DoRequest.prototype.fold = function(user, amount) {
105 	if(amount % 2 == 1)
106 		throw "Fold amounts must be multiples of 2.";
107 	return new DoRequest(this.user, this.vector.incr(user, amount),
108 		this.operation);
109 };
110 
111 /** Makes a request reversible, given a translated version of this request
112  *  and a State object. This only applies to requests carrying a Delete
113  *  operation; for all others, this does nothing.
114  *  @param {DoRequest} translated This request translated to the given state
115  *  @param {State} state The state which is used to make the request
116  *  reversible.
117  *  @type DoRequest
118  */
119 DoRequest.prototype.makeReversible = function(translated, state) {
120 	var result = this.copy();
121 	
122 	if(this.operation instanceof Operations.Delete) {
123 		result.operation = this.operation.makeReversible(translated.operation,
124 			state);
125 	}
126 	
127 	return result;
128 };
129 
130 /** Instantiates a new undo request.
131  *  @class Represents an undo request made by an user at a certain time.
132  *  @param {Number} user
133  *  @param {Vector} vector The time at which the request was issued.
134  */
135 function UndoRequest(user, vector) {
136 	this.user = user;
137 	this.vector = vector;
138 }
139 
140 UndoRequest.prototype.toString = function() {
141 	return "UndoRequest(" + [this.user, this.vector].join(", ") + ")";
142 };
143 
144 UndoRequest.prototype.toHTML = function() {
145 	return "UndoRequest(" + [this.user, this.vector.toHTML()].join(", ")
146 		+ ")";
147 };
148 
149 UndoRequest.prototype.copy = function() {
150 	return new UndoRequest(this.user, this.vector);
151 };
152 
153 /** Finds the corresponding DoRequest to this UndoRequest.
154  *  @param {Array} log The log to search
155  *  @type DoRequest
156  */
157 UndoRequest.prototype.associatedRequest = function(log) {
158 	var sequence = 1;
159 	var index = _indexOf(log, this);
160 	
161 	if(index == -1)
162 		index = log.length - 1;
163 	
164 	for(; index >= 0; index--)
165 	{
166 		if(log[index] === this || log[index].user != this.user)
167 			continue;
168 		if(log[index].vector.get(this.user) > this.vector.get(this.user))
169 			continue;
170 		
171 		if(log[index] instanceof UndoRequest)
172 			sequence += 1;
173 		else
174 			sequence -= 1;
175 		
176 		if(sequence == 0)
177 			return log[index];
178 	}
179 };
180 
181 /** Instantiates a new redo request.
182  *  @class Represents an redo request made by an user at a certain time.
183  *  @param {Number} user
184  *  @param {Vector} vector The time at which the request was issued.
185  */
186 function RedoRequest(user, vector) {
187 	this.user = user;
188 	this.vector = vector;
189 }
190 
191 RedoRequest.prototype.toString = function() {
192 	return "RedoRequest(" + [this.user, this.vector].join(", ") + ")";
193 };
194 
195 RedoRequest.prototype.toHTML = function() {
196 	return "RedoRequest(" + [this.user, this.vector.toHTML()].join(", ") + ")";
197 };
198 
199 RedoRequest.prototype.copy = function() {
200 	return new RedoRequest(this.user, this.vector);
201 };
202 
203 /** Finds the corresponding UndoRequest to this RedoRequest.
204  *  @param {Array} log The log to search
205  *  @type UndoRequest
206  */
207 RedoRequest.prototype.associatedRequest = function(log) {
208 	var sequence = 1;
209 	var index = _indexOf(log, this);
210 	
211 	if(index == -1)
212 		index = log.length - 1;
213 	
214 	for(; index >= 0; index--)
215 	{
216 		if(log[index] === this || log[index].user != this.user)
217 			continue;
218 		if(log[index].vector.get(this.user) > this.vector.get(this.user))
219 			continue;
220 		
221 		if(log[index] instanceof RedoRequest)
222 			sequence += 1;
223 		else
224 			sequence -= 1;
225 		
226 		if(sequence == 0)
227 			return log[index];
228 	}
229 };
230 
231 /** Helper function to provide an implementation of an Array's indexOf method.
232  *  This is necessary for browsers that don't support JavaScript 1.6, such as
233  *  Internet Explorer 6. It uses the browsers native implementation when
234  *  available.
235  *  @param {Array} array
236  *  @param searchElement
237  *  @param {Number} [fromIndex]
238  */
239 function _indexOf(array, searchElement, fromIndex)
240 {
241 	if(array.indexOf)
242 		return array.indexOf(searchElement, fromIndex);
243 	else {
244 		if(typeof(fromIndex) != "number")
245 			fromIndex = 0;
246 		
247 		for(var index = 0; index < array.length; index ++)
248 		{
249 			if(array[index] === searchElement)
250 				return index;
251 		}
252 		
253 		return -1;
254 	}
255 }
256