Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Principles of Object-Oriented Programming » Mutable Linear Recursive Structure

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • OrangeGrove display tagshide tags

    This collection is included inLens: Florida Orange Grove Textbooks
    By: Florida Orange Grove

    Click the "OrangeGrove" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

    Click the "Bookshare" link to see all content affiliated with them.

Also in these lenses

  • Busbee's Compter Science display tagshide tags

    This collection is included inLens: Busbee's Computer Science Lens
    By: Kenneth Leroy Busbee

    Comments:

    "Texas Common Course Numbering: COSC1337 or COSC1437"

    Click the "Busbee's Compter Science" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

  • eScience, eResearch and Computational Problem Solving

    This collection is included inLens: eScience, eResearch and Computational Problem Solving
    By: Jan E. Odegard

    Click the "eScience, eResearch and Computational Problem Solving" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Mutable Linear Recursive Structure

Module by: Dung Nguyen, Stephen Wong. E-mail the authors

Summary: Immutable lists are certainly very useful, but sometimes we naturally think of things as changing state. For instance, when we add an item to a list in real life, we don't throw away the old list; we mutate it to hold the new item. In this section we define the structure and behavior of a mutable list using a combination of the state dsign pattern and the visitor design pattern.

1. State Pattern and Dynamic Reclassification

In programming, it is often necessary to have objects with which one can store data, retrieve data when needed, and remove data when no longer needed. Such objects are instances of what we call container structures.

A mutable container structure is a system that may change its state from empty to non-empty, and vice-versa. For example, an empty container changes its state to non-empty after insertion of an object; and when the last element of a container is removed, its changes its state to empty. Figure 1 below diagrams the state transition of a container structure.

 

Figure 1: State transition diagram for container structures
Figure 1 (graphics1.png)

For each distinct state, the algorithms to implement the methods differ. For example, the algorithm for the retrieve method is trivial in the empty state -it simply returns null- while it is more complicated in the non-empty state. The system thus behaves as if it changes classes dynamically. This phenomenon is called “dynamic reclassification.” The state pattern is a design solution for languages that do not directly support dynamic reclassification. This pattern can be summarized as follow.

  • Define an abstract class for the states of the system. This abstract state class should provide all the abstract methods for all the concrete subclasses.
  • Define a concrete subclass of the above abstract class for each state of the system. Each concrete state must implement its own concrete methods.
  • Represent the system by a class, called the context, containing an instance of a concrete state. This instance represents the current state of the system.
  • Define methods for the system to return the current state and to change state.
  • Delegate all requests made to the system to the current state instance. Since this instance can change dynamically, the system will behave as if it can change its class dynamically.

Below is the UML class diagram for the state design pattern.

Figure 2: UML class diagram for the state design pattern
Figure 2 (graphics2.png)

2. Mutable Linear Recursive Structure Framework

A mutable linear recursive structure (LRStruct) can be in the empty state or in a non-empty state. If it is empty, it contains no object. Otherwise, it contains an object called first, and a LRStruct object called rest. When we insert a data object into an empty LRStruct, it changes it state to non-empty.   When we remove the last element from an non-empty LRStruct, it changes its state to empty.  We model a LRStruct using the state pattern, and as in the case of the immutable list, we also apply the visitor pattern to obtain a framework.  Below is the UML class diagram of the LRStruct framework.  Because of the current limitation of our diagramming tool, we are using the Object[] input notation to represent the variable argument list Object... inputClick here to download the codeClick here to download the javadoc documentation.. We will study the implementation code in the next lecture.

Figure 3: State and Visitor Patterns for Mutable Linear Recursive Structure
Figure 3 (graphics3.png)

The public constructor:

  • LRStruct()

and the methods:

  • insertFront(...)
  • removeFront(...)
  • getFirst()
  • setFirst(...)
  • getRest()
  • setRest(...)

of LRStruct expose the structure of an LRStruct to the client and constitute the intrinsic structural behavior of an LRStruct. They form a minimal and complete set of methods for manipulating an LRStruct. Using them, a client can create an empty LRStruct, store data in it, and remove/retrieve data from it at will.

The method, 

  • Object execute(IAlgo algo, Object inp) 

is called the extensibility "hook".  It allows the client to add an open-ended number of new application-dependent behaviors to the data structure LRStruct, such as computing its length or merging one LRStruct with another, without modifying any of the existing code.  The application-dependent behaviors of LRStruct are extrinsic behaviors and are encapsulated in a union represented by a visitor interface called IAlgo.

When a client programs with LRStruct, he/she only sees the public methods of LRStruct and IAlgo . To add a new operation on an LRStruct, the client writes appropriate concrete classes that implements IAlgo. The framework dictates the overall design of an algorithm on LRStruct: since an algorithm on LRStruct must implement IAlgo , there must be some concrete code for emptyCase(...) and some concrete code for nonEmptyCase(...). For example,


public class DoSomethingWithLRS implements IAlgo {
   // fields and constructor code...
   public Object emptyCase(LRStruct host, Object... inp) {
       // some concrete code here...
       return some Object; // may be null.
   }

   public Object nonEmptyCase(LRStruct host, Object... inp) {
       // some concrete code here...
       return some Object; // may be null.
   }
}  

As illustrated in the above, an algorithm on LRStruct is "declarative" in nature.  It does not involve any conditional to find out what state the LRStruct is in in order to perform the appropriate task.  It simply "declares" what needs to be done for each state of the host LRStruct, and leaves it to the polymorphism machinery to make the correct call.  Polymorphism is exploited to minimize flow control and  reduce code complexity.

To perform an algorithm on an LRStruct, the client must "ask" the LRStruct to "execute" the algorithm and passes to it all the inputs required by the algorithm.


LRStruct myList = new LRStruct();  // an empty list
// code to call on the structural methods of myList, e.g. myList.insertFront(/*whatever*/)
// Now call on myList to perform DoSomethingWithLRS:
Object result = myList.execute(
    new DoSomethingWithLRS(/* constructor argument list */), -2.75, "abc"); 

 Without knowing how LRStruct is implemented, let us look an example of an algorithm on an LRStruct .

3. Example

Consider the problem of inserting an Integer object in order into a sorted list of Integers.  Let us contrast the insert in order algorithms between IList, the immutable list, and LRStruct, the mutable list.

Table 1
Insert in order using factory Insert in order using mutation

import listFW.*;

public class InsertInOrder 
  implements IListAlgo {

  private IListFactory _fact;

  public InsertInOrder(IListFactory lf) {
    _fact = lf;
  }

  /**
  * Simply makes a new non-empty list with 
  * the given parameter n as first.
  * @param host an empty IList.
  * @param n n[0] is an Integer to be 
  *   inserted in order into host.
  * @return INEList.
  */
  public Object emptyCase(
    IEmptyList host, Object... n) {

    return _fact.makeNEList(n[0], host);
  }

  /**
  * Based on the comparison between first 
  * and n, creates a new list or recur!
  * @param host a non-empty IList.
  * @param n an Integer to be inserted in 
  *   order into host.
  * @return INEList
  */
  public Object nonEmptyCase(
    INEList host, Object... n) {
    
    return (Integer)n[0] < 
      (Integer)host.getFirst() ?
        _fact.makeNEList(n[0], host):
        _fact.makeNEList(host.getFirst(),
          (IList)host.getRest().execute(
            this, n[0]));
  }
}

import lrs.*;

public class InsertInOrderLRS 
  implements IAlgo {

  public static final InsertInOrderLRS 
    Singleton = new InsertInOrderLRS();

  private InsertInOrderLRS() {}

  /**
  * Simply inserts the given parameter n at 
  * the front.
  * @param host an empty LRStruct.
  * @param n n[0] isan Integer to be 
  *  inserted in order into host.
  * @return LRStruct
  */
  public Object emptyCase(
    LRStruct host, Object... n) {

    return host.insertFront(n[0]);
  }

  /**
  * Based on the comparison between first 
  * and n, inserts at the front or recurs!
  * @param host a non-empty LRStruct.
  * @param n n[0] is  an Integer to be 
  *   inserted in order into host.
  * @return LRStruct
  */
  public Object nonEmptyCase(
    LRStruct host, Object... n) {
    
    if ((Integer)n[0] < (
      Integer)host.getFirst()) {
      
      return host.insertFront(n[0]);
    }
    else {
      return host.getRest().execute(
        this, n[0]);
    }
  }
}
Note that the insert in order algorithm for LRStruct need not create any new list and thus needs no factory.Download the above code: lrs.zip

 

Collection Navigation

Content actions

Download:

Collection as:

PDF | More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks