15941591423

Committed 28 Jun 2025 06:56AM UTC coverage: 83.785% (-2.0%) from 85.806%

Build # 15941591423

Build Type

push

github

Committed by

kelindar

Commit Message

Update min/max tests to reflect correct expected values

- Adjusted test cases in TestMinMax to return the correct expected values for boundary conditions in array, bitmap, and run containers.
- Ensured consistency in expected results across all test scenarios, improving the accuracy of the min/max functionality tests.

Run Details

1700 of 2029 relevant lines covered (83.79%)

12383.02 hits per line

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

78.01

/container_array.go

// Copyright (c) Roman Atachiants and contributors. All rights reserved.
// Licensed under the MIT license. See LICENSE file in the project root

package roaring

// arrSet sets a value in an array container
func (c *container) arrSet(value uint16) bool {
        idx, exists := find16(c.Data, value)
        if exists {
                return false // Already exists
        }

        // Move elements to the right using bulk copy
        oldLen := len(c.Data)
        c.Data = append(c.Data, 0)
        if idx < oldLen {
                copy(c.Data[idx+1:], c.Data[idx:])
        }

        c.Data[idx] = value
        c.Size++
        return true
}

// arrDel removes a value from an array container
func (c *container) arrDel(value uint16) bool {
        idx, exists := find16(c.Data, value)
        if !exists {
                return false
        }

        // Remove element at index idx
        copy(c.Data[idx:], c.Data[idx+1:])
        c.Data = c.Data[:len(c.Data)-1]
        c.Size--
        return true
}

// arrHas checks if a value exists in an array container
func (c *container) arrHas(value uint16) bool {
        _, exists := find16(c.Data, value)
        return exists
}

// arrOptimize tries to optimize the container
func (c *container) arrOptimize() {
        switch {
        case c.arrIsDense():
                c.arrToRun()
        case c.Size > arrMinSize:
                c.arrToBmp()
        }
}

// arrIsDense quickly estimates if converting to run container would be beneficial
func (c *container) arrIsDense() bool {
        if len(c.Data) < 128 {
                return false
        }

        lo, hi := c.Data[0], c.Data[len(c.Data)-1]
        span := int(hi - lo + 1)
        size := len(c.Data)

        // Quick density filters
        density := float64(size) / float64(span)
        switch {
        case density < 0.1: // Very sparse
                return false
        case density > 0.8: // Very dense
                return true
        }

        // Estimate number of runs using density
        runs := size
        if gap := float64(span) / float64(size); gap < 2.0 {
                runs = int(float64(size) * (1.0 - density*0.7))
        }

        // Check if estimated conversion meets our criteria
        sizeAsArr := size * 2
        sizeAsRun := runs*4 + 2
        return sizeAsRun < sizeAsArr*3/4 && runs <= size/3
}

// arrToRun attempts to convert array to run in a single pass
func (c *container) arrToRun() bool {
        if len(c.Data) == 0 {
                return false
        }

        // Build runs and count them
        runsData := make([]uint16, 0, len(c.Data)/2)
        i0 := c.Data[0]
        i1 := c.Data[0]

        for i := 1; i < len(c.Data); i++ {
                if c.Data[i] == i1+1 {
                        // Continue current run
                        i1 = c.Data[i]
                } else {
                        // End current run and start new one
                        runsData = append(runsData, i0, i1)
                        i0 = c.Data[i]
                        i1 = c.Data[i]
                }
        }

        // Add the final run
        runsData = append(runsData, i0, i1)

        // Check conversion criteria with the actual run count
        numRuns := len(runsData) / 2
        sizeAsArray := len(c.Data) * 2
        sizeAsRun := numRuns*4 + 2 // 2 uint16 per run = 4 bytes

        // Only convert if we save at least 25% space and have reasonable compression
        shouldConvert := sizeAsRun < sizeAsArray*3/4 && numRuns <= len(c.Data)/3
        if shouldConvert {
                c.Data = runsData
                c.Type = typeRun
                return true
        }

        return false
}

// arrToBmp converts this container from array to bitmap
func (c *container) arrToBmp() {
        src := c.Data

        // Create bitmap data (65536 bits = 8192 bytes = 4096 uint16s)
        c.Data = make([]uint16, 4096)
        c.Type = typeBitmap
        dst := c.bmp()

        // Use bulk setting for better performance
        for _, value := range src {
                dst.Set(uint32(value))
        }
}

// arrMin returns the smallest value in an array container
func (c *container) arrMin() (uint16, bool) {
        if len(c.Data) == 0 {
                return 0, false
        }
        return c.Data[0], true
}

// arrMax returns the largest value in an array container
func (c *container) arrMax() (uint16, bool) {
        if len(c.Data) == 0 {
                return 0, false
        }
        return c.Data[len(c.Data)-1], true
}

// arrMinZero returns the smallest unset value in an array container
func (c *container) arrMinZero() (uint16, bool) {
        if len(c.Data) == 0 {
                return 0, true // Empty container, 0 is unset
        }

        // Check if 0 is unset
        if c.Data[0] != 0 {
                return 0, true
        }

        // Find first gap in the sorted array
        for i := 0; i < len(c.Data)-1; i++ {
                if c.Data[i+1] != c.Data[i]+1 {
                        return c.Data[i] + 1, true
                }
        }

        // No gaps found, check if we can increment the last element
        last := c.Data[len(c.Data)-1]
        if last < 65535 {
                return last + 1, true
        }

        return 0, false // Array contains all values 0-65535
}

// arrMaxZero returns the largest unset value in an array container
func (c *container) arrMaxZero() (uint16, bool) {
        if len(c.Data) == 0 {
                return 65535, true // Empty container, 65535 is unset
        }

        // Check if 65535 is unset
        last := c.Data[len(c.Data)-1]
        if last != 65535 {
                return 65535, true
        }

        // Find last gap in the sorted array (search backwards)
        for i := len(c.Data) - 1; i > 0; i-- {
                if c.Data[i] != c.Data[i-1]+1 {
                        return c.Data[i] - 1, true
                }
        }

        // No gaps found, check if we can decrement the first element
        if c.Data[0] > 0 {
                return c.Data[0] - 1, true
        }

        return 0, false // Array contains all values 0-65535
}

1	// Copyright (c) Roman Atachiants and contributors. All rights reserved.
2	// Licensed under the MIT license. See LICENSE file in the project root
3
4	package roaring
5
6	// arrSet sets a value in an array container
7	func (c *container) arrSet(value uint16) bool {	47,775✔
8	idx, exists := find16(c.Data, value)	47,775✔
9	if exists {	48,687✔
10	return false // Already exists	912✔
11	}	912✔
12
13	// Move elements to the right using bulk copy
14	oldLen := len(c.Data)	46,863✔
15	c.Data = append(c.Data, 0)	46,863✔
16	if idx < oldLen {	51,590✔
17	copy(c.Data[idx+1:], c.Data[idx:])	4,727✔
18	}	4,727✔
19
20	c.Data[idx] = value	46,863✔
21	c.Size++	46,863✔
22	return true	46,863✔
23	}
24
25	// arrDel removes a value from an array container
26	func (c *container) arrDel(value uint16) bool {	4,509✔
27	idx, exists := find16(c.Data, value)	4,509✔
28	if !exists {	7,846✔
29	return false	3,337✔
30	}	3,337✔
31
32	// Remove element at index idx
33	copy(c.Data[idx:], c.Data[idx+1:])	1,172✔
34	c.Data = c.Data[:len(c.Data)-1]	1,172✔
35	c.Size--	1,172✔
36	return true	1,172✔
37	}
38
39	// arrHas checks if a value exists in an array container
40	func (c *container) arrHas(value uint16) bool {	9,319✔
41	_, exists := find16(c.Data, value)	9,319✔
42	return exists	9,319✔
43	}	9,319✔
44
45	// arrOptimize tries to optimize the container
46	func (c *container) arrOptimize() {	55✔
47	switch {	55✔
48	case c.arrIsDense():	12✔
49	c.arrToRun()	12✔
50	case c.Size > arrMinSize:	2✔
51	c.arrToBmp()	2✔
52	}
53	}
54
55	// arrIsDense quickly estimates if converting to run container would be beneficial
56	func (c *container) arrIsDense() bool {	55✔
57	if len(c.Data) < 128 {	94✔
58	return false	39✔
59	}	39✔
60
61	lo, hi := c.Data[0], c.Data[len(c.Data)-1]	16✔
62	span := int(hi - lo + 1)	16✔
63	size := len(c.Data)	16✔
64		16✔
65	// Quick density filters	16✔
66	density := float64(size) / float64(span)	16✔
67	switch {	16✔
68	case density < 0.1: // Very sparse	×
69	return false	×
70	case density > 0.8: // Very dense	12✔
71	return true	12✔
72	}
73
74	// Estimate number of runs using density
75	runs := size	4✔
76	if gap := float64(span) / float64(size); gap < 2.0 {	6✔
77	runs = int(float64(size) * (1.0 - density*0.7))	2✔
78	}	2✔
79
80	// Check if estimated conversion meets our criteria
81	sizeAsArr := size * 2	4✔
82	sizeAsRun := runs*4 + 2	4✔
83	return sizeAsRun < sizeAsArr*3/4 && runs <= size/3	4✔
84	}
85
86	// arrToRun attempts to convert array to run in a single pass
87	func (c *container) arrToRun() bool {	12✔
88	if len(c.Data) == 0 {	12✔
89	return false	×
90	}	×
91
92	// Build runs and count them
93	runsData := make([]uint16, 0, len(c.Data)/2)	12✔
94	i0 := c.Data[0]	12✔
95	i1 := c.Data[0]	12✔
96		12✔
97	for i := 1; i < len(c.Data); i++ {	22,481✔
98	if c.Data[i] == i1+1 {	44,938✔
99	// Continue current run	22,469✔
100	i1 = c.Data[i]	22,469✔
101	} else {	22,469✔
102	// End current run and start new one	×
103	runsData = append(runsData, i0, i1)	×
104	i0 = c.Data[i]	×
105	i1 = c.Data[i]	×
106	}	×
107	}
108
109	// Add the final run
110	runsData = append(runsData, i0, i1)	12✔
111		12✔
112	// Check conversion criteria with the actual run count	12✔
113	numRuns := len(runsData) / 2	12✔
114	sizeAsArray := len(c.Data) * 2	12✔
115	sizeAsRun := numRuns*4 + 2 // 2 uint16 per run = 4 bytes	12✔
116		12✔
117	// Only convert if we save at least 25% space and have reasonable compression	12✔
118	shouldConvert := sizeAsRun < sizeAsArray*3/4 && numRuns <= len(c.Data)/3	12✔
119	if shouldConvert {	24✔
120	c.Data = runsData	12✔
121	c.Type = typeRun	12✔
122	return true	12✔
123	}	12✔
124
125	return false	×
126	}
127
128	// arrToBmp converts this container from array to bitmap
129	func (c *container) arrToBmp() {	16✔
130	src := c.Data	16✔
131		16✔
132	// Create bitmap data (65536 bits = 8192 bytes = 4096 uint16s)	16✔
133	c.Data = make([]uint16, 4096)	16✔
134	c.Type = typeBitmap	16✔
135	dst := c.bmp()	16✔
136		16✔
137	// Use bulk setting for better performance	16✔
138	for _, value := range src {	8,241✔
139	dst.Set(uint32(value))	8,225✔
140	}	8,225✔
141	}
142
143	// arrMin returns the smallest value in an array container
144	func (c *container) arrMin() (uint16, bool) {	5✔
145	if len(c.Data) == 0 {	5✔
146	return 0, false	×
147	}	×
148	return c.Data[0], true	5✔
149	}
150
151	// arrMax returns the largest value in an array container
152	func (c *container) arrMax() (uint16, bool) {	5✔
153	if len(c.Data) == 0 {	5✔
154	return 0, false	×
155	}	×
156	return c.Data[len(c.Data)-1], true	5✔
157	}
158
159	// arrMinZero returns the smallest unset value in an array container
160	func (c *container) arrMinZero() (uint16, bool) {	13✔
161	if len(c.Data) == 0 {	14✔
162	return 0, true // Empty container, 0 is unset	1✔
163	}	1✔
164
165	// Check if 0 is unset
166	if c.Data[0] != 0 {	21✔
167	return 0, true	9✔
168	}	9✔
169
170	// Find first gap in the sorted array
171	for i := 0; i < len(c.Data)-1; i++ {	5✔
172	if c.Data[i+1] != c.Data[i]+1 {	4✔
173	return c.Data[i] + 1, true	2✔
174	}	2✔
175	}
176
177	// No gaps found, check if we can increment the last element
178	last := c.Data[len(c.Data)-1]	1✔
179	if last < 65535 {	2✔
180	return last + 1, true	1✔
181	}	1✔
182
183	return 0, false // Array contains all values 0-65535	×
184	}
185
186	// arrMaxZero returns the largest unset value in an array container
187	func (c *container) arrMaxZero() (uint16, bool) {	×
188	if len(c.Data) == 0 {	×
189	return 65535, true // Empty container, 65535 is unset	×
190	}	×
191
192	// Check if 65535 is unset
193	last := c.Data[len(c.Data)-1]	×
194	if last != 65535 {	×
195	return 65535, true	×
196	}	×
197
198	// Find last gap in the sorted array (search backwards)
199	for i := len(c.Data) - 1; i > 0; i-- {	×
200	if c.Data[i] != c.Data[i-1]+1 {	×
201	return c.Data[i] - 1, true	×
202	}	×
203	}
204
205	// No gaps found, check if we can decrement the first element
206	if c.Data[0] > 0 {	×
207	return c.Data[0] - 1, true	×
208	}	×
209
210	return 0, false // Array contains all values 0-65535	×
211	}

kelindar / roaring / 15941591423

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