Understanding Golang Ordered Map with Code Examples

>> Read more about Golang:

• Introduction To The Go Programming Language
• Go Tutorial: Golang Basics of Knowledge for Beginners
• Best Practices For Dependency Inversion in Golang
• Detailed Code Examples of Dependency Inversion in Golang
• Hands-On Implementation for Dependency Injection in Go

What is An Ordered Map?

An ordered map (also known as a linked map or ordered dictionary) is a data structure that combines the properties of a map (or dictionary) and maintains the order of insertion of elements. Unlike a regular map in many programming languages, where the order of elements is not guaranteed, an ordered map ensures that the elements are stored in the order in which they were added.

The key features of a Golang ordered map include:

• Order Preservation: Elements in an ordered map are stored in the order in which they were inserted. This order is maintained when iterating over the map or when retrieving keys/values.
• Key-Value Pairs: Like a regular map, an ordered map consists of key-value pairs, where each key is associated with a unique value.
• Efficient Key Lookup: The map data structure allows for efficient lookup of values based on their corresponding keys.
• Iteration: Iterating over an ordered map provides elements in the order of insertion, allowing for predictable and sequential processing.

5 Reasons Why We Need Go Ordered Map

Here are five scenarios where maintaining the order of insertion in a map can be beneficial:

Configuration Settings

When loading configuration settings from a file or another data source, preserving the order in which the settings are specified can be essential. This ensures that the settings are applied in the intended sequence, which might be crucial for the correct behavior of a system.

Command Line Argument Processing

In command line argument parsing, the order of arguments can be important. Keeping track of the order in which the arguments are provided allows the program to interpret them correctly, especially when some arguments depend on others or when the order influences the program's behavior.

Transaction Logs

Maintaining the order of transactions in a log can be vital for auditing and debugging purposes. If you're logging events or transactions in a system, preserving the chronological order of these events can help in diagnosing issues and understanding the sequence of operations.

Template Rendering in Web Development

In web development, when rendering templates that include dynamic content or placeholders, the order in which the placeholders are defined can be crucial. Preserving this order ensures that the template is rendered correctly and that dynamic data is inserted in the intended locations.

Pipeline of Data Processing

When building a data processing pipeline, where data undergoes a series of transformations or analyses, the order in which processing steps are defined can be significant. Keeping track of this order in a map allows for a clear representation of the sequence of operations in the pipeline.

Go Ordered Map Code Sample

package main

import (
	"github.com/smallnest/exp/container/list"
	"log"
)

type OrderedMap[K comparable, V any] struct {
	entries map[K]*Entry[K, V]
	list    *list.List[*Entry[K, V]]
}

type Entry[K comparable, V any] struct {
	Key     K
	Value   V
	element *list.Element[*Entry[K, V]]
}

func (e *Entry[K, V]) Next() *Entry[K, V] {
	entry := e.element.Next()
	if entry == nil {
		return nil
	}
	return entry.Value
}

func (e *Entry[K, V]) Prev() *Entry[K, V] {
	entry := e.element.Prev()
	if entry == nil {
		return nil
	}
	return entry.Value
}

func (m *OrderedMap[K, V]) Set(key K, value V) (val V, existed bool) {
	if entry, existed := m.entries[key]; existed { // If the key exists, it is updated
		oldValue := entry.Value
		entry.Value = value
		return oldValue, true
	}
	entry := &Entry[K, V]{
		Key:   key,
		Value: value,
	}
	entry.element = m.list.PushBack(entry) // Add to linked list
	m.entries[key] = entry                 // Add to map
	return value, false
}

func (m *OrderedMap[K, V]) Delete(key K) (val V, existed bool) {
	if entry, existed := m.entries[key]; existed { // If present
		m.list.Remove(entry.element) // Remove from linked list
		delete(m.entries, key)       // Remove from map
		return entry.Value, true
	}
	return
}

func (m *OrderedMap[K, V]) Get(key K) (val V, existed bool) {
	if entry, existed := m.entries[key]; existed {
		return entry.Value, true
	}
	return
}
 
func (m *OrderedMap[K, V]) Range(f func(key K, value V) bool) {
	l := m.list
	for e := l.Front(); e != nil; e = e.Next() {
		if e.Value != nil {
			if ok := f(e.Value.Key, e.Value.Value); !ok {
				return
			}
		}
	}
}

func main() {
	m := OrderedMap[int, int]{}
	m.entries = make(map[int]*Entry[int, int])
	m.list = list.New[*Entry[int, int]]()
	m.Set(5, 4)
	m.Set(1, 2)
	m.Set(2, 3)
	m.Set(6, 1)
	m.Range(func(key int, value int) bool {
		log.Println(key, value)
		return true
	})
}

Result:

2023/12/22 22:41:47 5 4
2023/12/22 22:41:47 1 2
2023/12/22 22:41:47 2 3
2023/12/22 22:41:47 6 1

This Go code defines a simple implementation of an ordered map using a combination of a Go map (entries) and a linked list (list). The map (entries) is used for fast key-based access, while the linked list (list) is used to maintain the order of insertion.

Let's break down the code:

Package and Imports:

The code is part of the main package and imports the "github.com/smallnest/exp/container/list" package, which provides a doubly-linked list implementation.

OrderedMap and Entry Types:

• OrderedMap is a generic type that takes two parameters (K for key and V for value).
• It has two fields: entries (a map to store key-value pairs) and list (a linked list to maintain the order of insertion).
• Entry is a type that represents a key-value pair along with a pointer to an element in the linked list.

Next and Prev Methods:

The Next and Prev methods are defined on the Entry type. They allow navigation to the next and previous entries in the linked list.

Set Method:

• Set method adds or updates a key-value pair in the ordered map.
• If the key already exists, the value is updated, and the entry is moved to the end of the linked list (to represent the most recent access).
• If the key is new, a new entry is created, added to the end of the linked list, and added to the map.

Delete Method:

• Delete method removes a key-value pair from the ordered map.
• It removes the corresponding entry from the linked list and deletes the entry from the map.

Get Method:

• Get method retrieves the value associated with a key.
• It checks if the key exists in the map and returns the associated value along with a boolean indicating whether the key was found.

Range Method:

• Range method iterates over the key-value pairs in the order of insertion.
• It takes a function (f) as an argument and calls this function for each key-value pair.
• If the function returns false, the iteration stops.

Main Function:

• In the main function, an instance of OrderedMap with key and value types as int is created.
• Key-value pairs are added to the map using the Set method.
• The Range method is then used to iterate over the map and print the key-value pairs in the order of insertion.

This implementation allows you to maintain both fast key-based access and the order of insertion for the key-value pairs in the map. The linked list ensures that the elements are processed in the order in which they were added.

Log User Interaction

type UserInteraction struct {
	UserID   int
	Action   string
	DateTime string
}

func LogUserInteraction() {
	// Create an OrderedMap to track user interactions.
	interactionMap := OrderedMap[int, UserInteraction]{}
	interactionMap.entries = make(map[int]*Entry[int, UserInteraction])
	interactionMap.list = list.New[*Entry[int, UserInteraction]]()

	// Simulate user interactions and store them in the OrderedMap.
	interactionMap.Set(1, UserInteraction{UserID: 1, Action: "Login", DateTime: "2023-01-01 12:00:00"})
	interactionMap.Set(2, UserInteraction{UserID: 2, Action: "Register", DateTime: "2023-01-02 08:30:00"})
	interactionMap.Set(1, UserInteraction{UserID: 1, Action: "Logout", DateTime: "2023-01-03 15:45:00"})
	interactionMap.Set(3, UserInteraction{UserID: 3, Action: "ViewPage", DateTime: "2023-01-04 10:20:00"})

	// Iterate over user interactions in the order of insertion and print them.
	fmt.Println("User Interactions:")
	interactionMap.Range(func(userID int, interaction UserInteraction) bool {
		log.Printf("UserID: %d, Action: %s, DateTime: %s", userID, interaction.Action, interaction.DateTime)
		return true
	})
}

Result:

User Interactions:
2023/12/22 22:48:58 UserID: 1, Action: Logout, DateTime: 2023-01-03 15:45:00
2023/12/22 22:48:58 UserID: 2, Action: Register, DateTime: 2023-01-02 08:30:00
2023/12/22 22:48:58 UserID: 3, Action: ViewPage, DateTime: 2023-01-04 10:20:00

Explain:

This code defines a UserInteraction struct and a function LogUserInteraction that uses an OrderedMap to log and track user interactions. Let's break down the code step by step:

type UserInteraction struct {
    UserID   int
    Action   string
    DateTime string
}

The UserInteraction struct represents an interaction made by a user. It has three fields:

• UserID: An integer representing the user's ID.
• Action: A string representing the action the user performed (e.g., "Login," "Register," "Logout," "ViewPage").
• DateTime: A string representing the date and time of the interaction.

func LogUserInteraction() {
    // Create an OrderedMap to track user interactions.
    interactionMap := OrderedMap[int, UserInteraction]{}
    interactionMap.entries = make(map[int]*Entry[int, UserInteraction])
    interactionMap.list = list.New[*Entry[int, UserInteraction]]()
}

The LogUserInteraction function initializes an OrderedMap named interactionMap to store user interactions. It creates an empty map (entries) and an empty linked list (list). The OrderedMap is generic, with integer keys (int) representing user IDs and UserInteraction values representing the user's interaction details.

// Simulate user interactions and store them in the OrderedMap.
interactionMap.Set(1, UserInteraction{UserID: 1, Action: "Login", DateTime: "2023-01-01 12:00:00"})
interactionMap.Set(2, UserInteraction{UserID: 2, Action: "Register", DateTime: "2023-01-02 08:30:00"})
interactionMap.Set(1, UserInteraction{UserID: 1, Action: "Logout", DateTime: "2023-01-03 15:45:00"})
interactionMap.Set(3, UserInteraction{UserID: 3, Action: "ViewPage", DateTime: "2023-01-04 10:20:00"})

The function simulates user interactions by adding entries to the interactionMap using the Set method. The interactions include a user logging in, registering, logging out, and viewing a page. The Set method is used to add or update entries in the map.

// Iterate over user interactions in the order of insertion and print them.
	fmt.Println("User Interactions:")
	interactionMap.Range(func(userID int, interaction UserInteraction) bool {
		log.Printf("UserID: %d, Action: %s, DateTime: %s", userID, interaction.Action, interaction.DateTime)
		return true
	})

Finally, the function uses the Range method to iterate over the user interactions stored in the interactionMap. It prints the details of each interaction in the order of insertion, including the user ID, action, and date/time. The log.Printf function is used for logging.

>> Read more about Golang coding:

• Cloud Success Blueprint: Why Go Is A Perfect Match?
• A Comprehensive Guide To Dockerize A Golang Application
• Practical Guide to Dependency Injection in Go: Hands-On Implementation
• Practical SOLID in Golang: Single Responsibility Principle
• Instruction For Using Golang Generics With Code Examples
• Detailed Guide for Simplifying Testing with Golang Testify
• Go for Web Development: How Top Companies Achieve Powerful Business Results with Golang?

Data Processing

type DataProcessor struct {
	ID      int
	Name    string
	Process func(data int) int
}

func DataProcessing() {
	// Create an OrderedMap to store data processing steps.
	pipeline := OrderedMap[int, DataProcessor]{}
	pipeline.entries = make(map[int]*Entry[int, DataProcessor])
	pipeline.list = list.New[*Entry[int, DataProcessor]]()

	// Define data processing steps and add them to the pipeline.
	pipeline.Set(1, DataProcessor{ID: 1, Name: "Step A", Process: func(data int) int {
		log.Printf("Processing data %d with Step A", data)
		return data * 2
	}})
	pipeline.Set(2, DataProcessor{ID: 2, Name: "Step B", Process: func(data int) int {
		log.Printf("Processing data %d with Step B", data)
		return data + 5
	}})
	pipeline.Set(3, DataProcessor{ID: 3, Name: "Step C", Process: func(data int) int {
		log.Printf("Processing data %d with Step C", data)
		return data - 3
	}})
	pipeline.Set(4, DataProcessor{ID: 4, Name: "Step D", Process: func(data int) int {
		log.Printf("Processing data %d with Step D", data)
		return data / 2
	}})

	// Simulate processing data through the pipeline.
	inputData := 10
	for e := pipeline.list.Front(); e != nil; e = e.Next() {
		step := e.Value
		log.Printf("Input data: %d", inputData)
		inputData = step.Value.Process(inputData)
	}

	// Print the final result after processing through the pipeline.
	fmt.Printf("\nFinal Result: %d\n", inputData)
}

Result:

2023/12/22 23:06:38 Input data: 10
2023/12/22 23:06:38 Processing data 10 with Step A
2023/12/22 23:06:38 Input data: 20
2023/12/22 23:06:38 Processing data 20 with Step B
2023/12/22 23:06:38 Input data: 25
2023/12/22 23:06:38 Processing data 25 with Step C
2023/12/22 23:06:38 Input data: 22
2023/12/22 23:06:38 Processing data 22 with Step D

Explain:

This code defines a DataProcessor struct and a function DataProcessing that uses an OrderedMap to simulate a data processing pipeline. Let's break down the code step by step:

type DataProcessor struct {
    ID      int
    Name    string
    Process func(data int) int
}

The DataProcessor struct represents a step in the data processing pipeline. It has three fields:

• ID: An integer representing the identifier of the data processing step.
• Name: A string representing the name or description of the data processing step.
• Process: A function that takes an integer (data) as input and returns an integer as the processed output.

// Create an OrderedMap to store data processing steps.
pipeline := OrderedMap[int, DataProcessor]{}
pipeline.entries = make(map[int]*Entry[int, DataProcessor])
pipeline.list = list.New[*Entry[int, DataProcessor]]()

The DataProcessing function initializes an OrderedMap named pipeline to store data processing steps. It creates an empty map (entries) and an empty linked list (list). The OrderedMap is generic, with integer keys (int) representing the data processing step IDs and DataProcessor values representing the processing step details.

// Define data processing steps and add them to the pipeline.
pipeline.Set(1, DataProcessor{ID: 1, Name: "Step A", Process: func(data int) int {
    log.Printf("Processing data %d with Step A", data)
    return data * 2
}})
pipeline.Set(2, DataProcessor{ID: 2, Name: "Step B", Process: func(data int) int {
    log.Printf("Processing data %d with Step B", data)
    return data + 5
}})
pipeline.Set(3, DataProcessor{ID: 3, Name: "Step C", Process: func(data int) int {
    log.Printf("Processing data %d with Step C", data)
    return data - 3
}})
pipeline.Set(4, DataProcessor{ID: 4, Name: "Step D", Process: func(data int) int {
    log.Printf("Processing data %d with Step D", data)
    return data / 2
}})

The function defines four data processing steps (Step A, Step B, Step C, and Step D) and adds them to the pipeline using the Set method. Each processing step includes an ID, a name, and a processing function defined as a lambda function. The Set method is used to add or update entries in the map.

	
  // Simulate processing data through the pipeline.
  inputData := 10
  for e := pipeline.list.Front(); e != nil; e = e.Next() {
      step := e.Value
      log.Printf("Input data: %d", inputData)
      inputData = step.Value.Process(inputData)
  }

The function simulates processing data through the pipeline by iterating over the ordered map (pipeline) using the Front method of the linked list. It logs the input data for each processing step and updates the input data using the processing function associated with each step

Finally, the function prints the final result after processing through the entire pipeline. The inputData variable contains the final result of the data processing pipeline.