Skip to main content
Version: 2.10.x(Latest)

Josephus Problem​

We use gring to simulate the Josephus Problem:

info

The famous Jewish historian Josephus had the following story: After the Romans conquered Jotapata, 39 Jews and Josephus and his friend hid in a cave. The 39 Jews decided they would rather die than be captured by the enemy, so they decided on a suicide method. 41 people stood in a circle, starting from the first person to count. Every time they counted to the third person, that person had to commit suicide, and then the next person would restart counting until everyone had committed suicide.

However, Josephus and his friend did not want to comply. Starting from one person, skip k-2 people (because the first person was already skipped), and kill the kth person. Then, skip k-1 more people and kill the kth person. This process continues around the circle until only one person remains, who can continue to live. The question is, given the values, where should you stand initially to avoid being executed?

Traditional Implementation​

The following example is for non-concurrency-safe scenarios.

package main

import (
    "fmt"
    "github.com/gogf/gf/v2/container/gring"
)

type Player struct {
    position int  // position
    alive    bool // is alive
}

const (
    playerCount = 41  // number of players
    startPos    = 1   // starting position for counting
)

var (
    deadline = 3
)

func main() {
    r := gring.New(playerCount)

    // Set initial values for all players
    for i := 1; i <= playerCount; i++ {
        r.Put(&Player{i, true})
    }

    // If the starting position is not 1, set the starting position
    if startPos > 1 {
        r.Move(startPos - 1)
    }

    counter   := 1  // counting starts from 1, because the loop below starts counting from the second person
    deadCount := 0  // number of deaths, initial value is 0

    // Loop until all are dead
    for deadCount < playerCount {
        // Jump to next person
        r.Next()

        // If the person is alive, count
        if r.Val().(*Player).alive {
            counter++
        }

        // If count reaches deadline, this person is eliminated
        if counter == deadline {
            r.Val().(*Player).alive = false
            fmt.Printf("Player %d died!\n", r.Val().(*Player).position)
            deadCount++
            counter = 0
        }
    }
}

After execution, the output is:

Player 3 died!
Player 6 died!
Player 9 died!
Player 12 died!
Player 15 died!
Player 18 died!
Player 21 died!
Player 24 died!
Player 27 died!
Player 30 died!
Player 33 died!
Player 36 died!
Player 39 died!
Player 1 died!
Player 5 died!
Player 10 died!
Player 14 died!
Player 19 died!
Player 23 died!
Player 28 died!
Player 32 died!
Player 37 died!
Player 41 died!
Player 7 died!
Player 13 died!
Player 20 died!
Player 26 died!
Player 34 died!
Player 40 died!
Player 11 died!
Player 22 died!
Player 35 died!
Player 8 died!
Player 25 died!
Player 4 died!
Player 29 died!
Player 2 died!
Player 38 died!
Player 17 died!
Player 12 died!
Player 31 died!

Generic Version Implementation​

tip

Version requirement: v2.10.0

Starting from v2.10.0, you can use the generic version TRing[T] to implement the same functionality with cleaner code and type safety.

Josephus Problem Generic Implementation​

package main

import (
    "fmt"
    "github.com/gogf/gf/v2/container/gring"
)

type Player struct {
    Position int  // Position
    Alive    bool // Is alive
}

const (
    playerCount = 41 // number of players
    startPos    = 1  // starting position for counting
    deadline    = 3  // counting threshold
)

func main() {
    // Create generic ring, type-safe
    r := gring.NewTRing[*Player](playerCount)

    // Set initial values for all players
    for i := 1; i <= playerCount; i++ {
        r.Put(&Player{
            Position: i,
            Alive:    true,
        })
    }

    // If the starting position is not 1, set the starting position
    if startPos > 1 {
        r.Move(startPos - 1)
    }

    counter := 1   // counting starts from 1
    deadCount := 0 // number of deaths

    // Loop until all are dead
    for deadCount < playerCount {
        // Jump to next person
        r.Next()

        // No type assertion needed, use directly
        player := r.Val()
        
        // If the person is alive, count
        if player.Alive {
            counter++
        }

        // If count reaches deadline, this person is eliminated
        if counter == deadline {
            player.Alive = false
            fmt.Printf("Player %d died!\n", player.Position)
            deadCount++
            counter = 0
        }
    }
}

Circular Buffer Example​

Use generic ring to implement a fixed-size circular buffer:

package main

import (
    "fmt"
    "github.com/gogf/gf/v2/container/gring"
)

type LogEntry struct {
    Timestamp int64
    Message   string
    Level     string
}

func main() {
    // Create a log buffer ring with capacity 5
    logBuffer := gring.NewTRing[*LogEntry](5)

    // Add 10 log entries (exceeds capacity, old ones will be overwritten)
    for i := 1; i <= 10; i++ {
        logBuffer.Put(&LogEntry{
            Timestamp: int64(i),
            Message:   fmt.Sprintf("Log message %d", i),
            Level:     "INFO",
        })
    }

    fmt.Printf("Buffer capacity: %d\n", logBuffer.Cap())
    fmt.Printf("Buffer length: %d\n", logBuffer.Len())

    // Get all logs (only the latest 5)
    logBuffer.Move(-5)
    logBuffer.RLockIteratorNext(func(entry *LogEntry) bool {
        fmt.Printf("Timestamp: %d, Level: %s, Message: %s\n",
            entry.Timestamp, entry.Level, entry.Message)
        return true
    })
}

After execution, the output is:

Buffer capacity: 5
Buffer length: 5
Timestamp: 6, Level: INFO, Message: Log message 6
Timestamp: 7, Level: INFO, Message: Log message 7
Timestamp: 8, Level: INFO, Message: Log message 8
Timestamp: 9, Level: INFO, Message: Log message 9
Timestamp: 10, Level: INFO, Message: Log message 10

Sliding Window Statistics Example​

Use generic ring to implement sliding window statistics:

package main

import (
    "fmt"
    "github.com/gogf/gf/v2/container/gring"
)

func main() {
    // Create a statistics ring with window size 5
    window := gring.NewTRing[int](5)

    // Simulate data stream
    dataStream := []int{10, 20, 30, 40, 50, 60, 70, 80, 90, 100}

    for _, value := range dataStream {
        // Add new data
        window.Put(value)

        // Calculate current window sum
        sum := 0
        values := window.SliceNext()
        for _, v := range values {
            sum += v
        }

        // Calculate average
        count := len(values)
        if count > 0 {
            avg := float64(sum) / float64(count)
            fmt.Printf("Value: %d, Window: %v, Sum: %d, Avg: %.2f\n",
                value, values, sum, avg)
        }
    }
}

After execution, the output is:

Value: 10, Window: [10], Sum: 10, Avg: 10.00
Value: 20, Window: [10 20], Sum: 30, Avg: 15.00
Value: 30, Window: [10 20 30], Sum: 60, Avg: 20.00
Value: 40, Window: [10 20 30 40], Sum: 100, Avg: 25.00
Value: 50, Window: [10 20 30 40 50], Sum: 150, Avg: 30.00
Value: 60, Window: [20 30 40 50 60], Sum: 200, Avg: 40.00
Value: 70, Window: [30 40 50 60 70], Sum: 250, Avg: 50.00
Value: 80, Window: [40 50 60 70 80], Sum: 300, Avg: 60.00
Value: 90, Window: [50 60 70 80 90], Sum: 350, Avg: 70.00
Value: 100, Window: [60 70 80 90 100], Sum: 400, Avg: 80.00

Concurrency-Safe Usage​

Concurrent Write Example​

package main

import (
    "fmt"
    "sync"
    "time"
    "github.com/gogf/gf/v2/container/gring"
)

type Task struct {
    ID        int
    Name      string
    CreatedAt time.Time
}

func main() {
    // Create a concurrency-safe task ring
    taskRing := gring.NewTRing[*Task](10, true)

    var wg sync.WaitGroup

    // Concurrently add tasks
    for i := 0; i < 20; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            taskRing.Put(&Task{
                ID:        id,
                Name:      fmt.Sprintf("Task-%d", id),
                CreatedAt: time.Now(),
            })
        }(i)
    }

    wg.Wait()

    // Read all tasks
    fmt.Printf("Total tasks in ring: %d\n", taskRing.Len())
    taskRing.RLockIteratorNext(func(task *Task) bool {
        fmt.Printf("Task ID: %d, Name: %s\n", task.ID, task.Name)
        return true
    })
}

Type Safety Comparison​

Traditional vs Generic Approach​

package main

import (
    "fmt"
    "github.com/gogf/gf/v2/container/gring"
)

type User struct {
    ID   int
    Name string
}

func main() {
    // Traditional approach - requires type assertion
    r1 := gring.New(5)
    r1.Put(&User{ID: 1, Name: "Alice"})
    
    // Type assertion needed, may panic at runtime
    user1 := r1.Val().(*User)
    fmt.Printf("User1: %+v\n", user1)

    // Generic approach - type-safe
    r2 := gring.NewTRing[*User](5)
    r2.Put(&User{ID: 2, Name: "Bob"})
    
    // No type assertion needed, compile-time checking
    user2 := r2.Val()
    fmt.Printf("User2: %+v\n", user2)
}

Performance Notes​

  • Generic version TRing[T] has essentially the same performance as traditional version Ring
  • Generic version performs type checking at compile time, avoiding runtime type assertion overhead
  • Ring structure uses fixed memory, no additional memory allocation
  • Recommended to use generic version in new projects to improve code safety and maintainability