Home > Articles > Software Development & Management

  • Print
  • + Share This
This chapter is from the book

This chapter is from the book

Replace Implicit Tree with Composite

Replace Implicit Tree with Composite

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.

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.
  2. 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.

  3. 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.
  4. → Compile and test that the implicit tree still functions correctly.

  5. 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].
  6. 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.
  7. 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.

  8. Replace every occurrence of the implicit parent with code that uses a parent node instance, outfitted with the correct leaf node instances.
  9. → Compile and test that the implicit tree still functions correctly.

  10. 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:
  2. 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;
      }
  3. I can now replace the implicit leaf in the getContents() method with a TagNode instance:
  4. 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.

  5. 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.
  6. 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:
  7. 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:

  8. 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:
  9. 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.

  10. 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:
  11. 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);
      }   
  • + Share This
  • 🔖 Save To Your Account

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

Overview


Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

Collection and Use of Information


To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

Newsletters

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

Other Collection and Use of Information


Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

Do Not Track

This site currently does not respond to Do Not Track signals.

Security


Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

Children


This site is not directed to children under the age of 13.

Marketing


Pearson may send or direct marketing communications to users, provided that

  • Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
  • Such marketing is consistent with applicable law and Pearson's legal obligations.
  • Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
  • Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

Correcting/Updating Personal Information


If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

Choice/Opt-out


Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

Sale of Personal Information


Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

Supplemental Privacy Statement for California Residents


California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

Sharing and Disclosure


Pearson may disclose personal information, as follows:

  • As required by law.
  • With the consent of the individual (or their parent, if the individual is a minor)
  • In response to a subpoena, court order or legal process, to the extent permitted or required by law
  • To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
  • In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
  • To investigate or address actual or suspected fraud or other illegal activities
  • To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
  • To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
  • To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

Links


This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

Requests and Contact


Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice


We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020