fork download 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Test
  6. {
  7.    static class Node<T>
  8.    {
  9.       Node<T> left, right;
  10.       T data;
  11.       int subtreeCount;
  12.       Node(T data) { this.data = data; subtreeCount = 1; }
  13.  
  14.       public String toString(int spaces, char leftRight)
  15.       {
  16.          return String.format("%" + spaces + "s%c: %s\n", "", leftRight, data.toString())
  17.                  + (left != null ? left.toString(spaces+3, 'L') : "")
  18.                  + (right != null ? right.toString(spaces+3, 'R') : "");
  19.       }
  20.  
  21.       int subtreeSize(Node<T> node)
  22.       {
  23.          if (node == null)
  24.             return 0;
  25.          return node.subtreeCount;
  26.       }
  27.  
  28.       // combined add and get into 1 function for simplicity
  29.       // if data is null, it is an get, otherwise it's an add
  30.       private T addGet(int index, T data)
  31.       {
  32.          if (data != null)
  33.             subtreeCount++;
  34.          if (index == subtreeSize(left) && data == null)
  35.             return this.data;
  36.          if (index <= subtreeSize(left))
  37.          {
  38.             if (left == null && data != null)
  39.                return (left = new Node<>(data)).data;
  40.             else
  41.                return left.addGet(index, data);
  42.          }
  43.          else if (right == null && data != null)
  44.             return (right = new Node<>(data)).data;
  45.          else
  46.             return right.addGet(index-subtreeSize(left)-1, data);
  47.       }
  48.    }
  49.  
  50.    static class TreeArray<T>
  51.    {
  52.       private Node<T> root;
  53.       public int size() { return (root == null ? 0 : root.subtreeCount); }
  54.  
  55.       void add(int index, T data)
  56.       {
  57.          if (index < 0 || index > size())
  58.             throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
  59.          if (root == null)
  60.             root = new Node<>(data);
  61.          else
  62.             root.addGet(index, data);
  63.       }
  64.  
  65.       T get(int index)
  66.       {
  67.          if (index < 0 || index >= size())
  68.             throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
  69.          return root.addGet(index, null);
  70.       }
  71.  
  72.       @Override
  73.       public String toString() { return root == null ? "Empty" : root.toString(1, 'X'); }
  74.    }
  75.  
  76.    public static void main(String[] args)
  77.    {
  78.       TreeArray<String> tree = new TreeArray<>();
  79.       tree.add(0, "a");
  80.       tree.add(0, "b");
  81.       tree.add(1, "c");
  82.       tree.add(2, "d");
  83.       tree.add(1, "e");
  84.       tree.add(0, "f");
  85.       tree.add(6, "g");
  86.       tree.add(7, "h");
  87.       System.out.println("Tree view:");
  88.       System.out.print(tree);
  89.       System.out.println("Elements in order:");
  90.       for (int i = 0; i < tree.size(); i++)
  91.          System.out.println(i + ": " + tree.get(i));
  92.    }
  93. }
Success #stdin #stdout 0.09s 28172KB
comments (?)
stdin 
Standard input is empty
stdout 
Tree view:
 X: a
    L: b
       L: f
       R: c
          L: e
          R: d
    R: g
       R: h
Elements in order:
0: f
1: b
2: e
3: c
4: d
5: a
6: g
7: h
https://ideone.com/EsjvZW
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!