Replace Implicit Tree with Composite


Prev	don't be afraid of buying books	Next

You implicitly form a tree structure, using a primitive representation, such as a String.

Replace your primitive representation with a Composite.

Motivation

Data or code forms an implicit tree when it's not explicitly structured as a tree but may be represented as a tree. For example, the code that creates the XML data in the previous code sketch outputs values like this:

 String expectedResult =   "<orders>" +     "<order id='321'>" +       "<product id='f1234' color='red' size='medium'>" +         "<price currency='USD'>" +           "8.95" +         "</price>" +         "Fire Truck" +       "</product>" +       "<product id='p1112' color='red'>" +         "<price currency='USD'>" +           "230.0" +         "</price>" +         "Toy Porshe Convertible" +       "</product>" +     "</order>" +   "</orders>";

The structure of this XML may be represented as the following tree.

Conditional logic can also form an implicit tree. Consider the conditional logic in the following code, which queries products from a repository:

 public class ProductFinder...   public List belowPriceAvoidingAColor(float price, Color color) {     List foundProducts = new ArrayList();     Iterator products = repository.iterator();     while (products.hasNext()) {       Product product = (Product) products.next();       if ( product.getPrice() < price && product.getColor() != color)         foundProducts.add(product);     }     return foundProducts;   }

The structure of this conditional logic may also be represented as a tree.

The implicit trees in these examples are different in nature, yet both may be modeled by using a Composite [DP]. What's the primary motivation for such a refactoring? To make the code simpler to work with and less bloated.

For example, producing XML as a Composite is simpler and requires less code when you don't have to repeatedly format and close tags: a Composite tag can do that work for you. Transforming the above conditional logic to a Composite has a similar motivation, with one twist: the refactoring makes sense only when there is a proliferation of similar conditional logic:

 public class ProductFinder...   public List byColor(Color color)...      if (product.getColor() == color)...   public List byColorAndBelowPrice(Color color, float price)...      if (product.getPrice() < price && product.getColor() == color)...   public List byColorAndAbovePrice(Color color, float price) {      if (product.getColor() == color && product.getPrice() > price)...   public List byColorSizeAndBelowPrice(Color color, int size, float price)...      if (product.getColor() == color &&          product.getSize() == size &&          product.getPrice() < price)...

The above methods may be generalized to a single query method by representing each product query as a Composite. Replace Implicit Language with Interpreter (269) documents this transformation, which includes the implementation of a Composite.

Data-based implicit trees, like the earlier XML example, suffer from a tight coupling between the code that builds the implicit tree and how the tree is represented. Refactoring to a Composite loosens this coupling; however, the resulting client code is then coupled to the Composite. Sometimes you need another level of indirection to loosen such coupling. For example, on one project client code sometimes needed a Composite for building XML and sometimes needed to produce XML via a DOM. This led to the refactoring Encapsulate Composite with Builder (96).

Implicit tree creation may be sufficient if your system doesn't create many trees or the trees are small and manageable. You can always refactor to a Composite when it becomes hard to work with your implicit trees or your code begins to bloat because of implicit tree construction. The choice may also involve where you are in the evolution of new code. On a recent project, I was tasked with generating an HTML page from XML data using an XSLT processor. For this task, I needed to generate XML that would be used in the XSLT transformation. I knew I could use a Composite to build that XML, but I instead choose to build it by using an implicit tree. Why? Because I was more interested in going fast and facing every technical hurdle involved in doing the XSLT transformation than I was in producing good XML tree construction code. After completing the XSLT transformation, I went back to refactor the primitive tree construction code to use a Composite because that code was going to be emulated in many areas of the system.

Benefits and Liabilities

+	Encapsulates repetitive instructions like formatting, adding, or removing nodes.
+	Provides a generalized way to handle a proliferation of similar logic.
+	Simplifies construction responsibilities of a client.
–	Complicates a design when it's simpler to construct implicit trees.

Mechanics

The mechanics presented in this section feature two paths for implementing this refactoring. One path, which is standard throughout the book, involves applying refactorings on an implicit tree to gradually refactor it to a Composite, while the other way involves performing test-driven development [Beck, TDD] to gradually refactor the implicit tree to a Composite. Both paths work well. I tend to use the test-driven approach when an implicit tree, like the XML in the earlier example, doesn't lend itself well to applying refactorings like Extract Class [F].

1. Identify an implicit leaf, a part of the implicit tree that could be modeled with a new class. This new class will be a leaf node (called Composite:Leaf in Design Patterns [DP]). Create a leaf node class by applying refactorings like Extract Class [F] or by doing test-driven development—whichever is easier given your context.

If the implicit leaf has attributes, produce equivalents for these attributes in the leaf node, such that the representation of the entire leaf node, including its attributes, matches that of the implicit leaf.

Compile and test.

2. Replace every occurrence of the implicit leaf with an instance of the leaf node, such that the implicit tree now relies on the leaf node instead of the implicit leaf.

Compile and test that the implicit tree still functions correctly.

3. Repeat steps 1 and 2 for any additional parts of the implicit tree that represent an implicit leaf. Make sure that all leaf nodes you create share a common interface. You can create this interface by applying Extract Superclass [F] or Extract Interface [F].

4. Identify an implicit parent, a part of the implicit tree that acts as a parent to implicit leaves. The implicit parent will become a parent node class (called Composite [DP]). Develop this class by applying refactorings or doing test-driven development—again, use whichever approach is easier in your context.

Clients must be able to add leaf nodes to the parent node either through a constructor or an add(…) method. The parent node must treat all children identically (i.e., via their common interface). The parent node may or may not implement the common interface. If clients must be able to add parent nodes to parent nodes (as is mentioned in step 6) or if you don't want client code to distinguish between a leaf node and a parent node (as is the motivation for Replace One/Many Distinctions with Composite, 224), make the parent node implement the common interface.

5. Replace every occurrence of the implicit parent with code that uses a parent node instance, outfitted with the correct leaf node instances.

Compile and test that the implicit tree still functions correctly.

6. Repeat steps 4 and 5 for all additional implicit parents. Make it possible to add a parent node to a parent node only if your implicit parents support similar behavior.

Example

The code that produces the implicit tree in the code sketch at the beginning of this refactoring section comes from a shopping system. In that system, there is an OrdersWriter class, which has a getContents() method. Before proceeding with the refactoring, I first break the large getContents() method into smaller methods by applying Compose Method (123) and Move Accumulation to Collecting Parameter (313):

 public class OrdersWriter {   private Orders orders;   public OrdersWriter(Orders orders) {     this.orders = orders;   }   public String getContents() {     StringBuffer xml = new StringBuffer();      writeOrderTo(xml);     return xml.toString();   }    private void writeOrderTo(StringBuffer xml) {      xml.append("<orders>");      for (int i = 0; i < orders.getOrderCount(); i++) {        Order order = orders.getOrder(i);        xml.append("<order");        xml.append(" id='");        xml.append(order.getOrderId());        xml.append("'>");        writeProductsTo(xml, order);        xml.append("</order>");      }      xml.append("</orders>");    }    private void writeProductsTo(StringBuffer xml, Order order) {      for (int j=0; j < order.getProductCount(); j++) {        Product product = order.getProduct(j);        xml.append("<product");        xml.append(" id='");        xml.append(product.getID());        xml.append("'");        xml.append(" color='");        xml.append(colorFor(product));        xml.append("'");        if (product.getSize() != ProductSize.NOT_APPLICABLE) {          xml.append(" size='");          xml.append(sizeFor(product));          xml.append("'");        }        xml.append(">");        writePriceTo(xml, product);        xml.append(product.getName());        xml.append("</product>");      }    }    private void writePriceTo(StringBuffer xml, Product product) {      xml.append("<price");      xml.append(" currency='");      xml.append(currencyFor(product));      xml.append("'>");      xml.append(product.getPrice());      xml.append("</price>");    }

Now that getContents() has been refactored, it's easier to see additional refactoring possibilities. One reader of this code noticed that the methods writeOrderTo(…), writeProductsTo(…), and writePriceTo(…) all loop through the domain objects Order, Product, and Price in order to extract data from them for use in producing XML. This reader wondered why the code doesn't just ask the domain objects for their XML directly, rather than having to build it externally to the domain objects. In other words, if the Order class had a toXML() method and the Product and Price classes had one as well, obtaining XML for an Order would simply involve making one call to an Order's toXML() method. That call would obtain the XML from the Order, as well as the XML from whatever Product instances were part of the Order and whatever Price was associated with each Product. This approach would take advantage of the existing structure of the domain objects, rather than recreating that structure in methods like writeOrderTo(…), writeProductsTo(…), and writePriceTo(…).

As nice as this idea sounds, it isn't a good design when a system must create many XML representations of the same domain objects. For example, the code we've been looking at comes from a shopping system that requires diverse XML representations for the domain objects:

    <order id='987' totalPrice='14.00'>      <product id='f1234' price='9.00' quantity='1'>        Fire Truck      </product>      <product id='f4321' price='5.00' quantity='1'>        Rubber Ball      </product>    </order>    <orderHistory>      <order date='20041120' totalPrice='14.00'>        <product id='f1234'>        <product id='f4321'>      </order>    </orderHistory>    <order id='321'>      <product id='f1234' color='red' size='medium'>        <price currency='USD'>          8.95        </price>        Fire Truck      </product>    </order>

Producing the above XML would be difficult and awkward using a single toXML() method on each domain object because the XML is so different in each case. Given such a situation, you can either choose to do the XML rendering external to the domain objects (as the writeOrderTo(…), writeProductsTo(…), and writePriceTo(…) methods do), or you can pursue a Visitor solution (see Move Accumulation to Visitor, 320).

For this shopping system, which generates a lot of diverse XML for the same domain objects, refactoring to Visitor makes a lot of sense. However, at the moment, the creation of the XML is still not simple; you have to get the formatting just right and remember to close every tag. I want to simplify this XML generation prior to refactoring to Visitor. Because the Composite pattern can help simplify the XML generation, I proceed with this refactoring.

1. To identify an implicit leaf, I study fragments of test code, such as this one:

 String expectedResult = "<orders>" +   "<order id='321'>" +     "<product id='f1234' color='red' size='medium'>" +       "<price currency='USD'>" +         "8.95" +       "</price>" +       "Fire Truck" +     "</product>" +   "</order>" + "</orders>";

Here, I face a decision: Which should I treat as an implicit leaf, the <price>…</price> tag or its value, 8.95? I choose the <price>…</price> tag because I know that the leaf node class I'll create to correspond with the implicit leaf can easily represent the tag's value, 8.95.

Another observation I make is that every XML tag in the implicit tree has a name, an optional number of attributes (name/value pairs), optional children, and an optional value. I ignore the optional children part for the moment (we'll get to that in step 4). This means that I can produce one general leaf node to represent all implicit leaves in the implicit tree. I produce this class, which I call TagNode, using test-driven development. Here's a test I write after already writing and passing some simpler tests:

 public class TagTests extends TestCase...    private static final String SAMPLE_PRICE = "8.95";    public void testSimpleTagWithOneAttributeAndValue() {      TagNode priceTag = new TagNode("price");      priceTag.addAttribute("currency", "USD");      priceTag.addValue(SAMPLE_PRICE);      String expected =        "<price currency=" +        "'" +        "USD" +        "'>" +        SAMPLE_PRICE +        "</price>";      assertEquals("price XML", expected, priceTag.toString());    }

Here's the code to make the test pass:

  public class TagNode {    private String name = "";    private String value = "";    private StringBuffer attributes;    public TagNode(String name) {      this.name = name;      attributes = new StringBuffer("");    }    public void addAttribute(String attribute, String value) {      attributes.append(" ");      attributes.append(attribute);      attributes.append("='");      attributes.append(value);      attributes.append("'");    }    public void addValue(String value) {      this.value = value;    }    public String toString() {      String result;      result =        "<" + name + attributes + ">" +        value +        "</" + name + ">";      return result;    }

2. I can now replace the implicit leaf in the getContents() method with a TagNode instance:

 public class OrdersWriter...   private void writePriceTo(StringBuffer xml, Product product) {      TagNode priceNode = new TagNode("price");      priceNode.addAttribute("currency", currencyFor(product));      priceNode.addValue(priceFor(product));      xml.append(priceNode.toString());       xml.append(" currency='");      xml.append("<price");       xml.append(currencyFor(product));       xml.append("'>");       xml.append(product.getPrice());       xml.append("</price>");   }

I compile and run tests to ensure that the implicit tree is still rendered correctly.

3. Because TagNode models all of the implicit leaves in the XML, I do not need to repeat steps 1 and 2 to convert additional implicit leaves to leaf nodes, nor do I need to ensure that all newly created leaf nodes share a common interface—they already do.

4. Now I identify an implicit parent by studying fragments of test code. I find that a <product> tag is a parent for a <price> tag, an <order> tag is a parent for a <product> tag, and an <orders> tag is a parent for an <order> tag. Yet because each of these implicit parents is already so similar in nature to the implicit leaf identified earlier, I see that I can produce a parent node by adding child-handling support to TagNode. I follow test-driven development to produce this new code. Here's the first test I write:

  public void testCompositeTagOneChild() {    TagNode productTag = new TagNode("product");    productTag.add(new TagNode("price"));    String expected =      "<product>" +        "<price>" +        "</price>" +      "</product>";    assertEquals("price XML", expected, productTag.toString());  }

And here's code to pass that test:

 public class TagNode...    private List children;   public String toString() {     String result;     result = "<" + name + attributes + ">";      Iterator it = children().iterator();      while (it.hasNext()) {        TagNode node = (TagNode)it.next();        result += node.toString();      }     result += value;     result += "</" + name + ">";     return result;   }    private List children() {      if (children == null)        children = new ArrayList();      return children;    }    public void add(TagNode child) {      children().add(child);    }

Here's a slightly more robust test:

  public void testAddingChildrenAndGrandchildren() {     String expected =     "<orders>" +       "<order>" +          "<product>" +          "</product>" +       "</order>" +     "</orders>";     TagNode ordersTag = new TagNode("orders");     TagNode orderTag = new TagNode("order");     TagNode productTag = new TagNode("product");     ordersTag.add(orderTag);     orderTag.add(productTag);     assertEquals("price XML", expected, ordersTag.toString());  }

I continue writing and running tests until I'm satisfied that TagNode can behave as a proper parent node. When I'm done, TagNode is a class that can play all three participants in the Composite pattern:

5. Now I replace every occurrence of the implicit parent with code that uses a parent node instance, outfitted with the correct leaf node instance(s). Here's an example:

 public class OrdersWriter...   private void writeProductsTo(StringBuffer xml, Order order) {     for (int j=0; j < order.getProductCount(); j++) {       Product product = order.getProduct(j);        TagNode productTag = new TagNode("product");        productTag.addAttribute("id", product.getID());        productTag.addAttribute("color", colorFor(product));       if (product.getSize() != ProductSize.NOT_APPLICABLE)          productTag.addAttribute("size", sizeFor(product));        writePriceTo(productTag, product);        productTag.addValue(product.getName());       xml.append( productTag.toString());     }   }    private void writePriceTo(TagNode productTag, Product product) {     TagNode priceTag = new TagNode("price");     priceTag.addAttribute("currency", currencyFor(product));     priceTag.addValue(priceFor(product));      productTag.add(priceTag);   }

I compile and run tests to ensure that the implicit tree still renders itself correctly.

6. I repeat steps 4 and 5 for all remaining implicit parents. This yields the following code, which is identical to the after code in the code sketch on the first page of this refactoring, except that the code is broken up into smaller methods:

 public class OrdersWriter...   public String getContents() {     StringBuffer xml = new StringBuffer();     writeOrderTo(xml);     return xml.toString();   }   private void writeOrderTo(StringBuffer xml) {     TagNode ordersTag = new TagNode("orders");     for (int i = 0; i < orders.getOrderCount(); i++) {       Order order = orders.getOrder(i);       TagNode orderTag = new TagNode("order");       orderTag.addAttribute("id", order.getOrderId());       writeProductsTo(orderTag, order);       ordersTag.add(orderTag);     }     xml.append(ordersTag.toString());   }   private void writeProductsTo(TagNode orderTag, Order order) {     for (int j=0; j < order.getProductCount(); j++) {       Product product = order.getProduct(j);       TagNode productTag = new TagNode("product");       productTag.addAttribute("id", product.getID());       productTag.addAttribute("color", colorFor(product));       if (product.getSize() != ProductSize.NOT_APPLICABLE)         productTag.addAttribute("size", sizeFor(product));       writePriceTo(productTag, product);       productTag.addValue(product.getName());       orderTag.add(productTag);     }   }   private void writePriceTo(TagNode productTag, Product product) {     TagNode priceNode = new TagNode("price");     priceNode.addAttribute("currency", currencyFor(product));     priceNode.addValue(priceFor(product));     productTag.add(priceNode);   }


	Amazon