001    /*
002     *   Licensed to the Apache Software Foundation (ASF) under one
003     *   or more contributor license agreements.  See the NOTICE file
004     *   distributed with this work for additional information
005     *   regarding copyright ownership.  The ASF licenses this file
006     *   to you under the Apache License, Version 2.0 (the
007     *   "License"); you may not use this file except in compliance
008     *   with the License.  You may obtain a copy of the License at
009     *
010     *     http://www.apache.org/licenses/LICENSE-2.0
011     *
012     *   Unless required by applicable law or agreed to in writing,
013     *   software distributed under the License is distributed on an
014     *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015     *   KIND, either express or implied.  See the License for the
016     *   specific language governing permissions and limitations
017     *   under the License.
018     *
019     */
020    package org.apache.directory.server.core.avltree;
021    
022    
023    import java.io.ByteArrayInputStream;
024    import java.io.ByteArrayOutputStream;
025    import java.io.DataInputStream;
026    import java.io.DataOutputStream;
027    import java.io.IOException;
028    import java.util.Comparator;
029    
030    import org.apache.directory.server.i18n.I18n;
031    
032    
033    /**
034     * Class to serialize the AvlTree node data.
035     *
036     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
037     * @version $Rev$, $Date$
038     */
039    @SuppressWarnings("unchecked")
040    public class AvlTreeMarshaller<E> implements Marshaller<AvlTree<E>>
041    {
042        /** used for serialized form of an empty AvlTree */
043        private static final byte[] EMPTY_TREE = new byte[1];
044    
045        /** marshaller to be used for marshalling the keys */
046        private Marshaller<E> keyMarshaller;
047        
048        /** key Comparator for the AvlTree */
049        private Comparator<E> comparator;
050        
051    
052        /**
053         * Creates a new instance of AvlTreeMarshaller with a custom key
054         * Marshaller.
055         *
056         * @param comparator Comparator to be used for key comparision
057         * @param keyMarshaller marshaller for keys
058         */
059        public AvlTreeMarshaller( Comparator<E> comparator, Marshaller<E> keyMarshaller )
060        {
061            this.comparator = comparator;
062            this.keyMarshaller = keyMarshaller;
063        }
064    
065    
066        /**
067         * Creates a new instance of AvlTreeMarshaller with the default key
068         * Marshaller which uses Java Serialization.
069         *
070         * @param comparator Comparator to be used for key comparision
071         */
072        public AvlTreeMarshaller( Comparator<E> comparator )
073        {
074            this.comparator = comparator;
075            this.keyMarshaller = ( Marshaller<E> ) DefaultMarshaller.INSTANCE;
076        }
077    
078    
079        /**
080         * Marshals the given tree to bytes
081         * @param tree the tree to be marshalled
082         */
083        public byte[] serialize( AvlTree<E> tree )
084        {
085            if( tree.isEmpty() )
086            {
087                return EMPTY_TREE;
088            }
089    
090            LinkedAvlNode<E> x = tree.getFirst().next;
091            
092            while( x != null )
093            {
094                x.setIndex( x.previous.getIndex() + 1 );  
095                x = x.next;
096            }
097            
098            ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
099            DataOutputStream out = new DataOutputStream( byteStream );
100            byte[] data = null;
101            
102            try
103            {
104                out.writeByte( 0 ); // represents the start of AvlTree byte stream
105                out.writeInt( tree.getSize() );
106                writeTree( tree.getRoot(), out );
107                out.flush();
108                data = byteStream.toByteArray();
109                out.close();
110            }
111            catch( IOException e )
112            {
113                e.printStackTrace();
114            }
115            
116            return data;
117        }
118    
119        
120        /**
121         * writes the content of the AVLTree to an output stream.
122         * The current format is 
123         *  
124         *  AvlTree = [0(zero-byte-value)][node] // the '0' (zero) is to distinguish AvlTree from BTreeRedirect which starts with 1 (one)
125         *   node = [size] [data-length] [data] [index] [child-marker] [node] [child-marker] [node]
126         *
127         * @param node the node to be marshalled to bytes
128         * @param out OutputStream
129         * @throws IOException on write failures of serialized tree to stream
130         */
131        private void writeTree( LinkedAvlNode<E> node, DataOutputStream out ) throws IOException
132        {
133            byte[] data = keyMarshaller.serialize( node.getKey() );
134            
135            out.writeInt( data.length ); // data-length
136            out.write( data ); // data
137            out.writeInt( node.getIndex() ); // index
138            
139            if( node.getLeft() != null )
140            {
141                out.writeInt( 2 ); // left
142                writeTree( node.getLeft(), out );
143            }
144            else
145            {
146                out.writeInt( 0 );   
147            }
148            
149            if( node.getRight() != null )
150            {
151                out.writeInt( 4 ); // right
152                writeTree( node.getRight(), out );
153            }
154            else
155            {
156                out.writeInt( 0 );   
157            }
158            
159        }
160    
161        
162        /**
163         * Creates an AVLTree from given bytes of data.
164         * 
165         * @param data byte array to be converted into AVLTree  
166         */
167        public AvlTree<E> deserialize( byte[] data ) throws IOException
168        {
169            if ( data == null || data.length == 0 )
170            {
171                throw new IOException( I18n.err( I18n.ERR_439 ) );
172            }
173    
174            if ( data.length == 1 && data[0] == 0 )
175            {
176                return new AvlTreeImpl<E>( comparator );
177            }
178    
179            ByteArrayInputStream bin = new ByteArrayInputStream( data );
180            DataInputStream din = new DataInputStream( bin );
181            
182            byte startByte = din.readByte();
183            
184            if( startByte != 0 )
185            {
186                throw new IOException( I18n.err( I18n.ERR_443 ) );
187            }
188            
189            int size = din.readInt();
190            
191            LinkedAvlNode[] nodes = new LinkedAvlNode[ size ];
192            LinkedAvlNode<E> root = readTree( din, null, nodes );
193            
194            AvlTreeImpl<E> tree = new AvlTreeImpl<E>( comparator );
195            
196            tree.setRoot( root );
197            
198            tree.setFirst( nodes[0] );
199            
200            // Update the size
201            tree.setSize( size );
202            
203            if( nodes.length >= 1 )
204            {
205                tree.setLast( nodes[ nodes.length - 1 ] );
206            }
207            
208            for( int i = 0; i < nodes.length - 1; i++ )
209            {
210                nodes[ i ].setNext( nodes[ i + 1] );
211                nodes[ i + 1].setPrevious( nodes[ i ] );
212            }
213    
214            return tree;
215        }
216    
217        
218        /**
219         * Reads the data from given InputStream and creates the LinkedAvlNodes to
220         * form the tree node = [size] [data-length] [data] [index] [child-marker]
221         * [node] [child-marker] [node].
222         *
223         * @param in the input stream to deserialize from
224         * @param node the node to deserialize
225         * @return the deserialized AvlTree node
226         * @throws IOException on failures to deserialize or read from the stream
227         */
228        public LinkedAvlNode<E> readTree( DataInputStream in, LinkedAvlNode<E> node, LinkedAvlNode[] nodes ) throws IOException
229        {
230            int dLen = in.readInt();
231          
232            byte[] data = new byte[ dLen ];
233    
234            //noinspection ResultOfMethodCallIgnored
235            in.read( data );
236    
237            E key = keyMarshaller.deserialize( data );
238            node = new LinkedAvlNode( key );
239          
240            int index = in.readInt();
241            nodes[ index ] = node;
242          
243            int childMarker = in.readInt();
244          
245            if( childMarker == 2)
246            {
247                node.setLeft( readTree( in, node.getLeft(), nodes ) );
248            }
249          
250            childMarker = in.readInt();
251          
252            if( childMarker == 4 )
253            {
254                node.setRight( readTree( in, node.getRight(), nodes ) );
255            }
256          
257            return node;
258        }
259    }