Introduction
Go's standard package Container includes commonly used container types, including container/list, container/heap, container/ring. This article explains the use of container/ring.
ring package
The ring package provides operations for a ring-link list. It exports only one type, Ring:
// Ring represents the elements in the ring-linked list.type Ring struct { Value interface{} // Value type is interface{}, so it can accept any type} // Create a circular link table of length nfunc New(n int) *Ring // F(x) operation for each element x in the circular linked listfunc (r *Ring) Do(f func(interface{})) // Get the length of the ring link listfunc (r *Ring) Len() int // If r and s are in the same ring list, the elements between r and s are deleted.// The deleted elements form a new circular linked list, and the return value is the pointer to the circular linked list (that is, the element represented by r->Next() before deletion)// If r and s are not in the same circular list, then s is inserted after r and the return value is// After inserting s, the next element of the last element of s (that is, the element represented by r->Next() before insertion)func (r *Ring) Link(s *Ring) *Ring // Move n % () positions, both positive and negative can befunc (r *Ring) Move(n int) *Ring // Return to the next elementfunc (r *Ring) Next() *Ring // Return to the previous elementfunc (r *Ring) Prev() *Ring // Delete n % () elements after rfunc (r *Ring) Unlink(n int) *Ring
Example
How to use Ring
package main import ( "container/ring" "fmt" ) func main() { const rLen = 3 // Create a new Ring r := (rLen) for i := 0; i < rLen; i++ { = i r = () } ("Length of ring: %d\n", ()) // Length of ring: 3 // This anonymous function is used to print data in Ring printRing := func(v interface{}) { (v, " ") } (printRing) // 0 1 2 () // Multiply the value of the second element after r by 2 (2).Value = (2).Value.(int) * 2 (printRing) // 0 1 4 () // Delete the elements between r and r+2, that is, delete r+1 // Returns the Ring pointer composed of deleted elements result := ((2)) (printRing) // 0 4 () (printRing) // 1 () another := (rLen) = 7 ().Value = 8 // Assign a value to the element represented by another + 1, that is, the second element ().Value = 9 // Assign a value to the element represented by another - 1, that is, the third element (printRing) // 7 8 9 () // Insert another to the back of r, return to the next element before inserting r result = (another) (printRing) // 0 7 8 9 4 () (printRing) // 4 0 7 8 9 () // Delete the three elements after r and return the Ring pointer composed of the deleted elements result = (3) (printRing) // 0 4 () (printRing) // 7 8 9 () }
Simulate the Joseph problem
The ring list can simulate the Joseph problem. The Joseph problem is described as follows:
From Baidu:
It is said that the famous Jewish historian Josephus has had the following story: After the Romans occupied Jotapat, 39 Jews hid in a hole with Josephus and his friends, and 39 Jews decided to die rather than be caught by the enemy, so they decided to commit suicide. 41 people lined up in a circle, and the first person started to report the number. For each person who reported to the third person, the person had to commit suicide, and then the next person recounted until everyone killed himself. Yet Josephus and his friends didn't want to comply. First start with one person, go over k-2 people (because the first person has been crossed), and kill the k-th person. Then, go over k-1 and kill the k-th person. This process continues along the circle until in the end only one person is left, and the person can continue to live. The question is, given the Gang, where should we stand at the beginning to avoid being executed? Josephus asked his friend to pretend to comply first, and he arranged his friend and himself in the 16th and 31st positions, so he escaped the game of death.
Simulate it with code as follows:
package main import ( "container/ring" "fmt" ) type Player struct { position int // Location alive bool // Whether to survive} func main() { const ( playerCount = 41 // Number of players startPos = 1 // Start counting position ) deadline := 3 r := (playerCount) // Set the initial value of all players for i := 1; i <= playerCount; i++ { = &Player{i, true} r = () } // If the starting number position is not 1, set the starting position if startPos > 1 { r = (startPos - 1) } counter := 1 // The number starts at 1, because the following loop starts at the second deadCount := 0 // The number of deaths, the initial value is 0 for deadCount < playerCount { // until everyone dies, otherwise the loop will be executed r = () // Jump to the next person // If it is a living person, then the number will be reported if .(*Player).alive { counter++ } // If the report is deadline, the person will be eliminated if counter == deadline { .(*Player).alive = false ("Player %d died!\n", .(*Player).position) deadCount++ counter = 0 // Set the number to 0 } } }
The output is as follows, you can see that 16 and 31 are the last two out of the queue, so it is safe for Josephus to arrange his friends and himself in the 16th and 31st positions.
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 8 died!
Player 17 died!
Player 29 died!
Player 38 died!
Player 11 died!
Player 25 died!
Player 2 died!
Player 22 died!
Player 4 died!
Player 35 died!
Player 16 died!
Player 31 died!
Supplement: Heap, list, ring in go language
Use of heap heap:
package main import ( "container/heap" "fmt" ) type IntHeap []int //We need to implement 5 interfaces for customizing a heap//Len(),Less(),Swap() is inherited from//Push() and Pop() are the interfaces of the heap //Return lengthfunc (h *IntHeap) Len() int { return len(*h); } //Compare size (to implement the minimum heap)func (h *IntHeap) Less(i, j int) bool { return (*h)[i] < (*h)[j]; } //Swap valuesfunc (h *IntHeap) Swap(i, j int) { (*h)[i], (*h)[j] = (*h)[j], (*h)[i]; } //Press in datafunc (h *IntHeap) Push(x interface{}) { //Append data to h *h = append(*h, x.(int)) } //Popt datafunc (h *IntHeap) Pop() interface{} { old := *h; n := len(old); x := old[n-1]; //Let h point to the new slice *h = old[0: n-1]; //Return the last element return x; } //Print stackfunc (h *IntHeap) PrintHeap() { //Element index number i := 0 //The number of elements at the level levelCount := 1 for i+1 <= () { ((*h)[i: i+levelCount]) i += levelCount if (i + levelCount*2) <= () { levelCount *= 2 } else { levelCount = () - i } } } func main() { a := IntHeap{6, 2, 3, 1, 5, 4}; //Initialize the heap (&a); (); //Popt out data to ensure that every operation is a standard heap structure ((&a)); (); ((&a)); (); (&a, 0); (&a, 8); (); }
Use of list linked list:
package main; import ( "container/list" "fmt" ) func printList(l *) { for e := (); e != nil; e = () { (, " "); } (); } func main() { //Create a linked list l := (); //Elements are inserted at the end of the linked list a1 := (1); b2 := (2); //Insert elements at the head of the linked list (3); (4); printList(l); //Take the first element f := (); (); //Take the last element b := (); (); //Get the linked list length (()); //Insert after an element (66, a1); //Insert before an element (88, a1); printList(l); l2 := (); (11); (22); //A new link is inserted at the end (l2); printList(l); //Insert a new link to the header of the link (l2); printList(l); //Move the element to the end (a1); printList(l); //Move the element to the head (a1); printList(l); //Move the element after a certain element (b2, a1); printList(l); //Move the element before a certain element (b2, a1); printList(l); //Delete an element (a1); printList(l); }
Use of ring ring:
package main; import ( "container/ring" "fmt" ) func printRing(r *) { (func(v interface{}) { (v.(int), " "); }); (); } func main() { //Create a ring link table r := (5); //Cyclic assignment for i := 0; i < 5; i++ { = i; //Get the next element r = (); } printRing(r); //Length of the ring (()); //The pointer of the moving ring (2); //Delete n elements from the current pointer (2); printRing(r); //Connect two rings r2 := (3); for i := 0; i < 3; i++ { = i + 10; //Get the next element r2 = (); } printRing(r2); (r2); printRing(r); }
The above is personal experience. I hope you can give you a reference and I hope you can support me more. If there are any mistakes or no complete considerations, I would like to give you advice.