5.6 Composite Pattern

5.6.1 Overview

This image is very familiar, and the above diagram can be seen as a file system. This kind of structure is called a tree structure. In a tree structure, you can call a method to traverse the entire tree, and when you find a leaf node, you can perform relevant operations on the leaf node. You can think of this tree as a large container that contains many member objects, which can be container objects or leaf objects. However, due to the difference in functionality between container objects and leaf objects, it is necessary to distinguish between container objects and leaf objects during use, which brings unnecessary trouble to the client. As a client, it always hopes to treat container objects and leaf objects consistently.

Definition:

Also known as the part-whole pattern, it is used to treat a group of similar objects as a single object. The composite pattern creates a tree structure of objects based on the tree structure, used to represent parts and hierarchical levels. This type of design pattern belongs to the structural pattern, and it creates a tree structure of object groups.

5.6.2 Structure

The composite pattern mainly includes three roles:

• Abstract root node (Component): Defines the common methods and properties of objects at all levels of the system, and can predefine some default behaviors and properties.
• Branch node (Composite): Defines the behavior of branch nodes, stores child nodes, and forms a tree structure with branch nodes and leaf nodes.
• Leaf node (Leaf): Leaf node object, which has no branches below it, and is the smallest unit of the system hierarchy traversal.

5.6.3 Case Implementation

[Example] Software Menu

The following figure shows a menu that we often see when accessing other management systems. A menu can contain menu items (menu items refer to menu entries that do not contain other content), or it can contain menus with other menu items. Therefore, using the composite pattern to describe the menu is appropriate. Our requirement is to print out all the menus and menu items contained in a menu.

To implement this case, we first draw the class diagram:

Code Implementation:

Whether it's a menu or a menu item, they should all inherit from a unified interface. Here, we'll call this unified interface a menu component.

// Menu component - both menu and menu item should inherit this class
public abstract class MenuItem {

    protected String name;
    protected int level;

    // Add menu
    public void add(MenuItem menuItem) {
        throw new UnsupportedOperationException();
    }

    // Remove menu
    public void remove(MenuItem menuItem) {
        throw new UnsupportedOperationException();
    }

    // Get specified child menu
    public MenuItem getChild(int i) {
        throw new UnsupportedOperationException();
    }

    // Get menu name
    public String getName() {
        return name;
    }

    public void print() {
        throw new UnsupportedOperationException();
    }
}

Here, MenuItem defines an abstract class because some common attributes and behaviors need to be implemented in this class. Menu and MenuEntry classes can only override the methods they are interested in, without having to deal with methods they don't need or are not interested in. For example, the Menu class can contain sub-menus, so it needs to override the add(), remove(), and getChild() methods, but the MenuEntry class should not have these methods. The default implementation here throws an exception, but you can also rewrite the default implementation according to your needs.

public class Menu extends MenuItem {

    private List<MenuItem> menuItemList;

    public Menu(String name, int level) {
        this.level = level;
        this.name = name;
        menuItemList = new ArrayList<MenuItem>();
    }

    @Override
    public void add(MenuItem menuItem) {
        menuItemList.add(menuItem);
    }

    @Override
    public void remove(MenuItem menuItem) {
        menuItemList.remove(menuItem);
    }

    @Override
    public MenuItem getChild(int i) {
        return menuItemList.get(i);
    }

    @Override
    public void print() {

        for (int i = 1; i < level; i++) {
            System.out.print("--");
        }
        System.out.println(name);
        for (MenuItem menuItem : menuItemList) {
            menuItem.print();
        }
    }
}

The Menu class has implemented all methods except getName, because the Menu class has the functions of adding menus, removing menus, and getting child menus.

public class MenuEntry extends MenuItem {

    public MenuEntry(String name, int level) {
        this.name = name;
        this.level = level;
    }

    @Override
    public void print() {
        for (int i = 1; i < level; i++) {
            System.out.print("--");
        }
        System.out.println(name);
    }
}

MenuEntry is a menu entry, which cannot have any sub-menus, so the functions of adding menus, removing menus, and getting sub-menus cannot be implemented.

5.6.4 Classification of the Composite Pattern

When using the composite pattern, depending on the definition form of the abstract component class, the composite pattern can be divided into two forms: transparent composite pattern and safe composite pattern.

• Transparent Composite Pattern

In the transparent composite pattern, the abstract root role declares all methods for managing member objects, such as the MenuItem class declaring add, remove, and getChild methods in the example. The advantage of doing this is to ensure that all component classes have the same interface. The transparent composite pattern is also the standard form of the composite pattern.

The disadvantage of the transparent composite pattern is that it is not safe enough, because leaf objects and container objects are essentially different. Leaf objects cannot have the next level of objects, that is, they cannot contain member objects. Therefore, providing add() and remove() methods for them is meaningless, which will not cause errors during the compilation phase, but may cause errors during the runtime phase (if there is no corresponding error handling code).

• Safe Composite Pattern

In the safe composite pattern, the abstract component role does not declare any methods for managing member objects, and these methods are declared and implemented in the branch node Menu class. The disadvantage of the safe composite pattern is that it is not transparent enough, because the leaf components and container components have different methods, and the methods in the container components for managing member objects are not defined in the abstract component class. Therefore, the client cannot completely rely on abstraction programming and must distinguish between leaf components and container components.

5.6.5 Advantages

• The composite pattern can clearly define complex objects with hierarchical structures, representing all or part of the hierarchy of objects. It allows clients to ignore the differences in the hierarchy, making it easy to control the entire hierarchy structure.
• Clients can consistently use a composite structure or a single object, without needing to care whether it is a single object or an entire composite structure, simplifying the client code.
• It is convenient to add new branch nodes and leaf nodes in the composite pattern, without modifying any existing classes, conforming to the 'open-closed principle'.
• The composite pattern provides a flexible solution for the object-oriented implementation of a tree structure. By recursively combining leaf nodes and branch nodes, complex tree structures can be formed, but controlling the tree structure is very simple.

5.6.6 Usage Scenarios

The composite pattern is born for tree structures, so its usage scenarios are places where tree structures appear. For example: file directory display, multi-level directory presentation, etc., for operations on tree-structured data.

5.7 Flyweight Pattern

5.7.1 Overview

Definition:

Use sharing technology to effectively support the reuse of a large number of fine-grained objects. It reduces the number of objects that need to be created by sharing existing objects, avoiding the cost of a large number of similar objects, thereby improving the utilization of system resources.

5.7.2 Structure

The flyweight pattern has the following two states:

1. Internal state, which is the shareable part that does not change with the environment.
2. External state, which is the non-shareable part that changes with the environment. The key to implementing the flyweight pattern is to distinguish these two states in the application and externalize the external state.

The main roles in the flyweight pattern are:

• Abstract flyweight role (Flyweight): Usually an interface or abstract class. The abstract flyweight class declares public methods of specific flyweight classes. These methods can provide internal data (internal state) of the flyweight object to the outside world, and can also set external data (external state) through these methods.
• Concrete flyweight (Concrete Flyweight) role: It implements the abstract flyweight class, called the flyweight object; in the specific flyweight class, storage space is provided for the internal state. Usually, we can combine the singleton pattern to design the specific flyweight class, providing a unique flyweight object for each specific flyweight class.
• Unsharable flyweight (Unsharable Flyweight) role: Not all subclasses of the abstract flyweight class need to be shared. Subclasses that cannot be shared can be designed as non-shared specific flyweight classes; when a non-shared specific flyweight class object is needed, it can be directly instantiated.
• Flyweight factory (Flyweight Factory) role: Responsible for creating and managing flyweight roles. When a client object requests a flyweight object, the flyweight factory checks whether there is a suitable flyweight object in the system. If it exists, it provides it to the client; if it does not exist, it creates a new flyweight object.

5.7.3 Case Implementation

[Example] Tetris

The following picture is one of the blocks in the well-known Tetris game. If each different block in the Tetris game is an instance object, these objects would occupy a lot of memory space. Below is an implementation using the flyweight pattern.

First, look at the class diagram:

Code as follows:

Tetris has different shapes, and we can extract an AbstractBox upwards to define the common properties and behaviors.

public abstract class AbstractBox {
    public abstract String getShape();

    public void display(String color) {
        System.out.println("Block shape: " + this.getShape() + " Color: " + color);
    }
}

Next, define different shapes, such as IBox class, LBox class, OBox class, etc.

public class IBox extends AbstractBox {

    @Override
    public String getShape() {
        return "I";
    }
}

public class LBox extends AbstractBox {

    @Override
    public String getShape() {
        return "L";
    }
}

public class OBox extends AbstractBox {

    @Override
    public String getShape() {
        return "O";
    }
}

A factory class (BoxFactory) is provided to manage the flyweight objects (i.e., AbstractBox subclass objects). This factory class only needs one instance, so it can be designed using the singleton pattern. And provide a method to get the shape.

public class BoxFactory {

    private static HashMap<String, AbstractBox> map;

    private BoxFactory() {
        map = new HashMap<String, AbstractBox>();
        AbstractBox iBox = new IBox();
        AbstractBox lBox = new LBox();
        AbstractBox oBox = new OBox();
        map.put("I", iBox);
        map.put("L", lBox);
        map.put("O", oBox);
    }

    public static final BoxFactory getInstance() {
        return SingletonHolder.INSTANCE;
    }

    private static class SingletonHolder {
        private static final BoxFactory INSTANCE = new BoxFactory();
    }

    public AbstractBox getBox(String key) {
        return map.get(key);
    }
}

5.7.5 Advantages, Disadvantages, and Usage Scenarios

1, Advantages

• Significantly reduce the number of similar or identical objects in memory, save system resources, and improve system performance
• The external state of the flyweight pattern is relatively independent and does not affect the internal state

2, Disadvantages:

• To make the object shareable, it is necessary to externalize part of the state of the flyweight object, separate the internal state and external state, which makes the program logic more complex

3, Usage Scenarios:

• A system has a large number of identical or similar objects, causing a large consumption of memory.
• Most of the state of the object can be externalized, and these external states can be passed into the object.
• When using the flyweight pattern, its necessary to maintain a flyweight pool storing flyweight objects, which consumes certain system resources. Therefore, it is worth using the flyweight pattern only when the flyweight object needs to be reused multiple times.

5.7.6 JDK Source Code Analysis

The Integer class uses the flyweight pattern. Let's look at the following example:

public class Demo {
    public static void main(String[] args) {
        Integer i1 = 127;
        Integer i2 = 127;

        System.out.println("i1 and i2 are the same object? " + (i1 == i2));

        Integer i3 = 128;
        Integer i4 = 128;

        System.out.println("i3 and i4 are the same object? " + (i3 == i4));
    }
}

Running the above code, the result is as follows:

Why does the first output statement output true, and the second output statement output false? By decompiling the code, the code is as follows:

public class Demo {
    public static void main(String[] args) {
        Integer i1 = Integer.valueOf((int)127);
        Integer i2 Integer.valueOf((int)127);
        System.out.println((String)new StringBuilder().append((String)"i1和i2对象是否是同一个对象？").append((boolean)(i1 == i2)).toString());
        Integer i3 = Integer.valueOf((int)128);
        Integer i4 = Integer.valueOf((int)128);
        System.out.println((String)new StringBuilder().append((String)"i3和i4对象是否是同一个对象？").append((boolean)(i3 == i4)).toString());
    }
}

The above code shows that the operation of assigning a basic data type to an Integer-type variable uses valueOf() at the bottom. So we only need to look at this method.

public final class Integer extends Number implements Comparable<Integer> {

    public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

    private static class IntegerCache {
        static final int low = -128;
        static final int high;
        static final Integer cache[];

        static {
            int h = 127;
            String integerCacheHighPropValue =
                sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
            if (integerCacheHighPropValue != null) {
                try {
                    int i = parseInt(integerCacheHighPropValue);
                    i = Math.max(i, 127);
                    // Maximum array size is Integer.MAX_VALUE
                    h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
                } catch( NumberFormatException nfe) {
                }
            }
            high = h;
            cache = new Integer[(high - low) + 1];
            int j = low;
            for(int k = 0; k < cache.length; k++)
                cache[k] = new Integer(j++);
            // range [-128, 127] must be interned (JLS7 5.1.7)
            assert IntegerCache.high >= 127;
        }

        private IntegerCache() {}
    }
}

It can be seen that Integer defaults to creating and caching Integer objects for numbers between -128 ~ 127. When calling valueOf(), if the parameter is within -128 ~ 127, it calculates the index and returns from the cache, otherwise it creates a new Integer object.

6, Behavioral Patterns

Behavioral patterns are used to describe complex process control in programs during runtime, i.e., how multiple classes or objects collaborate to complete tasks that individual objects cannot complete alone. It involves the allocation of algorithms and responsibilities between objects.

Behavioral patterns are divided into class behavioral patterns and object behavioral patterns. The former uses inheritance to distribute behavior between classes, while the latter uses composition or aggregation to distribute behavior between objects. Since composition or aggregation relationships are less coupled than inheritance relationships, they satisfy the 'composite reuse principle', so object behavioral patterns are more flexible than class behavioral patterns.

Behavioral patterns are divided into:

• Template Method Pattern
• Strategy Pattern
• Command Pattern
• Chain of Responsibility Pattern
• State Pattern
• Observer Pattern
• Mediator Pattern
• Iterator Pattern
• Visitor Pattern
• Memento Pattern
• Interpreter Pattern

Among the above 11 behavioral patterns, the template method pattern and interpreter pattern are class behavioral patterns, while the rest are object behavioral patterns.

6.1 Template Method Pattern

6.1.1 Overview

In object-oriented programming, programmers often encounter the following situation: when designing a system, they know the key steps required for the algorithm, and they have determined the execution order of these steps, but the specific implementation of some steps is unknown, or the implementation of some steps is related to the specific environment.

For example, when going to the bank to handle business, it generally goes through the following four processes: taking a number, queuing, handling specific business, and rating the bank staff. Among these, taking a number, queuing, and rating the bank staff are the same for each customer and can be implemented in the parent class, but handling specific business varies from person to person, which could be depositing, withdrawing, or transferring, and can be delayed to the subclass for implementation.

Definition:

Define the skeleton of an algorithm, and delay some steps of the algorithm to subclasses, allowing subclasses to redefine certain steps of the algorithm without changing the structure of the algorithm.

6.1.2 Structure

The template method (Template Method) pattern includes the following main roles:

• Abstract Class (Abstract Class): Responsible for giving the outline and framework of an algorithm. It consists of a template method and several basic methods.

  • Template method: Defines the skeleton of the algorithm, and calls its included basic methods in a certain order.

  • Basic method: Is the method that implements each step of the algorithm, and is a component of the template method. Basic methods can be divided into three types:

    • Abstract method (Abstract Method): An abstract method is declared by an abstract class and implemented by its specific subclass.

    • Concrete method (Concrete Method): A concrete method is declared and implemented by an abstract class or a specific class, and its subclass can either override it or directly inherit it.

    • Hook method (Hook Method): A method already implemented in the abstract class, including logical methods for judgment and empty methods that need to be rewritten by the subclass.

      Generally, hook methods are logical methods for judgment, and their names are usually named as isXxx, with a return type of boolean type.

• Concrete Class (Concrete Class): Implements the abstract methods and hook methods defined in the abstract class, which are the composing steps of the top-level logic.

6.1.3 Case Implementation

[Example] Cooking Vegetables

The steps for cooking vegetables are fixed, including pouring oil, heating oil, pouring vegetables, pouring seasoning, and frying. Now simulate it with the template method pattern. The class diagram is as follows:

Code as follows:

public abstract class AbstractClass {

    public final void cookProcess() {
        // Step 1: Pour oil
        this.pourOil();
        // Step 2: Heat oil
        this.heatOil();
        // Step 3: Pour vegetables
        this.pourVegetable();
        // Step 4: Pour seasoning
        this.pourSauce();
        // Step 5: Fry
        this.fry();
    }

    public void pourOil() {
        System.out.println("Pour oil");
    }

    // Step 2: Heating oil is the same, so implement directly
    public void heatOil() {
        System.out.println("Heat oil");
    }

    // Step 3: Pouring vegetables is different (one is cabbage, one is vegetable heart)
    public abstract void pourVegetable();

    // Step 4: Pouring seasoning is different
    public abstract void pourSauce();


    // Step 5: Frying is the same, so implement directly
    public void fry(){
        System.out.println("Fry until cooked");
    }
}

public class ConcreteClass_BaoCai extends AbstractClass {

    @Override
    public void pourVegetable() {
        System.out.println("The vegetable put in is cabbage");
    }

    @Override
    public void pourSauce() {
        System.out.println("The sauce put in is chili");
    }
}

public class ConcreteClass_CaiXin extends AbstractClass {
    @Override
    public void pourVegetable() {
        System.out.println("The vegetable put in is vegetable heart");
    }

    @Override
    public void pourSauce() {
        System.out.println("The sauce put in is garlic");
    }
}

public class Client {
    public static void main(String[] args) {
        // Cook shredded pork
        ConcreteClass_BaoCai baoCai = new ConcreteClass_BaoCai();
        baoCai.cookProcess();

        // Cook garlic vegetable heart
        ConcreteClass_CaiXin caiXin = new ConcreteClass_CaiXin();
        caiXin.cookProcess();
    }
}

Note: To prevent malicious operations, the template method is generally added with the final keyword.

6.1.3 Pros and Cons

Advantages:

• Improve code reusability

  Place the same parts of the code in the abstract parent class, and place the different parts in different subclasses.

• Achieve reverse control

  By calling the subclass's operation through a parent class, the behavior can be extended by the subclass's specific implementation, achieving reverse control, and conforming to the 'open-closed principle'.

Disadvantages:

• Each different implementation requires defining a subclass, which leads to an increase in the number of classes, making the system larger and the design more abstract.
• The abstract method in the parent class is implemented by the subclass, and the result of the subclass's execution affects the result of the parent class, which leads to a reverse control structure, increasing the difficulty of reading the code.

6.1.4 Applicable Scenarios

• When the overall steps of the algorithm are fixed, but some parts are prone to change, this can be used to abstract out the parts that are prone to change and let the subclasses implement them.
• When the parent class needs to determine whether a certain step in the algorithm is executed, it realizes the reverse control of the subclass over the parent class.

6.1.5 JDK Source Code Analysis

The InputStream class uses the template method pattern. In the InputStream class, multiple read() methods are defined, as follows:

public abstract class InputStream implements Closeable {
    // Abstract method requiring subclasses to override
    public abstract int read() throws IOException;

    public int read(byte b[]) throws IOException {
        return read(b, 0, b.length);
    }

    public int read(byte b[], int off, int len) throws IOException {
        if (b == null) {
            throw new NullPointerException();
        } else if (off < 0 || len < 0 || len > b.length - off) {
            throw new IndexOutOfBoundsException();
        } else if (len == 0) {
            return 0;
        }

        int c = read(); // Calls the no-argument read method, which reads one byte of data each time
        if (c == -1) {
            return -1;
        }
        b[off] = (byte)c;

        int i = 1;
        try {
            for (; i < len ; i++) {
                c = read();
                if (c == -1) {
                    break;
                }
                b[off + i] = (byte)c;
            }
        } catch (IOException ee) {
        }
        return i;
    }
}

From the above code, it can be seen that the no-argument read() method is an abstract method that requires the subclass to implement. The read(byte b[]) method calls the read(byte b[], int off, int len) method, so the method to focus on here is the method with three parameters.

In this method, line 18 and line 27 show that the no-argument abstract read() method is called.

Summary: In the InputStream parent class, the method for reading a byte array data is defined as reading one byte at a time and storing it in the first index position of the array, reading len bytes of data. How to read one byte of data is implemented by the subclass.

6.2 Strategy Pattern

6.2.1 Overview

Look at the following picture, when we travel, there are many ways to choose the mode of transportation. We can ride a bicycle, take a car, take a train, or take a plane.

As a programmer, developing requires choosing a development tool. There are many tools available for code development, and we can choose to develop with Idea, or use Eclipse, or use other development tools.

Definition:

This pattern defines a series of algorithms and encapsulates each algorithm, allowing them to be replaced with each other. The change of the algorithm does not affect the customers who use the algorithm. The strategy pattern belongs to the object behavior pattern. It encapsulates the algorithm, separates the responsibility of using the algorithm from the implementation of the algorithm, and delegates the management of these algorithms to different objects.

6.2.2 Structure

The main roles of the strategy pattern are as follows:

• Abstract strategy (Strategy) class: This is an abstract role, usually implemented by an interface or abstract class. This role gives the interface required by all specific strategy classes.
• Concrete strategy (Concrete Strategy) class: Implements the interface defined by the abstract strategy, providing specific algorithm implementations or behaviors.
• Context (Context) class: Holds a reference to a strategy class, and finally calls it for the client.

6.2.3 Case Implementation

[Example] Promotion Activities

A department store sets annual promotion activities. Different festivals (Spring Festival, Mid-Autumn Festival, Christmas) have different promotion activities, and the salesperson displays the promotion activities to the customer. The class diagram is as follows:

Code as follows:

Define the common interface for all promotion activities of the department store

public interface Strategy {
    void show();
}

Define the specific strategy role (Concrete Strategy): Each festival's specific promotion activity

// Promotion activity A for the Spring Festival
public class StrategyA implements Strategy {

    public void show() {
        System.out.println("Buy one get one free");
    }
}

// Promotion activity B for the Mid-Autumn Festival
public class StrategyB implements Strategy {

    public void show() {
        System.out.println("200 yuan discount 50 yuan");
    }
}

// Promotion activity C for Christmas
public class StrategyC implements Strategy {

    public void show() {
        System.out.println("1000 yuan plus one yuan to exchange any 200 yuan product");
    }
}

Define the context role (Context): Used to connect the context, that is, to promote the promotion activity to the customer, which can be understood as the salesperson

public class SalesMan { 
    // Hold a reference to the abstract strategy role 
    private Strategy strategy; 

    public SalesMan(Strategy strategy) { 
        this.strategy = strategy; 
    } 

    // Show the promotion activity to the customer 
    public void salesManShow() { 
        strategy.show(); 
    } 
}

6.2.4 Pros and Cons

1, Advantages:

• Strategies can be freely switched

  Since all strategies implement the same interface, they can be freely switched.

• Easy to expand

  Adding a new strategy only requires adding a specific strategy class, which basically does not require changing the original code, conforming to the 'open-closed principle'

• Avoid using multiple conditional statements (if else), fully reflecting the object-oriented design philosophy.

2, Disadvantages:

• The client must know all the strategies and choose which one to use.
• The strategy pattern will cause a lot of strategy classes to be generated, which can be reduced to some extent by using the flyweight pattern.

6.2.5 Applicable Scenarios

• When a system needs to dynamically choose one of several algorithms, each algorithm can be encapsulated into a strategy class.
• A class defines many behaviors, and these behaviors are in the form of multiple conditional statements in this class's operations. Each conditional branch can be moved into their respective strategy classes to replace these conditional statements.
• The algorithms in the system are completely independent, and the specific algorithm implementation details should be hidden from the client.
• When the system requires the client to not know the data operated by the algorithm, the strategy pattern can be used to hide the data structure related to the algorithm.
• Multiple classes only differ in their behavior, and the strategy pattern can be used to dynamically select the specific behavior to be executed at runtime.

6.2.6 JDK Source Code Analysis

Comparator uses the strategy pattern. In the Arrays class, there is a sort() method, as follows:

public class Arrays{
    public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }
}

Arrays is the context role class, and this sort method can pass a new strategy to Arrays to sort according to this strategy. For example, the following test class.

public class demo {
    public static void main(String[] args) {

        Integer[] data = {12, 2, 3, 2, 4, 5, 1};
        // Implement descending order sorting
        Arrays.sort(data, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        System.out.println(Arrays.toString(data)); //[12, 5, 4, 3, 2, 2, 1]
    }
}

Here, when we call the sort method of Arrays, the second parameter passes an object of the Comparator interface's subclass. So Comparator plays the role of the abstract strategy, and the specific subclass of the comparator plays the role of the specific strategy. The context role class (Arrays) should hold a reference to the abstract strategy to call it. So does the sort method of the Arrays class really use the compare() method of the subclass of the Comparator interface? Let's continue to look at the sort() method of the TimSort class, the code is as follows:

class TimSort<T> {
    static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
                         T[] work, int workBase, int workLen) {
        assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;

        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted

        // If array is small, do a