internal sealed class Root<T>
{
    private readonly Leaf<T> rootLeaf = new Leaf<T>();

    // dictionary contains a reference to each item, and the leaf it is assigned to (its parent)
    private readonly IDictionary<T, Leaf<T>> allItems = new Dictionary<T, Leaf<T>>();

    /// <summary>
    /// Gets GetAllChildren.
    /// </summary>
    public IList<T> GetAllChildren
    {
        get
        {
            return this.rootLeaf.GetAllChildren;
        }
    }

    public void Add(T o)
    {
        var addedTo = this.rootLeaf.Add(o);

        this.allItems.Add(o, addedTo); // Add object reference to AllItems dictionary
    }

    public void Update()
    {
        foreach (var i in from i in this.allItems from b in this.GetNeighbors(i.Key) select i)
        {
            // Would do collision checks here
        }
    }

    private IEnumerable<T> GetNeighbors(T obj)
    {
        return this.allItems[obj].GetAllChildren.Where(o => ReferenceEquals(obj, o));
    }
}

internal class Leaf<T>
{
    private const int MaxChildCount = 1;

    private static readonly Random rand = new Random();

    private readonly IList<T> children = new List<T>();

    private List<Leaf<T>> childLeaves;

    private bool hasLeaves; // Should we use the leaves?

    private bool leavesGenerated; // Have the leaves been created? (Low Level, do not touch)

    /// <summary>
    /// Returns children of this leaf, and all of its subleaves
    /// </summary>
    public IList<T> GetAllChildren
    {
        get
        {
            var outp = this.children.ToList();

            if (this.hasLeaves)
            {
                this.childLeaves.ToList().ForEach(l => outp.AddRange(l.GetAllChildren));
            }

            return outp;
        }
    }

    /// <summary>
    /// Get count of all children in this leaf, and its subleaves
    /// </summary>
    public int GetChildCount
    {
        get
        {
            var outp = this.children.Count;

            if (this.hasLeaves)
            {
                outp += this.childLeaves.Sum(l => l.GetChildCount);
            }

            return outp;
        }
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="o">The object to be added</param>
    /// <returns>The leaf the object was added to</returns>
    public Leaf<T> Add(T o)
    {
        if (this.children.Count < MaxChildCount)
        {
            this.children.Add(o);
            return this;
        }

        // Pick random subleaf, I know this isn't correct for a quadtree, but it will simplify this explanation code
        if (!this.hasLeaves)
        {
            this.CreateLeaves();
        }

        return this.childLeaves[rand.Next(0, 3)].Add(o);
    }

    protected void CreateLeaves()
    {
        if (!this.leavesGenerated)
        {
            // create each of the four leaves
            this.childLeaves = new List<Leaf<T>> { new Leaf<T>(), new Leaf<T>(), new Leaf<T>(), new Leaf<T>() };

            this.leavesGenerated = true;
        }

        this.hasLeaves = true;
    }

    protected void RemoveLeaves()
    {
        this.hasLeaves = false;
    }
}

internal sealed class Root<T>
{
    private readonly Leaf<T> rootLeaf = new Leaf<T>();

    // dictionary contains a reference to each item, and the leaf it is assigned to (its parent)
    private readonly IDictionary<T, Leaf<T>> allItems = new Dictionary<T, Leaf<T>>();

    /// <summary>
    /// Gets GetAllChildren.
    /// </summary>
    public IList<T> GetAllChildren
    {
        get
        {
            return this.rootLeaf.GetAllChildren;
        }
    }

    public void Add(T o)
    {
        var addedTo = this.rootLeaf.Add(o);

        this.allItems.Add(o, addedTo); // Add object reference to AllItems dictionary
    }

    public void Update()
    {
        foreach (var i in from i in this.allItems from b in this.GetNeighbors(i.Key) select i)
        {
            // Would do collision checks here
        }
    }

    private IEnumerable<T> GetNeighbors(T obj)
    {
        return this.allItems[obj].GetAllChildren.Where(o => ReferenceEquals(obj, o));
    }
}

internal class Leaf<T>
{
    private const int MaxChildCount = 1;

    private static readonly Random rand = new Random();

    private readonly IList<T> children = new List<T>();

    private List<Leaf<T>> childLeaves;

    private bool hasLeaves; // Should we use the leaves?

    private bool leavesGenerated; // Have the leaves been created? (Low Level, do not touch)

    /// <summary>
    /// Returns children of this leaf, and all of its subleaves
    /// </summary>
    public IList<T> GetAllChildren
    {
        get
        {
            var allChildren = this.children.ToList();

            if (this.hasLeaves)
            {
                this.childLeaves.ToList().ForEach(l => allChildren.AddRange(l.GetAllChildren));
            }

            return allChildren;
        }
    }

    /// <summary>
    /// Get count of all children in this leaf, and its subleaves
    /// </summary>
    public int GetChildCount
    {
        get
        {
            var allChildrenCount = this.children.Count;

            if (this.hasLeaves)
            {
                allChildrenCount += this.childLeaves.Sum(l => l.GetChildCount);
            }

            return allChildrenCount;
        }
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="o">The object to be added</param>
    /// <returns>The leaf the object was added to</returns>
    public Leaf<T> Add(T o)
    {
        if (this.children.Count < MaxChildCount)
        {
            this.children.Add(o);
            return this;
        }

        // Pick random subleaf, I know this isn't correct for a quadtree, but it will simplify this explanation code
        if (!this.hasLeaves)
        {
            this.CreateLeaves();
        }

        return this.childLeaves[rand.Next(0, 3)].Add(o);
    }

    protected void CreateLeaves()
    {
        if (!this.leavesGenerated)
        {
            // create each of the four leaves
            this.childLeaves = new List<Leaf<T>> { new Leaf<T>(), new Leaf<T>(), new Leaf<T>(), new Leaf<T>() };

            this.leavesGenerated = true;
        }

        this.hasLeaves = true;
    }

    protected void RemoveLeaves()
    {
        this.hasLeaves = false;
    }
}