Source/core/animation/KeyframeAnimationEffect.cpp - platform/external/chromium_org/third_party/WebKit - Git at Google

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * 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.
  *     * Neither the name of Google Inc. nor the names of its
  * contributors may be used to endorse or promote products derived from
  * this software without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  * "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 COPYRIGHT
  * OWNER OR CONTRIBUTORS 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.
  */

 #include "config.h"
 #include "core/animation/KeyframeAnimationEffect.h"

 #include "wtf/MathExtras.h"
 #include "wtf/text/StringHash.h"

 namespace {

 using namespace WebCore;

 class ReplaceCompositableValue : public AnimationEffect::CompositableValue {
 public:
     static PassRefPtr<ReplaceCompositableValue> create(const AnimatableValue* value)
     {
         return adoptRef(new ReplaceCompositableValue(value));
     }
     virtual PassRefPtr<AnimatableValue> compositeOnto(const AnimatableValue* underlyingValue) const
     {
         return PassRefPtr<AnimatableValue>(m_value);
     }
 private:
     ReplaceCompositableValue(const AnimatableValue* value)
         : m_value(const_cast<AnimatableValue*>(value))
     {
     }
     RefPtr<AnimatableValue> m_value;
 };

 class AddCompositableValue : public AnimationEffect::CompositableValue {
 public:
     static PassRefPtr<AddCompositableValue> create(const AnimatableValue* value)
     {
         return adoptRef(new AddCompositableValue(value));
     }
     virtual PassRefPtr<AnimatableValue> compositeOnto(const AnimatableValue* underlyingValue) const
     {
         return AnimatableValue::add(underlyingValue, m_value.get());
     }
 private:
     AddCompositableValue(const AnimatableValue* value)
         : m_value(const_cast<AnimatableValue*>(value))
     {
     }
     RefPtr<AnimatableValue> m_value;
 };

 class BlendedCompositableValue : public AnimationEffect::CompositableValue {
 public:
     static PassRefPtr<BlendedCompositableValue> create(const AnimationEffect::CompositableValue* before, const AnimationEffect::CompositableValue* after, double fraction)
     {
         return adoptRef(new BlendedCompositableValue(before, after, fraction));
     }
     virtual PassRefPtr<AnimatableValue> compositeOnto(const AnimatableValue* underlyingValue) const
     {
         return AnimatableValue::interpolate(m_before->compositeOnto(underlyingValue).get(), m_after->compositeOnto(underlyingValue).get(), m_fraction);
     }
 private:
     BlendedCompositableValue(const AnimationEffect::CompositableValue* before, const AnimationEffect::CompositableValue* after, double fraction)
         : m_before(const_cast<AnimationEffect::CompositableValue*>(before))
         , m_after(const_cast<AnimationEffect::CompositableValue*>(after))
         , m_fraction(fraction)
     { }
     RefPtr<AnimationEffect::CompositableValue> m_before;
     RefPtr<AnimationEffect::CompositableValue> m_after;
     double m_fraction;
 };

 bool compareOffsets(const RefPtr<Keyframe>& a, const RefPtr<Keyframe>& b)
 {
     return a->offset() < b->offset();
 }

 } // namespace


 namespace WebCore {

 Keyframe::Keyframe()
     : m_offset(std::numeric_limits<double>::quiet_NaN())
     , m_composite(AnimationEffect::CompositeReplace)
 { }

 void Keyframe::setPropertyValue(CSSPropertyID property, const AnimatableValue* value)
 {
     m_propertyValues.add(property, const_cast<AnimatableValue*>(value));
 }

 const AnimatableValue* Keyframe::propertyValue(CSSPropertyID property) const
 {
     ASSERT(m_propertyValues.contains(property));
     return m_propertyValues.get(property);
 }

 PropertySet Keyframe::properties() const
 {
     // This is only used when setting up the keyframe groups, so there's no
     // need to cache the result.
     PropertySet properties;
     for (PropertyValueMap::const_iterator iter = m_propertyValues.begin(); iter != m_propertyValues.end(); ++iter)
         properties.add(*iter.keys());
     return properties;
 }


 KeyframeAnimationEffect::KeyframeAnimationEffect(const KeyframeVector& keyframes)
     : m_keyframes(keyframes)
 {
 }

 PassOwnPtr<AnimationEffect::CompositableValueMap> KeyframeAnimationEffect::sample(int iteration, double fraction) const
 {
     const_cast<KeyframeAnimationEffect*>(this)->ensureKeyframeGroups();
     OwnPtr<CompositableValueMap> map = adoptPtr(new CompositableValueMap());
     for (KeyframeGroupMap::const_iterator iter = m_keyframeGroups->begin(); iter != m_keyframeGroups->end(); ++iter)
         map->add(iter->key, iter->value->sample(iteration, fraction));
     return map.release();
 }

 KeyframeAnimationEffect::KeyframeVector KeyframeAnimationEffect::normalizedKeyframes() const
 {
     KeyframeVector keyframes = m_keyframes;

     // Set offsets at 0.0 and 1.0 at ends if unset.
     if (keyframes.size() >= 2) {
         Keyframe* firstKeyframe = keyframes.first().get();
         if (std::isnan(firstKeyframe->offset()))
             firstKeyframe->setOffset(0.0);
     }
     if (keyframes.size() >= 1) {
         Keyframe* lastKeyframe = keyframes.last().get();
         if (lastKeyframe && std::isnan(lastKeyframe->offset()))
             lastKeyframe->setOffset(1.0);
     }

     // FIXME: Distribute offsets where missing.
     for (KeyframeVector::iterator iter = keyframes.begin(); iter != keyframes.end(); ++iter)
         ASSERT(!std::isnan((*iter)->offset()));

     // Sort by offset.
     std::stable_sort(keyframes.begin(), keyframes.end(), compareOffsets);
     return keyframes;
 }

 void KeyframeAnimationEffect::ensureKeyframeGroups()
 {
     if (m_keyframeGroups)
         return;

     m_keyframeGroups = adoptPtr(new KeyframeGroupMap);
     const KeyframeVector& keyframes = normalizedKeyframes();
     for (KeyframeVector::const_iterator keyframeIter = keyframes.begin(); keyframeIter != keyframes.end(); ++keyframeIter) {
         const Keyframe* keyframe = keyframeIter->get();
         PropertySet keyframeProperties = keyframe->properties();
         for (PropertySet::const_iterator propertyIter = keyframeProperties.begin(); propertyIter != keyframeProperties.end(); ++propertyIter) {
             CSSPropertyID property = *propertyIter;
             KeyframeGroupMap::iterator groupIter = m_keyframeGroups->find(property);
             if (groupIter == m_keyframeGroups->end()) {
                 KeyframeGroupMap::AddResult result = m_keyframeGroups->add(property, adoptPtr(new PropertySpecificKeyframeGroup));
                 ASSERT(result.isNewEntry);
                 groupIter = result.iterator;
             }
             groupIter->value->appendKeyframe(adoptPtr(
                 new PropertySpecificKeyframe(keyframe->offset(), keyframe->propertyValue(property), keyframe->composite())));
         }
     }

     // Add synthetic keyframes.
     for (KeyframeGroupMap::iterator iter = m_keyframeGroups->begin(); iter != m_keyframeGroups->end(); ++iter) {
         iter->value->addSyntheticKeyframeIfRequired();
         iter->value->removeRedundantKeyframes();
     }
 }


 KeyframeAnimationEffect::PropertySpecificKeyframe::PropertySpecificKeyframe(double offset, const AnimatableValue* value, CompositeOperation composite)
     : m_offset(offset)
     , m_value(composite == AnimationEffect::CompositeReplace ?
         static_cast<PassRefPtr<CompositableValue> >(ReplaceCompositableValue::create(value)) :
         static_cast<PassRefPtr<CompositableValue> >(AddCompositableValue::create(value)))
 {
 }

 KeyframeAnimationEffect::PropertySpecificKeyframe::PropertySpecificKeyframe(double offset, PassRefPtr<CompositableValue> value)
     : m_offset(offset)
     , m_value(value)
 {
     ASSERT(!std::isnan(m_offset));
 }

 PassOwnPtr<KeyframeAnimationEffect::PropertySpecificKeyframe> KeyframeAnimationEffect::PropertySpecificKeyframe::cloneWithOffset(double offset) const
 {
     return adoptPtr(new PropertySpecificKeyframe(offset, PassRefPtr<CompositableValue>(m_value)));
 }


 void KeyframeAnimationEffect::PropertySpecificKeyframeGroup::appendKeyframe(PassOwnPtr<PropertySpecificKeyframe> keyframe)
 {
     ASSERT(m_keyframes.isEmpty() || m_keyframes.last()->offset() <= keyframe->offset());
     m_keyframes.append(keyframe);
 }

 void KeyframeAnimationEffect::PropertySpecificKeyframeGroup::removeRedundantKeyframes()
 {
     // As an optimization, removes keyframes in the following categories, as
     // they will never be used by sample().
     // - End keyframes with the same offset as their neighbor
     // - Interior keyframes with the same offset as both their neighbors
     // Note that synthetic keyframes must be added before this method is
     // called.
     ASSERT(m_keyframes.size() >= 2);
     for (int i = m_keyframes.size() - 1; i >= 0; --i) {
         double offset = m_keyframes[i]->offset();
         bool hasSameOffsetAsPreviousNeighbor = !i || m_keyframes[i - 1]->offset() == offset;
         bool hasSameOffsetAsNextNeighbor = i == m_keyframes.size() - 1 || m_keyframes[i + 1]->offset() == offset;
         if (hasSameOffsetAsPreviousNeighbor && hasSameOffsetAsNextNeighbor)
             m_keyframes.remove(i);
     }
     ASSERT(m_keyframes.size() >= 2);
 }

 void KeyframeAnimationEffect::PropertySpecificKeyframeGroup::addSyntheticKeyframeIfRequired()
 {
     ASSERT(!m_keyframes.isEmpty());
     double offset = m_keyframes.first()->offset();
     bool allOffsetsEqual = true;
     for (PropertySpecificKeyframeVector::const_iterator iter = m_keyframes.begin() + 1; iter != m_keyframes.end(); ++iter) {
         if ((*iter)->offset() != offset) {
             allOffsetsEqual = false;
             break;
         }
     }
     if (!allOffsetsEqual)
         return;

     if (!offset)
         appendKeyframe(m_keyframes.first()->cloneWithOffset(1.0));
     else
         m_keyframes.insert(0, adoptPtr(new PropertySpecificKeyframe(0.0, AnimatableValue::neutralValue(), CompositeAdd)));
 }

 PassRefPtr<AnimationEffect::CompositableValue> KeyframeAnimationEffect::PropertySpecificKeyframeGroup::sample(int iteration, double offset) const
 {
     // FIXME: Implement accumulation.
     ASSERT_UNUSED(iteration, !iteration);

     double minimumOffset = m_keyframes.first()->offset();
     double maximumOffset = m_keyframes.last()->offset();
     ASSERT(minimumOffset != maximumOffset);

     PropertySpecificKeyframeVector::const_iterator before;
     PropertySpecificKeyframeVector::const_iterator after;

     // Note that this algorithm is simpler than that in the spec because we
     // have removed keyframes with equal offsets in
     // removeRedundantKeyframes().
     if (offset < minimumOffset) {
         before = m_keyframes.begin();
         after = before + 1;
         ASSERT((*before)->offset() > offset);
         ASSERT((*after)->offset() > offset);
     } else if (offset >= maximumOffset) {
         after = m_keyframes.end() - 1;
         before = after - 1;
         ASSERT((*before)->offset() < offset);
         ASSERT((*after)->offset() <= offset);
     } else {
         // FIXME: This is inefficient for large numbers of keyframes. Consider
         // using binary search.
         after = m_keyframes.begin();
         while ((*after)->offset() <= offset)
             ++after;
         before = after - 1;
         ASSERT((*before)->offset() <= offset);
         ASSERT((*after)->offset() > offset);
     }

     if ((*before)->offset() == offset)
         return const_cast<CompositableValue*>((*before)->value());
     if ((*after)->offset() == offset)
         return const_cast<CompositableValue*>((*after)->value());
     return BlendedCompositableValue::create((*before)->value(), (*after)->value(),
         (offset - (*before)->offset()) / ((*after)->offset() - (*before)->offset()));
 }

 } // namespace
	/*
	* Copyright (C) 2013 Google Inc. All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions are
	* met:
	*
	* * Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* * 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.
	* * Neither the name of Google Inc. nor the names of its
	* contributors may be used to endorse or promote products derived from
	* this software without specific prior written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	* "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 COPYRIGHT
	* OWNER OR CONTRIBUTORS 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.
	*/

	#include "config.h"
	#include "core/animation/KeyframeAnimationEffect.h"

	#include "wtf/MathExtras.h"
	#include "wtf/text/StringHash.h"

	namespace {

	using namespace WebCore;

	class ReplaceCompositableValue : public AnimationEffect::CompositableValue {
	public:
	static PassRefPtr<ReplaceCompositableValue> create(const AnimatableValue* value)
	{
	return adoptRef(new ReplaceCompositableValue(value));
	}
	virtual PassRefPtr<AnimatableValue> compositeOnto(const AnimatableValue* underlyingValue) const
	{
	return PassRefPtr<AnimatableValue>(m_value);
	}
	private:
	ReplaceCompositableValue(const AnimatableValue* value)
	: m_value(const_cast<AnimatableValue*>(value))
	{
	}
	RefPtr<AnimatableValue> m_value;
	};

	class AddCompositableValue : public AnimationEffect::CompositableValue {
	public:
	static PassRefPtr<AddCompositableValue> create(const AnimatableValue* value)
	{
	return adoptRef(new AddCompositableValue(value));
	}
	virtual PassRefPtr<AnimatableValue> compositeOnto(const AnimatableValue* underlyingValue) const
	{
	return AnimatableValue::add(underlyingValue, m_value.get());
	}
	private:
	AddCompositableValue(const AnimatableValue* value)
	: m_value(const_cast<AnimatableValue*>(value))
	{
	}
	RefPtr<AnimatableValue> m_value;
	};

	class BlendedCompositableValue : public AnimationEffect::CompositableValue {
	public:
	static PassRefPtr<BlendedCompositableValue> create(const AnimationEffect::CompositableValue* before, const AnimationEffect::CompositableValue* after, double fraction)
	{
	return adoptRef(new BlendedCompositableValue(before, after, fraction));
	}
	virtual PassRefPtr<AnimatableValue> compositeOnto(const AnimatableValue* underlyingValue) const
	{
	return AnimatableValue::interpolate(m_before->compositeOnto(underlyingValue).get(), m_after->compositeOnto(underlyingValue).get(), m_fraction);
	}
	private:
	BlendedCompositableValue(const AnimationEffect::CompositableValue* before, const AnimationEffect::CompositableValue* after, double fraction)
	: m_before(const_cast<AnimationEffect::CompositableValue*>(before))
	, m_after(const_cast<AnimationEffect::CompositableValue*>(after))
	, m_fraction(fraction)
	{ }
	RefPtr<AnimationEffect::CompositableValue> m_before;
	RefPtr<AnimationEffect::CompositableValue> m_after;
	double m_fraction;
	};

	bool compareOffsets(const RefPtr<Keyframe>& a, const RefPtr<Keyframe>& b)
	{
	return a->offset() < b->offset();
	}

	} // namespace


	namespace WebCore {

	Keyframe::Keyframe()
	: m_offset(std::numeric_limits<double>::quiet_NaN())
	, m_composite(AnimationEffect::CompositeReplace)
	{ }

	void Keyframe::setPropertyValue(CSSPropertyID property, const AnimatableValue* value)
	{
	m_propertyValues.add(property, const_cast<AnimatableValue*>(value));
	}

	const AnimatableValue* Keyframe::propertyValue(CSSPropertyID property) const
	{
	ASSERT(m_propertyValues.contains(property));
	return m_propertyValues.get(property);
	}

	PropertySet Keyframe::properties() const
	{
	// This is only used when setting up the keyframe groups, so there's no
	// need to cache the result.
	PropertySet properties;
	for (PropertyValueMap::const_iterator iter = m_propertyValues.begin(); iter != m_propertyValues.end(); ++iter)
	properties.add(*iter.keys());
	return properties;
	}


	KeyframeAnimationEffect::KeyframeAnimationEffect(const KeyframeVector& keyframes)
	: m_keyframes(keyframes)
	{
	}

	PassOwnPtr<AnimationEffect::CompositableValueMap> KeyframeAnimationEffect::sample(int iteration, double fraction) const
	{
	const_cast<KeyframeAnimationEffect*>(this)->ensureKeyframeGroups();
	OwnPtr<CompositableValueMap> map = adoptPtr(new CompositableValueMap());
	for (KeyframeGroupMap::const_iterator iter = m_keyframeGroups->begin(); iter != m_keyframeGroups->end(); ++iter)
	map->add(iter->key, iter->value->sample(iteration, fraction));
	return map.release();
	}

	KeyframeAnimationEffect::KeyframeVector KeyframeAnimationEffect::normalizedKeyframes() const
	{
	KeyframeVector keyframes = m_keyframes;

	// Set offsets at 0.0 and 1.0 at ends if unset.
	if (keyframes.size() >= 2) {
	Keyframe* firstKeyframe = keyframes.first().get();
	if (std::isnan(firstKeyframe->offset()))
	firstKeyframe->setOffset(0.0);
	}
	if (keyframes.size() >= 1) {
	Keyframe* lastKeyframe = keyframes.last().get();
	if (lastKeyframe && std::isnan(lastKeyframe->offset()))
	lastKeyframe->setOffset(1.0);
	}

	// FIXME: Distribute offsets where missing.
	for (KeyframeVector::iterator iter = keyframes.begin(); iter != keyframes.end(); ++iter)
	ASSERT(!std::isnan((*iter)->offset()));

	// Sort by offset.
	std::stable_sort(keyframes.begin(), keyframes.end(), compareOffsets);
	return keyframes;
	}

	void KeyframeAnimationEffect::ensureKeyframeGroups()
	{
	if (m_keyframeGroups)
	return;

	m_keyframeGroups = adoptPtr(new KeyframeGroupMap);
	const KeyframeVector& keyframes = normalizedKeyframes();
	for (KeyframeVector::const_iterator keyframeIter = keyframes.begin(); keyframeIter != keyframes.end(); ++keyframeIter) {
	const Keyframe* keyframe = keyframeIter->get();
	PropertySet keyframeProperties = keyframe->properties();
	for (PropertySet::const_iterator propertyIter = keyframeProperties.begin(); propertyIter != keyframeProperties.end(); ++propertyIter) {
	CSSPropertyID property = *propertyIter;
	KeyframeGroupMap::iterator groupIter = m_keyframeGroups->find(property);
	if (groupIter == m_keyframeGroups->end()) {
	KeyframeGroupMap::AddResult result = m_keyframeGroups->add(property, adoptPtr(new PropertySpecificKeyframeGroup));
	ASSERT(result.isNewEntry);
	groupIter = result.iterator;
	}
	groupIter->value->appendKeyframe(adoptPtr(
	new PropertySpecificKeyframe(keyframe->offset(), keyframe->propertyValue(property), keyframe->composite())));
	}
	}

	// Add synthetic keyframes.
	for (KeyframeGroupMap::iterator iter = m_keyframeGroups->begin(); iter != m_keyframeGroups->end(); ++iter) {
	iter->value->addSyntheticKeyframeIfRequired();
	iter->value->removeRedundantKeyframes();
	}
	}


	KeyframeAnimationEffect::PropertySpecificKeyframe::PropertySpecificKeyframe(double offset, const AnimatableValue* value, CompositeOperation composite)
	: m_offset(offset)
	, m_value(composite == AnimationEffect::CompositeReplace ?
	static_cast<PassRefPtr<CompositableValue> >(ReplaceCompositableValue::create(value)) :
	static_cast<PassRefPtr<CompositableValue> >(AddCompositableValue::create(value)))
	{
	}

	KeyframeAnimationEffect::PropertySpecificKeyframe::PropertySpecificKeyframe(double offset, PassRefPtr<CompositableValue> value)
	: m_offset(offset)
	, m_value(value)
	{
	ASSERT(!std::isnan(m_offset));
	}

	PassOwnPtr<KeyframeAnimationEffect::PropertySpecificKeyframe> KeyframeAnimationEffect::PropertySpecificKeyframe::cloneWithOffset(double offset) const
	{
	return adoptPtr(new PropertySpecificKeyframe(offset, PassRefPtr<CompositableValue>(m_value)));
	}


	void KeyframeAnimationEffect::PropertySpecificKeyframeGroup::appendKeyframe(PassOwnPtr<PropertySpecificKeyframe> keyframe)
	{
	ASSERT(m_keyframes.isEmpty() \|\| m_keyframes.last()->offset() <= keyframe->offset());
	m_keyframes.append(keyframe);
	}

	void KeyframeAnimationEffect::PropertySpecificKeyframeGroup::removeRedundantKeyframes()
	{
	// As an optimization, removes keyframes in the following categories, as
	// they will never be used by sample().
	// - End keyframes with the same offset as their neighbor
	// - Interior keyframes with the same offset as both their neighbors
	// Note that synthetic keyframes must be added before this method is
	// called.
	ASSERT(m_keyframes.size() >= 2);
	for (int i = m_keyframes.size() - 1; i >= 0; --i) {
	double offset = m_keyframes[i]->offset();
	bool hasSameOffsetAsPreviousNeighbor = !i \|\| m_keyframes[i - 1]->offset() == offset;
	bool hasSameOffsetAsNextNeighbor = i == m_keyframes.size() - 1 \|\| m_keyframes[i + 1]->offset() == offset;
	if (hasSameOffsetAsPreviousNeighbor && hasSameOffsetAsNextNeighbor)
	m_keyframes.remove(i);
	}
	ASSERT(m_keyframes.size() >= 2);
	}

	void KeyframeAnimationEffect::PropertySpecificKeyframeGroup::addSyntheticKeyframeIfRequired()
	{
	ASSERT(!m_keyframes.isEmpty());
	double offset = m_keyframes.first()->offset();
	bool allOffsetsEqual = true;
	for (PropertySpecificKeyframeVector::const_iterator iter = m_keyframes.begin() + 1; iter != m_keyframes.end(); ++iter) {
	if ((*iter)->offset() != offset) {
	allOffsetsEqual = false;
	break;
	}
	}
	if (!allOffsetsEqual)
	return;

	if (!offset)
	appendKeyframe(m_keyframes.first()->cloneWithOffset(1.0));
	else
	m_keyframes.insert(0, adoptPtr(new PropertySpecificKeyframe(0.0, AnimatableValue::neutralValue(), CompositeAdd)));
	}

	PassRefPtr<AnimationEffect::CompositableValue> KeyframeAnimationEffect::PropertySpecificKeyframeGroup::sample(int iteration, double offset) const
	{
	// FIXME: Implement accumulation.
	ASSERT_UNUSED(iteration, !iteration);

	double minimumOffset = m_keyframes.first()->offset();
	double maximumOffset = m_keyframes.last()->offset();
	ASSERT(minimumOffset != maximumOffset);

	PropertySpecificKeyframeVector::const_iterator before;
	PropertySpecificKeyframeVector::const_iterator after;

	// Note that this algorithm is simpler than that in the spec because we
	// have removed keyframes with equal offsets in
	// removeRedundantKeyframes().
	if (offset < minimumOffset) {
	before = m_keyframes.begin();
	after = before + 1;
	ASSERT((*before)->offset() > offset);
	ASSERT((*after)->offset() > offset);
	} else if (offset >= maximumOffset) {
	after = m_keyframes.end() - 1;
	before = after - 1;
	ASSERT((*before)->offset() < offset);
	ASSERT((*after)->offset() <= offset);
	} else {
	// FIXME: This is inefficient for large numbers of keyframes. Consider
	// using binary search.
	after = m_keyframes.begin();
	while ((*after)->offset() <= offset)
	++after;
	before = after - 1;
	ASSERT((*before)->offset() <= offset);
	ASSERT((*after)->offset() > offset);
	}

	if ((*before)->offset() == offset)
	return const_cast<CompositableValue>((before)->value());
	if ((*after)->offset() == offset)
	return const_cast<CompositableValue>((after)->value());
	return BlendedCompositableValue::create((before)->value(), (after)->value(),
	(offset - (before)->offset()) / ((after)->offset() - (*before)->offset()));
	}

	} // namespace