CodingGyan

Flyweight: Shared Glyph Objects

medium Design Principles and Patterns

Problem

A text editor draws a long text. Instead of one Glyph object for every character on the page, a GlyphFactory keeps one shared Glyph for each different character, and gives out the same object again for the same character. For the given word, print chars=N (the number of characters), objects=K (the number of Glyph objects that exist) and shared=true if every repeated character got exactly the same object.

Constraints

  • 1 <= length <= 100

Examples

Input

hello

Output

chars=5
objects=4
shared=true

Solutions

Best approachTime O(n)Space O(k)

Many equal small objects waste memory. The flyweight pattern keeps one shared object per distinct value, and a factory hands it out. Shared objects must not be changed, so they are immutable.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Count the glyph objects.
 * Input   : One word.
 * Output  : Three lines.
 * Approach: Flyweight factory
 * Time    : O(n)
 * Space   : O(k)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A Glyph holds the data that is the same for every use of one character. It is created once.
        static class Glyph {
            final char symbol;

            Glyph(char symbol) {
                this.symbol = symbol;
            }
        }

        // Step 2: The factory is the only place that creates Glyphs. It returns the stored one when it exists.
        static class GlyphFactory {
            private final java.util.Map<Character, Glyph> cache = new java.util.HashMap<>();

            Glyph get(char symbol) {
                return cache.computeIfAbsent(symbol, Glyph::new);
            }

            int size() {
                return cache.size();
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String s) {
        GlyphFactory factory = new GlyphFactory();
        java.util.Map<Character, Glyph> first = new java.util.HashMap<Character, Glyph>();
        boolean shared = true;
        // Step 3: Ask for the glyph of every character. A repeated character must give back the very same object.
        for (int i = 0; i < s.length(); i++) {
            Glyph glyph = factory.get(s.charAt(i));
            Glyph seen = first.putIfAbsent(s.charAt(i), glyph);
            if (seen != null && seen != glyph) {
                shared = false;
            }
        }
        return new String[] {"chars=" + s.length(), "objects=" + factory.size(), "shared=" + shared};
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(String.join("\n", solve(s)));
    }
}
Hints (2)
  1. Why must a flyweight be immutable?
  2. How many objects for n equal characters?