1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.server.core.avltree;
21
22
23 import java.io.ByteArrayInputStream;
24 import java.io.ByteArrayOutputStream;
25 import java.io.DataInputStream;
26 import java.io.DataOutputStream;
27 import java.io.IOException;
28 import java.util.Comparator;
29
30
31
32
33
34
35
36
37 @SuppressWarnings("unchecked")
38 public class AvlTreeMarshaller<E> implements Marshaller<AvlTree<E>>
39 {
40
41 private static final byte[] EMPTY_TREE = new byte[1];
42
43
44 private Marshaller<E> keyMarshaller;
45
46
47 private Comparator<E> comparator;
48
49
50
51
52
53
54
55
56
57 public AvlTreeMarshaller( Comparator<E> comparator, Marshaller<E> keyMarshaller )
58 {
59 this.comparator = comparator;
60 this.keyMarshaller = keyMarshaller;
61 }
62
63
64
65
66
67
68
69
70 public AvlTreeMarshaller( Comparator<E> comparator )
71 {
72 this.comparator = comparator;
73 this.keyMarshaller = ( Marshaller<E> ) DefaultMarshaller.INSTANCE;
74 }
75
76
77
78
79
80
81 public byte[] serialize( AvlTree<E> tree )
82 {
83 if( tree.isEmpty() )
84 {
85 return EMPTY_TREE;
86 }
87
88 LinkedAvlNode<E> x = tree.getFirst().next;
89
90 while( x != null )
91 {
92 x.setIndex( x.previous.getIndex() + 1 );
93 x = x.next;
94 }
95
96 ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
97 DataOutputStream out = new DataOutputStream( byteStream );
98 byte[] data = null;
99
100 try
101 {
102 out.writeByte( 0 );
103 out.writeInt( tree.getSize() );
104 writeTree( tree.getRoot(), out );
105 out.flush();
106 data = byteStream.toByteArray();
107 out.close();
108 }
109 catch( IOException e )
110 {
111 e.printStackTrace();
112 }
113
114 return data;
115 }
116
117
118
119
120
121
122
123
124
125
126
127
128
129 private void writeTree( LinkedAvlNode<E> node, DataOutputStream out ) throws IOException
130 {
131 byte[] data = keyMarshaller.serialize( node.getKey() );
132
133 out.writeInt( data.length );
134 out.write( data );
135 out.writeInt( node.getIndex() );
136
137 if( node.getLeft() != null )
138 {
139 out.writeInt( 2 );
140 writeTree( node.getLeft(), out );
141 }
142 else
143 {
144 out.writeInt( 0 );
145 }
146
147 if( node.getRight() != null )
148 {
149 out.writeInt( 4 );
150 writeTree( node.getRight(), out );
151 }
152 else
153 {
154 out.writeInt( 0 );
155 }
156
157 }
158
159
160
161
162
163
164
165 public AvlTree<E> deserialize( byte[] data ) throws IOException
166 {
167 if ( data == null || data.length == 0 )
168 {
169 throw new IOException( "Null or empty data array is invalid." );
170 }
171
172 if ( data.length == 1 && data[0] == 0 )
173 {
174 return new AvlTree<E>( comparator );
175 }
176
177 ByteArrayInputStream bin = new ByteArrayInputStream( data );
178 DataInputStream din = new DataInputStream( bin );
179
180 byte startByte = din.readByte();
181
182 if( startByte != 0 )
183 {
184 throw new IOException("wrong AvlTree serialized data format");
185 }
186
187 int size = din.readInt();
188
189 LinkedAvlNode[] nodes = new LinkedAvlNode[ size ];
190 LinkedAvlNode<E> root = readTree( din, null, nodes );
191
192 AvlTree<E> tree = new AvlTree<E>( comparator );
193
194 tree.setRoot( root );
195
196 tree.setFirst( nodes[0] );
197
198 if( nodes.length >= 1 )
199 {
200 tree.setLast( nodes[ nodes.length - 1 ] );
201 }
202
203 for( int i = 0; i < nodes.length - 1; i++ )
204 {
205 nodes[ i ].setNext( nodes[ i + 1] );
206 nodes[ i + 1].setPrevious( nodes[ i ] );
207 }
208
209 return tree;
210 }
211
212
213
214
215
216
217
218
219
220
221
222
223 public LinkedAvlNode<E> readTree( DataInputStream in, LinkedAvlNode<E> node, LinkedAvlNode[] nodes ) throws IOException
224 {
225 int dLen = in.readInt();
226
227 byte[] data = new byte[ dLen ];
228
229
230 in.read( data );
231
232 E key = keyMarshaller.deserialize( data );
233 node = new LinkedAvlNode( key );
234
235 int index = in.readInt();
236 nodes[ index ] = node;
237
238 int childMarker = in.readInt();
239
240 if( childMarker == 2)
241 {
242 node.setLeft( readTree( in, node.getLeft(), nodes ) );
243 }
244
245 childMarker = in.readInt();
246
247 if( childMarker == 4 )
248 {
249 node.setRight( readTree( in, node.getRight(), nodes ) );
250 }
251
252 return node;
253 }
254 }