code: /*--------------------------------------------------------------*
    Copyright (C) 2006-2015 OpenSim Ltd.
  
    This file is distributed WITHOUT ANY WARRANTY. See the file
    'License' for details on this and other legal matters.
  *--------------------------------------------------------------*/
  
  package org.omnetpp.common.ui;
  
  import java.util.Arrays;
  import java.util.Comparator;
  
  import org.apache.commons.lang3.ArrayUtils;
  import org.apache.commons.lang3.ObjectUtils;
  import org.eclipse.core.runtime.Assert;
  
  /**
   * Node for a generic tree where every node contains a payload object.
   * We use this with GenericTreeContentProvider to display an arbitrary
   * object tree in a TreeViewer.
   *
   * The children list of this node can be built by using the addChild() methods,
   * or lazily by overriding computeChildren().
   *
   * @author andras
   */
  //XXX use org.eclipse.jface.viewers.TreeNode instead? (just discovered such thing exists)
  public class GenericTreeNode {
      protected static final GenericTreeNode[] EMPTY_ARRAY = new GenericTreeNode[0];
  
      private GenericTreeNode parent;
      private GenericTreeNode[] children; // ==null, if not yet computed
      private Object payload;
      private Comparator<GenericTreeNode> childOrder; // order of the children (maybe null)
  
      @SuppressWarnings("unchecked")
      private static class PayloadComparator implements Comparator<GenericTreeNode> {
          private Comparator comparator;
  
          public PayloadComparator(Comparator<?> comparator) {
              this.comparator = comparator;
          }
  
          public int compare(GenericTreeNode left, GenericTreeNode right) {
              return comparator.compare(left.payload, right.payload);
          }
      }
  
      /**
       * Constructs a new tree node with the given payload.
       * @param payload may NOT be null
       */
      public GenericTreeNode(Object payload) {
          this(payload, null);
      }
  
      public GenericTreeNode(Object payload, Comparator<? extends Object> childOrder) {
          Assert.isTrue(payload!=null);
          this.payload = payload;
          this.children = null;
          this.childOrder = childOrder != null ? new PayloadComparator(childOrder) : null;
      }
  
      /**
       * Add a child node to this node.
       * @param child may NOT be null
       */
      public void addChild(GenericTreeNode child) {
          if (child.parent!=null)
              throw new RuntimeException("child node already has a parent");
  
          GenericTreeNode[] childrenNew = new GenericTreeNode[children == null ? 1 : children.length + 1];
          if (childOrder == null || childrenNew.length == 1) {
              if (children != null)
                  System.arraycopy(children, 0, childrenNew, 0, children.length);  //XXX potential bottleneck -- use ArrayList? (Andras)
              childrenNew[childrenNew.length - 1] = child;
          }
          else {
              int insertionPoint = Arrays.binarySearch(children, child, childOrder);
              if (insertionPoint < 0)
                  insertionPoint = - insertionPoint - 1;
  
              if (insertionPoint > 0)
                  System.arraycopy(children, 0, childrenNew, 0, insertionPoint);
              childrenNew[insertionPoint] = child;
              if (insertionPoint < children.length)
                  System.arraycopy(children, insertionPoint, childrenNew, insertionPoint + 1, children.length - insertionPoint);
  
          }
  
          child.parent = this;
          children = childrenNew;
      }
  
      public void addChild(int index, GenericTreeNode child) {
          Assert.isTrue(childOrder == null);
          children = (GenericTreeNode[])ArrayUtils.add(children, index, child); // children == null is accepted by ArrayUtils.add().
          child.parent = this;
      }
  
      /**
       * Returns the payload object, which cannot be null.
       */
      public Object getPayload() {
          return payload;
      }
  
      /**
       * Sets the payload object. null is not accepted.
       */
      public void setPayload(Object payload) {
          Assert.isTrue(payload!=null);
          this.payload = payload;
      }
  
      public int getChildCount() {
          ensureChildren();
          return children.length;
      }
  
      public boolean hasChildren() {
          ensureChildren();
          return children.length > 0;
      }
  
      /**
       * Returns the children. The result is never null.
       */
      public GenericTreeNode[] getChildren() {
          ensureChildren();
          return children;
      }
  
      protected GenericTreeNode[] internalGetChildren() {
          return children;
      }
  
      public GenericTreeNode getChild(int index) {
          ensureChildren();
          Assert.isLegal(0 <= index && index < children.length);
          return children[index];
      }
  
      /**
       * Returns the parent node.
       */
      public GenericTreeNode getParent() {
          return parent;
      }
  
      /**
       * Returns the index of this node within its parent.
       * Returns -1 if this is the root node.
       */
      public int indexInParent() {
          if (parent == null)
              return -1;
          GenericTreeNode[] siblings = parent.children;
          Assert.isNotNull(siblings);
          for (int i = 0; i < siblings.length; ++i)
              if (siblings[i] == this)
                  return i;
          throw new RuntimeException("tree inconsistency");
      }
  
      /**
       * Adds a child node with the given payload if it not already exists.
       */
      public GenericTreeNode getOrCreateChild(Object payload) {
          return getOrCreateChild(payload, null);
      }
  
      /**
       * Adds a child node with the given payload and child order if it not already exists.
       */
      public GenericTreeNode getOrCreateChild(Object payload, Comparator<? extends Object> childOrder) {
          ensureChildren();
          for (int i = 0; i < children.length; ++i) {
              GenericTreeNode child = children[i];
              if (child.payload.equals(payload))
                  return child;
          }
  
          GenericTreeNode child = new GenericTreeNode(payload, childOrder);
          addChild(child);
  
          return child;
      }
  
      public void unlink() {
          Assert.isLegal(parent != null);
          Assert.isNotNull(parent.children);
          parent.children = (GenericTreeNode[])ArrayUtils.remove(parent.children, indexInParent());
          parent = null;
      }
  
      public GenericTreeNode findPayload(Object payload) {
          if (this.payload==payload || this.payload.equals(payload))
              return this;
          GenericTreeNode result;
          ensureChildren();
          for (GenericTreeNode child : children)
              if ((result=child.findPayload(payload)) != null)
                  return result;
          return null;
      }
  
      /**
       * Clones this node and its descendants recursively.
       * The comparators and the payloads are not cloned though.
       * The parent of the returned node is always null.
       *
       * If there are any uncomputed child list in the tree,
       * they are computed before cloning.
       */
      public GenericTreeNode cloneTree() {
          ensureChildren();
          GenericTreeNode node = new GenericTreeNode(payload, childOrder);
          for (GenericTreeNode child : children)
              node.addChild(child.cloneTree());
          return node;
      }
  
      /**
       * Ensures that the {@code children} field is filled in
       * by calling computeChildren() when needed.
       */
      private void ensureChildren() {
          if (children == null) {
              children = computeChildren();
              Assert.isNotNull(children);
          }
      }
  
      /**
       * Override this method if the children are computed on demand.
       *
       * This method is not allowed to return null.
       */
      protected GenericTreeNode[] computeChildren() {
          return EMPTY_ARRAY;
      }
  
      /**
       * Delegates to payload's toString().
       */
      @Override
      public String toString() {
          return "GenericTreeNode(" +payload.toString() + ")";
      }
  
      /**
       * Compares payloads only (of two GenericTreeNodes)
       */
      @Override
      public boolean equals(Object obj) {
          if (obj==null || getClass()!=obj.getClass())
              return false;
          if (this==obj)
              return true;
          GenericTreeNode node = (GenericTreeNode)obj;
          return ObjectUtils.equals(node.payload, payload);
      }
  
      @Override
      public int hashCode() {
          return payload==null ? super.hashCode() : payload.hashCode();
      }
  }
  