CODEWITHSUNDEEP
javarecursiontree
CLOUGH
CLOUGH

Reputation: 741

Java - Appending a tree to a branch of another tree by given UNIQUE index number

I have a java class like this,

    class Block{
        private int index;
        private Block left;
        private Block right;

        public int getIndex() {
            return index;
        }

        public Block setIndex(int index) {
            this.index = index;
            return this;
        }

        public Block getLeft() {
            return left;
        }

        public Block setLeft(Block left) {
            this.left = left;
            return this;
        }

        public Block getRight() {
            return right;
        }

        public Block setRight(Block right) {
            this.right = right;
            return this;
        }
    }

Then, I've created two trees like this using setter methods.

    Block tree1 = new Block()
        .setLeft(new Block()
                        .setLeft(new Block())
                        .setRight(new Block())
        )
        .setRight(new Block()
                        .setLeft(new Block())
                        .setRight(new Block())
        );

and, 

    Block tree2 = new Block()
        .setRight(new Block()
                .setRight(new Block()
                        .setRight(new Block()
                                .setLeft(new Block())
                                .setLeft(new Block())
                        )
                )
        );

So, I would like to have a method like,

int blockIndex = 3;
boolean replace = false;//add if new, else do nothing
tree1.appendBlock(blockIndex,tree2,replace);

Trees should be able to create directly (like tree1 and tree2) and also within loops. Any ideas? Thanks in advance!

Upvotes: 3

Views: 358

Answers (1)

ankhzet
ankhzet

Reputation: 2568

Here possible solution:

class Block {

    ...

    boolean appendBlock(int atIndex, Block tree, boolean replace) {
        if (left == right == null)
            return false;

        if ((left != null) && (left.index == atIndex) {
            if (replace) 
                setLeft(tree);
        } else
            if ((right != null) && (right.index == atIndex)) {
                if (replace) 
                    setRight(tree);
            } else
                if ((left == null) || !left.appendBlock(atIndex, tree, replace))
                    if ((right == null) || !right.appendBlock(atIndex, tree, replace))
                        return false;

        return true;
    }

    ...

}

Usage:

...

replace = false;
if (!tree1.appendBlock(index, tree2, replace))
    throw Exception(String.format("Child node with index %d not found", index));

When replace = false - method searches for child node with specified index and returns false if not found.

If replace = true, then if child node with specified index was found - it will be replaced with specified Block node.

Upd.

To make it always throw an exception if node was not found, following trick could be used:

// define actual searcher function as private util
// it's safe to call it as it's only indicates success with boolean
// result, so no exceptions would be thrown
protected boolean appendBlockIfFound(int atIndex, Block tree, boolean replace) {
    if (left == right == null)
        return false;

    // same code as above in appendBlock() method
    ...

    return true;
}

// ... and the real worker, exposed to the class user (developer)
// will throw exception on error
public void appendBlock(int atIndex, Block tree, boolean replace) {
    if (!appendBlockIfFound(atIndex, tree, replace))
        throw Exception(String.format("Child node with index %d not found", atIndex));
}

Upd. 2

Searcher function for non-fixed amount of childnodes:

class Block extends ArrayList<Block> {

    ...

    public Block(int childs) {
        super(childs);
        while (childs > 0)
            add(null);
    }

    private boolean appendBlockIfFound(int atIndex, Block tree, boolean replace) {
        if (size() <= 0)
            return false;

        for (int i = 0; i < size(); i++) {
            Block child = get(i);
            if (child == null)
                continue;
            if (child.index == atIndex) {
                if (replace)
                  set(i, tree);
                return true;
            }
        }

        for (Block child: this)
          if ((child != null) && child.appendBlockIfFound(atIndex, tree, replace))
            return true;

        return false;
    }

    @Override
    public Block set(int index, Block child) {
      super.set(index, child);
      return this;
    }

    ...

}

Usage:

class TenBlock extends Block {

    public TenBlock() {
        super(10);
    }

}

... and then:

Block root = new TenBlock();

Block child10 = root.get(9);

root.set(5, (new TenBlock()).set(2, new TenBlock()))
    .set(6, new TenBlock())

Upvotes: 3

Related Questions