// Aqsis
// Copyright (c) 1997 - 2001, Paul C. Gregory
//
// Contact: pgregory@aqsis.com
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

/**
 * Copyright (C) 2006-2007  NTT DATA CORPORATION
 * 
 * Version: 1.0.0 2007/04/01
 *  
 */
package net.cellcomputing.himawari.library;

import net.cellcomputing.himawari.accessory.STLVector;

/**
 * 
 * KDTreeを実現するクラス。
 * 
 * @author NTT DATA Corporation
 */
public strictfp class CqKDTree<T> {

    private STLVector<T>		m_aLeaves;
    private IqKDTreeData<T>	m_pDataInterface;
    private int				m_Dim;
    
    public CqKDTree( IqKDTreeData<T> pDataInterface, Class<? extends T> cls )
    {
    	m_pDataInterface = pDataInterface;
    	m_Dim = 0;
    	m_aLeaves = new STLVector<T>( cls );
    }
    
    public void Subdivide( CqKDTree<T> side1, CqKDTree<T> side2 )
    {
    	m_pDataInterface.SortElements( m_aLeaves, m_Dim );
    	
    	int median = (int)( aLeaves().size() / 2.0f );
    	
//    	side1.aLeaves().assign( aLeaves().begin(), aLeaves().begin() + median );
//    	side2.aLeaves().assign( aLeaves().begin() + median, aLeaves().end() );
    	side1.aLeaves().removeAllElements();
    	side1.aLeaves().addAll( aLeaves().subList( 0, median ) );
    	side2.aLeaves().removeAllElements();
    	side2.aLeaves().addAll( aLeaves().subList( median, aLeaves().size() ) );
    	
    	side1.m_Dim = ( m_Dim + 1 ) % m_pDataInterface.Dimensions();
    	side2.m_Dim = ( m_Dim + 1 ) % m_pDataInterface.Dimensions();
    }

    /// Accessor for leaves array
    public STLVector<T> aLeaves()
    {
    	return(m_aLeaves);
    }
    
    // 自動的に作成されるコピーコンストラクタ
    public CqKDTree<T> assignment( final CqKDTree<T> From )
    {
        m_aLeaves			= From.m_aLeaves;
        m_pDataInterface	= From.m_pDataInterface;
        m_Dim				= From.m_Dim;
        
        return (this);
    }

}
