TreeTraversal

TreeTraversal.pde

static final float CANVAS_X = 900;
static float CANVAS_Y = 0; // compute me later

class Node
{
  Integer value;
  
  int level;
  int levelOffset;
  int index; 
  
  Node leftChild;
  Node rightChild;
  
  NodeState state;
  
  Node() { }
 
  Node(int value) { this.value = value; }
  
  Node(Integer nodeValues[])
  {
    int index = 0;
    
    if ( index >= nodeValues.length )
      return;
      
    this.value = nodeValues[index];
    
    Node focus = this;
    
    Node nodes[] = new Node[nodeValues.length];
    nodes[0] = this;
    
    int nodeCounter = 0;
    int levelNodes = 1;
    
    int currentLevel = 0;
 
    for ( ; index < nodeValues.length; index++ )
    {
      focus = nodes[index];
      
      int savedLevel = currentLevel;
      
      focus.level = savedLevel;
      focus.index = index;
      focus.levelOffset = nodeCounter;
      
      Node leftNode = new Node();
      
      int leftIndex = index * 2 + 1;
      int rightIndex = index * 2 + 2;
      
      if ( ++nodeCounter >= levelNodes )
      {
        levelNodes = levelNodes * 2;
        
        currentLevel++;
        nodeCounter = 0;
      }
      
      if ( rightIndex >= nodeValues.length )
        continue;
        
      print(leftIndex); print(", ");
      println(rightIndex);
        
      leftNode.value = nodeValues[leftIndex];
      leftNode.level = savedLevel + 1;
      leftNode.index = leftIndex;
      
      Node rightNode = new Node();
      
      rightNode.value = nodeValues[rightIndex];
      rightNode.level = savedLevel + 1;
      rightNode.index = rightIndex;
      
      nodes[leftIndex] = leftNode;
      nodes[rightIndex] = rightNode;
      
      focus.leftChild = leftNode;
      focus.rightChild = rightNode;
    }
  }
}

class NodeState
{
  boolean touched;
  boolean searching;
}

int treeLevelCount(int nodeCount)
{
  if ( nodeCount <= 0 )
    throw new IllegalArgumentException("Invalid node count");
    
  return (int) floor((log(nodeCount+1) / log(2)));
}

class Painter
{
  void paintTree(Node node, float dx, float dy, float levels)
  {
    if ( node == null )
      return;
      
    paintNode(node, dx, dy, levels);
    
    paintTree(node.leftChild, dx, dy, levels);
    paintTree(node.rightChild, dx, dy, levels);
  }
  
  void paintNode(Node node, float dx, float dy, float levels)
  {
    if ( node.value == null )
      return;
      
    // 
    // L0         -> L1         -> L2         -> L4
    // (4  , 8  ) -> (2  , 4  ) -> (1  , 2  ) -> (0, 1)
    // (2^2, 2^3) -> (2^1, 2^2) -> (2^0, 2^1) -> (2^-1, 2^0) 
    
    float startAt = pow(2, levels - (node.level+2));
      
    int levelOffset = node.levelOffset;
    int moveBy = (int)pow(2, levels - (node.level+1));
    
    if ( moveBy == 0 )
      moveBy = 1;
        
    float baseX = dx * startAt;
    
    //if ( startAt < 1 ) 
    //  baseX = -baseX;
      
    float baseY = CANVAS_Y / levels;
        
    float x = baseX + (moveBy*levelOffset)*dx;
    float y = (baseY * (node.level+1)) - (dy / 2);
/*
    print("node.level = ");
    print(node.level); print(", ");
    print("levelOffset = ");
    print(levelOffset); print(", ");
    print("node.index = ");
    print(node.index); print(", ");
    print("startAt = ");
    print(startAt); print(", ");
    print("moveBy = ");
    print(moveBy); print(", ");
    print("baseX = ");
    print(baseX); print(", ");
    print("x = ");
    print(x); print(", ");
    print("y = ");
    print(y); println("");      
*/    
    ellipse(x, y, dx, dy);
  }
}

Integer g_nodeValues[] = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
Node g_tree = null;

abstract class TreeSearch
{
  Node _tree;

  public void init(Node tree)
  {
    _tree = tree;
  }
  
  abstract public void update();
}

class BreadthFirstSearch extends TreeSearch
{
  Node _focus = null;
  
  public void update()
  {
    
  }
}

class DepthFirstSearch extends TreeSearch
{
  public void update()
  {
    
  }
}


void draw()
{ 
  background(0);

  Painter painter = new Painter();
  int levels = treeLevelCount(g_nodeValues.length+1);
  
  //println(levels);
  
  float node_dX = CANVAS_X / pow(2, levels-1);
  float node_dY = CANVAS_Y / levels;
  
  painter.paintTree(g_tree, node_dX, node_dY, levels);
}

void setup()
{
  g_tree = new Node(g_nodeValues);
 
  int levels = treeLevelCount(g_nodeValues.length);
  float lastRowCount = pow(2, levels-1);
  float ratio = levels / lastRowCount;
  
  CANVAS_Y = CANVAS_X*ratio;
  
  size((int)CANVAS_X, (int)CANVAS_Y);
  background(0);
  frameRate(5);
}