User A User B User C
Chapter 8 Conclusion
8.2 Open Questions
Optimizations on TreeDoc
The main problem of TreeDoc is unbalance, which causes the path of node to grow indefinitely. Therefore, it is necessary to provide optimizations to TreeDoc in order to reduce the degree of unbalance or even design new commutative replicated data type to alleviate this problem. Besides insert, delete operation, TreeDoc needs to provide more kinds of operation such as undo, redo, lock, unlock...
User Identification
In a wider environment, the configuration for collaboration session could be information provided by a document server. In that case, user should be identified by some creden-tials rather than IP address. Because IP address can change in a mobile environment, identifying a user (a device) by its IP address is a poor choice.
Message Broadcast on MANETs
In our current application, we did not pay attention on the message broadcast scheme on MANETs. In the future, it is necessary to develop mechanisms for broadcasting message on MANETs to reduce message loss in the system.
Bibliography
[1] J. F. Patterson, R. D. Hill, S. L. Rohall and S. W. Meeks, Rendezvous: an architecture for synchronous multi-user applications, In Proceedings of the 1990 ACM conference on Computer Supported Cooperative Work, pp. 317-328, Los Angeles, California, United States. ACM Press, 1990.
[2] N. A. Streitz, J. Geiler, J. M. Haake and J. Hol, DOLPHIN: integrated meeting support across local and remote desktop environments and LiveBoards, In Proceedings of the 1994 ACM conference on Computer Supported Cooperative Work, Chapel Hill, North Carolina, United States. ACM Press, 1994.
[3] D. A. Nichols, P. Curtis, M. Dixon and J. Lamping, High-latency, low-bandwidth win-dowing in the Jupiter collaboration system, In Proceedings of the 8th annual ACM symposium on User interface and software technology, pp. 111-120, Pittsburgh, Penn-sylvania, United States. ACM Press, 1995.
[4] M. Stefik, G. Foster, D. G. Bobrow, K. Kahn, S. Lanning and L. Suchman, Beyond the chalkboard: computer support for collaboration and problem solving in meetings, Communications of the ACM, 30(1): 32-47, 1987.
[5] C. A. Ellis, S. J. Gibbs and G. L. Rein, Design and Use of a Group Editor, In Pro-ceedings of the IFIP TC2/WG2.7 Working Conference on Engineering for Human-Computer Interaction, pp. 13-28, Napa Valley, California. Elsevier, 1989.
[6] C. Sun and C. Ellis, Operational transformation in real-time group editors: issues, algorithms, and achievements, In Proceedings of the 1998 ACM conference on Com-puter Supported Cooperative Work, pp. 59-68, Seattle, Washington, United States.
ACM Press, 1998.
[7] C. Sun, X. Jia, Y. Zhang, Y. Yang and D. Chen, Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems, ACM Transactions on Computer-Human Interaction (TOCHI), 5(1): 63-108, 1998.
[8] A. Karsenty, C. Tronche and M. Beaudouinlafon, GroupDesign: shared editing in a heterogeneous environment, Usenix Journal of Computing Systems, 6(2): 167-195, 1993.
[9] C. Sun and D. Chen, Consistency maintenance in real-time collaborative graphics editing systems, ACM Transactions on Computer-Human Interaction (TOCHI), 9(1):
1-41, 2002.
[10] C. L. Ignat and M. C. Norrie, Draw-together: graphical editor for collaborative draw-ing, In Proceedings of the 2006 20th anniversary conference on Computer supported Cooperative Work, pp. 269-278, Banff, Alberta, Canada. ACM Press, 2006.
[11] L. Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, Comm. ACM, vol. 21, no. 7, pp. 558-565, 1978.
[12] P.R. Johnson and R.H. Thomas, RFC 677: Maintenance of Duplicate Databases, http://www.faqs.org/rfcs/rfc677.html, Jan. 1975.
[13] C. A. Ellis and S. J. Gibbs, Concurrency control in groupware systems, In Proceedings of the 1989 ACM SIGMOD international conference on Management of data, pp. 399-407, Portland, Oregon, United States. ACM Press, 1989.
[14] M. Ressel, D. Nitsche-Ruhland and R. Gunzenhuser, An integrating, transformation-oriented approach to concurrency control and undo in group editors, In Proceedings of the 1996 ACM conference on Computer Supported Cooperative Work, pp. 288-297, Boston, Massachusetts, United States. ACM Press, 1996.
[15] M. Suleiman, M. Cart and J. Ferri, Serialization of concurrent operations in a dis-tributed collaborative environment, In Proceedings of the international ACM SIG-GROUP conference on Supporting group work: the integration challenge, pp. 435-445, Phoenix, Arizona, United States. ACM Press, 1997.
[16] N. Vidot, M. Cart, J. Ferri and M. Suleiman, Copies convergence in a distributed real-time collaborative environment, In Proceedings of the 2000 ACM conference on Com-puter Supported Cooperative Work, pp. 171-180, Philadelphia, Pennsylvania, United States. ACM Press, 2000.
[17] G. Oster, P. Urso, P. Molli, and A. Imine, Proving correctness of transformation func-tions in collaborative editing systems, LORIAINRIA Lorraine, Rapport de recherche RR-5795, Dec. 2005.
[18] F. Mattern, Virtual time and global states of distributed systems, In Proceedings of the International Workshop on Parallel and Distributed Algorithms, pp. 215-276.
Elsevier Pub., 1989.
[19] Nuno Preguia, Joan Manuel Marqus, Marc Shapiro, and Mihai Letia, A commutative replicated data type for cooperative editing, In Int. Conf. on Distributed Comp. Sys.
(ICDCS), pages 395403, Montral, Canada, June 2009.
[20] Marek Zawirski, Marc Shapiro, and Nuno Preguia, Asynchronous rebalancing of a replicated tree, Conference Franaise de Systmes d’Exploitation (CFSE), Saint-Malo, France, May 2011.
[21] D. Buszko, W. Lee and A. Helal, Decentralized ad-hoc groupware API and framework for mobile collaboration, In Proceedings of the 2001 International ACM SIGGROUP Conference on Supporting Group Work, pp. 5-14, Boulder, Colorado, USA. ACM Press, 2001.
[22] C. Sun, S. Xia, D. Sun, D. Chen, H. Shen and W. Cai, Transparent adaptation of single-user applications for multi-user real-time collaboration, ACM Transactions on Computer-Human Interaction (TOCHI), 13(4): 531 - 582, 2006.
[23] Allison C., Concurrency Control for Real Time Groupware, CE94: Concurrent En-gineering Research and Applications, pp. 163170, A global Perspective, Pittsbourg, August 1994.
[24] Mark Claypool, Tom Beibeder, Rory Coughlan, Corey Lusher, John Plunkett, Em-manuel Agu, The Effects of Loss and Latency on User Performance in Unreal Tourn-ment 2003, Computer Science DepartTourn-ment at Worchester Polytechnic Institute, 2004.
[25] Paul Bettner, Mark Terrano, 1500 archers on a 28.8: Network programming in Age of Empires and beyond, the game developer conference proceedings, 2001.
[26] Marc Shapiro, Nuno Preguica, Carlos Baquero, and Marek Zawirski, A compre-hensive study of Convergent and Commutative Replicated Data Types, Rapport de recherche 7506, Institut Nat. de la Recherche en Informatique et Automatique (IN-RIA), Rocquencourt, France, January 2011.
Appendix A
System Architecture
Editor
State Vector Manager
Collaboration Session Manager
Document Manager
Connection Manager
Local op Updated document
State vector of remote op
Whether remote op is causally ready?
Remote / local op Updated document
Message Message
Figure A.1: System Architecture
Appendix B Class Diagram
TreeDoc
+applyLocalInsertOp(op: Operation): String +applyLocalDeleteOp(op: Operation): String +applyRemoteInsertOp(op: Operation): String +applyRemoteDeleteOp(op: Operation): String +rebalance(): void
+getInfixOrderContent(): String +TreeDoc()
+catch-up(op: Operation): void +getPosID(node: Node): String
Node
+Node(font: Font, value: Character, leftchild: Node, rightchild: Node, parent: Node) +setEmptyNode()
+atom: Char Font
+ftFontSize: float +dbFontColor: double +intFontStyle: int +intFontTyle: int
+Font( fontsize: float, fontcolor: double, fonttyle: int, fonttype: int ) Epoch
+epoch: int +strInitialState: String +Epoch( e: int, initialState: String) +addOperation(op: Operation): void
eector +arrStates: int [ ]
+addElement(userID: String): void +updateElement(userID: String): void +removeElement(userID: String): void
+getElement(userID: String): int +StateVector( )
+ isCausal(LocalStaVector:StateVector, remoteStaVector: StateVector): Boolean
oll orationession
+executeLocalOp(op: Operation): void +executeRemoteOp(op: Operation): void +receiveRemoteOp(op: String): Operation +
+sendLocalOp(op: Operation): String +strUserID: String
+isExecuted(op: Operation): Boolean User
+strUserID: String +strUserIP: String +intUserPort: int
+User(userID: String, userIP: String, userPort: int)
+addUser(user: User): void +removeUser(user: User): void
+CollaborationSession(editor: String,userID: String) Edior
reeDocuent
ector
rrUsers
cononection essession
edidior
ndoo
rrNodes Font
onnection +sendMessage(message: String, user: User): void +broadcastMessage(message: String, users: Users): void
+broadcastMessage(message: String, users: Users, exceptedUser: User): void +Connection(cosession: CollaborationSession): void
+arrperations
MaorNode +MajorNode(parent: Node) +addNode(node: Node)
+ftFont
+nodearent
+node!efthild
+nodei"hthild +nodeontainer
+id: String OpfromWaitList(): Operation
+ generateNode(left: Node, right: Node): Node
peration
+Operation(value:Character, posID: String, font: Font, svector: StateVector) +atom: Character
+staVector
Figure B.1: Class Diagram
Appendix C
TreeDoc Source Code
1 impo r t j a v a . u t i l . A r r a y L i s t ; p u b l i c c l a s s TreeDoc {
3 MajorNode r o o t ; /∗∗
5 ∗ Apply remote d e l e t e o p e r a t i o n
∗ @param op : d e l e t e o p e r a t i o n
7 ∗ @return d e l e l e d node
∗/
9 p u b l i c DocNode applyRemoteDeleteOp ( O per a tio n op ) {
DocNode u = getNode ( op . posID ) ;
11 u . setAtom (n u l l) ; r e t u r n u ;
13 }
/∗∗
15 ∗ Apply remote i n s e r t o p e r a t i o n
∗ @param op : i n s e r t o p e r a t i o n
17 ∗ @return i n s e r t e d node
∗/
19 p u b l i c DocNode applyRemoteInsertOp ( O per a tio n op ) { DocNode u = getNode ( op . posID ) ;
21 u . setAtom ( op . atom ) ; u . s e t F o n t ( op . f o n t ) ;
23 r e t u r n u ; }
25 /∗∗
∗ Get t h e node c o r r e s p o n d i n g with a posID
27 ∗ @param posID : posID o f t h e node
∗ @return t h e node c o r r e s p o n d i n g with posID
29 ∗/
p u b l i c DocNode getNode ( S t r i n g posID ) {
31 A r r a y L i s t<S t r i n g> p a t h d i s = new A r r a y L i s t<S t r i n g>() ; A r r a y L i s t<I n t e g e r> p a t h b i t = new A r r a y L i s t<I n t e g e r>() ;
33 decodePosID ( posID , p a t h d i s , p a t h b i t ) ; DocNode u = n u l l;
35 f o r (i n t i = 0 ; i < p a t h d i s . s i z e ( ) ; i ++) { S t r i n g d i s g = p a t h d i s . g e t ( i ) ;
37 i n t d i r e c t i o n = p a t h b i t . g e t ( i ) ;
u = gotoNode ( u , d i r e c t i o n , d i s g ) ;
39 }
r e t u r n u ;
41 }
p u b l i c DocNode gotoNode ( DocNode u , i n t d i r e c t i o n , S t r i n g d i s g ) {
43 MajorNode tempMj = n u l l; i f ( u == n u l l)
45 tempMj = r o o t ; e l s e {
47 i f ( d i r e c t i o n == 1 ) tempMj = u . r i g h t ;
49 e l s e
tempMj = u . l e f t ;
51 }
i f ( tempMj != n u l l) {
53 i n t i ;
f o r ( i = 0 ; i < tempMj . arrDocNode . s i z e ( ) ; i ++) {
55 i f ( d i s g . e q u a l s ( tempMj . arrDocNode . g e t ( i ) . i d ) == t r u e) { u = tempMj . arrDocNode . g e t ( i ) ;
57 br ea k;
}
59 i f ( tempMj . arrDocNode . g e t ( i ) . i d . compareTo ( d i s g ) > 0 ) { DocNode uu = new DocNode(n u l l , f a l s e , n u l l , d i s g ) ;
61 uu . majorNode = tempMj ;
tempMj . arrDocNode . add ( i , uu ) ;
63 u = uu ;
br ea k;
65 }
}
67 i f ( i == tempMj . arrDocNode . s i z e ( ) ) {
DocNode uu = new DocNode(’ ’, f a l s e , n u l l , d i s g ) ;
69 uu . majorNode = tempMj ;
tempMj . arrDocNode . add ( uu ) ;
71 u = uu ;
73 }
} e l s e {
75 DocNode uu = new DocNode(’ ’, f a l s e , n u l l , d i s g ) ; MajorNode mm = new MajorNode ( ) ;
77 mm. add ( uu ) ; mm. p a r r e n t = u ;
79 i f ( d i r e c t i o n == 1 ) u . r i g h t = mm;
81 e l s e i f ( d i r e c t i o n == 0 ) u . l e f t = mm;
83 e l s e
r o o t = mm;
85 u = uu ;
}
87 r e t u r n u ; }
89 /∗∗
∗ Gener a te a node on t h e t r e e
91 ∗ @param l e f t : t h e node a t r i g h t p o s i t i o n o f i n s e r t e d node
∗ @param r i g h t : t h e node a t l e f t p o s i t i o n o f i n s e r t e d node
93 ∗ @param u : i n s e r t e d node
∗ @return i n s e r t e d node
95 ∗/
p u b l i c DocNode g ener a teNo de ( DocNode l e f t , DocNode r i g h t , DocNode u ) {
97 i f ( r o o t == n u l l) {
MajorNode um = new MajorNode ( ) ;
99 um. add ( u ) ; r o o t = um ;
101 r e t u r n u ;
}
103 i f ( l e f t == n u l l && r i g h t == n u l l) { u = addToMajorNode ( r o o t , u ) ;
105 r e t u r n u ;
}
107 i f ( l e f t == n u l l) {
i f ( r i g h t . l e f t == n u l l) {
109 MajorNode um = new MajorNode ( ) ;
um . add ( u ) ;
111 r i g h t . l e f t = um;
um . p a r r e n t = r i g h t ;
113 } e l s e {
u = addToMajorNode ( r i g h t . l e f t , u ) ;
115 }
r e t u r n u ;
117 }
i f ( r i g h t == n u l l) {
119 i f ( l e f t . r i g h t == n u l l) {
MajorNode um = new MajorNode ( ) ;
121 um . add ( u ) ;
l e f t . r i g h t = um;
123 um . p a r r e n t = l e f t ; } e l s e {
125 u = addToMajorNode ( l e f t . r i g h t , u ) ; }
127 r e t u r n u ;
}
129 i f ( l e f t . i s a n c e s t o r ( r i g h t ) == t r u e) {
131 i f ( r i g h t . l e f t == n u l l) {
MajorNode um = new MajorNode ( ) ;
133 um . add ( u ) ;
r i g h t . l e f t = um;
135 um . p a r r e n t = r i g h t ; } e l s e {
137 u = addToMajorNode ( r i g h t . l e f t , u ) ; }
139
} e l s e {
141 i f ( l e f t . r i g h t == n u l l) {
MajorNode um = new MajorNode ( ) ;
143 um . add ( u ) ;
l e f t . r i g h t = um;
145 um . p a r r e n t = l e f t ; } e l s e {
147 u = addToMajorNode ( l e f t . r i g h t , u ) ; }
149 }
r e t u r n u ;
151 }
/∗∗
153 ∗ Apply l o c a l i n s e r t o p e r a t i o n
∗ @param b e f o r e : t h e node a t r i g h t p o s i t i o n o f i n s e r t e d node
155 ∗ @param a f t e r : t h e node a t l e f t p o s i t i o n o f i n s e r t e d node
∗ @param u : i n s e r t e d node
157 ∗ @return posID o f i n s e r t e d node
∗/
159 p u b l i c S t r i n g a p p l y L o c a l I n s e r t o p ( DocNode b e f o r e , DocNode a f t e r , DocNode u )
{
161 u=g ener a teNo de ( b e f o r e , a f t e r , u ) ; S t r i n g p = getPosID ( u ) ;
163 r e t u r n p ; }
165 /∗∗
∗ Apply l o c a l d e l e t e o p e r a t i o n
167 ∗ @param u : d e l e t e d node
∗ @return posID o f d e l e t e d node
169 ∗/
p u b l i c S t r i n g a p p l y l o c a l D e l e t e O p e r a t i o n ( DocNode u ) {
171 u . setAtom (n u l l) ;
S t r i n g p = getPosID ( u ) ;
173 r e t u r n p ; }
175 p u b l i c DocNode addToMajorNode ( MajorNode mj , DocNode u ) {
i n t i ;
177 f o r ( i = 0 ; i < mj . arrDocNode . s i z e ( ) ; i ++) {
i f ( mj . arrDocNode . g e t ( i ) . i d . compareTo ( u . i d ) > 0 ) {
179 u . majorNode = mj ;
mj . arrDocNode . add ( i , u ) ;
181 r e t u r n u ;
}
183 }
i f ( i == mj . arrDocNode . s i z e ( ) ) {
185 u . majorNode = mj ;
mj . arrDocNode . add ( u ) ;
187 r e t u r n u ;
}
189 r e t u r n n u l l; }
191 l o n g d e s i r e d h e i g h t ; l o n g e x t r a n o d e ;
193 s t a t i c i n t c u r r e n t h e i g h t ; i n t a ddedindex ;
195 /∗∗
∗ Rebanlance Tree
197 ∗ @param No deList : t h e l i s t o f no des o f r e b a l a n c e d Tree
∗/
199 p u b l i c v o i d r e b a l a n c i n g ( A r r a y L i s t<DocNode> No deList ) { f o r (i n t y = No deList . s i z e ( ) − 1 ; y >= 0 ; y−−) {
201 i f ( No deList . g e t ( y ) . getAtom ( ) == n u l l) { No deList . remove ( y ) ;
203 }
}
205 d e s i r e d h e i g h t = ( (l o n g) ( Math . l o g ( No deList . s i z e ( ) + 1 ) / Math . l o g ( 2 ) ) )
− 1 ;
e x t r a n o d e = (l o n g) ( No deList . s i z e ( ) − Math . pow ( 2 , d e s i r e d h e i g h t + 1 ) + 1 ) ;
207 i f ( e x t r a n o d e > 0 ) { d e s i r e d h e i g h t ++;
209 }
c u r r e n t h e i g h t = 0 ;
211 a ddedindex = 0 ;
R e b a l a n c i n g ( r o o t , No deList ) ;
213 }
v o i d R e b a l a n c i n g ( MajorNode u , A r r a y L i s t<DocNode> NonemptyNdList ) {
215 w h i l e ( u . arrDocNode . s i z e ( ) > 1 ) { u . arrDocNode . remove ( 1 ) ;
217 }
i f ( u . arrDocNode . g e t ( 0 ) . l e f t != n u l l) {
219 i f ( c u r r e n t h e i g h t < d e s i r e d h e i g h t ) { c u r r e n t h e i g h t ++;
221 R e b a l a n c i n g ( u . arrDocNode . g e t ( 0 ) . l e f t , NonemptyNdList ) ; c u r r e n t h e i g h t−−;
223 } e l s e {
u . arrDocNode . g e t ( 0 ) . l e f t = n u l l;
225 }
} e l s e {
227 i f ( c u r r e n t h e i g h t < d e s i r e d h e i g h t ) {
DocNode uu = new DocNode(’ ’, t r u e , n u l l , ”1 ”) ;
229 MajorNode mm = new MajorNode ( ) ;
mm. add ( uu ) ;
231 mm. p a r r e n t = u . arrDocNode . g e t ( 0 ) ; u . arrDocNode . g e t ( 0 ) . l e f t = mm;
233 c u r r e n t h e i g h t ++;
R e b a l a n c i n g ( u . arrDocNode . g e t ( 0 ) . l e f t , NonemptyNdList ) ;
235 c u r r e n t h e i g h t−−;
}
237 }
u . arrDocNode . g e t ( 0 ) . i d = ”1 ”;
239 u . arrDocNode . g e t ( 0 ) . setAtom ( NonemptyNdList . g e t ( a ddedindex ) . getAtom ( ) ) ; u . arrDocNode . g e t ( 0 ) . r e b a l a n c e = t r u e;
241 a ddedindex++;
i f ( c u r r e n t h e i g h t == d e s i r e d h e i g h t && e x t r a n o d e > 0 ) {
243 extr a no de−−;
i f ( e x t r a n o d e == 0 ) {
245 d e s i r e d h e i g h t−−;
}
247 }
i f ( u . arrDocNode . g e t ( 0 ) . r i g h t != n u l l) {
249 i f ( c u r r e n t h e i g h t < d e s i r e d h e i g h t ) { c u r r e n t h e i g h t ++;
251 R e b a l a n c i n g ( u . arrDocNode . g e t ( 0 ) . r i g h t , NonemptyNdList ) ; c u r r e n t h e i g h t−−;
253 } e l s e {
u . arrDocNode . g e t ( 0 ) . r i g h t = n u l l;
255 }
} e l s e {
257 i f ( c u r r e n t h e i g h t < d e s i r e d h e i g h t ) {
DocNode uu = new DocNode(’ ’, t r u e , n u l l , ”1 ”) ;
259 MajorNode mm = new MajorNode ( ) ;
mm. add ( uu ) ;
261 mm. p a r r e n t = u . arrDocNode . g e t ( 0 ) ; u . arrDocNode . g e t ( 0 ) . r i g h t = mm;
263 c u r r e n t h e i g h t ++;
R e b a l a n c i n g ( u . arrDocNode . g e t ( 0 ) . r i g h t , NonemptyNdList ) ;
265 c u r r e n t h e i g h t−−;
}
267 }
}
269 s t a t i c i n t nonEmptyNode ; s t a t i c i n t EmptyNode ;
271 /∗ ∗
∗ T r a n s l a t e no des t h a t don ’ t b e l o n g t o epoch n t o epoch n+1
273 ∗ @param a : Tree b e f o r e r e b a l a n c i n g
∗ @param b Tree a f t e r r e b a l a n c i n g
275 ∗/
p u b l i c s t a t i c v o i d T r a n s l a t e ( TreeDoc a , TreeDoc b ) {
277 c u r r e n t h e i g h t = 0 ; nonEmptyNode = −1;
279 EmptyNode = 0 ;
A r r a y L i s t<S t r i n g> po sIDP a ir = new A r r a y L i s t<S t r i n g>() ;
281 v i s i t f o r T r a n s l a t e ( a , a . r o o t , b , po sIDP a ir ) ; }
283 s t a t i c p u b l i c v o i d v i s i t f o r T r a n s l a t e ( TreeDoc a , MajorNode r , TreeDoc b , A r r a y L i s t<S t r i n g> po sIDP a ir ) {
285 f o r (i n t i = 0 ; i < r . arrDocNode . s i z e ( ) ; i ++) { i f ( r . arrDocNode . g e t ( i ) . r e b a l a n c e == t r u e
287 && r . arrDocNode . g e t ( i ) . l e f t != n u l l) { c u r r e n t h e i g h t ++;
289 v i s i t f o r T r a n s l a t e ( a , r . arrDocNode . g e t ( i ) . l e f t , b , po sIDP a ir ) ; c u r r e n t h e i g h t−−;
291 }
DocNode temp = r . arrDocNode . g e t ( i ) ;
293 i f ( temp . r e b a l a n c e == t r u e) { i f ( temp . getAtom ( ) != n u l l) {
295 nonEmptyNode++;
EmptyNode = 0 ;
297 } e l s e {
EmptyNode++;
299 }
} e l s e {
301 S t r i n g oldPosID = a . getPosID ( temp ) ;
a p p l y t o R e b a l a n c e T r e e ( c u r r e n t h e i g h t , EmptyNode , nonEmptyNode ,
303 temp , b ) ;
S t r i n g newPosID = b . getPosID ( temp ) ;
305 po sIDP a ir . add ( oldPosID ) ; po sIDP a ir . add ( newPosID ) ;
307 }
i f ( r . arrDocNode . g e t ( i ) . r e b a l a n c e == t r u e
309 && r . arrDocNode . g e t ( i ) . r i g h t != n u l l) {
r . arrDocNode . g e t ( i ) . r i g h t . p a r r e n t = r . arrDocNode . g e t ( i ) ;
311 c u r r e n t h e i g h t ++;
v i s i t f o r T r a n s l a t e ( a , r . arrDocNode . g e t ( i ) . r i g h t , b , po s IDP a ir ) ;
313 c u r r e n t h e i g h t−−;
}
315 }
}
317 p u b l i c s t a t i c v o i d a p p l y t o R e b a l a n c e T r e e (i n t Height , i n t IndexEmptyNode ,
i n t NotEmptyNode , DocNode temp , TreeDoc b ) {
319 S t r i n g d i s = ” 0”;
cha r s t r H e i g h = (cha r) Heig ht ;
321 i f ( IndexEmptyNode == 0 ) {
d i s = d i s + ”|” + ”+” + s t r H e i g h ;
323 } e l s e {
cha r strindexEmptyNode = (cha r) IndexEmptyNode ;
325 d i s = d i s + ”|” + ”−” + strindexEmptyNode + ”|” + ”+” + s t r H e i g h ; }
327 i f ( temp . i d . e q u a l s (” ”) == f a l s e) { d i s = d i s + ”|” + temp . i d ;
329 }
temp . i d = d i s ;
331 i f ( NotEmptyNode == −1) { DocNode u = b . FindNode ( 0 ) ;
333 i f ( u . l e f t == n u l l) {
MajorNode mm = new MajorNode ( ) ;
335 mm. add ( temp ) ;
temp . majorNode = mm;
337 u . l e f t = mm;
mm. p a r r e n t = u ;
339
} e l s e {
341 temp . majorNode = u . l e f t ;
i f ( u . l e f t . arrDocNode . g e t ( u . l e f t . arrDocNode . s i z e ( ) − 1 ) . i d
343 . e q u a l s (” 1 ”) == t r u e) {
u . l e f t . arrDocNode . add ( u . l e f t . arrDocNode . s i z e ( ) − 1 , temp ) ;
345
} e l s e {
347 u . l e f t . arrDocNode . add ( temp ) ; }
349 }
} e l s e {
351 DocNode u = b . FindNode ( NotEmptyNode ) ; i f ( u . r i g h t == n u l l) {
353 MajorNode mm = new MajorNode ( ) ;
mm. add ( temp ) ;
355 temp . majorNode = mm;
u . r i g h t = mm;
357 mm. p a r r e n t = u ; } e l s e {
359 temp . majorNode = u . r i g h t ;
i f ( u . r i g h t . arrDocNode . g e t ( u . r i g h t . arrDocNode . s i z e ( ) − 1 ) . i d
361 . e q u a l s (” 1 ”) == t r u e) {
u . r i g h t . arrDocNode . add ( u . r i g h t . arrDocNode . s i z e ( ) − 1 , temp ) ;
363
} e l s e {
365 u . r i g h t . arrDocNode . add ( temp ) ; }
367 }
}
369 }
/∗∗
371 ∗ Get posID o f a node on t h e t r e e
∗ @param u : t h e node on t h e t r e e
373 ∗ @return posID o f pa r a meter node
∗/
375 p u b l i c S t r i n g getPosID ( DocNode u ) { S t r i n g p a t h b i t = ” ”;
377 S t r i n g p a t h d i s = ” ”; byte a = 1 ;
379 byte o nebyte = 0 ; i n t n u m b e r o f b i t = 0 ;
381 DocNode temp = u ;
w h i l e ( temp . majorNode != r o o t ) {
383 S t r i n g d = temp . i d ;
MajorNode majorNode = temp . majorNode ;
385 temp = temp . majorNode . p a r r e n t ; i f ( temp . r i g h t == majorNode ) {
387 o nebyte = (byte) ( o nebyte | a ) ; }
389 n u m b e r o f b i t++;
a = (byte) ( a << 1 ) ;
391 i f ( n u m b e r o f b i t % 8 == 0 ) {
p a t h b i t = p a t h b i t + (cha r) ( ( o nebyte << 8 ) >>> 8 ) ;
393 a = 1 ;
o nebyte = 0 ;
395 n u m b e r o f b i t = 0 ; }
397 p a t h d i s = d + ”−” + p a t h d i s ;
399 }
r e t u r n p a t h b i t + ” : ” + p a t h d i s ;
401 }
/∗∗
403 ∗ Decode posID
∗ @param r e c e i v e d p o s I D
405 ∗ @param p a t h d i s : t h e a r r a y o f disa mbig uo us o f posID
∗ @param p a t h b i t : t h e a r r a y o f b i t o f posID
407 ∗/
v o i d decodePosID ( S t r i n g posID , A r r a y L i s t<S t r i n g> p a t h d i s ,
409 A r r a y L i s t<I n t e g e r> p a t h b i t ) { i n t i n d e x = posID . indexO f (” : ”) ;
411 S t r i n g d i s a r r = posID . s u b s t r i n g ( 0 , i n d e x ) ;
S t r i n g b i t a r r = posID . s u b s t r i n g ( i n d e x + 1 , posID . l e n g t h ( ) ) ;
413 i n d e x = d i s a r r . indexO f (”−”) ; w h i l e ( i n d e x != −1) {
415 p a t h d i s . add ( d i s a r r . s u b s t r i n g ( 0 , i n d e x ) ) ;
d i s a r r = d i s a r r . s u b s t r i n g ( i n d e x + 1 , d i s a r r . l e n g t h ( ) ) ;
417 i n d e x = d i s a r r . indexO f (”−”) ; }
419 p a t h d i s . add ( d i s a r r ) ; kk = b i t a r r ;
421 i i = −1;
f o r (i n t i = 0 ; i < p a t h d i s . s i z e ( ) − 1 ; i ++) {
423 p a t h b i t . add ( 0 , g etNext ( ) ) ; }
425
}
427 S t r i n g kk ; i n t i i , j j ;
429 byte dd ;
p u b l i c i n t g etNext ( ) {
431
i n t k = 0 ;
433 i f ( i i == −1) { j j = 0 ;
435 }
i f ( i i == 8 | | i i == −1) {
437 dd = (byte) kk . charAt ( j j ) ; j j ++;
439 i i = 0 ;
}
441 i f ( i i < 8 ) {
k = (i n t) ( dd & 1 ) ;
443 dd = (byte) ( dd >> 1 ) ; i i ++;
445 }
r e t u r n k ;
447 }
}
Listing C.1: TreeDoc.class
impo r t j a v a . u t i l . A r r a y L i s t ;
2 p u b l i c c l a s s MajorNode { p u b l i c DocNode p a r r e n t ;
4 p u b l i c A r r a y L i s t<DocNode> arrDocNode ; p u b l i c MajorNode ( ) {
6 arrDocNode = new A r r a y L i s t<DocNode>() ; p a r r e n t = n u l l;
8 }
/∗∗
10 ∗ add a DocNode t o major node
∗ @param u : DocNode
12 ∗/
p u b l i c v o i d add ( DocNode u ) {
14 u . majorNode = t h i s; arrDocNode . add ( u ) ;
16 }
}
Listing C.2: MajorNode.class
1 p u b l i c c l a s s DocNode { p u b l i c C h a r a c t e r atom ;
3 p u b l i c S t r i n g i d ;
p u b l i c MajorNode majorNode ;
5 p u b l i c MajorNode l e f t ; p u b l i c MajorNode r i g h t ;
7 p u b l i c b o o l e a n r e b a l a n c e ; p u b l i c Font f o n t ;
9 p u b l i c DocNode( C h a r a c t e r a , b o o l e a n s , Font f t , S t r i n g d i s ) { atom = a ;
11 l e f t = n u l l; r i g h t = n u l l;
13 i d=d i s ; f o n t=f t ;
15 r e b a l a n c e=f a l s e; }
17 }
Listing C.3: DocNode.class
1 impo r t j a v a . u t i l . A r r a y L i s t ; p u b l i c c l a s s O per a tio n {
3 p u b l i c i n t epoch ;
p u b l i c S t r i n g g e n e r a t o r ;
5 p u b l i c S t a t e V e c t o r s t a t e V e c t o r ; p u b l i c i n t optype ;
7 p u b l i c S t r i n g posID ; p u b l i c C h a r a c t e r atom ;
9 p u b l i c Font f o n t ;
p u b l i c O per a tio n ( S t r i n g gen , S t a t e V e c t o r v e r s ,i n t opetype , S t r i n g pos , Font f , i n t e , C h a r a c t e r a )
11 {