//-----------------------------------------------------------------------------
// Copyright (c) 2012 GarageGames, LLC
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.
//-----------------------------------------------------------------------------

#ifndef _FORESTCELL_H_
#define _FORESTCELL_H_

#ifndef _FORESTITEM_H_
#include "forest/forestItem.h"
#endif
#ifndef _H_FOREST_
#include "forest/forest.h"
#endif
#ifndef _BITVECTOR_H_
#include "core/bitVector.h"
#endif

class ForestCellBatch;
class SceneRenderState;
class Frustum;
class IForestCellCollision;
class PhysicsBody;
//class ForestRayInfo;


///
class ForestCell
{
   friend class Forest;

protected:

   /// The area which this cell represents in the world.
   RectF mRect;

   /// If items have been added or removed the dirty flag
   /// is set so that the bounds can be rebuilt on the next
   /// request.
   bool mIsDirty;

   /// The combined bounding box of all the items 
   /// in or children of this cell.
   Box3F mBounds;

   /// All the items in this cell.
   Vector<ForestItem> mItems;

   /// A vector of the current batches 
   /// associated with this cell.
   Vector<ForestCellBatch*> mBatches;

   /// The largest item in this cell.
   ForestItem mLargestItem;
   
   /// PhysicsBody for client and server for all trees in this ForestCell,
   /// if it is a leaf cell.
   PhysicsBody *mPhysicsRep[2];

   /// The quad tree cells below this one which 
   /// may contain sub elements.
   ForestCell* mSubCells[4];

   /// The zone overlap for this cell.
   /// @note The bit for the outdoor zone is never set.
   BitVector mZoneOverlap;

   /// Whether this cell is fully contained inside interior zones.
   bool mIsInteriorOnly;

   ///
   inline U32 _getSubCell( F32 x, F32 y ) const 
   {
      bool left = x < ( mRect.point.x + ( mRect.extent.x / 2.0f ) );
      bool top = y < ( mRect.point.y + ( mRect.extent.y / 2.0f ) );

      if ( left && top ) return 0;
      if ( left && !top ) return 1;
      if ( !left && top ) return 2;

      return 3;
   }

   ///
   inline RectF _makeChildRect( U32 index ) const 
   {
      RectF rect( mRect.point, mRect.extent / 2.0f );

      if ( index == 1 || index == 3 )
         rect.point.y += rect.extent.y;

      if ( index > 1 )
         rect.point.x += rect.extent.x;

      return rect;
   }

   void _updateBounds();

   ///
   void _updateZoning( const SceneZoneSpaceManager *zoneManager );

public:

   /// The maximum amount of objects allowed in a 
   /// cell before we repartition it.
   static const U32 MaxItems = 200;

   ForestCell( const RectF &rect );
   virtual ~ForestCell();

   /// Returns the 2D rectangle of quad tree bounds for this 
   /// cell.  It is fixed and does not change during runtime.
   const RectF& getRect() const { return mRect; }

   /// The bounds of the cell generated by combining the 
   /// bounds of all the contained items or child cells.
   const Box3F& getBounds() const;

   /// Set flag so this cells bounds will be recalculated the next call to getBounds.
   void invalidateBounds() { mIsDirty = true; }

   /// Returns true if this cell has no items and no child cells.
   bool isEmpty() const { return isLeaf() && mItems.empty(); }

   /// Returns true if this cell does not have child cells.
   /// It should directly contain items.
   bool isLeaf() const { return !mSubCells[0]; }

   /// Returns true if this cell has child cells.
   /// This is the same as !isLeaf() but exists for clarity.
   bool isBranch() const { return mSubCells[0] != NULL; }

   /// Returns a bit vector of what zones overlap this cell.
   const BitVector& getZoneOverlap() const { return mZoneOverlap; }

   ///
   bool castRay( const Point3F &start, const Point3F &end, RayInfo *outInfo, bool rendered ) const;

   bool hasBatches() const { return !mBatches.empty(); }

   void buildBatches();

   void freeBatches();

   S32 renderBatches( SceneRenderState *state, Frustum *culler );


   S32 render( TSRenderState *rdata, const Frustum *culler );


   /// The find function does a binary search thru the sorted
   /// item list.  If the key is found then the index is the 
   /// position of the item. If the key is not found the index
   /// is the correct insertion position for adding the new item.
   ///
   /// @param key The item key to search for.
   ///
   /// @param outIndex  The item index or insertion index if
   ///                  the item was not found.
   ///
   /// @return Returns true if the item index is found.
   ///
   bool findIndexByKey( ForestItemKey key, U32 *outIndex ) const;

   const ForestItem& getLargestItem() const { return mLargestItem; }

   const ForestItem& insertItem( ForestItemKey key,
                                 ForestItemData *data,
                                 const MatrixF &xfm,
                                 F32 scale );

   bool removeItem( ForestItemKey key, const Point3F &keyPos, bool deleteIfEmpty = false );

   /// Returns the child cell at the position.  The position is
   /// assumed to be within this cell.
   ForestCell* getChildAt( const Point3F &pos ) const;

   /// Returns the child cells.
   void getChildren( Vector<ForestCell*> *outCells ) const { outCells->merge( mSubCells, 4 ); }
   void getChildren( Vector<const ForestCell*> *outCells ) const { outCells->merge( mSubCells, 4 ); }

   /// Returns the items from this one cell.
   const Vector<ForestItem>& getItems() const { return mItems; }

   /// Returns the items from this cell and all its sub-cells.
   void getItems( Vector<ForestItem> *outItems ) const;

   void clearPhysicsRep( Forest *forest );
   void buildPhysicsRep( Forest *forest );
};


inline const Box3F& ForestCell::getBounds() const 
{ 
   if ( mIsDirty )
      const_cast<ForestCell*>( this )->_updateBounds(); 

   return mBounds; 
}

inline ForestCell* ForestCell::getChildAt( const Point3F &pos ) const
{
   U32 index = _getSubCell( pos.x, pos.y );
   return mSubCells[index];
}

#endif // _FORESTCELL_H_