lundi 28 novembre 2016

Empty Object Pruner Algorithm

My assignment is to write a Java algorithm for setting to NULL objects that are "empty," defined as having all-NULL data members. It should be a recursive algorithm because nested sub-objects should be checked. Reflection will be used to iterate over the object and check its structure.

E.g. suppose the structure of my top-level Java object is, with all subobjects constructed:

TopLevel
   |--Boolean
   |--String
   |--CustomLevel2
         |--String
         |--CustomLevel3
                |--CustomLevel4
                      |--String
                      |--String

Now suppose CustomLevel4 contains [null,null] for its 2 strings. In this case, CustomLevel3's object customLevel4 should be set to NULL -- we've in effect "pruned" the extraneous all-empty CustomLevel4 data member.

My understanding of this problem is, the 2 BASE cases of this recursive problem are:

  • We've reached an all-NULL object; stop, and set the parent reference to NULL.
  • We've reached an all-"Base" object (no complex objects, all-Leaves); stop.

I wrote this code, which seems to work in my test above. But am I missing something in this algorithm, or does it look correct?

// Define our "Base" Leaves
private static final List LEAVES = Arrays.asList(
        Boolean.class, Character.class, Byte.class, Short.class,
        Integer.class, Long.class, Float.class, Double.class, Void.class,
        String.class, 
        List.class, Map.class, Set.class);  // Also add collections as leaves  


// 1. Utility Method 1: Tells us whether this is an all-NULL object
// ----------------------------------------------------------------
private static boolean allFieldsNull(Field[] fields, Object o) throws Exception
{
   for (Field field : fields)
   {
        field.setAccessible(true);
        if (field.get(o) != null)
            return false;
   }
   return true;
}


// 2. Main Recursive Method  
// ------------------------      
private static boolean traverseNonBaseClassObjects(Object o) throws Exception
{

   Field[] fields = o.getClass().getDeclaredFields();

   System.out.println("Traversing: " + o.getClass().getName()); 

   if (allFieldsNull(fields, o))
   {
       // End recursion - reached an all-NULL field, return TRUE
       System.out.println("Ending traversal of " + o.getClass().getName() + " - it's an all-NULL obj, setting parent ref to NULL");
       return true;
   }
   else
   {       
        boolean nonBaseClassObjectsFound = false;
        for (Field field : fields)
        {
            field.setAccessible(true);
            if (!LEAVES.contains(field.getType()))
            {
                nonBaseClassObjectsFound = true;
                // Recurse
                if (traverseNonBaseClassObjects(field.get(o)))
                {
                    // Set this parent reference to NULL (prune)
                    field.set(o, null);
                }
            }
        }

        if (!nonBaseClassObjectsFound)
            System.out.println("Ending traversal of " + o.getClass().getName() + " - it's an all-Leaf object");
        return false;
   }

}

I start this program by invoking the recursive method on the top-level object. I've only checked 1 case so far, which is shown above, but I haven't tested any other ones, just wanted to confirm the correctness first.

traverseNonBaseClassObjects(topLevel);





Aucun commentaire:

Enregistrer un commentaire