//------------------------------------------------------------------------------
// Lamp : Open source game middleware
// Copyright (C) 2004  Junpei Ohtani ( Email : junpee@users.sourceforge.jp )
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 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
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser 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
//------------------------------------------------------------------------------

/** @file
 * ベクトル補間圧縮実装
 * @author Junpee
 */

#include "LampBasic.h"
#include "Animation/VectorInterpolator/VectorInterpolationCompressor.h"
#include "Animation/VectorInterpolator/VectorArrayInterpolator.h"
#include "Animation/VectorInterpolator/VectorConstantInterpolator.h"
#include "Animation/VectorInterpolator/VectorLinearInterpolator.h"
#include "Core/Container/Deque.h"

namespace Lamp{

//------------------------------------------------------------------------------
// 生成、破棄
//------------------------------------------------------------------------------
// コンストラクタ
VectorInterpolationCompressor::VectorInterpolationCompressor() :
	tolerance_(0.f), length_(0.f), sourceKeyCount_(0), compressedKeyCount_(0),
	compressedKeySize_(0){
}
//------------------------------------------------------------------------------
// デストラクタ
VectorInterpolationCompressor::~VectorInterpolationCompressor(){
}
//------------------------------------------------------------------------------
// 圧縮
//------------------------------------------------------------------------------
// 圧縮
VectorInterpolator* VectorInterpolationCompressor::compress(
	VectorArrayInterpolator* source, float tolerance){
	// 圧縮準備
	compressSetup(source, tolerance);
	VectorInterpolator* result = NULL;

	// 定数圧縮
	result = compressConstant(source);
	if(result != NULL){ return result; }

	// 線形圧縮
	result = compressLinear(source);
	if(result != NULL){ return result; }

	// スプライン系の圧縮と線形圧縮の結果を重み付けした上で比較して出力可能
	// その場合にsetCompressedDataを忘れないように注意

	// 全ての圧縮に失敗したなら元データのコピーを返す
	result = source->duplicate();
	setCompressedData(getSourceKeyCount(), sourceKeySize_);
	
	return result;
}
//------------------------------------------------------------------------------
// 圧縮準備
void VectorInterpolationCompressor::compressSetup(
	VectorArrayInterpolator* source, float tolerance){
	Assert((source != NULL) && (tolerance >= 0.f));
	tolerance_ = tolerance;
	length_ = source->getLength();
	sourceKeyCount_ = source->getSize();
	Assert(sourceKeyCount_ > 1);
}
//------------------------------------------------------------------------------
// 定数圧縮
VectorInterpolator* VectorInterpolationCompressor::compressConstant(
	VectorArrayInterpolator* source){
	// ターゲットとなる値の算出、バウンディングボックスの中心
	AxisAlignedBox boundingBox(source->getValue(0), source->getValue(0));
	for(int i = 1; i < sourceKeyCount_; i++){
		boundingBox.merge(source->getValue(i));
	}
	Vector3 targetValue = boundingBox.getCenter();

	// 誤差チェック
	float squaredTolerance = getTolerance() * getTolerance();
	for(int i = 0; i < sourceKeyCount_; i++){
		Vector3 distance = source->getValue(i) - targetValue;
		// 定数圧縮に失敗
		if(distance.getSquaredLength() > squaredTolerance){ return NULL; }
	}

	// 定数圧縮に成功
	VectorConstantInterpolator* result = new VectorConstantInterpolator();
	result->setLength(getLength());
	result->setValue(targetValue);
	setCompressedData(1, sizeof(Vector3) + sizeof(float));
	return result;
}
//------------------------------------------------------------------------------
// 線形圧縮
VectorInterpolator* VectorInterpolationCompressor::compressLinear(
	VectorArrayInterpolator* source){
	// キーのリストを作成し、誤差が小さいキーから間引いていく

	// キーリストの作成
	int sourceKeyCount = getSourceKeyCount();
	Deque<LinearKey> keys_(sourceKeyCount);
	for(int i = 0; i < sourceKeyCount; i++){
		LinearKey key;
		key.value_ = source->getValue(i);
		key.time_ = (float)i;
		keys_.pushBack(key);
	}

	// 全誤差の算出
	int keyCount = keys_.getCount();
	int maxKeyCount = keyCount - 1;
	// 最初と最後の値は操作しない
	keys_[0].squaredError_ = 0.f;
	keys_[maxKeyCount].squaredError_ = 0.f;
	Assert(keys_[0].time_ == 0.f)
	Assert(keys_[maxKeyCount].time_ == getLength());
	for(int i = 1; i < maxKeyCount; i++){
		LinearKey& key = keys_[i];
		LinearKey& preKey = keys_[i - 1];
		LinearKey& postKey = keys_[i + 1];
		// 誤差の初期化時は前のキーと後ろのキーの平均が補間値になる
		Vector3 value = (preKey.value_ + postKey.value_) * 0.5f;
		key.squaredError_ = (value - key.value_).getSquaredLength();
	}

	// 圧縮ループ、キーが2個になったら抜ける
	float squaredTolerance = getTolerance() * getTolerance();
	while(keys_.getCount() > 2){
		// 誤差が最小のキーを調べる
		int targetIndex = 1;
		float targetSquaredError = keys_[targetIndex].squaredError_;
		maxKeyCount = keys_.getCount() - 1;
		for(int i = 2; i < maxKeyCount; i++){
			if(keys_[i].squaredError_ < targetSquaredError){
				targetSquaredError = keys_[i].squaredError_;
				targetIndex = i;
			}
		}

		// 最小誤差が許容範囲外なら圧縮ループを抜ける
		if(targetSquaredError > squaredTolerance){ break; }

		// 最小誤差キーの削除と誤差のアップデート
		keys_.remove(targetIndex);
		// 前のキーが先頭キーでなければ誤差を再計算
		if((targetIndex - 1) > 0){
			recalcLinearError(source, keys_[targetIndex - 2],
				keys_[targetIndex - 1], keys_[targetIndex]);
		}
		// 後ろのキーが最後尾キーでなければ誤差を再計算
		if(targetIndex < (keys_.getCount() - 1)){
			recalcLinearError(source, keys_[targetIndex - 1],
				keys_[targetIndex], keys_[targetIndex + 1]);
		}

	}

	// サイズが小さくなっていなければ失敗、失敗条件を厳しくするのもあり
	keyCount = keys_.getCount();
	int keySize = sizeof(Vector3) + sizeof(float);
	if((keyCount * keySize) >= getSourceSize()){ return NULL; }

	// 線形圧縮に成功
	VectorLinearInterpolator* result = new VectorLinearInterpolator();
	result->setKeyCount(keyCount);
	for(int i = 0; i < keyCount; i++){
		LinearKey& key = keys_[i];
		result->setKey(i, key.time_, key.value_);
	}
	setCompressedData(keyCount, keySize);
	return result;
}
//------------------------------------------------------------------------------
// 線形圧縮誤差の再計算
void VectorInterpolationCompressor::recalcLinearError(
	VectorArrayInterpolator* source,
	LinearKey& preKey, LinearKey& key, LinearKey& postKey){
	int preTime = (int)preKey.time_;
	Vector3 preValue = preKey.value_;
	int postTime = (int)postKey.time_;
	Vector3 postValue = postKey.value_;
	int timeRange = postTime - preTime;
	Vector3 distance = postValue - preValue;

	// 最大の二乗誤差を算出
	float maxSquaredError = 0.f;
	for(int i = 1; i < timeRange; i++){
		int time = preTime + i;
		Vector3 sourceValue = source->getValue(time);
		float rate = (float)i / (float)timeRange;
		Vector3 targetValue = distance * rate + preValue;
		float squaredError = (targetValue - sourceValue).getSquaredLength();
		if(squaredError > maxSquaredError){ maxSquaredError = squaredError; }
	}
	key.squaredError_ = maxSquaredError;
}
//------------------------------------------------------------------------------
// 圧縮結果
//------------------------------------------------------------------------------
// 結果文字列の取得
String VectorInterpolationCompressor::getResultString() const{
	String result;
	result.format(
		"%.2f%%  Key %d/%d  Size %.2f/%.2fKb  Length %.0f",
		getCompressionRate() * 100.f,
		getCompressedKeyCount(), getSourceKeyCount(),
		(float)getCompressedSize() / 1024.f, (float)getSourceSize() / 1024.f,
		getLength());
	return result;
}
//------------------------------------------------------------------------------
} // End of namespace Lamp
//------------------------------------------------------------------------------
