oop - Tree traversal in Java with Generic classes -

to precise, trying flatten tree , stuck on trying values of private attributes in generic class using generic function.

i have attached classes show how tree structured exactly. it's looks this:

  /|\  1 | 6   /|\  5 4 9 

i going paste attempt @ end. first, let me introduce classes:

triple stores 3 values of same type.

public class triple<v> {     private final v l, m, r;     public triple(v l, v m, v r) {         this.l = l;         this.m = m;         this.r = r;     }     public v left()   { return l; }     public v middle() { return m; }     public v right()  { return r; } } 

straightforward interface:

public interface function<p, r> {      r apply(p p); } 

now, tricky class. 1 type stores 1 of eitheror of 2 types of value, not both.

public class eitheror<a,b> {     // constructs left-type eitheror     public static <a> eitheror left(a a) {          return new eitheror(a, null);     }     // constructs right-type eitheror     public static <b> eitheror right(b b) {          return new eitheror(null, b);     }     private final a;     private final b b;      private eitheror(a a, b b) {          this.a = a; this.b = b;     }      public<t> t ifleft(function<a,t> f) {         return f.apply(a);     }  public<t> t ifright(function<b,t> f) {         return f.apply(b);     }      public boolean isleft() {         return b == null;     } } 

i know getting long, bear me. class implements tree structure.

public interface tree<t> {     eitheror<t, triple<tree<t>>> get();      static final class leaf<t> implements tree<t> {            public static <t> leaf<t> leaf (t value) {                 return new leaf<t>(value);            }             private final t t;             public leaf(t t) { this.t = t; }             @override            public eitheror<t, triple<tree<t>>> get() {                  return eitheror.left(t);            }     }      static final class node<t> implements tree<t> {          public static <t> tree<t> tree (t left, t middle, t right) {              return new node<t>(leaf.leaf(left), leaf.leaf(middle), leaf.leaf(right));      }           private final triple<tree<t>> branches;           public node(tree<t> left, tree<t> middle, tree<t> right) {                this.branches = new triple<tree<t>>(left, middle, right);          }           @override          public eitheror<t, triple<tree<t>>> get() {                  return eitheror.right(branches);          }     } } 

alright. here idea flattening:

public class myflattentree<t> implements flattentree<t> {     public list<t> flatteninorder(tree<t> tree) {           list<t> list = new arraylist<t>();           eitheror<t, triple<tree<t>>> eitheror;           eitheror = tree.get();           // leaf           if (eitheror.isleft()) {                // problem lies                // don't how value using function f                list.add((t) eitheror.ifleft(f));                return list;           }           else {                // recursively go through tree somehow           }           return null;     } } 

as said, stuck trying retreive value in eitheror class using function interface. thinking of implementing function interface , write function "apply" gets value, not sure how that. appreciated. thanks!

so, here flatteninorder method:

public list<t> flatteninorder(final tree<t> tree) {     final eitheror<t, triple<tree<t>>> eitheror = tree.get();     if (eitheror.isleft()) {         return collections.singletonlist(eitheror.ifleft(this.ifleftfunction));     }      return eitheror.ifright(this.ifrightfunction); } 

quite simple, assuming that:

• ifleftfunction yields single element (since eitheror<t, triple<tree<t>>> has single t elem' if s "left")

... and:

• ifrightfunction yields collection of elements (since eitheror<t, triple<tree<t>>> has list of t elems' if "right")

---

let's these functions now:

ifleftfunction is... basic. want extract t from... t.

final function<t, t> ifleftfunction = new function<t, t>() {      @override     public t apply(final t t) {         return t;     } }; 

ifrightfunction more complex: has recursive , collect ts tree it's browsing:

final function<triple<tree<t>>, list<t>> ifrightfunction = new function<triple<tree<t>>, list<t>>() {      @override     public list<t> apply(final triple<tree<t>> t) {         final list<t> res = new arraylist<>();         res.addall(myflattentree.this.flatteninorder(t.left()));         res.addall(myflattentree.this.flatteninorder(t.middle()));         res.addall(myflattentree.this.flatteninorder(t.right()));         return res;     } }; 

and... you're done!

---

sample working code:

public class myflattentree<t> {      private final function<triple<tree<t>>, list<t>> ifrightfunction = new function<triple<tree<t>>, list<t>>() {          @override         public list<t> apply(final triple<tree<t>> t) {             final list<t> res = new arraylist<>();             res.addall(myflattentree.this.flatteninorder(t.left()));             res.addall(myflattentree.this.flatteninorder(t.middle()));             res.addall(myflattentree.this.flatteninorder(t.right()));             return res;         }     };      private final function<t, t> ifleftfunction = new function<t, t>() {          @override         public t apply(final t t) {             return t;         }     };      public static void main(final string[] args) {         final tree<string> tree = new node<>(new leaf<>("1"), new node<>(new leaf<>("5"), new leaf<>("4"), new leaf<>("9")), new leaf<>("6"));         system.out.println(new myflattentree<string>().flatteninorder(tree));     }      public list<t> flatteninorder(final tree<t> tree) {         final eitheror<t, triple<tree<t>>> eitheror = tree.get();         if (eitheror.isleft()) {             return collections.singletonlist(eitheror.ifleft(this.ifleftfunction));         }          return eitheror.ifright(this.ifrightfunction);     } } 

note i'm creating exact tree you're featuring example in question in main method here:

public static void main(final string[] args) {     final tree<string> tree = new node<>(new leaf<>("1"), new node<>(new leaf<>("5"), new leaf<>("4"), new leaf<>("9")), new leaf<>("6"));     system.out.println(new myflattentree<string>().flatteninorder(tree)); } 

output: [1, 5, 4, 9, 6]

---

cheers ;)