/*
 * (c) Copyright 2009 Hewlett-Packard Development Company, LP
 * (c) Copyright 2011 Epimorphics Ltd.
 * 
 * All rights reserved.
 * [See end of file]
 */

package structure.radix;

import java.util.HashSet;
import java.util.List ;
import java.util.Set;

import org.openjena.atlas.io.IndentedWriter ;
import org.openjena.atlas.lib.Bytes ;
import org.openjena.atlas.logging.Log;



public final class RadixNode //extends PrintableBase implements Printable 
{
    // Debugging? Needed for traversal?
    // Not needed for deployment version (we only go down the tree).
    /*package*/ int parentId ;
    /*package*/ RadixNode parent ;

    RadixNode(RadixNode parent)
    { 
        this.parent = parent ;
        this.parentId = (parent==null)?-1 : parent.id ;
    }
    /*
     * http://en.wikipedia.org/wiki/Radix_tree
     */

    static int counter = 0 ; 
    int id = (counter++); // Debugging
    
    // Prefix to this node from node above.
    
    byte[] prefix ;     // Null means "".
    
    // Position of the end of the prefix in the overall key at this point.
    int lenFinish ; // Debugging? Use tracking to know these values. 
    int lenStart ;
    
    // The nodes below this one, corresponding to each possible next byte
    List<RadixNode> nodes ;         // When real, use an array[]; null for leaf.
    
    // Space cost:
    //     parent
    //     prefix array (so 3 slot overhead)
    //     node array   (can use array so 3 slot overhead)
    
    // More (??) compact would be a giant, segemented array for 
    // each of the node arrays then
    
    // Optimization (to do): nodes entry of null mean zero length prefix/leaf.
    
    // --------
    // Return
    //   Index of first non-matching byte.
    //   - (1+length) if key runs out
    //   prefix length means complete match
    
    public final int countMatchPrefix(byte[] key)
    {
        for ( int i = 0 ; i < prefix.length ; i++ )
        {
            // Index into key.
            int j = i+lenStart ;
            if ( j == key.length )
                // Key ran out.
                return -(i+1) ;
            if ( prefix[i] != key[j] )
                return i ;
        }
        return prefix.length ;
    }

    @Override
    public String toString()
    {
        String prefixStr = Bytes.asHex(prefix) ;
        if ( isLeaf() )
            return String.format("Leaf[%d/%d]: Length=(%d,%d) :: prefix = %s", id, parentId, lenStart, lenFinish, prefixStr) ; 
        
        StringBuilder b = new StringBuilder() ;
        for ( RadixNode n : nodes )
        {
            b.append(" ") ;
            b.append(n.id+"") ;
        }
        return String.format("Node[%d/%d]: Length=(%d,%d) :: prefix = %s -> Sub:%s", id, parentId, lenStart, lenFinish, prefixStr, b.toString() ) ;
    }
    
    /*public*/ void output(final IndentedWriter out)
    {
        RadixNodeVisitor<Object> v = new RadixNodeVisitorBase()
        {
            @Override
            public void before(RadixNode node)
            {
                String str = node.toString() ;
                out.print(str) ;
                out.println();
                out.incIndent() ;
            }

            @Override
            public void after(RadixNode node)
            {
                out.decIndent() ;
            }
            
        } ;
        this.visit(v) ;
    }

    // Re-consider for persistence - this looks into the subnode.
    // Should pull up first byte (nibble?) for dispatch purposes.
    
    /** Return the index of the node with this byte as the start of prefix
     *  or -(i+1) for insertion point if not found.
     */
    /*package*/ int locate(byte[] bytes, int start)
    {
//        if ( RadixTree.logging  && RadixTree.log.isDebugEnabled() )
//        {
//            RadixTree.log.debug("locate: <"+Bytes.asHex(bytes, start, bytes.length)) ;
//        }
            
        if ( nodes == null )
            return -1 ;
        // Nothing to test -- so is there a subnode of prefix ""
        if ( bytes.length == start )
        {
            if ( nodes.get(0).prefix.length == 0 )
                return 0 ;
            else
                return -(0+1) ;
        }
        
        byte b = bytes[start] ;
        
        // Only the root an have a prefix of no bytes 
        for ( int i = 0 ; i < nodes.size() ; i++ )
        {
//            if ( RadixTree.logging  && RadixTree.log.isDebugEnabled() )
//                RadixTree.log.debug("locate: >"+Bytes.asHex(nodes.get(i).prefix)) ;
            // Look first byte only.
            // Prefixes must differ at first byte
            if ( nodes.get(i).prefix.length == 0 )
                // No bytes is lowest 
                continue ;
            
            
            int x = Bytes.compareByte(b, nodes.get(i).prefix[0]) ;
            //int x = compare(bytes, start, nodes.get(i).prefix) ;
            if ( x > 0 ) 
                continue ;
            if ( x < 0 )
                // Overshoot.
                return -(i+1) ;
            //if ( keyByte == b ) 
            return i ;
        }
        return -(nodes.size()+1) ;
    }
    
    private int compare(byte[] bytes, int start, byte[] nextPrefix)
    {
        int n = Math.min(bytes.length-start, nextPrefix.length) ;
        
        for ( int i = 0 ; i < n ; i++ )
        {
            byte b1 = bytes[i+start] ;
            byte b2 = nextPrefix[i] ;
            if ( b1 == b2 )
                continue ;
            // Treat as unsigned values in the bytes. 
            return (b1&0xFF) - (b2&0xFF) ;  
        }

        return (bytes.length-start) - nextPrefix.length ;
    }

    public void check()
    { 
        _check(0, new HashSet<Integer>()) ; 
    }
    
    private void _check(int length, Set<Integer> seen)
    {
        // It's a tree and so we seen nodes only once. 
        if ( seen.contains(this) )
        {
            error(this, "Node %d already seen",id) ;
            return ;
        }
        seen.add(this.id) ;
        
        if (parentId != -1 && !seen.contains(parentId) )
            error(this, "Parent not seen") ;

        if ( prefix == null )
            error(this, "Null prefix") ;
     
        if ( lenStart != length )
            error(this, "Start length error %d/%d", lenStart, length) ;

        if ( lenStart > lenFinish )
            error(this, "Finish length error") ;
        
        if ( lenFinish - lenStart != prefix.length )
            error(this, "Prefix lenth error %d,%d", lenFinish - lenStart, prefix.length) ;

        if ( nodes == null )
            return ;
        
        if ( nodes.size() < 2 )
            error(this, "Internal node has length of "+nodes.size()) ;
        // Check subnodes are sorted and start with a different byte
        Set<Integer> bytes = new HashSet<Integer>() ;
        int last = -2 ;
        for ( RadixNode n : nodes )
        {
            int b = -1 ;
            if ( n.prefix.length > 0 )
                b = n.prefix[0] ;
            if ( last >= b )
                error(this, "Prefix start not strictly increasing") ;
            if ( n.parentId != id )
                error(this, "Child %d points to %d, not parent %d", n.id, n.parentId, id) ;
        }
        
        int nextStartLen = length+prefix.length ;
        for ( RadixNode n : nodes )
            n._check(nextStartLen, seen) ;
    }

    public boolean isLeaf()
    {
        return nodes == null ;
    }

    public <T> void visit(RadixNodeVisitor<T> visitor)
    {
        _visit(visitor, new HashSet<RadixNode>()) ;
    }

    private <T> void _visit(RadixNodeVisitor<T> visitor, Set<RadixNode> seen)
    {
        if ( seen.contains(this) )
        {
            Log.warn(this, "Bad tree: "+id) ;
            return ;
        }
        seen.add(this) ;
        visitor.before(this) ;
        if ( nodes != null )
        {
            for ( RadixNode n : nodes )
                n._visit(visitor, seen) ;
        }
        visitor.after(this) ;
    }
    
    private static void error(RadixNode node, String message, Object... args)
    {
        message = String.format(message, args) ;
        System.err.println("Error: "+node) ;
        System.err.println(message) ;
        RadixTree.error(message) ;
    }
}

/*
 * (c) Copyright 2009 Hewlett-Packard Development Company, LP
 * (c) Copyright 2011 Epimorphics Ltd.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */