Template for split, move and track objects

Can anyone help me find an elegant design for splitting, moving and tracking objects.

The diagram below shows an object with an initial size of 100 that spills into two (50, 75), then one of the child objects (75) then splits into three (25, 25, 25).

My question is, can anyone think of an elegant design that will allow me from any object to traverse the entire tree (for example, to identify the parent-root of any subsequent child)?

My current attempt (see code below) uses instance fields Parent and Children to keep track of objects, but obviously doesn't give me the functionality I need - as from Obj [Id: 6] I can't recursively find the parent root directory.

Can anyone think of a solution? I don't think a double linked list will work as the spilled parameter is not limited to two.

                      Obj [Id:1, Size:100]
                             |
                    Split operation (50, 75)
                             <>
       Obj [Id:2, Size:25]      Obj [Id:2, Size:75]
                                          |
                              Split operation (25, 25, 25)
                                          <>
         Obj [Id:4, Size:25]     Obj [Id:5, Size:25]       Obj [Id:6, Size:25]




public class SplitableObj : IEquatable<SplitableObj>
{
    private Guid _id = Guid.NewGuid();
    private int _size;
    private SplitableObj _parent;
    private List<SplitableObj> _childern;

    public SplitableObj(int size)
    {
        _size = size;
    }
    public Guid id
    {
        get { return _id; }
        set { _id = value; }
    }

    public SplitableObj Parent
    {
        get { return _parent; }
        set { _parent = value; }
    }

    public List<SplitableObj> Children
    {
        get { return _childern; }
        set { _childern = value; }
    }

    public int Size
    {
        get { return _size; }
        set { _size = value; }
    }

    public IEnumerable<SplitableObj> Split(params int[] splits)
    {
        if (splits.Length < 2)
        {
            throw new ApplicationException("splits must be least 2.");
        }

        int totalSplits = 0;
        foreach (int split in splits)
        {
            totalSplits += split;
        }

        if (_size != totalSplits)
        {
            throw new ApplicationException("Total splits must equal Size.");
        }

        foreach (int split in splits)
        {
            SplitableObj splitAmount = new SplitableObj(split);
            splitAmount.Parent = this;
            this.Children.Add(splitAmount);
            yield return splitAmount;
        }
    }

    public bool Equals(SplitableObj splitableObj)
    {
        if (splitableObj == null) return false;
        return Equals(_id, splitableObj._id);
    }
    public override bool Equals(object obj)
    {
        if (ReferenceEquals(this, obj)) return true;
        return Equals(obj as SplitableObj);
    }
    public override int GetHashCode()
    {
        return _id.GetHashCode();
    }
}

      

+1


source to share


2 answers


Homework?



set RootObject to the current object.
while the parent of RootObject is not undefined, set RootObject to its parent.
Finally, return RootObject.

      

+1


source


Why are you having difficulty finding root? go from parent to parent until parent is set.



By the way, are you talking about B + trees? They automatically balance using child blocks that split when the threshold is exceeded, see this image on Wikipediaimage

0


source







All Articles