View Javadoc

1   /*
2    *   Licensed to the Apache Software Foundation (ASF) under one
3    *   or more contributor license agreements.  See the NOTICE file
4    *   distributed with this work for additional information
5    *   regarding copyright ownership.  The ASF licenses this file
6    *   to you under the Apache License, Version 2.0 (the
7    *   "License"); you may not use this file except in compliance
8    *   with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *   Unless required by applicable law or agreed to in writing,
13   *   software distributed under the License is distributed on an
14   *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *   KIND, either express or implied.  See the License for the
16   *   specific language governing permissions and limitations
17   *   under the License.
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   * Class to serialize the AvlTree node data.
33   *
34   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
35   * @version $Rev$, $Date$
36   */
37  @SuppressWarnings("unchecked")
38  public class AvlTreeMarshaller<E> implements Marshaller<AvlTree<E>>
39  {
40      /** used for serialized form of an empty AvlTree */
41      private static final byte[] EMPTY_TREE = new byte[1];
42  
43      /** marshaller to be used for marshalling the keys */
44      private Marshaller<E> keyMarshaller;
45      
46      /** key Comparator for the AvlTree */
47      private Comparator<E> comparator;
48      
49  
50      /**
51       * Creates a new instance of AvlTreeMarshaller with a custom key
52       * Marshaller.
53       *
54       * @param comparator Comparator to be used for key comparision
55       * @param keyMarshaller marshaller for keys
56       */
57      public AvlTreeMarshaller( Comparator<E> comparator, Marshaller<E> keyMarshaller )
58      {
59          this.comparator = comparator;
60          this.keyMarshaller = keyMarshaller;
61      }
62  
63  
64      /**
65       * Creates a new instance of AvlTreeMarshaller with the default key
66       * Marshaller which uses Java Serialization.
67       *
68       * @param comparator Comparator to be used for key comparision
69       */
70      public AvlTreeMarshaller( Comparator<E> comparator )
71      {
72          this.comparator = comparator;
73          this.keyMarshaller = ( Marshaller<E> ) DefaultMarshaller.INSTANCE;
74      }
75  
76  
77      /**
78       * Marshals the given tree to bytes
79       * @param tree the tree to be marshalled
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 ); // represents the start of AvlTree byte stream
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      * writes the content of the AVLTree to an output stream.
120      * The current format is 
121      *  
122      *  AvlTree = [0(zero-byte-value)][node] // the '0' (zero) is to distinguish AvlTree from BTreeRedirect which starts with 1 (one)
123      *   node = [size] [data-length] [data] [index] [child-marker] [node] [child-marker] [node]
124      *
125      * @param node the node to be marshalled to bytes
126      * @param out OutputStream
127      * @throws IOException on write failures of serialized tree to stream
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 ); // data-length
134         out.write( data ); // data
135         out.writeInt( node.getIndex() ); // index
136         
137         if( node.getLeft() != null )
138         {
139             out.writeInt( 2 ); // left
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 ); // right
150             writeTree( node.getRight(), out );
151         }
152         else
153         {
154             out.writeInt( 0 );   
155         }
156         
157     }
158 
159     
160     /**
161      * Creates an AVLTree from given bytes of data.
162      * 
163      * @param data byte array to be converted into AVLTree  
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      * Reads the data from given InputStream and creates the LinkedAvlNodes to
215      * form the tree node = [size] [data-length] [data] [index] [child-marker]
216      * [node] [child-marker] [node].
217      *
218      * @param in the input stream to deserialize from
219      * @param node the node to deserialize
220      * @return the deserialized AvlTree node
221      * @throws IOException on failures to deserialize or read from the stream
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         //noinspection ResultOfMethodCallIgnored
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 }