Monthly Archives: April 2014

Two ways to avoid a large amount of similar sub-classes

A question on stackoverflow, which I’ve edited:

Is it bad OOP practice to subclass MANY classes from a base class?

Is it is bad practice in Object Oriented Design to subclass multiple classes from a single base class?

Say for instance you are designing a game and you have several different monsters you might come across. The approach I would take is to have a base abstract class for just a general monster object and then subclass all of the specific types of monsters from the base class using a new class.

One of my instructors told me that you shouldn't rely on inheritance in this case because the number of monsters will continue to grow and grow and the number of classes will increase to a point where it is hard to keep track of all of them and thus you will have to recompile the program with every new class added in the future.

My answer:

If monsters are very similar, in that the only differences are (for example) their name, how much damage they impart, what color they are, etc., then these differences which can be reflected in a field (in values), may make sub-classing unnecessary.

If, however, you have monsters that are fundamentally different from others, such that it is necessary to have very different methods and logic, and more specifically, differences that cannot be reflected in fields, then a sub-class SpecialMonster may be necessary.

But again, even SpecialMonster may not need to be sub-classed by individual monster types, as it’s fields may be enough to distinguish between them.

While it’s legal to have a million sub-classes of specific monster types, you don’t want to take care of all that duplicate code when it could simply be expressed in the fields of new Monster instances, such as

new Monster("Goob", WakeTime.NOCTURNAL, 35, new Weapon[]{sword, hammer, knittingNeedle});
new Monster("Mister Mxyzptlk", WakeTime.ANYTIME, 71, new Weapon[]{sword, mindMeld, cardboardCutter});

There is an alternative, where you do have a lot of classes, but you don’t impose them onto your users, and you don’t clutter up your API/JavaDoc with them. If your Monster happens to be an abstract class

public abstract class Monster  {
   private final String name;
   ...
   public Monster(String name, int default_damage, WakeTime wake_time, Weapon[] weapons)  {
      this.name = name;
      ...
   }
   public String getName()  {
      return  name;
   }
   ...
   public abstract int getDamage(int hit_strength);
}

Then you could have a Monster convenience creator like this:

/**
  <P>Convenience functions for creating new monsters of a specific type.</P>
 **/
public class NewMonsterOfType  {
  private NewMonsterOfType()  {
     throw  new IllegalStateException("Do not instantiate.");
  }
  /**
     <P>Creates a new monster that is nocturnal, has 35-default-damage, and whose weapens are: sword, hammer, knittingNeedle.</P>
   **/
  public static final GOOB = new GoobMonster();
  /**
     <P>Creates a new monster that can be awake at any time, has 71-default-damage, and whose weapens are: sword, mindMeld, cardboardCutter.</P>
   **/
  public static final MISTER_MXYZPTLK = new MisterMxyzptlkMonster();
}
class GoobMonster extends Monster  {
  public GoobMonster()  {
     super("Goob", WakeTime.NOCTURNAL, 35, new Weapon[]{sword, hammer, knittingNeedle});
  }
   public int getDamage(int hit_strength)  {
     return  (hit_strength < 70) ? getDefaultDamage() : (getDefaultDamage() * 2);
  }
}
class MisterMxyzptlkMonster extends Monster  {
  public GoobMonster()  {
     super("Mister Mxyzptlk", WakeTime.ANYTIME, 71, new Weapon[]{sword, mindMeld, cardboardCutter});
  }
   public int getDamage(int hit_strength)  {
     return  (hit_strength < 160) ? getDefaultDamage() + 10 : (getDefaultDamage() * 3);
  }
}

In order for these private (actually package-protected) classes to not show up in you JavaDoc, you need to set its access to something either protected or public.

How to do “indexOf” and “lastIndexOf” on an integer with bit flags? (Get the *power* of the found index)

This is a self-answered question I posted on stackoverflow, and is a follow up on my previous question on bit flags, where I cleared up some big misconceptions.

I need to create these functions to find a single bit-flag in an int containing zero or more flags:

BitBinaryUtil
   int twoExponentOfHighestOneBit(int all_flags)

   int twoExponentOfHighestOneBitAtMost(int all_flags,
         int twoExponentOfTwo_max0Thr30Incl)

   int twoExponentOfLowestOneBit(int all_flags)

   int twoExponentOfLowestOneBitAtLeast(int all_flags,
         int twoExponentOfTwo_min0Thr30Incl)

Which are roughly similar to `String.indexOf` and `lastIndexOf`, except they return the *exponent* of two of the found-bit. For example (all 31 bits)

twoExponentOfHighestOneBit:
   1000000000000000000000000000000  -->  30 (2^30=1073741824)
   0000000000000000000000000000001  -->  0  (2^0=1)
   0000000000000100000000000000001  -->  18
   0000000000000000000000000000000  -->  -1

twoExponentOfLowestOneBit:
   1000000000000000000000000000000  -->  30
   0000000000000000000000000000001  -->  0
   0000000000000100000000000000001  -->  0

How can I do this?

This was a brain buster. First, I figured it out with converting the ints to binary strings of length 31 (which is the limit of bit-flags as I understand it):

/**
  <P>Given a 31-bit binary-int, as a string (representing an int with zero or more bit-flags, where the most-significant-bit, the &quot;sign bit&quot;, is removed), get the <I>inverted</I> index of the first one-bit (if the left-most bit is a 1, 31 is the result).</P>

  <P>{@code java InvertedIndexOfHighestOneBitUsingBinaryStrings}</P>
 **/
public class InvertedIndexOfHighestOneBitUsingBinaryStrings  {
  public static final void main(String[] ignored)  {
     //One bit
        test("1000000000000000000000000000000");  //VALUE_OF_31ST_ONE_BIT
        test("0000100000000000000000000000000");
        test("0000000000000000000000000000010");
        test("0000000000000000000000000000000");

     //Two
        test("0110000000000000000000000000000");
        test("0000000000000000000000000000011");
  }
  private static final void test(String int_binStr)  {
     int i = Integer.parseInt(int_binStr, 2);
     System.out.println("31-bits: " + int_binStr + ", int: " + i);

     int exponent = getInvertedIndexHighestOneBit(int_binStr);
     System.out.println("      Highest one-bit is two-to-the-exponent-of: " + exponent);

     if(exponent != -1)  {
        exponent = getInvertedIndexHighestOneBit(int_binStr, (exponent - 1));
        System.out.println("      Next-highest one-bit is two-to-the-exponent-of: " + exponent);
     }
     System.out.println();
  }

Main logic:

  public static final int getInvertedIndexHighestOneBit(String all31Bits_zeroPadded)  {
     return  getInvertedIndexHighestOneBit(all31Bits_zeroPadded, 30);
  }
  public static final int getInvertedIndexHighestOneBit(String all31Bits_zeroPadded, int inverted_startIdx)  {
     int idxFirstOneBit = all31Bits_zeroPadded.indexOf("1", (30 - inverted_startIdx));
     if(idxFirstOneBit == -1)  {
        return  -1;
     }
     return  (30 - idxFirstOneBit);
  }
}

Output:

31-bits: 1000000000000000000000000000000, int: 1073741824
      Highest one-bit is two-to-the-exponent-of: 30
      Next-highest one-bit is two-to-the-exponent-of: -1

31-bits: 0000100000000000000000000000000, int: 67108864
      Highest one-bit is two-to-the-exponent-of: 26
      Next-highest one-bit is two-to-the-exponent-of: -1

31-bits: 0000000000000000000000000000010, int: 2
      Highest one-bit is two-to-the-exponent-of: 1
      Next-highest one-bit is two-to-the-exponent-of: -1

31-bits: 0000000000000000000000000000000, int: 0
      Highest one-bit is two-to-the-exponent-of: -1

31-bits: 0110000000000000000000000000000, int: 805306368
      Highest one-bit is two-to-the-exponent-of: 29
      Next-highest one-bit is two-to-the-exponent-of: 28

31-bits: 0000000000000000000000000000011, int: 3
      Highest one-bit is two-to-the-exponent-of: 1
      Next-highest one-bit is two-to-the-exponent-of: 0

And then I figured it out with bit-manipulation:

 /**
  <P>Given a 31-bit binary-int, as a string (representing an int with zero or more bit-flags, where the most-significant-bit, the &quot;sign bit&quot;, is removed), get the <I>inverted</I> index of the first one-bit (if the left-most bit is a 1, 31 is the result).</P>

  <P>{@code java InvertedIndexOfHighestOneBitUsingInts}</P>
  **/
 public class InvertedIndexOfHighestOneBitUsingInts  {
  public static final int VALUE_OF_31ST_ONE_BIT = Integer.parseInt("1000000000000000000000000000000", 2);
  public static final void main(String[] ignored)  {
     //One bit
        test(VALUE_OF_31ST_ONE_BIT);
        test(Integer.parseInt("0000100000000000000000000000000", 2));
        test(Integer.parseInt("0000000000000000000000000000010", 2));
        test(Integer.parseInt("0000000000000000000000000000000", 2));

     //Two
        test(Integer.parseInt("0110000000000000000000000000000", 2));
        test(Integer.parseInt("0000000000000000000000000000011", 2));
  }
  private static final void test(int num)  {
     System.out.println("Testing: 31-bit binary=" + getIntAsZeroPadded31BitStringNoSign(num) + ", int=" + num);
     int exponent = twoExponentOfHighestOneBit(num);
     System.out.println("   Highest one-bit is two-to-the-exponent-of: " + exponent);
     if(exponent > 0)  {
        System.out.println("   Next-highest one-bit is two-to-the-exponent-of: " + twoExponentOfHighestOneBitAtMost(num, (exponent - 1)));
     }

     exponent = twoExponentOfLowestOneBit(num);
     System.out.println("   Lowest one-bit is two-to-the-exponent-of: " + exponent);
     if(exponent != -1  &&  exponent < 30)  {
        System.out.println("   Next-highest one-bit is two-to-the-exponent-of: " + twoExponentOfLowestOneBitAtLeast(num, (exponent + 1)));
     }
     System.out.println();

  }

Main logic for highest:

  public static final int twoExponentOfHighestOneBit(int all_flags)  {
     return  twoExponentOfHighestOneBitAtMost(all_flags, 30);
  }
  public static final int twoExponentOfHighestOneBitAtMost(int all_flags, int twoExponentOfTwo_max0Thr30Incl)  {
     if(twoExponentOfTwo_max0Thr30Incl < 0  ||  twoExponentOfTwo_max0Thr30Incl > 30)  {
        throw  new IllegalArgumentException("twoExponentOfTwo_max0Thr30Incl (" + twoExponentOfTwo_max0Thr30Incl + ") must be between 1 and 31, inclusive");
     }

     //Index of first one bit:
     int currentBitMask = VALUE_OF_31ST_ONE_BIT >> (30 - twoExponentOfTwo_max0Thr30Incl);
     int exponent = twoExponentOfTwo_max0Thr30Incl;
     while(exponent >= 0)  {
 //System.out.println("   high.currentBitMask=" + getIntAsZeroPadded31BitStringNoSign(currentBitMask) + ", exponent=" + exponent + "");
 //System.out.println("   high.all_flags=     " + getIntAsZeroPadded31BitStringNoSign(all_flags));
        if((all_flags & currentBitMask) == currentBitMask)  {
           return  exponent;
        }
 //System.out.println();
        exponent--;
        currentBitMask >>= 1;
     }
     return  -1;
  }

Main logic for lowest:

  public static final int twoExponentOfLowestOneBit(int all_flags)  {
      return  twoExponentOfLowestOneBitAtLeast(all_flags, 0);
   }
   public static final int twoExponentOfLowestOneBitAtLeast(int all_flags, int twoExponentOfTwo_min0Thr30Incl)  {
      if(twoExponentOfTwo_min0Thr30Incl < 0  ||  twoExponentOfTwo_min0Thr30Incl > 30)  {
         throw  new IllegalArgumentException("twoExponentOfTwo_min0Thr30Incl (" + twoExponentOfTwo_min0Thr30Incl + ") must be between 1 and 30, inclusive.");
      }

      //Index of first one bit:
      int currentBitMask = 1 << twoExponentOfTwo_min0Thr30Incl;
      int exponent = twoExponentOfTwo_min0Thr30Incl;
      while(exponent <= 30)  {
  //System.out.println("   low.currentBitMask=" + getIntAsZeroPadded31BitStringNoSign(currentBitMask) + ", exponent=" + exponent + "");
  //System.out.println("   low.all_flags=     " + getIntAsZeroPadded31BitStringNoSign(all_flags));
         if((all_flags & currentBitMask) == currentBitMask)  {
            return  exponent;
         }
  //System.out.println();
         exponent++;
         currentBitMask <<= 1;
      }
      return  -1;
   }
   public static final String getIntAsZeroPadded31BitStringNoSign(int num)  {
      return  String.format("%32s", Integer.toBinaryString(num)).replace(' ', '0').substring(1, 32);
   }
}

Output:

Testing: 31-bit binary=1000000000000000000000000000000, int=1073741824
   Highest one-bit is two-to-the-exponent-of: 30
   Next-highest one-bit is two-to-the-exponent-of: -1
   Lowest one-bit is two-to-the-exponent-of: 30

Testing: 31-bit binary=0000100000000000000000000000000, int=67108864
   Highest one-bit is two-to-the-exponent-of: 26
   Next-highest one-bit is two-to-the-exponent-of: -1
   Lowest one-bit is two-to-the-exponent-of: 26
   Next-highest one-bit is two-to-the-exponent-of: -1

Testing: 31-bit binary=0000000000000000000000000000010, int=2
   Highest one-bit is two-to-the-exponent-of: 1
   Next-highest one-bit is two-to-the-exponent-of: -1
   Lowest one-bit is two-to-the-exponent-of: 1
   Next-highest one-bit is two-to-the-exponent-of: -1

Testing: 31-bit binary=0000000000000000000000000000000, int=0
   Highest one-bit is two-to-the-exponent-of: -1
   Lowest one-bit is two-to-the-exponent-of: -1

Testing: 31-bit binary=0110000000000000000000000000000, int=805306368
   Highest one-bit is two-to-the-exponent-of: 29
   Next-highest one-bit is two-to-the-exponent-of: 28
   Lowest one-bit is two-to-the-exponent-of: 28
   Next-highest one-bit is two-to-the-exponent-of: 29

Testing: 31-bit binary=0000000000000000000000000000011, int=3
   Highest one-bit is two-to-the-exponent-of: 1
   Next-highest one-bit is two-to-the-exponent-of: 0
   Lowest one-bit is two-to-the-exponent-of: 0
   Next-highest one-bit is two-to-the-exponent-of: 1

Full code:

/**
  <P>Given a 31-bit binary-int, as a string (representing an int with zero or more bit-flags, where the most-significant-bit, the &quot;sign bit&quot;, is removed), get the <I>inverted</I> index of the first one-bit (if the left-most bit is a 1, 31 is the result).</P>

  <P>{@code java InvertedIndexOfHighestOneBitUsingBinaryStrings}</P>
 **/
public class InvertedIndexOfHighestOneBitUsingBinaryStrings  {
  public static final void main(String[] ignored)  {
     //One bit
        test("1000000000000000000000000000000");  //VALUE_OF_31ST_ONE_BIT
        test("0000100000000000000000000000000");
        test("0000000000000000000000000000010");
        test("0000000000000000000000000000000");

     //Two
        test("0110000000000000000000000000000");
        test("0000000000000000000000000000011");
  }
  private static final void test(String int_binStr)  {
     int i = Integer.parseInt(int_binStr, 2);
     System.out.println("31-bits: " + int_binStr + ", int: " + i);

     int exponent = getInvertedIndexHighestOneBit(int_binStr);
     System.out.println("      Highest one-bit is two-to-the-exponent-of: " + exponent);

     if(exponent != -1)  {
        exponent = getInvertedIndexHighestOneBit(int_binStr, (exponent - 1));
        System.out.println("      Next-highest one-bit is two-to-the-exponent-of: " + exponent);
     }
     System.out.println();
  }
  public static final int getInvertedIndexHighestOneBit(String all31Bits_zeroPadded)  {
     return  getInvertedIndexHighestOneBit(all31Bits_zeroPadded, 30);
  }
  public static final int getInvertedIndexHighestOneBit(String all31Bits_zeroPadded, int inverted_startIdx)  {
     int idxFirstOneBit = all31Bits_zeroPadded.indexOf("1", (30 - inverted_startIdx));
     if(idxFirstOneBit == -1)  {
        return  -1;
     }
     return  (30 - idxFirstOneBit);
  }
}
 /**
  <P>Given a 31-bit binary-int, as a string (representing an int with zero or more bit-flags, where the most-significant-bit, the &quot;sign bit&quot;, is removed), get the <I>inverted</I> index of the first one-bit (if the left-most bit is a 1, 31 is the result).</P>

  <P>{@code java InvertedIndexOfHighestOneBitUsingInts}</P>
  **/
 public class InvertedIndexOfHighestOneBitUsingInts  {
  public static final int VALUE_OF_31ST_ONE_BIT = Integer.parseInt("1000000000000000000000000000000", 2);
  public static final void main(String[] ignored)  {
     //One bit
        test(VALUE_OF_31ST_ONE_BIT);
        test(Integer.parseInt("0000100000000000000000000000000", 2));
        test(Integer.parseInt("0000000000000000000000000000010", 2));
        test(Integer.parseInt("0000000000000000000000000000000", 2));

     //Two
        test(Integer.parseInt("0110000000000000000000000000000", 2));
        test(Integer.parseInt("0000000000000000000000000000011", 2));
  }
  private static final void test(int num)  {
     System.out.println("Testing: 31-bit binary=" + getIntAsZeroPadded31BitStringNoSign(num) + ", int=" + num);
     int exponent = twoExponentOfHighestOneBit(num);
     System.out.println("   Highest one-bit is two-to-the-exponent-of: " + exponent);
     if(exponent > 0)  {
        System.out.println("   Next-highest one-bit is two-to-the-exponent-of: " + twoExponentOfHighestOneBitAtMost(num, (exponent - 1)));
     }

     exponent = twoExponentOfLowestOneBit(num);
     System.out.println("   Lowest one-bit is two-to-the-exponent-of: " + exponent);
     if(exponent != -1  &&  exponent < 30)  {
        System.out.println("   Next-highest one-bit is two-to-the-exponent-of: " + twoExponentOfLowestOneBitAtLeast(num, (exponent + 1)));
     }
     System.out.println();

  }
  public static final int twoExponentOfHighestOneBit(int all_flags)  {
     return  twoExponentOfHighestOneBitAtMost(all_flags, 30);
  }
  public static final int twoExponentOfHighestOneBitAtMost(int all_flags, int twoExponentOfTwo_max0Thr30Incl)  {
     if(twoExponentOfTwo_max0Thr30Incl < 0  ||  twoExponentOfTwo_max0Thr30Incl > 30)  {
        throw  new IllegalArgumentException("twoExponentOfTwo_max0Thr30Incl (" + twoExponentOfTwo_max0Thr30Incl + ") must be between 1 and 31, inclusive");
     }

     //Index of first one bit:
     int currentBitMask = VALUE_OF_31ST_ONE_BIT >> (30 - twoExponentOfTwo_max0Thr30Incl);
     int exponent = twoExponentOfTwo_max0Thr30Incl;
     while(exponent >= 0)  {
 //System.out.println("   high.currentBitMask=" + getIntAsZeroPadded31BitStringNoSign(currentBitMask) + ", exponent=" + exponent + "");
 //System.out.println("   high.all_flags=     " + getIntAsZeroPadded31BitStringNoSign(all_flags));
        if((all_flags & currentBitMask) == currentBitMask)  {
           return  exponent;
        }
 //System.out.println();
        exponent--;
        currentBitMask >>= 1;
     }
     return  -1;
  }
  public static final int twoExponentOfLowestOneBit(int all_flags)  {
      return  twoExponentOfLowestOneBitAtLeast(all_flags, 0);
   }
   public static final int twoExponentOfLowestOneBitAtLeast(int all_flags, int twoExponentOfTwo_min0Thr30Incl)  {
      if(twoExponentOfTwo_min0Thr30Incl < 0  ||  twoExponentOfTwo_min0Thr30Incl > 30)  {
         throw  new IllegalArgumentException("twoExponentOfTwo_min0Thr30Incl (" + twoExponentOfTwo_min0Thr30Incl + ") must be between 1 and 30, inclusive.");
      }

      //Index of first one bit:
      int currentBitMask = 1 << twoExponentOfTwo_min0Thr30Incl;
      int exponent = twoExponentOfTwo_min0Thr30Incl;
      while(exponent <= 30)  {
  //System.out.println("   low.currentBitMask=" + getIntAsZeroPadded31BitStringNoSign(currentBitMask) + ", exponent=" + exponent + "");
  //System.out.println("   low.all_flags=     " + getIntAsZeroPadded31BitStringNoSign(all_flags));
         if((all_flags & currentBitMask) == currentBitMask)  {
            return  exponent;
         }
  //System.out.println();
         exponent++;
         currentBitMask <<= 1;
      }
      return  -1;
   }
   public static final String getIntAsZeroPadded31BitStringNoSign(int num)  {
      return  String.format("%32s", Integer.toBinaryString(num)).replace(' ', '0').substring(1, 32);
   }
}