<commit_before>/*
 * Copyright (c) Contributors, http://opensimulator.org/
 * See CONTRIBUTORS.TXT for a full list of copyright holders.
 *
 * 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 the OpenSimulator Project 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 DEVELOPERS ``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 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.
 */

using System;
using System.Threading;
using System.Collections.Generic;
using System.Reflection;
using OpenMetaverse;
using OpenMetaverse.Packets;
using log4net;
using OpenSim.Framework;
using OpenSim.Region.Framework.Scenes.Types;
using OpenSim.Region.Physics.Manager;
using OpenSim.Region.Framework.Interfaces;

namespace OpenSim.Region.Framework.Scenes
{
    public delegate void PhysicsCrash();

    public delegate void AttachToBackupDelegate(SceneObjectGroup sog);

    public delegate void DetachFromBackupDelegate(SceneObjectGroup sog);

    public delegate void ChangedBackupDelegate(SceneObjectGroup sog);

    /// <summary>
    /// This class used to be called InnerScene and may not yet truly be a SceneGraph.  The non scene graph components
    /// should be migrated out over time.
    /// </summary>
    public class SceneGraph
    {
        private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);

        #region Events

        protected internal event PhysicsCrash UnRecoverableError;
        private PhysicsCrash handlerPhysicsCrash = null;

        public event AttachToBackupDelegate OnAttachToBackup;
        public event DetachFromBackupDelegate OnDetachFromBackup;
        public event ChangedBackupDelegate OnChangeBackup;

        #endregion

        #region Fields

        protected OpenMetaverse.ReaderWriterLockSlim m_scenePresencesLock = new OpenMetaverse.ReaderWriterLockSlim();
        protected Dictionary<UUID, ScenePresence> m_scenePresenceMap = new Dictionary<UUID, ScenePresence>();
        protected List<ScenePresence> m_scenePresenceArray = new List<ScenePresence>();

        protected internal EntityManager Entities = new EntityManager();

        protected Scene m_parentScene;
        protected Dictionary<UUID, SceneObjectGroup> m_updateList = new Dictionary<UUID, SceneObjectGroup>();
        protected int m_numRootAgents = 0;
        protected int m_numPrim = 0;
        protected int m_numChildAgents = 0;
        protected int m_physicalPrim = 0;

        protected int m_activeScripts = 0;
        protected int m_scriptLPS = 0;

        protected internal PhysicsScene _PhyScene;
        
        /// <summary>
        /// Index the SceneObjectGroup for each part by the root part's UUID.
        /// </summary>
        protected internal Dictionary<UUID, SceneObjectGroup> SceneObjectGroupsByFullID = new Dictionary<UUID, SceneObjectGroup>();
        
        /// <summary>
        /// Index the SceneObjectGroup for each part by that part's UUID.
        /// </summary>
        protected internal Dictionary<UUID, SceneObjectGroup> SceneObjectGroupsByFullPartID = new Dictionary<UUID, SceneObjectGroup>();
        
        /// <summary>
        /// Index the SceneObjectGroup for each part by that part's local ID.
        /// </summary>
        protected internal Dictionary<uint, SceneObjectGroup> SceneObjectGroupsByLocalPartID = new Dictionary<uint, SceneObjectGroup>();        

        /// <summary>
        /// Lock to prevent object group update, linking, delinking and duplication operations from running concurrently.
        /// </summary>
        /// <remarks>
        /// These operations rely on the parts composition of the object.  If allowed to run concurrently then race
        /// conditions can occur.
        /// </remarks>
        private Object m_updateLock = new Object();

        #endregion

        protected internal SceneGraph(Scene parent)
        {
            m_parentScene = parent;
        }

        public PhysicsScene PhysicsScene
        {
            get { return _PhyScene; }
            set
            {
                // If we're not doing the initial set
                // Then we've got to remove the previous
                // event handler
                if (_PhyScene != null)
                    _PhyScene.OnPhysicsCrash -= physicsBasedCrash;

                _PhyScene = value;

                if (_PhyScene != null)
                    _PhyScene.OnPhysicsCrash += physicsBasedCrash;
            }
        }

        protected internal void Close()
        {
            m_scenePresencesLock.EnterWriteLock();
            try
            {
                Dictionary<UUID, ScenePresence> newmap = new Dictionary<UUID, ScenePresence>();
                List<ScenePresence> newlist = new List<ScenePresence>();
                m_scenePresenceMap = newmap;
                m_scenePresenceArray = newlist;
            }
            finally
            {
                m_scenePresencesLock.ExitWriteLock();
            }

            lock (SceneObjectGroupsByFullID)
                SceneObjectGroupsByFullID.Clear();
            lock (SceneObjectGroupsByFullPartID)
                SceneObjectGroupsByFullPartID.Clear();
            lock (SceneObjectGroupsByLocalPartID)
                SceneObjectGroupsByLocalPartID.Clear();

            Entities.Clear();
        }

        #region Update Methods

        protected internal void UpdatePreparePhysics()
        {
            // If we are using a threaded physics engine
            // grab the latest scene from the engine before
            // trying to process it.

            // PhysX does this (runs in the background).

            if (_PhyScene.IsThreaded)
            {
                _PhyScene.GetResults();
            }
        }

        /// <summary>
        /// Update the position of all the scene presences.
        /// </summary>
        /// <remarks>
        /// Called only from the main scene loop.
        /// </remarks>
        protected internal void UpdatePresences()
        {
            ForEachScenePresence(delegate(ScenePresence presence)
            {
                presence.Update();
            });
        }

        /// <summary>
        /// Perform a physics frame update.
        /// </summary>
        /// <param name="elapsed"></param>
        /// <returns></returns>
        protected internal float UpdatePhysics(double elapsed)
        {
            // Here is where the Scene calls the PhysicsScene. This is a one-way
            // interaction; the PhysicsScene cannot access the calling Scene directly.
            // But with joints, we want a PhysicsActor to be able to influence a
            // non-physics SceneObjectPart. In particular, a PhysicsActor that is connected
            // with a joint should be able to move the SceneObjectPart which is the visual
            // representation of that joint (for editing and serialization purposes).
            // However the PhysicsActor normally cannot directly influence anything outside
            // of the PhysicsScene, and the non-physical SceneObjectPart which represents
            // the joint in the Scene does not exist in the PhysicsScene.
            //
            // To solve this, we have an event in the PhysicsScene that is fired when a joint
            // has changed position (because one of its associated PhysicsActors has changed 
            // position).
            //
            // Therefore, JointMoved and JointDeactivated events will be fired as a result of the following Simulate().
            return _PhyScene.Simulate((float)elapsed);
        }

        protected internal void UpdateScenePresenceMovement()
        {
            ForEachScenePresence(delegate(ScenePresence presence)
            {
                presence.UpdateMovement();
            });
        }

        public void GetCoarseLocations(out List<Vector3> coarseLocations, out List<UUID> avatarUUIDs, uint maxLocations)
        {
            coarseLocations = new List<Vector3>();
            avatarUUIDs = new List<UUID>();

            List<ScenePresence> presences = GetScenePresences();
            for (int i = 0; i < Math.Min(presences.Count, maxLocations); ++i)
            {
                ScenePresence sp = presences[i];
                
                // If this presence is a child agent, we don't want its coarse locations
                if (sp.IsChildAgent)
                    continue;

                coarseLocations.Add(sp.AbsolutePosition);

                avatarUUIDs.Add(sp.UUID);
            }
        }

        #endregion

        #region Entity Methods

        /// <summary>
        /// Add an object into the scene that has come from storage
        /// </summary>
        /// <param name="sceneObject"></param>
        /// <param name="attachToBackup">
        /// If true, changes to the object will be reflected in its persisted data
        /// If false, the persisted data will not be changed even if the object in the scene is changed
        /// </param>
        /// <param name="alreadyPersisted">
        /// If true, we won't persist this object until it changes
        /// If false, we'll persist this object immediately
        /// </param>
        /// <param name="sendClientUpdates">
        /// If true, we send updates to the client to tell it about this object
        /// If false, we leave it up to the caller to do this
        /// </param>
        /// <returns>
        /// true if the object was added, false if an object with the same uuid was already in the scene
        /// </returns>
        protected internal bool AddRestoredSceneObject(
            SceneObjectGroup sceneObject, bool attachToBackup, bool alreadyPersisted, bool sendClientUpdates)
        {
            if (!m_parentScene.CombineRegions)
            {
                // KF: Check for out-of-region, move inside and make static.
                Vector3 npos = new Vector3(sceneObject.RootPart.GroupPosition.X,
                                           sceneObject.RootPart.GroupPosition.Y,
                                           sceneObject.RootPart.GroupPosition.Z);
                if (!(((sceneObject.RootPart.Shape.PCode == (byte)PCode.Prim) && (sceneObject.RootPart.Shape.State != 0))) && (npos.X < 0.0 || npos.Y < 0.0 || npos.Z < 0.0 ||
                    npos.X > Constants.RegionSize ||
                    npos.Y > Constants.RegionSize))
                {
                    if (npos.X < 0.0) npos.X = 1.0f;
                    if (npos.Y < 0.0) npos.Y = 1.0f;
                    if (npos.Z < 0.0) npos.Z = 0.0f;
                    if (npos.X > Constants.RegionSize) npos.X = Constants.RegionSize - 1.0f;
                    if (npos.Y > Constants.RegionSize) npos.Y = Constants.RegionSize - 1.0f;
     
                    foreach (SceneObjectPart part in sceneObject.Parts)
                    {
                        part.GroupPosition = npos;
                    }
                    sceneObject.RootPart.Velocity = Vector3.Zero;
                    sceneObject.RootPart.AngularVelocity = Vector3.Zero;
                    sceneObject.RootPart.Acceleration = Vector3.Zero;
                    sceneObject.RootPart.Velocity = Vector3.Zero;
                }
            }

            bool ret = AddSceneObject(sceneObject, attachToBackup, sendClientUpdates);

            if (attachToBackup && (!alreadyPersisted))
            {
                sceneObject.ForceInventoryPersistence();
                sceneObject.HasGroupChanged = true;
            }

            return ret;
        }
                
        /// <summary>
        /// Add a newly created object to the scene.  This will both update the scene, and send information about the
        /// new object to all clients interested in the scene.
        /// </summary>
        /// <param name="sceneObject"></param>
        /// <param name="attachToBackup">
        /// If true, the object is made persistent into the scene.
        /// If false, the object will not persist over server restarts
        /// </param>
        /// <returns>
        /// true if the object was added, false if an object with the same uuid was already in the scene
        /// </returns>
        protected internal bool AddNewSceneObject(SceneObjectGroup sceneObject, bool attachToBackup, bool sendClientUpdates)
        {
 

            bool ret = AddSceneObject(sceneObject, attachToBackup, sendClientUpdates);

           // Ensure that we persist this new scene object if it's not an
            // attachment

            if (attachToBackup)
                sceneObject.HasGroupChanged = true;

            return ret;
        }
        
        /// <summary>
        /// Add a newly created object to the scene.
        /// </summary>
        /// 
        /// This method does not send updates to the client - callers need to handle this themselves.
        /// Caller should also trigger EventManager.TriggerObjectAddedToScene
        /// <param name="sceneObject"></param>
        /// <param name="attachToBackup"></param>
        /// <param name="pos">Position of the object.  If null then the position stored in the object is used.</param>
        /// <param name="rot">Rotation of the object.  If null then the rotation stored in the object is used.</param>
        /// <param name="vel">Velocity of the object.  This parameter only has an effect if the object is physical</param>
        /// <returns></returns>
        public bool AddNewSceneObject(
            SceneObjectGroup sceneObject, bool attachToBackup, Vector3? pos, Quaternion? rot, Vector3 vel)
        {
            AddNewSceneObject(sceneObject, attachToBackup, false);

            if (pos != null)
                sceneObject.AbsolutePosition = (Vector3)pos;

            if (sceneObject.RootPart.Shape.PCode == (byte)PCode.Prim)
            {
                sceneObject.ClearPartAttachmentData();
            }

            if (rot != null)
                sceneObject.UpdateGroupRotationR((Quaternion)rot);

            PhysicsActor pa = sceneObject.RootPart.PhysActor;
            if (pa != null && pa.IsPhysical && vel != Vector3.Zero)
            {
                sceneObject.RootPart.ApplyImpulse((vel * sceneObject.GetMass()), false);
            }

            return true;
        }

        /// <summary>
        /// Add an object to the scene.  This will both update the scene, and send information about the
        /// new object to all clients interested in the scene.
        /// </summary>
        /// <remarks>
        /// The object's stored position, rotation and velocity are used.
        /// </remarks>
        /// <param name="sceneObject"></param>
        /// <param name="attachToBackup">
        /// If true, the object is made persistent into the scene.
        /// If false, the object will not persist over server restarts
        /// </param>
        /// <param name="sendClientUpdates">
        /// If true, updates for the new scene object are sent to all viewers in range.
        /// If false, it is left to the caller to schedule the update
        /// </param>
        /// <returns>
        /// true if the object was added, false if an object with the same uuid was already in the scene
        /// </returns>
        protected bool AddSceneObject(SceneObjectGroup sceneObject, bool attachToBackup, bool sendClientUpdates)
        {
            if (sceneObject == null)
            {
                m_log.ErrorFormat("[SCENEGRAPH]: Tried to add null scene object");
                return false;
            }
            if (sceneObject.UUID == UUID.Zero)
            {
                m_log.ErrorFormat(
                    "[SCENEGRAPH]: Tried to add scene object {0} to {1} with illegal UUID of {2}",
                    sceneObject.Name, m_parentScene.RegionInfo.RegionName, UUID.Zero);

                return false;
            }

            if (Entities.ContainsKey(sceneObject.UUID))
            {
                m_log.DebugFormat(
                    "[SCENEGRAPH]: Scene graph for {0} already contains object {1} in AddSceneObject()",
                    m_parentScene.RegionInfo.RegionName, sceneObject.UUID);

                return false;
            }

//            m_log.DebugFormat(
//                "[SCENEGRAPH]: Adding scene object {0} {1}, with {2} parts on {3}",
//                sceneObject.Name, sceneObject.UUID, sceneObject.Parts.Length, m_parentScene.RegionInfo.RegionName);

            SceneObjectPart[] parts = sceneObject.Parts;

            // Clamp child prim sizes and add child prims to the m_numPrim count
            if (m_parentScene.m_clampPrimSize)
            {
                foreach (SceneObjectPart part in parts)
                {
                    Vector3 scale = part.Shape.Scale;

                    scale.X = Math.Max(m_parentScene.m_minNonphys, Math.Min(m_parentScene.m_maxNonphys, scale.X));
                    scale.Y = Math.Max(m_parentScene.m_minNonphys, Math.Min(m_parentScene.m_maxNonphys, scale.Y));
                    scale.Z = Math.Max(m_parentScene.m_minNonphys, Math.Min(m_parentScene.m_maxNonphys, scale.Z));

                    part.Shape.Scale = scale;
                }
            }
            m_numPrim += parts.Length;

            sceneObject.AttachToScene(m_parentScene);


            Entities.Add(sceneObject);


            lock (SceneObjectGroupsByFullID)
                SceneObjectGroupsByFullID[sceneObject.UUID] = sceneObject;

            lock (SceneObjectGroupsByFullPartID)
            {
                foreach (SceneObjectPart part in parts)
                    SceneObjectGroupsByFullPartID[part.UUID] = sceneObject;
            }

            lock (SceneObjectGroupsByLocalPartID)
            {
//                m_log.DebugFormat(
//                    "[SCENE GRAPH]: Adding scene object {0} {1} {2} to SceneObjectGroupsByLocalPartID in {3}",
//                    sceneObject.Name, sceneObject.UUID, sceneObject.LocalId, m_parentScene.RegionInfo.RegionName);

                foreach (SceneObjectPart part in parts)
                    SceneObjectGroupsByLocalPartID[part.LocalId] = sceneObject;
            }

            if (sendClientUpdates)
                sceneObject.ScheduleGroupForFullUpdate();

            if (attachToBackup)
                sceneObject.AttachToBackup();

            return true;
        }

        public void updateScenePartGroup(SceneObjectPart part, SceneObjectGroup grp)
        {
            // no tests, caller has responsability...
            lock (SceneObjectGroupsByFullPartID)
            {
                    SceneObjectGroupsByFullPartID[part.UUID] = grp;
            }

            lock (SceneObjectGroupsByLocalPartID)
            {
                    SceneObjectGroupsByLocalPartID[part.LocalId] = grp;
            }
        }

        /// <summary>
        /// Delete an object from the scene
        /// </summary>
        /// <returns>true if the object was deleted, false if there was no object to delete</returns>
        public bool DeleteSceneObject(UUID uuid, bool resultOfObjectLinked)
        {
//            m_log.DebugFormat(
//                "[SCENE GRAPH]: Deleting scene object with uuid {0}, resultOfObjectLinked = {1}",
//                uuid, resultOfObjectLinked);

            EntityBase entity;
            if (!Entities.TryGetValue(uuid, out entity) || (!(entity is SceneObjectGroup)))
                return false;

            SceneObjectGroup grp = (SceneObjectGroup)entity;

            if (entity == null)
                return false;

            if (!resultOfObjectLinked)
            {
                m_numPrim -= grp.PrimCount;

                if ((grp.RootPart.Flags & PrimFlags.Physics) == PrimFlags.Physics)
                    RemovePhysicalPrim(grp.PrimCount);
            }
            
            lock (SceneObjectGroupsByFullID)
                SceneObjectGroupsByFullID.Remove(grp.UUID);

            lock (SceneObjectGroupsByFullPartID)
            {
                SceneObjectPart[] parts = grp.Parts;
                for (int i = 0; i < parts.Length; i++)
                    SceneObjectGroupsByFullPartID.Remove(parts[i].UUID);
            }

            lock (SceneObjectGroupsByLocalPartID)
            {
                SceneObjectPart[] parts = grp.Parts;
                for (int i = 0; i < parts.Length; i++)
                    SceneObjectGroupsByLocalPartID.Remove(parts[i].LocalId);
            }

            return Entities.Remove(uuid);
        }

        /// <summary>
        /// Add an object to the list of prims to process on the next update
        /// </summary>
        /// <param name="obj">
        /// A <see cref="SceneObjectGroup"/>
        /// </param>
        protected internal void AddToUpdateList(SceneObjectGroup obj)
        {
            lock (m_updateList)
                m_updateList[obj.UUID] = obj;
        }

        public void FireAttachToBackup(SceneObjectGroup obj)
        {
            if (OnAttachToBackup != null)
            {
                OnAttachToBackup(obj);
            }
        }

        public void FireDetachFromBackup(SceneObjectGroup obj)
        {
            if (OnDetachFromBackup != null)
            {
                OnDetachFromBackup(obj);
            }
        }

        public void FireChangeBackup(SceneObjectGroup obj)
        {
            if (OnChangeBackup != null)
            {
                OnChangeBackup(obj);
            }
        }

        /// <summary>
        /// Process all pending updates
        /// </summary>
        protected internal void UpdateObjectGroups()
        {
            if (!Monitor.TryEnter(m_updateLock))
                return;
            try
            {
                List<SceneObjectGroup> updates;

                // Some updates add more updates to the updateList. 
                // Get the current list of updates and clear the list before iterating
                lock (m_updateList)
                {
                    updates = new List<SceneObjectGroup>(m_updateList.Values);
                    m_updateList.Clear();
                }

                // Go through all updates
                for (int i = 0; i < updates.Count; i++)
                {
                    SceneObjectGroup sog = updates[i];

                    // Don't abort the whole update if one entity happens to give us an exception.
                    try
                    {
                        sog.Update();
                    }
                    catch (Exception e)
                    {
                        m_log.ErrorFormat(
                            "[INNER SCENE]: Failed to update {0}, {1} - {2}", sog.Name, sog.UUID, e);
                    }
                }
            }
            finally
            {
                Monitor.Exit(m_updateLock);
            }
        }

        protected internal void AddPhysicalPrim(int number)
        {
            m_physicalPrim += number;
        }

        protected internal void RemovePhysicalPrim(int number)
        {
            m_physicalPrim -= number;
        }

        protected internal void AddToScriptLPS(int number)
        {
            m_scriptLPS += number;
        }

        protected internal void AddActiveScripts(int number)
        {
            m_activeScripts += number;
        }

        protected internal void HandleUndo(IClientAPI remoteClient, UUID primId)
        {
            if (primId != UUID.Zero)
            {
                SceneObjectPart part =  m_parentScene.GetSceneObjectPart(primId);
                if (part != null)
                    part.Undo();
            }
        }

        protected internal void HandleRedo(IClientAPI remoteClient, UUID primId)
        {
            if (primId != UUID.Zero)
            {
                SceneObjectPart part = m_parentScene.GetSceneObjectPart(primId);

                if (part != null)
                    part.Redo();
            }
        }

        protected internal ScenePresence CreateAndAddChildScenePresence(
            IClientAPI client, AvatarAppearance appearance, PresenceType type)
        {
            // ScenePresence always defaults to child agent
            ScenePresence presence = new ScenePresence(client, m_parentScene, appearance, type);

            Entities[presence.UUID] = presence;

            m_scenePresencesLock.EnterWriteLock();
            try
            {
                m_numChildAgents++;

                Dictionary<UUID, ScenePresence> newmap = new Dictionary<UUID, ScenePresence>(m_scenePresenceMap);
                List<ScenePresence> newlist = new List<ScenePresence>(m_scenePresenceArray);

                if (!newmap.ContainsKey(presence.UUID))
                {
                    newmap.Add(presence.UUID, presence);
                    newlist.Add(presence);
                }
                else
                {
                    // Remember the old presence reference from the dictionary
                    ScenePresence oldref = newmap[presence.UUID];
                    // Replace the presence reference in the dictionary with the new value
                    newmap[presence.UUID] = presence;
                    // Find the index in the list where the old ref was stored and update the reference
                    newlist[newlist.IndexOf(oldref)] = presence;
                }

                // Swap out the dictionary and list with new references
                m_scenePresenceMap = newmap;
                m_scenePresenceArray = newlist;
            }
            finally
            {
                m_scenePresencesLock.ExitWriteLock();
            }

            return presence;
        }

        /// <summary>
        /// Remove a presence from the scene
        /// </summary>
        protected internal void RemoveScenePresence(UUID agentID)
        {
            if (!Entities.Remove(agentID))
            {
                m_log.WarnFormat(
                    "[SCENE GRAPH]: Tried to remove non-existent scene presence with agent ID {0} from scene Entities list",
                    agentID);
            }

            m_scenePresencesLock.EnterWriteLock();
            try
            {
                Dictionary<UUID, ScenePresence> newmap = new Dictionary<UUID, ScenePresence>(m_scenePresenceMap);
                List<ScenePresence> newlist = new List<ScenePresence>(m_scenePresenceArray);
                
                // Remove the presence reference from the dictionary
                if (newmap.ContainsKey(agentID))
                {
                    ScenePresence oldref = newmap[agentID];
                    newmap.Remove(agentID);

                    // Find the index in the list where the old ref was stored and remove the reference
                    newlist.RemoveAt(newlist.IndexOf(oldref));
                    // Swap out the dictionary and list with new references
                    m_scenePresenceMap = newmap;
                    m_scenePresenceArray = newlist;
                }
                else
                {
                    m_log.WarnFormat("[SCENE GRAPH]: Tried to remove non-existent scene presence with agent ID {0} from scene ScenePresences list", agentID);
                }
            }
            finally
            {
                m_scenePresencesLock.ExitWriteLock();
            }
        }

        protected internal void SwapRootChildAgent(bool direction_RC_CR_T_F)
        {
            if (direction_RC_CR_T_F)
            {
                m_numRootAgents--;
                m_numChildAgents++;
            }
            else
            {
                m_numChildAgents--;
                m_numRootAgents++;
            }
        }

        public void removeUserCount(bool TypeRCTF)
        {
            if (TypeRCTF)
            {
                m_numRootAgents--;
            }
            else
            {
                m_numChildAgents--;
            }
        }

        public void RecalculateStats()
        {
            int rootcount = 0;
            int childcount = 0;

            ForEachScenePresence(delegate(ScenePresence presence)
            {
                if (presence.IsChildAgent)
                    ++childcount;
                else
                    ++rootcount;
            });

            m_numRootAgents = rootcount;
            m_numChildAgents = childcount;
        }

        public int GetChildAgentCount()
        {
            return m_numChildAgents;
        }

        public int GetRootAgentCount()
        {
            return m_numRootAgents;
        }

        public int GetTotalObjectsCount()
        {
            return m_numPrim;
        }

        public int GetActiveObjectsCount()
        {
            return m_physicalPrim;
        }

        public int GetActiveScriptsCount()
        {
            return m_activeScripts;
        }

        public int GetScriptLPS()
        {
            int returnval = m_scriptLPS;
            m_scriptLPS = 0;
            return returnval;
        }

        #endregion

        #region Get Methods
        
        /// <summary>
        /// Get the controlling client for the given avatar, if there is one.
        ///
        /// FIXME: The only user of the method right now is Caps.cs, in order to resolve a client API since it can't
        /// use the ScenePresence.  This could be better solved in a number of ways - we could establish an
        /// OpenSim.Framework.IScenePresence, or move the caps code into a region package (which might be the more
        /// suitable solution).
        /// </summary>
        /// <param name="agentId"></param>
        /// <returns>null if either the avatar wasn't in the scene, or
        /// they do not have a controlling client</returns>
        /// <remarks>this used to be protected internal, but that
        /// prevents CapabilitiesModule from accessing it</remarks>
        public IClientAPI GetControllingClient(UUID agentId)
        {
            ScenePresence presence = GetScenePresence(agentId);

            if (presence != null)
            {
                return presence.ControllingClient;
            }

            return null;
        }

        /// <summary>
        /// Get a reference to the scene presence list. Changes to the list will be done in a copy
        /// There is no guarantee that presences will remain in the scene after the list is returned.
        /// This list should remain private to SceneGraph. Callers wishing to iterate should instead
        /// pass a delegate to ForEachScenePresence.
        /// </summary>
        /// <returns></returns>
        protected internal List<ScenePresence> GetScenePresences()
        {
            return m_scenePresenceArray;
        }

        /// <summary>
        /// Request a scene presence by UUID. Fast, indexed lookup.
        /// </summary>
        /// <param name="agentID"></param>
        /// <returns>null if the presence was not found</returns>
        protected internal ScenePresence GetScenePresence(UUID agentID)
        {
            Dictionary<UUID, ScenePresence> presences = m_scenePresenceMap;
            ScenePresence presence;
            presences.TryGetValue(agentID, out presence);
            return presence;
        }

        /// <summary>
        /// Request the scene presence by name.
        /// </summary>
        /// <param name="firstName"></param>
        /// <param name="lastName"></param>
        /// <returns>null if the presence was not found</returns>
        protected internal ScenePresence GetScenePresence(string firstName, string lastName)
        {
            List<ScenePresence> presences = GetScenePresences();
            foreach (ScenePresence presence in presences)
            {
                if (presence.Firstname == firstName && presence.Lastname == lastName)
                    return presence;
            }
            return null;
        }

        /// <summary>
        /// Request the scene presence by localID.
        /// </summary>
        /// <param name="localID"></param>
        /// <returns>null if the presence was not found</returns>
        protected internal ScenePresence GetScenePresence(uint localID)
        {
            List<ScenePresence> presences = GetScenePresences();
            foreach (ScenePresence presence in presences)
                if (presence.LocalId == localID)
                    return presence;
            return null;
        }

        protected internal bool TryGetScenePresence(UUID agentID, out ScenePresence avatar)
        {
            Dictionary<UUID, ScenePresence> presences = m_scenePresenceMap;
            presences.TryGetValue(agentID, out avatar);
            return (avatar != null);
        }

        protected internal bool TryGetAvatarByName(string name, out ScenePresence avatar)
        {
            avatar = null;
            foreach (ScenePresence presence in GetScenePresences())
            {
                if (String.Compare(name, presence.ControllingClient.Name, true) == 0)
                {
                    avatar = presence;
                    break;
                }
            }
            return (avatar != null);
        }

        /// <summary>
        /// Get a scene object group that contains the prim with the given local id
        /// </summary>
        /// <param name="localID"></param>
        /// <returns>null if no scene object group containing that prim is found</returns>
        public SceneObjectGroup GetGroupByPrim(uint localID)
        {
            EntityBase entity;
            if (Entities.TryGetValue(localID, out entity))
                return entity as SceneObjectGroup;

//            m_log.DebugFormat("[SCENE GRAPH]: Entered GetGroupByPrim with localID {0}", localID);

            SceneObjectGroup sog;
            lock (SceneObjectGroupsByLocalPartID)
                SceneObjectGroupsByLocalPartID.TryGetValue(localID, out sog);

            if (sog != null)
            {
                if (sog.ContainsPart(localID))
                {
//                    m_log.DebugFormat(
//                        "[SCENE GRAPH]: Found scene object {0} {1} {2} containing part with local id {3} in {4}.  Returning.",
//                        sog.Name, sog.UUID, sog.LocalId, localID, m_parentScene.RegionInfo.RegionName);

                    return sog;
                }
                else
                {
                    lock (SceneObjectGroupsByLocalPartID)
                    {
                        m_log.WarnFormat(
                            "[SCENE GRAPH]: Found scene object {0} {1} {2} via SceneObjectGroupsByLocalPartID index but it doesn't contain part with local id {3}.  Removing from entry from index in {4}.",
                            sog.Name, sog.UUID, sog.LocalId, localID, m_parentScene.RegionInfo.RegionName);

                        SceneObjectGroupsByLocalPartID.Remove(localID);
                    }
                }
            }

            EntityBase[] entityList = GetEntities();
            foreach (EntityBase ent in entityList)
            {
                //m_log.DebugFormat("Looking at entity {0}", ent.UUID);
                if (ent is SceneObjectGroup)<commit_msg>debug show stack trace<commit_after>/*
 * Copyright (c) Contributors, http://opensimulator.org/
 * See CONTRIBUTORS.TXT for a full list of copyright holders.
 *
 * 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 the OpenSimulator Project 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 DEVELOPERS ``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 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.
 */

using System;
using System.Threading;
using System.Collections.Generic;
using System.Reflection;
using OpenMetaverse;
using OpenMetaverse.Packets;
using log4net;
using OpenSim.Framework;
using OpenSim.Region.Framework.Scenes.Types;
using OpenSim.Region.Physics.Manager;
using OpenSim.Region.Framework.Interfaces;

namespace OpenSim.Region.Framework.Scenes
{
    public delegate void PhysicsCrash();

    public delegate void AttachToBackupDelegate(SceneObjectGroup sog);

    public delegate void DetachFromBackupDelegate(SceneObjectGroup sog);

    public delegate void ChangedBackupDelegate(SceneObjectGroup sog);

    /// <summary>
    /// This class used to be called InnerScene and may not yet truly be a SceneGraph.  The non scene graph components
    /// should be migrated out over time.
    /// </summary>
    public class SceneGraph
    {
        private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);

        #region Events

        protected internal event PhysicsCrash UnRecoverableError;
        private PhysicsCrash handlerPhysicsCrash = null;

        public event AttachToBackupDelegate OnAttachToBackup;
        public event DetachFromBackupDelegate OnDetachFromBackup;
        public event ChangedBackupDelegate OnChangeBackup;

        #endregion

        #region Fields

        protected OpenMetaverse.ReaderWriterLockSlim m_scenePresencesLock = new OpenMetaverse.ReaderWriterLockSlim();
        protected Dictionary<UUID, ScenePresence> m_scenePresenceMap = new Dictionary<UUID, ScenePresence>();
        protected List<ScenePresence> m_scenePresenceArray = new List<ScenePresence>();

        protected internal EntityManager Entities = new EntityManager();

        protected Scene m_parentScene;
        protected Dictionary<UUID, SceneObjectGroup> m_updateList = new Dictionary<UUID, SceneObjectGroup>();
        protected int m_numRootAgents = 0;
        protected int m_numPrim = 0;
        protected int m_numChildAgents = 0;
        protected int m_physicalPrim = 0;

        protected int m_activeScripts = 0;
        protected int m_scriptLPS = 0;

        protected internal PhysicsScene _PhyScene;
        
        /// <summary>
        /// Index the SceneObjectGroup for each part by the root part's UUID.
        /// </summary>
        protected internal Dictionary<UUID, SceneObjectGroup> SceneObjectGroupsByFullID = new Dictionary<UUID, SceneObjectGroup>();
        
        /// <summary>
        /// Index the SceneObjectGroup for each part by that part's UUID.
        /// </summary>
        protected internal Dictionary<UUID, SceneObjectGroup> SceneObjectGroupsByFullPartID = new Dictionary<UUID, SceneObjectGroup>();
        
        /// <summary>
        /// Index the SceneObjectGroup for each part by that part's local ID.
        /// </summary>
        protected internal Dictionary<uint, SceneObjectGroup> SceneObjectGroupsByLocalPartID = new Dictionary<uint, SceneObjectGroup>();        

        /// <summary>
        /// Lock to prevent object group update, linking, delinking and duplication operations from running concurrently.
        /// </summary>
        /// <remarks>
        /// These operations rely on the parts composition of the object.  If allowed to run concurrently then race
        /// conditions can occur.
        /// </remarks>
        private Object m_updateLock = new Object();

        #endregion

        protected internal SceneGraph(Scene parent)
        {
            m_parentScene = parent;
        }

        public PhysicsScene PhysicsScene
        {
            get { return _PhyScene; }
            set
            {
                // If we're not doing the initial set
                // Then we've got to remove the previous
                // event handler
                if (_PhyScene != null)
                    _PhyScene.OnPhysicsCrash -= physicsBasedCrash;

                _PhyScene = value;

                if (_PhyScene != null)
                    _PhyScene.OnPhysicsCrash += physicsBasedCrash;
            }
        }

        protected internal void Close()
        {
            m_scenePresencesLock.EnterWriteLock();
            try
            {
                Dictionary<UUID, ScenePresence> newmap = new Dictionary<UUID, ScenePresence>();
                List<ScenePresence> newlist = new List<ScenePresence>();
                m_scenePresenceMap = newmap;
                m_scenePresenceArray = newlist;
            }
            finally
            {
                m_scenePresencesLock.ExitWriteLock();
            }

            lock (SceneObjectGroupsByFullID)
                SceneObjectGroupsByFullID.Clear();
            lock (SceneObjectGroupsByFullPartID)
                SceneObjectGroupsByFullPartID.Clear();
            lock (SceneObjectGroupsByLocalPartID)
                SceneObjectGroupsByLocalPartID.Clear();

            Entities.Clear();
        }

        #region Update Methods

        protected internal void UpdatePreparePhysics()
        {
            // If we are using a threaded physics engine
            // grab the latest scene from the engine before
            // trying to process it.

            // PhysX does this (runs in the background).

            if (_PhyScene.IsThreaded)
            {
                _PhyScene.GetResults();
            }
        }

        /// <summary>
        /// Update the position of all the scene presences.
        /// </summary>
        /// <remarks>
        /// Called only from the main scene loop.
        /// </remarks>
        protected internal void UpdatePresences()
        {
            ForEachScenePresence(delegate(ScenePresence presence)
            {
                presence.Update();
            });
        }

        /// <summary>
        /// Perform a physics frame update.
        /// </summary>
        /// <param name="elapsed"></param>
        /// <returns></returns>
        protected internal float UpdatePhysics(double elapsed)
        {
            // Here is where the Scene calls the PhysicsScene. This is a one-way
            // interaction; the PhysicsScene cannot access the calling Scene directly.
            // But with joints, we want a PhysicsActor to be able to influence a
            // non-physics SceneObjectPart. In particular, a PhysicsActor that is connected
            // with a joint should be able to move the SceneObjectPart which is the visual
            // representation of that joint (for editing and serialization purposes).
            // However the PhysicsActor normally cannot directly influence anything outside
            // of the PhysicsScene, and the non-physical SceneObjectPart which represents
            // the joint in the Scene does not exist in the PhysicsScene.
            //
            // To solve this, we have an event in the PhysicsScene that is fired when a joint
            // has changed position (because one of its associated PhysicsActors has changed 
            // position).
            //
            // Therefore, JointMoved and JointDeactivated events will be fired as a result of the following Simulate().
            return _PhyScene.Simulate((float)elapsed);
        }

        protected internal void UpdateScenePresenceMovement()
        {
            ForEachScenePresence(delegate(ScenePresence presence)
            {
                presence.UpdateMovement();
            });
        }

        public void GetCoarseLocations(out List<Vector3> coarseLocations, out List<UUID> avatarUUIDs, uint maxLocations)
        {
            coarseLocations = new List<Vector3>();
            avatarUUIDs = new List<UUID>();

            List<ScenePresence> presences = GetScenePresences();
            for (int i = 0; i < Math.Min(presences.Count, maxLocations); ++i)
            {
                ScenePresence sp = presences[i];
                
                // If this presence is a child agent, we don't want its coarse locations
                if (sp.IsChildAgent)
                    continue;

                coarseLocations.Add(sp.AbsolutePosition);

                avatarUUIDs.Add(sp.UUID);
            }
        }

        #endregion

        #region Entity Methods

        /// <summary>
        /// Add an object into the scene that has come from storage
        /// </summary>
        /// <param name="sceneObject"></param>
        /// <param name="attachToBackup">
        /// If true, changes to the object will be reflected in its persisted data
        /// If false, the persisted data will not be changed even if the object in the scene is changed
        /// </param>
        /// <param name="alreadyPersisted">
        /// If true, we won't persist this object until it changes
        /// If false, we'll persist this object immediately
        /// </param>
        /// <param name="sendClientUpdates">
        /// If true, we send updates to the client to tell it about this object
        /// If false, we leave it up to the caller to do this
        /// </param>
        /// <returns>
        /// true if the object was added, false if an object with the same uuid was already in the scene
        /// </returns>
        protected internal bool AddRestoredSceneObject(
            SceneObjectGroup sceneObject, bool attachToBackup, bool alreadyPersisted, bool sendClientUpdates)
        {
            if (!m_parentScene.CombineRegions)
            {
                // KF: Check for out-of-region, move inside and make static.
                Vector3 npos = new Vector3(sceneObject.RootPart.GroupPosition.X,
                                           sceneObject.RootPart.GroupPosition.Y,
                                           sceneObject.RootPart.GroupPosition.Z);
                if (!(((sceneObject.RootPart.Shape.PCode == (byte)PCode.Prim) && (sceneObject.RootPart.Shape.State != 0))) && (npos.X < 0.0 || npos.Y < 0.0 || npos.Z < 0.0 ||
                    npos.X > Constants.RegionSize ||
                    npos.Y > Constants.RegionSize))
                {
                    if (npos.X < 0.0) npos.X = 1.0f;
                    if (npos.Y < 0.0) npos.Y = 1.0f;
                    if (npos.Z < 0.0) npos.Z = 0.0f;
                    if (npos.X > Constants.RegionSize) npos.X = Constants.RegionSize - 1.0f;
                    if (npos.Y > Constants.RegionSize) npos.Y = Constants.RegionSize - 1.0f;
     
                    foreach (SceneObjectPart part in sceneObject.Parts)
                    {
                        part.GroupPosition = npos;
                    }
                    sceneObject.RootPart.Velocity = Vector3.Zero;
                    sceneObject.RootPart.AngularVelocity = Vector3.Zero;
                    sceneObject.RootPart.Acceleration = Vector3.Zero;
                    sceneObject.RootPart.Velocity = Vector3.Zero;
                }
            }

            bool ret = AddSceneObject(sceneObject, attachToBackup, sendClientUpdates);

            if (attachToBackup && (!alreadyPersisted))
            {
                sceneObject.ForceInventoryPersistence();
                sceneObject.HasGroupChanged = true;
            }

            return ret;
        }
                
        /// <summary>
        /// Add a newly created object to the scene.  This will both update the scene, and send information about the
        /// new object to all clients interested in the scene.
        /// </summary>
        /// <param name="sceneObject"></param>
        /// <param name="attachToBackup">
        /// If true, the object is made persistent into the scene.
        /// If false, the object will not persist over server restarts
        /// </param>
        /// <returns>
        /// true if the object was added, false if an object with the same uuid was already in the scene
        /// </returns>
        protected internal bool AddNewSceneObject(SceneObjectGroup sceneObject, bool attachToBackup, bool sendClientUpdates)
        {
 

            bool ret = AddSceneObject(sceneObject, attachToBackup, sendClientUpdates);

           // Ensure that we persist this new scene object if it's not an
            // attachment

            if (attachToBackup)
                sceneObject.HasGroupChanged = true;

            return ret;
        }
        
        /// <summary>
        /// Add a newly created object to the scene.
        /// </summary>
        /// 
        /// This method does not send updates to the client - callers need to handle this themselves.
        /// Caller should also trigger EventManager.TriggerObjectAddedToScene
        /// <param name="sceneObject"></param>
        /// <param name="attachToBackup"></param>
        /// <param name="pos">Position of the object.  If null then the position stored in the object is used.</param>
        /// <param name="rot">Rotation of the object.  If null then the rotation stored in the object is used.</param>
        /// <param name="vel">Velocity of the object.  This parameter only has an effect if the object is physical</param>
        /// <returns></returns>
        public bool AddNewSceneObject(
            SceneObjectGroup sceneObject, bool attachToBackup, Vector3? pos, Quaternion? rot, Vector3 vel)
        {
            AddNewSceneObject(sceneObject, attachToBackup, false);

            if (pos != null)
                sceneObject.AbsolutePosition = (Vector3)pos;

            if (sceneObject.RootPart.Shape.PCode == (byte)PCode.Prim)
            {
                sceneObject.ClearPartAttachmentData();
            }

            if (rot != null)
                sceneObject.UpdateGroupRotationR((Quaternion)rot);

            PhysicsActor pa = sceneObject.RootPart.PhysActor;
            if (pa != null && pa.IsPhysical && vel != Vector3.Zero)
            {
                sceneObject.RootPart.ApplyImpulse((vel * sceneObject.GetMass()), false);
            }

            return true;
        }

        /// <summary>
        /// Add an object to the scene.  This will both update the scene, and send information about the
        /// new object to all clients interested in the scene.
        /// </summary>
        /// <remarks>
        /// The object's stored position, rotation and velocity are used.
        /// </remarks>
        /// <param name="sceneObject"></param>
        /// <param name="attachToBackup">
        /// If true, the object is made persistent into the scene.
        /// If false, the object will not persist over server restarts
        /// </param>
        /// <param name="sendClientUpdates">
        /// If true, updates for the new scene object are sent to all viewers in range.
        /// If false, it is left to the caller to schedule the update
        /// </param>
        /// <returns>
        /// true if the object was added, false if an object with the same uuid was already in the scene
        /// </returns>
        protected bool AddSceneObject(SceneObjectGroup sceneObject, bool attachToBackup, bool sendClientUpdates)
        {
            if (sceneObject == null)
            {
                m_log.ErrorFormat("[SCENEGRAPH]: Tried to add null scene object");
                return false;
            }
            if (sceneObject.UUID == UUID.Zero)
            {
                m_log.ErrorFormat(
                    "[SCENEGRAPH]: Tried to add scene object {0} to {1} with illegal UUID of {2}",
                    sceneObject.Name, m_parentScene.RegionInfo.RegionName, UUID.Zero);

                return false;
            }

            if (Entities.ContainsKey(sceneObject.UUID))
            {
                m_log.DebugFormat(
                    "[SCENEGRAPH]: Scene graph for {0} already contains object {1} in AddSceneObject()",
                    m_parentScene.RegionInfo.RegionName, sceneObject.UUID);

                return false;
            }

//            m_log.DebugFormat(
//                "[SCENEGRAPH]: Adding scene object {0} {1}, with {2} parts on {3}",
//                sceneObject.Name, sceneObject.UUID, sceneObject.Parts.Length, m_parentScene.RegionInfo.RegionName);

            SceneObjectPart[] parts = sceneObject.Parts;

            // Clamp child prim sizes and add child prims to the m_numPrim count
            if (m_parentScene.m_clampPrimSize)
            {
                foreach (SceneObjectPart part in parts)
                {
                    Vector3 scale = part.Shape.Scale;

                    scale.X = Math.Max(m_parentScene.m_minNonphys, Math.Min(m_parentScene.m_maxNonphys, scale.X));
                    scale.Y = Math.Max(m_parentScene.m_minNonphys, Math.Min(m_parentScene.m_maxNonphys, scale.Y));
                    scale.Z = Math.Max(m_parentScene.m_minNonphys, Math.Min(m_parentScene.m_maxNonphys, scale.Z));

                    part.Shape.Scale = scale;
                }
            }
            m_numPrim += parts.Length;

            sceneObject.AttachToScene(m_parentScene);


            Entities.Add(sceneObject);


            lock (SceneObjectGroupsByFullID)
                SceneObjectGroupsByFullID[sceneObject.UUID] = sceneObject;

            lock (SceneObjectGroupsByFullPartID)
            {
                foreach (SceneObjectPart part in parts)
                    SceneObjectGroupsByFullPartID[part.UUID] = sceneObject;
            }

            lock (SceneObjectGroupsByLocalPartID)
            {
//                m_log.DebugFormat(
//                    "[SCENE GRAPH]: Adding scene object {0} {1} {2} to SceneObjectGroupsByLocalPartID in {3}",
//                    sceneObject.Name, sceneObject.UUID, sceneObject.LocalId, m_parentScene.RegionInfo.RegionName);

                foreach (SceneObjectPart part in parts)
                    SceneObjectGroupsByLocalPartID[part.LocalId] = sceneObject;
            }

            if (sendClientUpdates)
                sceneObject.ScheduleGroupForFullUpdate();

            if (attachToBackup)
                sceneObject.AttachToBackup();

            return true;
        }

        public void updateScenePartGroup(SceneObjectPart part, SceneObjectGroup grp)
        {
            // no tests, caller has responsability...
            lock (SceneObjectGroupsByFullPartID)
            {
                    SceneObjectGroupsByFullPartID[part.UUID] = grp;
            }

            lock (SceneObjectGroupsByLocalPartID)
            {
                    SceneObjectGroupsByLocalPartID[part.LocalId] = grp;
            }
        }

        /// <summary>
        /// Delete an object from the scene
        /// </summary>
        /// <returns>true if the object was deleted, false if there was no object to delete</returns>
        public bool DeleteSceneObject(UUID uuid, bool resultOfObjectLinked)
        {
//            m_log.DebugFormat(
//                "[SCENE GRAPH]: Deleting scene object with uuid {0}, resultOfObjectLinked = {1}",
//                uuid, resultOfObjectLinked);

            EntityBase entity;
            if (!Entities.TryGetValue(uuid, out entity) || (!(entity is SceneObjectGroup)))
                return false;

            SceneObjectGroup grp = (SceneObjectGroup)entity;

            if (entity == null)
                return false;

            if (!resultOfObjectLinked)
            {
                m_numPrim -= grp.PrimCount;

                if ((grp.RootPart.Flags & PrimFlags.Physics) == PrimFlags.Physics)
                    RemovePhysicalPrim(grp.PrimCount);
            }
            
            lock (SceneObjectGroupsByFullID)
                SceneObjectGroupsByFullID.Remove(grp.UUID);

            lock (SceneObjectGroupsByFullPartID)
            {
                SceneObjectPart[] parts = grp.Parts;
                for (int i = 0; i < parts.Length; i++)
                    SceneObjectGroupsByFullPartID.Remove(parts[i].UUID);
            }

            lock (SceneObjectGroupsByLocalPartID)
            {
                SceneObjectPart[] parts = grp.Parts;
                for (int i = 0; i < parts.Length; i++)
                    SceneObjectGroupsByLocalPartID.Remove(parts[i].LocalId);
            }

            return Entities.Remove(uuid);
        }

        /// <summary>
        /// Add an object to the list of prims to process on the next update
        /// </summary>
        /// <param name="obj">
        /// A <see cref="SceneObjectGroup"/>
        /// </param>
        protected internal void AddToUpdateList(SceneObjectGroup obj)
        {
            lock (m_updateList)
                m_updateList[obj.UUID] = obj;
        }

        public void FireAttachToBackup(SceneObjectGroup obj)
        {
            if (OnAttachToBackup != null)
            {
                OnAttachToBackup(obj);
            }
        }

        public void FireDetachFromBackup(SceneObjectGroup obj)
        {
            if (OnDetachFromBackup != null)
            {
                OnDetachFromBackup(obj);
            }
        }

        public void FireChangeBackup(SceneObjectGroup obj)
        {
            if (OnChangeBackup != null)
            {
                OnChangeBackup(obj);
            }
        }

        /// <summary>
        /// Process all pending updates
        /// </summary>
        protected internal void UpdateObjectGroups()
        {
            if (!Monitor.TryEnter(m_updateLock))
                return;
            try
            {
                List<SceneObjectGroup> updates;

                // Some updates add more updates to the updateList. 
                // Get the current list of updates and clear the list before iterating
                lock (m_updateList)
                {
                    updates = new List<SceneObjectGroup>(m_updateList.Values);
                    m_updateList.Clear();
                }

                // Go through all updates
                for (int i = 0; i < updates.Count; i++)
                {
                    SceneObjectGroup sog = updates[i];

                    // Don't abort the whole update if one entity happens to give us an exception.
                    try
                    {
                        sog.Update();
                    }
                    catch (Exception e)
                    {
                        m_log.ErrorFormat(
                            "[INNER SCENE]: Failed to update {0}, {1} - {2}", sog.Name, sog.UUID, e);
                    }
                }
            }
            finally
            {
                Monitor.Exit(m_updateLock);
            }
        }

        protected internal void AddPhysicalPrim(int number)
        {
            m_physicalPrim += number;
        }

        protected internal void RemovePhysicalPrim(int number)
        {
            m_physicalPrim -= number;
        }

        protected internal void AddToScriptLPS(int number)
        {
            m_scriptLPS += number;
        }

        protected internal void AddActiveScripts(int number)
        {
            m_activeScripts += number;
        }

        protected internal void HandleUndo(IClientAPI remoteClient, UUID primId)
        {
            if (primId != UUID.Zero)
            {
                SceneObjectPart part =  m_parentScene.GetSceneObjectPart(primId);
                if (part != null)
                    part.Undo();
            }
        }

        protected internal void HandleRedo(IClientAPI remoteClient, UUID primId)
        {
            if (primId != UUID.Zero)
            {
                SceneObjectPart part = m_parentScene.GetSceneObjectPart(primId);

                if (part != null)
                    part.Redo();
            }
        }

        protected internal ScenePresence CreateAndAddChildScenePresence(
            IClientAPI client, AvatarAppearance appearance, PresenceType type)
        {
            // ScenePresence always defaults to child agent
            ScenePresence presence = new ScenePresence(client, m_parentScene, appearance, type);

            Entities[presence.UUID] = presence;

            m_scenePresencesLock.EnterWriteLock();
            try
            {
                m_numChildAgents++;

                Dictionary<UUID, ScenePresence> newmap = new Dictionary<UUID, ScenePresence>(m_scenePresenceMap);
                List<ScenePresence> newlist = new List<ScenePresence>(m_scenePresenceArray);

                if (!newmap.ContainsKey(presence.UUID))
                {
                    newmap.Add(presence.UUID, presence);
                    newlist.Add(presence);
                }
                else
                {
                    // Remember the old presence reference from the dictionary
                    ScenePresence oldref = newmap[presence.UUID];
                    // Replace the presence reference in the dictionary with the new value
                    newmap[presence.UUID] = presence;
                    // Find the index in the list where the old ref was stored and update the reference
                    newlist[newlist.IndexOf(oldref)] = presence;
                }

                // Swap out the dictionary and list with new references
                m_scenePresenceMap = newmap;
                m_scenePresenceArray = newlist;
            }
            finally
            {
                m_scenePresencesLock.ExitWriteLock();
            }

            return presence;
        }

        /// <summary>
        /// Remove a presence from the scene
        /// </summary>
        protected internal void RemoveScenePresence(UUID agentID)
        {
            if (!Entities.Remove(agentID))
            {
                m_log.WarnFormat(
                    "[SCENE GRAPH]: Tried to remove non-existent scene presence with agent ID {0} from scene Entities list",
                    agentID);
            }

            m_scenePresencesLock.EnterWriteLock();
            try
            {
                Dictionary<UUID, ScenePresence> newmap = new Dictionary<UUID, ScenePresence>(m_scenePresenceMap);
                List<ScenePresence> newlist = new List<ScenePresence>(m_scenePresenceArray);
                
                // Remove the presence reference from the dictionary
                if (newmap.ContainsKey(agentID))
                {
                    ScenePresence oldref = newmap[agentID];
                    newmap.Remove(agentID);

                    // Find the index in the list where the old ref was stored and remove the reference
                    newlist.RemoveAt(newlist.IndexOf(oldref));
                    // Swap out the dictionary and list with new references
                    m_scenePresenceMap = newmap;
                    m_scenePresenceArray = newlist;
                }
                else
                {
                    m_log.WarnFormat("[SCENE GRAPH]: Tried to remove non-existent scene presence with agent ID {0} from scene ScenePresences list", agentID);
                }
            }
            finally
            {
                m_scenePresencesLock.ExitWriteLock();
            }
        }

        protected internal void SwapRootChildAgent(bool direction_RC_CR_T_F)
        {
            if (direction_RC_CR_T_F)
            {
                m_numRootAgents--;
                m_numChildAgents++;
            }
            else
            {
                m_numChildAgents--;
                m_numRootAgents++;
            }
        }

        public void removeUserCount(bool TypeRCTF)
        {
            if (TypeRCTF)
            {
                m_numRootAgents--;
            }
            else
            {
                m_numChildAgents--;
            }
        }

        public void RecalculateStats()
        {
            int rootcount = 0;
            int childcount = 0;

            ForEachScenePresence(delegate(ScenePresence presence)
            {
                if (presence.IsChildAgent)
                    ++childcount;
                else
                    ++rootcount;
            });

            m_numRootAgents = rootcount;
            m_numChildAgents = childcount;
        }

        public int GetChildAgentCount()
        {
            return m_numChildAgents;
        }

        public int GetRootAgentCount()
        {
            return m_numRootAgents;
        }

        public int GetTotalObjectsCount()
        {
            return m_numPrim;
        }

        public int GetActiveObjectsCount()
        {
            return m_physicalPrim;
        }

        public int GetActiveScriptsCount()
        {
            return m_activeScripts;
        }

        public int GetScriptLPS()
        {
            int returnval = m_scriptLPS;
            m_scriptLPS = 0;
            return returnval;
        }

        #endregion

        #region Get Methods
        
        /// <summary>
        /// Get the controlling client for the given avatar, if there is one.
        ///
        /// FIXME: The only user of the method right now is Caps.cs, in order to resolve a client API since it can't
        /// use the ScenePresence.  This could be better solved in a number of ways - we could establish an
        /// OpenSim.Framework.IScenePresence, or move the caps code into a region package (which might be the more
        /// suitable solution).
        /// </summary>
        /// <param name="agentId"></param>
        /// <returns>null if either the avatar wasn't in the scene, or
        /// they do not have a controlling client</returns>
        /// <remarks>this used to be protected internal, but that
        /// prevents CapabilitiesModule from accessing it</remarks>
        public IClientAPI GetControllingClient(UUID agentId)
        {
            ScenePresence presence = GetScenePresence(agentId);

            if (presence != null)
            {
                return presence.ControllingClient;
            }

            return null;
        }

        /// <summary>
        /// Get a reference to the scene presence list. Changes to the list will be done in a copy
        /// There is no guarantee that presences will remain in the scene after the list is returned.
        /// This list should remain private to SceneGraph. Callers wishing to iterate should instead
        /// pass a delegate to ForEachScenePresence.
        /// </summary>
        /// <returns></returns>
        protected internal List<ScenePresence> GetScenePresences()
        {
            return m_scenePresenceArray;
        }

        /// <summary>
        /// Request a scene presence by UUID. Fast, indexed lookup.
        /// </summary>
        /// <param name="agentID"></param>
        /// <returns>null if the presence was not found</returns>
        protected internal ScenePresence GetScenePresence(UUID agentID)
        {
            Dictionary<UUID, ScenePresence> presences = m_scenePresenceMap;
            ScenePresence presence;
            presences.TryGetValue(agentID, out presence);
            return presence;
        }

        /// <summary>
        /// Request the scene presence by name.
        /// </summary>
        /// <param name="firstName"></param>
        /// <param name="lastName"></param>
        /// <returns>null if the presence was not found</returns>
        protected internal ScenePresence GetScenePresence(string firstName, string lastName)
        {
            List<ScenePresence> presences = GetScenePresences();
            foreach (ScenePresence presence in presences)
            {
                if (presence.Firstname == firstName && presence.Lastname == lastName)
                    return presence;
            }
            return null;
        }

        /// <summary>
        /// Request the scene presence by localID.
        /// </summary>
        /// <param name="localID"></param>
        /// <returns>null if the presence was not found</returns>
        protected internal ScenePresence GetScenePresence(uint localID)
        {
            List<ScenePresence> presences = GetScenePresences();
            foreach (ScenePresence presence in presences)
                if (presence.LocalId == localID)
                    return presence;
            return null;
        }

        protected internal bool TryGetScenePresence(UUID agentID, out ScenePresence avatar)
        {
            Dictionary<UUID, ScenePresence> presences = m_scenePresenceMap;
            presences.TryGetValue(agentID, out avatar);
            return (avatar != null);
        }

        protected internal bool TryGetAvatarByName(string name, out ScenePresence avatar)
        {
            avatar = null;
            foreach (ScenePresence presence in GetScenePresences())
            {
                if (String.Compare(name, presence.ControllingClient.Name, true) == 0)
                {
                    avatar = presence;
                    break;
                }
            }
            return (avatar != null);
        }

        /// <summary>
        /// Get a scene object group that contains the prim with the given local id
        /// </summary>
        /// <param name="localID"></param>
        /// <returns>null if no scene object group containing that prim is found</returns>
        public SceneObjectGroup GetGroupByPrim(uint localID)
        {
            EntityBase entity;
            if (Entities.TryGetValue(localID, out entity))
                return entity as SceneObjectGroup;

//            m_log.DebugFormat("[SCENE GRAPH]: Entered GetGroupByPrim with localID {0}", localID);

            SceneObjectGroup sog;
            lock (SceneObjectGroupsByLocalPartID)
                SceneObjectGroupsByLocalPartID.TryGetValue(localID, out sog);

            if (sog != null)
            {
                if (sog.ContainsPart(localID))
                {
//                    m_log.DebugFormat(
//                        "[SCENE GRAPH]: Found scene object {0} {1} {2} containing part with local id {3} in {4}.  Returning.",
//                        sog.Name, sog.UUID, sog.LocalId, localID, m_parentScene.RegionInfo.RegionName);

                    return sog;
                }
                else
                {
                    lock (SceneObjectGroupsByLocalPartID)
                    {
                        m_log.WarnFormat(
                            "[SCENE GRAPH]: Found scene object {0} {1} {2} via SceneObjectGroupsByLocalPartID index but it doesn't contain part with local id {3}.  Removing from entry from index in {4}.",
                            sog.Name, sog.UUID, sog.LocalId, localID, m_parentScene.RegionInfo.RegionName);
                        m_log.WarnFormat("stack: {0}", Environment.StackTrace);
                        SceneObjectGroupsByLocalPartID.Remove(localID);
                    }
                }
            }

            EntityBase[] entityList = GetEntities();
            foreach (EntityBase ent in entityList)
            {
                //m_log.DebugFormat("Looking at entity {0}", ent.UUID);
                if (ent is SceneObjectGroup)
{'fraction_non_alphanumeric': 0.08128733490436785, 'fraction_numerical': 0.002288047350249356, 'mean_word_length': 1.617218875502008, 'pattern_counts': {'":': 0, '<': 333, '<?xml version=': 0, '>': 321, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3944972', 'n_tokens_mistral': 18492, 'n_tokens_neox': 17551, 'n_words': 5355}