4
\$\begingroup\$

I have implemented a data structure that allows storage of number of users of a hypothetical application in a tree-like data structure in nodes as per their classification based on categories such as Gender or Country which have specific values such as Male and Female and India, China and USA respectively. The requirements of the data structure are that it should be able have fast access to the number of users for a particular classification and also be able to reorder.

Reordering accepts 2 parameters which indicate the indices of categories which need to be swapped (exchange nodes of one level of the tree-like structure with nodes of another level).

I am looking for suggestions to improve my code in terms of efficiency, organization and reduction of warnings.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.EnumMap;
import java.util.Random;

import interviews.ReorderableDS.Category;

public class ReorderableDS<M extends Enum<M> & Category> {

    public interface Category {
    }

    private enum Gender implements Category {
        Male, Female;
    }

    private enum Country implements Category {
        India, China, USA;
    }

    public enum MaritalStatus implements Category {
        Single, Married;
    }

    public class User {
        public Gender g;
        public Country c;
        public MaritalStatus m;

        public User() {
            super();
            this.g = (Gender) generateUserInfo(Gender.values());
            this.c = (Country) generateUserInfo(Country.values());
            this.m = (MaritalStatus) generateUserInfo(MaritalStatus.values());
        }
    }

    private Category generateUserInfo(Category[] category) {
        return category[new Random().nextInt(category.length - 1)];
    }

    private class Node {
        Class<M> classType;
        EnumMap<M, Node> children;
        long count;

        public Node(Class<M> classType) {
            super();
            this.classType = classType;
            this.count = 0;
        }
    }

    Node root;

    final ArrayList<Class<M>> classOrder;

    public ReorderableDS(Class<M>... classes) {
        super();
        classOrder = new ArrayList<Class<M>>(Arrays.asList(classes));
        root = new Node(classOrder.get(0));
    }

    public ReorderableDS(ArrayList<Class<M>> classOrder) {
        super();
        this.classOrder = classOrder;
        root = new Node(classOrder.get(0));
    }

    private ReorderableDS<M> reorder(int index1, int index2) {
        ArrayList<Class<M>> newClassOrder = (ArrayList<Class<M>>) this.classOrder.clone();
        Class<M> class1 = newClassOrder.get(index1);
        newClassOrder.set(index1, newClassOrder.get(index2));
        newClassOrder.set(index2, class1);
        ReorderableDS<M> reorderedDS = new ReorderableDS<M>(newClassOrder);
        Node temp = this.root;
        performDFS(temp, reorderedDS, new User());
        return reorderedDS;
    }

    private void performDFS(Node temp, ReorderableDS<M> reorderedDS, User user) {
        if (temp.children == null) {
            reorderedDS.insertUser(user, temp.count);
            return;
        }
        for (Enum<M> next : temp.children.keySet()) {
            setUserInfo(next, user);
            performDFS(temp.children.get(next), reorderedDS, user);
        }
    }

    private void setUserInfo(Enum<M> next, User user) {
        if (next instanceof Country) {
            user.c = (Country) next;
        } else if (next instanceof MaritalStatus) {
            user.m = (MaritalStatus) next;
        } else if (next instanceof Gender) {
            user.g = (Gender) next;
        }
    }

    public void insertRandomUser() {
        insertUser(new User(), 1);
    }

    public void insertUser(User user, long userCount) {
        Node curNode = root;
        for (int i = 0; i < classOrder.size(); i++) {
            Category userCat = getRelevantField(classOrder.get(i), user);
            if (userCat != null) {
                curNode.count += userCount;
                if (i != classOrder.size() - 1) {
                    if (curNode.children == null) {
                        curNode.children = new EnumMap<M, Node>(classOrder.get(i));
                    }
                    if (!curNode.children.containsKey(userCat)) {
                        curNode.children.put((M) userCat, new Node(classOrder.get(i + 1)));
                    }
                    curNode = curNode.children.get(userCat);
                }

            }
        }

    }

    private Category getRelevantField(Class<M> classType, User user) {
        if (classType.equals(user.c.getClass())) {
            return user.c;
        } else if (classType.equals(user.m.getClass())) {
            return user.m;
        } else if (classType.equals(user.g.getClass())) {
            return user.g;
        }
        return null;
    }

    public static void main(String args[]) {
        ReorderableDS<?> datastruct = new ReorderableDS(Country.class, Gender.class, MaritalStatus.class);
        datastruct.insertRandomUser();
        datastruct.insertRandomUser();
        datastruct.insertRandomUser();
        datastruct.insertRandomUser();
        datastruct.insertRandomUser();
        datastruct.insertRandomUser();

        ReorderableDS<?> datatstruct2 = datastruct.reorder(0, datastruct.classOrder.size() - 1);
    }
}
\$\endgroup\$
  • \$\begingroup\$ I'm looking at your code, now. At basic level, its format is rather clean. Looking at OOP: compartmentalization is a big issue (non-existent) and testing code resides inside the class, which hides the fact that it's unusable as-is. At an even higher level, I need to know how you plan to use this (i.e. read the data structure). There is no getUser() or iterateUsers() at all... I think you mean to have a series of instances, that can be classified by their fields in a tree. is 'performDFS' supposed to perform a Depth-First-Search? Where is the Node tree initialisation? \$\endgroup\$ – MrBrushy Dec 16 '16 at 15:16
  • \$\begingroup\$ Why does the structure have to be reordered? This seems wasteful as ordered iteration or reordering during display makes much more sense to me. \$\endgroup\$ – Emily L. Mar 19 '17 at 15:35
  • \$\begingroup\$ Hi Emily, this was just a question posed to me by someone I knew that I worked on. I do agree ordered iteration would be fast. \$\endgroup\$ – Dhruva Bharadwaj Mar 20 '17 at 0:51
1
\$\begingroup\$

I liked the idea of dynamic, controlled classification of a bunch of objects.

So I went through your code, so here we go.

This is buggy

First off, the Tree implementation wasn't one, I had to fix that.

Second, your data structure did not actually store the objects, just a count. So if they had non-enum or non-classified fields, this uniqueness was lost as the reference was never kept. I you intend to only have Enum fields, it could have worked, but not with your implementation (another bug).

Your data structure had no way to read its content. I added a search and a count methods because you stated:

The requirements of the data structure are that it should be able have fast access to the number of users for a particular classification and also be able to reorder.

So I also fixed the reorder, which did not work. It's still very naive (I brute forced it), so it certainly can be improved. But it now works.

In the future, refrain from posting code that you haven't tested thoroughly.

Several important notes:

  • I renamed the class to Classifier. That's what it actually does, the reordering is icing on the cake.
  • The parameter <M> is :
    • Poorly named (use T for anything, E for Enums, K for keys... even CAT for Category is short and easy to read)
    • Useless because it tries to put a redundant bound on the Category types, which is never used anywhere (no method do M.doSomethingSpecial()). Instead, I used a T for stored Object type, which was missing (!)
  • You had restricted the Classifier types to be Enums. Makes sense if you want to generate the full tree immediately. But you failed that tree structure, and also I chose to initiate the tree lazily (only when you add objects which require a new branch). That means the requirement for having enum-only Categories could be dropped, so I did. Now anything can be a classifier!
  • OOP-wise, you do not encapsulate objects and their methods correctly. The Node object is method-less, with public fields. This is bad, I made the Node objects more OOP. Added inheritance for Branch/Leaf, though that was optional I suppose.
  • Always store higher-level types whenever you can. List instead of ArrayList, Map instead of HashMap - though for your enumMap that was useful.
  • There is no input checking. I added a few exception for that.
  • A few Generic methods were wrong (setUserInfo needed casting because generateUserInfo didn't use Generics properly.)
  • Loggers are missing, use one, wherever I left e.printStackTrace()
  • Added very basic Javadoc, you must improve that at least on public methods.
  • I used a touch of Java8 streams to compile sub-node results. A good 1-liner, that always works because backed by a powerful API.

I still have an eclipse warning:

Type safety: Potential heap pollution via varargs parameter classes

But it should be fine. Don't know how to make it disappear.

My take on it:

I added a few comments as well, read them if you can.

(The internal tree classes are not in their own file, that is on purpose: they are not static, so they inherit the parameter <T>. Otherwise, always split in as many files as you can.)

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.stream.Collectors;

/** This class bundles Objects by their field's category.
 * @param <T> the Object to be stored */
public class Classifier<T> {

    /** Any Field implementing this Interface can become a filter {@link Category} for the  {@link Classifier}. */
    public interface Category { }

    /** Abstract Tree node type. Can {@link Node#add(List, Object)}, {@link Node#search(List)} and {@link Node#count(List)} some Items.*/
    private abstract class Node {
        protected long count; // Made private
        public Node() {
            super();
            this.count = 0;
        }
        public abstract void add(List<Class<? extends Category>> classHierarchy, T item);
        protected abstract List<T> search(List<? extends Category> criteria);
        protected abstract long count(List<? extends Category> criteria);
    }

    /** Tree Branch. Does not store anything, all data is in a {@link Leaf} further down.*/
    private class Branch extends Node {

        protected final Class<? extends Category> classType; // Made private
        private Map<Category, Node> children = new HashMap<>(); // Made private, made general (map)

        public Branch(Class<? extends Category> class1) {
            super();
            this.classType = class1;
        }

        public Branch(List<Class<? extends Category>> classHierarchy, T item) {
            super();
            this.classType = classHierarchy.get(0);
            List<Class<? extends Category>> downstreamCategories = new ArrayList<>(classHierarchy);
            downstreamCategories.remove(0);
            Category fieldValue = getRelevantField(classType, item);
            final Node child;
            if(downstreamCategories.isEmpty()){
                child = new Leaf(item);
            }else{
                child = new Branch(downstreamCategories, item);
            }
            children.put(fieldValue, child);
            count++;
        }

        public void add(List<Class<? extends Category>> classHierarchy, T item){
            Class<? extends Category> filterCat = classHierarchy.remove(0);
            Category field = getRelevantField(filterCat, item);
            if(children.containsKey(field)){
                children.get(field).add(classHierarchy, item);
            }else{
                if(classHierarchy.isEmpty()){ // No more classifiers to apply
                    children.put(field, new Leaf(item));
                } else {
                    children.put(field, new Branch(classHierarchy, item));
                }
            }
            count++;
        }

        protected List<T> search(List<? extends Category> criteria) {
            // Locate a criteria of the class that this node handles
            for(Category criterion: criteria){
                if(this.classType.isInstance(criterion)){
                    // This node handles this Criteria Class
                    Node matchingChild = children.get(criterion);
                    if(matchingChild != null){
                        // This criteria *instance* is known: we can dive down the tree
                        List<? extends Category> remainingCriteria = new ArrayList<>(criteria);
                        remainingCriteria.remove(criterion);
                        return matchingChild.search(remainingCriteria);
                    }else{
                        // The criteria *instance* has no matching key. There can be no results down this node
                        return new ArrayList<>();
                    }
                }
            }
            // This node does not filter any requested criteria class. All subnodes are equally valid.
            // Let's merge the result of all the subnodes!
            return children.values().stream().flatMap(node -> node.search(criteria).stream()).collect(Collectors.toList());
        }

        protected long count(List<? extends Category> criteria) {
            // Locate a criteria of the class that this node handles
            for(Category criterion: criteria){
                if(this.classType.isInstance(criterion)){
                    // This node handles this Criteria Class
                    Node matchingChild = children.get(criterion);
                    if(matchingChild != null){
                        // This criteria *instance* is known: we can dive down the tree
                        List<? extends Category> remainingCriteria = new ArrayList<>(criteria);
                        remainingCriteria.remove(criterion);
                        return matchingChild.count(remainingCriteria);
                    }else{
                        // The criteria *instance* has no matching key. There can be no results down this node
                        return 0;
                    }
                }
            }
            // This node does not filter any requested criteria class. All subnodes are equally valid.
            // Let's add the result of all the subnodes!
            return children.values().stream().collect(Collectors.summingLong(node -> node.count(criteria)));
        }
    }

    /** Tree Leaf. Stores all objects sharing the same Categories. */
    private class Leaf extends Node {
        List<T> storedItems = new ArrayList<>();
        public Leaf(T item) {
            super();
            storedItems.add(item);
        }
        public void add(List<Class<? extends Category>> classHierarchy, T item){
            storedItems.add(item);
        }
        protected List<T> search(List<? extends Category> criteria) {
            return storedItems;
        }
        @Override
        protected long count(List<? extends Category> criteria) {
            return count; // everyone here is a match
        }
    }

    private Node root; // Initialized at first insertion
    final List<Class<? extends Category>> classOrder;

    /** Builds a Classifier, using fields of the provided Category classes. The parameters order defines the classification priority.<br>
     * <i>Note: Only the first Field of the class will be used in the classification.</i> */
    public Classifier(Class<? extends Category>... classes) {
        super();
        classOrder = new ArrayList<Class<? extends Category>>();
        for(Class<? extends Category> toAdd: classes){
            classOrder.add(toAdd);
        }
    }

    /** Builds a Classifier, using fields of the provided Category classes. The {@link List} order defines the classification priority.<br>
     * <i>Note: Only the first Field of the class will be used in the classification.</i> */
    public Classifier(List<Class<? extends Category>> classOrder) {
        super();
        this.classOrder = new ArrayList<>(classOrder);
    }

    /** Creates a Classifier instance containing the same data, but with swapped classification order. */
    public Classifier<T> reorder(int index1, int index2) {
        if(index1 <0 || index2 <0 || index1 >= classOrder.size() || index2 >=classOrder.size() || index1 == index2){
            throw new IllegalArgumentException("The swapped indices (" + index1 + ", " + index2 + ") must be different, and each in the range [0, " + (classOrder.size()-1) + "]");
        }
        List<Class<? extends Category>> newClassOrder = new ArrayList<>(this.classOrder); // Don't use clone, Oracle messed this method up. This is a shallow copy, make it clear
        // Much clearer if you use source data when swapping, not the data you're currently modifying
        newClassOrder.set(index1, classOrder.get(index2));
        newClassOrder.set(index2, classOrder.get(index1));
        Classifier<T> reorderedClassifier = new Classifier<T>(newClassOrder);
        if(root != null){
            // Very bad solution (TEMPORARY): take all elements, and insert them in the new classifier
            // (a much better solution would be to reorganize the Nodes tree in place, and not return a new Classifier object)
            // But tree reordering are tricky, and I was lazy
            List<T> contents = root.search(new ArrayList<>()); // returns EVERYTHING
            for(T elem: contents){
                reorderedClassifier.insert(elem);
            }
        }
        return reorderedClassifier;
    }

    /** Inserts an Item in this Classifier. */
    public void insert(T item) {
        if(item == null){
            throw new IllegalArgumentException("The input Item must not be null");
        }
        if(root == null){
            root = new Branch(classOrder.get(0));
        }
        root.add(new ArrayList<>(classOrder), item); // Copy the classOrder it'll be mutated there
    }

    /** Returns all items that correspond the input category filters.*/
    public List<T> search(Category... searchCriteria){
        if(root==null){
            return new ArrayList<>();
        }else{
            List<? extends Category> criteriaAsList = searchCriteria == null ? new ArrayList<>() : Arrays.asList(searchCriteria);
            return root.search(criteriaAsList);
        }
    }

    /** Counts all items that correspond the input category filters.*/
    public long count(Category... searchCriteria){
        if(root==null || searchCriteria == null){
            return 0;
        }else{
            List<? extends Category> criteriaAsList = Arrays.asList(searchCriteria);
            return root.count(criteriaAsList);
        }
    }

    /** Counts all items.*/
    public long total(){
        return root == null ? 0: root.count;
    }

    private Category getRelevantField(Class<? extends Category> classType, T item) { // Was BAD! hardcoded= not extensible. Instead, I used reflection
        Field[] fields = item.getClass().getFields();
        for(Field field: fields){
            Class<?> fieldClass = field.getType();
            if(fieldClass.equals(classType)){
                try {
                    return (Category)field.get(item);
                } catch (IllegalArgumentException | IllegalAccessException e) {
                    // Very bad code! Handle it with a proper logger please
                    e.printStackTrace();
                }
            }
        }
        throw new IllegalArgumentException("The input item "+ item + " does not contain a Field of type " + classType.getTypeName());
    }
}

Now for the testing framework.

First off, you should have declared it in a different class, because the test uses internal data. You can't fiddle with the internals for testing, that's not how testing is done. You must put yourself in a user's perspective. Read up on proper testing methodology.

If you had put it in its own file, you'd have seen this class did not provide a way to interact correctly.

I only made asserts in a main, but you should make proper unit tests.

When generating a random number, you don't need the size -1 in return category[new Random().nextInt(category.length - 1)];

When generating random numbers, you should reuse a global Random variable, otherwise all you users can be identical.

/** TEST  class */
public static class User {

    private static enum Gender implements Category {
        MALE, FEMALE;
    }

    private static enum Country implements Category {
        INDIA, CHINA, USA;
    }

    public static enum MaritalStatus implements Category {
        SINGLE, MARRIED;
    }

    private static final Random RAND = new Random(); // This must be global. Otherwise you could be generating users with the same fields! Read up on Pseudo-Random Number Generators
    public Gender g;
    public Country c;
    public MaritalStatus m; // These are enums, but can now be anything like a String name!

    public User(Gender gender, Country country, MaritalStatus status) {
        super();
        this.g = gender;
        this.c = country;
        this.m = status;
    }

    public static User randomUser(){
        return new User(
            randomUserInfo(Gender.values()), // No Casting!
                randomUserInfo(Country.values()), // No Casting!
                randomUserInfo(MaritalStatus.values()) // No Casting!
                );
    }

    private static <T extends Category> T randomUserInfo(T[] category) { // Generics! They are good for you
        return category[RAND.nextInt(category.length)]; // No need for length-1 !
    }

    public static void main(String args[]) {
        Classifier<User> datastruct = new Classifier<User>(Country.class, Gender.class, MaritalStatus.class);
        for(int i=0; i< 20; i++){
            datastruct.insert( User.randomUser());
        }
        List<User> chineseFemale = datastruct.search(Country.CHINA, Gender.FEMALE);
        List<User> anyMale = datastruct.search(Gender.MALE);
        List<User> femaleSingles = datastruct.search(Gender.FEMALE, MaritalStatus.SINGLE);
        long femaleSinglesCount = datastruct.count(Gender.FEMALE, MaritalStatus.SINGLE);
        assert femaleSingles.size() == femaleSinglesCount;
        Classifier<User> datastruct2 = datastruct.reorder(0, 2); // Can't use classorder, it is some internal state, NOT to be shared outside!
        assert datastruct2.total() == datastruct.total();
    }
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks Sylvain for the this reply. Although I had not initially planned for saving the actual users (or T) I find what I learned from your reply quite valuable. I'm actually quite interested in the efficient reordering of the nodes and I'm wondering whether in place reording of nodes is even possible, since the in-degrees and the out-degrees of the new branch nodes in the data structure would be different \$\endgroup\$ – Dhruva Bharadwaj Mar 20 '17 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.