Composite Pattern

Part of the Object Oriented Programming section of Coddy's GDScript journey. Lesson 55 of 65.

The Composite pattern builds trees in which a single object and a group of objects have the same methods, so code can treat a whole group like one item. A bag holds items, a bag can hold other bags, and you ask any of them for its weight the same way.

Both kinds share an abstract parent:

# entry.gd
@abstract
class_name Entry
extends RefCounted

var entry_name: String

@abstract func get_weight() -> int
@abstract func display(indent: String) -> void

The leaf is a single item:

# item.gd
class_name Item
extends Entry

var weight: int

func _init(n: String, w: int) -> void:
	entry_name = n
	weight = w

func get_weight() -> int:
	return weight

func display(indent: String) -> void:
	print(indent, entry_name, " (", weight, ")")

The composite holds other entries and answers by asking each of them. A bag weighs 1 itself:

# bag.gd
class_name Bag
extends Entry

var contents: Array[Entry] = []

func _init(n: String) -> void:
	entry_name = n

func add(entry: Entry) -> void:
	contents.append(entry)

func get_weight() -> int:
	var total := 1
	for entry in contents:
		total += entry.get_weight()
	return total

func display(indent: String) -> void:
	print(indent, entry_name, " [", get_weight(), "]")
	for entry in contents:
		entry.display(indent + "  ")

# main.gd
var pouch := Bag.new("Pouch")
pouch.add(Item.new("Gem", 2))
var backpack := Bag.new("Backpack")
backpack.add(Item.new("Sword", 8))
backpack.add(pouch)
backpack.display("")

Backpack [12]
  Sword (8)
  Pouch [3]
    Gem (2)

Bag.get_weight() never checks whether an entry is an item or a bag: it calls the same method on each, and a bag inside answers by asking its own contents. That recursion walks the whole tree, however deep it is.

Links go one way, from a bag to its contents. If every entry also stored the bag it is in, each bag and its entries would point at each other, a reference cycle that is never freed. When an entry needs to know where it is, pass that information down as an argument, the way display() passes the indent.

Challenge

Medium

Build a folder tree with the Composite pattern. DiskEntry (disk_entry.gd) declares get_size(), count_files() and list_lines(indent). Write:

FileEntry: its size is its own size, it counts as 1 file, and list_lines() prints the indent, then NAME (SIZE KB).
FolderEntry: add(entry) stores a child. Its size is the sum of its children's sizes, its file count the sum of theirs, and list_lines() prints the indent, then NAME/ (SIZE KB), then lists every child with the indent plus two spaces.

The supplied code builds the tree from the input (how many lines follow, then folder NAME, file NAME SIZE or end, which closes the current folder), lists it and prints the totals. For a Root folder holding notes.txt (4 KB) and a Music folder with song.mp3 (300 KB) the output is:

Root/ (304 KB)
  notes.txt (4 KB)
  Music/ (300 KB)
    song.mp3 (300 KB)
Total: 304 KB, files: 2

Your code goes in file_entry.gd and folder_entry.gd. main.gd holds the supplied input/output code and cannot be edited.

Try it yourself

extends Node

func _ready():
	# Supplied input/output code: keep it as it is
	var open_folders: Array[FolderEntry] = []
	var root: FolderEntry = null
	var count := int(OS.read_string_from_stdin())
	for i in count:
		var parts := OS.read_string_from_stdin().split(" ")
		match parts[0]:
			"folder":
				var folder := FolderEntry.new(parts[1])
				if open_folders.is_empty():
					root = folder
				else:
					open_folders.back().add(folder)
				open_folders.append(folder)
			"file":
				open_folders.back().add(FileEntry.new(parts[1], int(parts[2])))
			"end":
				open_folders.pop_back()
	root.list_lines("")
	print("Total: %d KB, files: %d" % [root.get_size(), root.count_files()])