5561080764

Committed 15 Jul 2023 07:24AM UTC coverage: 73.196% (+0.05%) from 73.149%

Build # 5561080764

Build Type

push

github

Committed by

HDT3213

Commit Message

chore: use t.Errorf(...) instead of t.Error(fmt.Sprintf(...))

Run Details

7660 of 10465 relevant lines covered (73.2%)

0.81 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

16.17

/datastruct/sortedset/sortedset.go

package sortedset

import (
        "strconv"
)

// SortedSet is a set which keys sorted by bound score
type SortedSet struct {
        dict     map[string]*Element
        skiplist *skiplist
}

// Make makes a new SortedSet
func Make() *SortedSet {
        return &SortedSet{
                dict:     make(map[string]*Element),
                skiplist: makeSkiplist(),
        }
}

// Add puts member into set,  and returns whether it has inserted new node
func (sortedSet *SortedSet) Add(member string, score float64) bool {
        element, ok := sortedSet.dict[member]
        sortedSet.dict[member] = &Element{
                Member: member,
                Score:  score,
        }
        if ok {
                if score != element.Score {
                        sortedSet.skiplist.remove(member, element.Score)
                        sortedSet.skiplist.insert(member, score)
                }
                return false
        }
        sortedSet.skiplist.insert(member, score)
        return true
}

// Len returns number of members in set
func (sortedSet *SortedSet) Len() int64 {
        return int64(len(sortedSet.dict))
}

// Get returns the given member
func (sortedSet *SortedSet) Get(member string) (element *Element, ok bool) {
        element, ok = sortedSet.dict[member]
        if !ok {
                return nil, false
        }
        return element, true
}

// Remove removes the given member from set
func (sortedSet *SortedSet) Remove(member string) bool {
        v, ok := sortedSet.dict[member]
        if ok {
                sortedSet.skiplist.remove(member, v.Score)
                delete(sortedSet.dict, member)
                return true
        }
        return false
}

// GetRank returns the rank of the given member, sort by ascending order, rank starts from 0
func (sortedSet *SortedSet) GetRank(member string, desc bool) (rank int64) {
        element, ok := sortedSet.dict[member]
        if !ok {
                return -1
        }
        r := sortedSet.skiplist.getRank(member, element.Score)
        if desc {
                r = sortedSet.skiplist.length - r
        } else {
                r--
        }
        return r
}

// ForEachByRank visits each member which rank within [start, stop), sort by ascending order, rank starts from 0
func (sortedSet *SortedSet) ForEachByRank(start int64, stop int64, desc bool, consumer func(element *Element) bool) {
        size := int64(sortedSet.Len())
        if start < 0 || start >= size {
                panic("illegal start " + strconv.FormatInt(start, 10))
        }
        if stop < start || stop > size {
                panic("illegal end " + strconv.FormatInt(stop, 10))
        }

        // find start node
        var node *node
        if desc {
                node = sortedSet.skiplist.tail
                if start > 0 {
                        node = sortedSet.skiplist.getByRank(int64(size - start))
                }
        } else {
                node = sortedSet.skiplist.header.level[0].forward
                if start > 0 {
                        node = sortedSet.skiplist.getByRank(int64(start + 1))
                }
        }

        sliceSize := int(stop - start)
        for i := 0; i < sliceSize; i++ {
                if !consumer(&node.Element) {
                        break
                }
                if desc {
                        node = node.backward
                } else {
                        node = node.level[0].forward
                }
        }
}

// RangeByRank returns members which rank within [start, stop), sort by ascending order, rank starts from 0
func (sortedSet *SortedSet) RangeByRank(start int64, stop int64, desc bool) []*Element {
        sliceSize := int(stop - start)
        slice := make([]*Element, sliceSize)
        i := 0
        sortedSet.ForEachByRank(start, stop, desc, func(element *Element) bool {
                slice[i] = element
                i++
                return true
        })
        return slice
}

// RangeCount returns the number of  members which score or member within the given border
func (sortedSet *SortedSet) RangeCount(min Border, max Border) int64 {
        var i int64 = 0
        // ascending order
        sortedSet.ForEachByRank(0, sortedSet.Len(), false, func(element *Element) bool {
                gtMin := min.less(element) // greater than min
                if !gtMin {
                        // has not into range, continue foreach
                        return true
                }
                ltMax := max.greater(element) // less than max
                if !ltMax {
                        // break through score border, break foreach
                        return false
                }
                // gtMin && ltMax
                i++
                return true
        })
        return i
}

// ForEach visits members which score or member within the given border
func (sortedSet *SortedSet) ForEach(min Border, max Border, offset int64, limit int64, desc bool, consumer func(element *Element) bool) {
        // find start node
        var node *node
        if desc {
                node = sortedSet.skiplist.getLastInRange(min, max)
        } else {
                node = sortedSet.skiplist.getFirstInRange(min, max)
        }

        for node != nil && offset > 0 {
                if desc {
                        node = node.backward
                } else {
                        node = node.level[0].forward
                }
                offset--
        }

        // A negative limit returns all elements from the offset
        for i := 0; (i < int(limit) || limit < 0) && node != nil; i++ {
                if !consumer(&node.Element) {
                        break
                }
                if desc {
                        node = node.backward
                } else {
                        node = node.level[0].forward
                }
                if node == nil {
                        break
                }
                gtMin := min.less(&node.Element) // greater than min
                ltMax := max.greater(&node.Element)
                if !gtMin || !ltMax {
                        break // break through score border
                }
        }
}

// Range returns members which score or member within the given border
// param limit: <0 means no limit
func (sortedSet *SortedSet) Range(min Border, max Border, offset int64, limit int64, desc bool) []*Element {
        if limit == 0 || offset < 0 {
                return make([]*Element, 0)
        }
        slice := make([]*Element, 0)
        sortedSet.ForEach(min, max, offset, limit, desc, func(element *Element) bool {
                slice = append(slice, element)
                return true
        })
        return slice
}

// RemoveRange removes members which score or member within the given border
func (sortedSet *SortedSet) RemoveRange(min Border, max Border) int64 {
        removed := sortedSet.skiplist.RemoveRange(min, max, 0)
        for _, element := range removed {
                delete(sortedSet.dict, element.Member)
        }
        return int64(len(removed))
}

func (sortedSet *SortedSet) PopMin(count int) []*Element {
        first := sortedSet.skiplist.getFirstInRange(scoreNegativeInfBorder, scorePositiveInfBorder)
        if first == nil {
                return nil
        }
        border := &ScoreBorder{
                Value:   first.Score,
                Exclude: false,
        }
        removed := sortedSet.skiplist.RemoveRange(border, scorePositiveInfBorder, count)
        for _, element := range removed {
                delete(sortedSet.dict, element.Member)
        }
        return removed
}

// RemoveByRank removes member ranking within [start, stop)
// sort by ascending order and rank starts from 0
func (sortedSet *SortedSet) RemoveByRank(start int64, stop int64) int64 {
        removed := sortedSet.skiplist.RemoveRangeByRank(start+1, stop+1)
        for _, element := range removed {
                delete(sortedSet.dict, element.Member)
        }
        return int64(len(removed))
}

1	package sortedset
2
3	import (
4	"strconv"
5	)
6
7	// SortedSet is a set which keys sorted by bound score
8	type SortedSet struct {
9	dict map[string]*Element
10	skiplist *skiplist
11	}
12
13	// Make makes a new SortedSet
14	func Make() *SortedSet {	1✔
15	return &SortedSet{	1✔
16	dict: make(map[string]*Element),	1✔
17	skiplist: makeSkiplist(),	1✔
18	}	1✔
19	}	1✔
20
21	// Add puts member into set, and returns whether it has inserted new node
22	func (sortedSet *SortedSet) Add(member string, score float64) bool {	1✔
23	element, ok := sortedSet.dict[member]	1✔
24	sortedSet.dict[member] = &Element{	1✔
25	Member: member,	1✔
26	Score: score,	1✔
27	}	1✔
28	if ok {	1✔
29	if score != element.Score {	×
30	sortedSet.skiplist.remove(member, element.Score)	×
31	sortedSet.skiplist.insert(member, score)	×
32	}	×
33	return false	×
34	}
35	sortedSet.skiplist.insert(member, score)	1✔
36	return true	1✔
37	}
38
39	// Len returns number of members in set
40	func (sortedSet *SortedSet) Len() int64 {	×
41	return int64(len(sortedSet.dict))	×
42	}	×
43
44	// Get returns the given member
45	func (sortedSet SortedSet) Get(member string) (element Element, ok bool) {	×
46	element, ok = sortedSet.dict[member]	×
47	if !ok {	×
48	return nil, false	×
49	}	×
50	return element, true	×
51	}
52
53	// Remove removes the given member from set
54	func (sortedSet *SortedSet) Remove(member string) bool {	×
55	v, ok := sortedSet.dict[member]	×
56	if ok {	×
57	sortedSet.skiplist.remove(member, v.Score)	×
58	delete(sortedSet.dict, member)	×
59	return true	×
60	}	×
61	return false	×
62	}
63
64	// GetRank returns the rank of the given member, sort by ascending order, rank starts from 0
65	func (sortedSet *SortedSet) GetRank(member string, desc bool) (rank int64) {	×
66	element, ok := sortedSet.dict[member]	×
67	if !ok {	×
68	return -1	×
69	}	×
70	r := sortedSet.skiplist.getRank(member, element.Score)	×
71	if desc {	×
72	r = sortedSet.skiplist.length - r	×
73	} else {	×
74	r--	×
75	}	×
76	return r	×
77	}
78
79	// ForEachByRank visits each member which rank within [start, stop), sort by ascending order, rank starts from 0
80	func (sortedSet SortedSet) ForEachByRank(start int64, stop int64, desc bool, consumer func(element Element) bool) {	×
81	size := int64(sortedSet.Len())	×
82	if start < 0 \|\| start >= size {	×
83	panic("illegal start " + strconv.FormatInt(start, 10))	×
84	}
85	if stop < start \|\| stop > size {	×
86	panic("illegal end " + strconv.FormatInt(stop, 10))	×
87	}
88
89	// find start node
90	var node *node	×
91	if desc {	×
92	node = sortedSet.skiplist.tail	×
93	if start > 0 {	×
94	node = sortedSet.skiplist.getByRank(int64(size - start))	×
95	}	×
96	} else {	×
97	node = sortedSet.skiplist.header.level[0].forward	×
98	if start > 0 {	×
99	node = sortedSet.skiplist.getByRank(int64(start + 1))	×
100	}	×
101	}
102
103	sliceSize := int(stop - start)	×
104	for i := 0; i < sliceSize; i++ {	×
105	if !consumer(&node.Element) {	×
106	break	×
107	}
108	if desc {	×
109	node = node.backward	×
110	} else {	×
111	node = node.level[0].forward	×
112	}	×
113	}
114	}
115
116	// RangeByRank returns members which rank within [start, stop), sort by ascending order, rank starts from 0
117	func (sortedSet SortedSet) RangeByRank(start int64, stop int64, desc bool) []Element {	×
118	sliceSize := int(stop - start)	×
119	slice := make([]*Element, sliceSize)	×
120	i := 0	×
121	sortedSet.ForEachByRank(start, stop, desc, func(element *Element) bool {	×
122	slice[i] = element	×
123	i++	×
124	return true	×
125	})	×
126	return slice	×
127	}
128
129	// RangeCount returns the number of members which score or member within the given border
130	func (sortedSet *SortedSet) RangeCount(min Border, max Border) int64 {	×
131	var i int64 = 0	×
132	// ascending order	×
133	sortedSet.ForEachByRank(0, sortedSet.Len(), false, func(element *Element) bool {	×
134	gtMin := min.less(element) // greater than min	×
135	if !gtMin {	×
136	// has not into range, continue foreach	×
137	return true	×
138	}	×
139	ltMax := max.greater(element) // less than max	×
140	if !ltMax {	×
141	// break through score border, break foreach	×
142	return false	×
143	}	×
144	// gtMin && ltMax
145	i++	×
146	return true	×
147	})
148	return i	×
149	}
150
151	// ForEach visits members which score or member within the given border
152	func (sortedSet SortedSet) ForEach(min Border, max Border, offset int64, limit int64, desc bool, consumer func(element Element) bool) {	×
153	// find start node	×
154	var node *node	×
155	if desc {	×
156	node = sortedSet.skiplist.getLastInRange(min, max)	×
157	} else {	×
158	node = sortedSet.skiplist.getFirstInRange(min, max)	×
159	}	×
160
161	for node != nil && offset > 0 {	×
162	if desc {	×
163	node = node.backward	×
164	} else {	×
165	node = node.level[0].forward	×
166	}	×
167	offset--	×
168	}
169
170	// A negative limit returns all elements from the offset
171	for i := 0; (i < int(limit) \|\| limit < 0) && node != nil; i++ {	×
172	if !consumer(&node.Element) {	×
173	break	×
174	}
175	if desc {	×
176	node = node.backward	×
177	} else {	×
178	node = node.level[0].forward	×
179	}	×
180	if node == nil {	×
181	break	×
182	}
183	gtMin := min.less(&node.Element) // greater than min	×
184	ltMax := max.greater(&node.Element)	×
185	if !gtMin \|\| !ltMax {	×
186	break // break through score border	×
187	}
188	}
189	}
190
191	// Range returns members which score or member within the given border
192	// param limit: <0 means no limit
193	func (sortedSet SortedSet) Range(min Border, max Border, offset int64, limit int64, desc bool) []Element {	×
194	if limit == 0 \|\| offset < 0 {	×
195	return make([]*Element, 0)	×
196	}	×
197	slice := make([]*Element, 0)	×
198	sortedSet.ForEach(min, max, offset, limit, desc, func(element *Element) bool {	×
199	slice = append(slice, element)	×
200	return true	×
201	})	×
202	return slice	×
203	}
204
205	// RemoveRange removes members which score or member within the given border
206	func (sortedSet *SortedSet) RemoveRange(min Border, max Border) int64 {	×
207	removed := sortedSet.skiplist.RemoveRange(min, max, 0)	×
208	for _, element := range removed {	×
209	delete(sortedSet.dict, element.Member)	×
210	}	×
211	return int64(len(removed))	×
212	}
213
214	func (sortedSet SortedSet) PopMin(count int) []Element {	1✔
215	first := sortedSet.skiplist.getFirstInRange(scoreNegativeInfBorder, scorePositiveInfBorder)	1✔
216	if first == nil {	1✔
217	return nil	×
218	}	×
219	border := &ScoreBorder{	1✔
220	Value: first.Score,	1✔
221	Exclude: false,	1✔
222	}	1✔
223	removed := sortedSet.skiplist.RemoveRange(border, scorePositiveInfBorder, count)	1✔
224	for _, element := range removed {	2✔
225	delete(sortedSet.dict, element.Member)	1✔
226	}	1✔
227	return removed	1✔
228	}
229
230	// RemoveByRank removes member ranking within [start, stop)
231	// sort by ascending order and rank starts from 0
232	func (sortedSet *SortedSet) RemoveByRank(start int64, stop int64) int64 {	×
233	removed := sortedSet.skiplist.RemoveRangeByRank(start+1, stop+1)	×
234	for _, element := range removed {	×
235	delete(sortedSet.dict, element.Member)	×
236	}	×
237	return int64(len(removed))	×
238	}

HDT3213 / godis / 5561080764

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous