Блог

Если быть точным, я пытаюсь сгладить дерево и застрял в попытке получить значения частных атрибутов в универсальном классе с помощью универсальной функции.

Я прикрепил классы, чтобы показать, как именно структурировано дерево. Но это выглядит примерно так:

   /|
 1 | 6
  /|
 5 4 9
  

Я собираюсь вставить свою попытку в конце. Сначала позвольте мне представить классы:

Triple просто хранит три значения одного и того же типа.

 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; }
}
  

Простой интерфейс:

 public interface Function<P, R> {
     R apply(P p);
}
  

Теперь, для сложного класса. Это просто тип, который хранит один из двух типов значений, но не оба.

 public class EitherOr<A,B> {
    // Constructs a left-type EitherOr
    public static <A> EitherOr left(A a) {
         return new EitherOr(a, null);
    }
    // Constructs a right-type EitherOr
    public static <B> EitherOr right(B b) {
         return new EitherOr(null, b);
    }
    private final A 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;
    }
}
  

Я знаю, что это становится долгим, но потерпите меня. Этот класс реализует древовидную структуру.

 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);
         }
    }
}
  

Хорошо. Вот моя идея для сглаживания:

 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();
          // it is a leaf
          if (EitherOr.isLeft()) {
               // This is where the problem lies
               // I don't how to get the value using a function f
               list.add((T) EitherOr.ifLeft(f));
               return list;
          }
          else {
               // basically recursively go through the tree somehow
          }
          return null;
    }
}
  

Как я уже сказал, я застрял в попытке восстановить значение в классе EitherOr с помощью интерфейса функции. Я подумываю о реализации интерфейса функции и написании функции для «apply», которая просто получает значение, но я не уверен, как это сделать. Любая помощь будет оценена. Спасибо!

Итак, вот ваш flattenInOrder метод:

 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);
}
  

Довольно просто, предполагая, что:

• ifLeftFunction выдает один элемент (поскольку EitherOr<T, Triple<Tree<T>>> имеет один T элемент, если он «левый»)

… и:

• ifRightFunction выдает коллекцию элементов (поскольку EitherOr<T, Triple<Tree<T>>> имеет список T элементов, если он «правильный»)

Давайте теперь рассмотрим эти функции:

ifLeftFunction является … базовым. Я хочу извлечь a T из … a T .

 final Function<T, T> ifLeftFunction = new Function<T, T>() {

    @Override
    public T apply(final T t) {
        return t;
    }
};
  

ifRightFunction немного сложнее: он должен быть рекурсивным и собирать все T s из просматриваемого дерева:

 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;
    }
};
  

И … готово!

Пример рабочего кода:

 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);
    }
}
  

Обратите внимание, что я создаю именно Tree то, что вы показываете в качестве примера в вашем вопросе в main методе здесь:

 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));
}
  

Вывод: [1, 5, 4, 9, 6]

Приветствия 😉