15946630268

Committed 28 Jun 2025 05:41PM UTC coverage: 85.945% (-1.0%) from 86.978%

Build # 15946630268

Build Type

push

github

Committed by

web-flow

Commit Message

Add min/max methods and fixed run container math (#12)

* Add copyright notice and implement min/max functions for containers

- Added copyright notice to all relevant files.
- Implemented min and max functions for array, bitmap, and run containers to retrieve the smallest and largest values, respectively.
- Introduced minZero and maxZero functions to find the smallest and largest unset values in each container type.
- Enhanced tests to validate the new min, max, minZero, and maxZero functionalities across various scenarios.

* table tests

* 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.

* Update boundary test case in TestMinMax to reflect correct expected value

* Update README and refine MaxZero function logic

- Adjusted logo dimensions in README for better display.
- Updated the MaxZero function in the Bitmap struct to improve logic for finding the last zero bit, ensuring accurate results across various scenarios.
- Enhanced test cases in TestMinMax to reflect correct expected values for boundary conditions in array, bitmap, and run containers.

* Refactor container functions and enhance test coverage

- Updated container methods to improve logic for finding unset values, including arrMinZero and runMinZero.
- Removed unused maxZero functions from container types to streamline code.
- Added arrToRun function to optimize array to run conversion.
- Enhanced test cases in TestMinMax to ensure accurate results for boundary conditions and removed commented-out tests for clarity.
- Updated .gitignore to include *.exe files.

* Enhance arrToRun function in assert_test.go

- Updated arrToRun function to set container type and handle empty data cases, improving robustness.
- Removed re... (continued)

Run Details

210 of 256 new or added lines in 10 files covered. (82.03%)

8 existing lines in 2 files now uncovered.

1651 of 1921 relevant lines covered (85.94%)

13343.65 hits per line

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

88.62

/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) {
        switch {
        case len(c.Data) == 0:
                return 0, true
        case 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
        if last := c.Data[len(c.Data)-1]; last < 0xFFFF {
                return last + 1, true
        }

        return 0, false
}

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 {	48,722✔
8	idx, exists := find16(c.Data, value)	48,722✔
9	if exists {	49,634✔
10	return false // Already exists	912✔
11	}	912✔
12
13	// Move elements to the right using bulk copy
14	oldLen := len(c.Data)	47,810✔
15	c.Data = append(c.Data, 0)	47,810✔
16	if idx < oldLen {	52,544✔
17	copy(c.Data[idx+1:], c.Data[idx:])	4,734✔
18	}	4,734✔
19
20	c.Data[idx] = value	47,810✔
21	c.Size++	47,810✔
22	return true	47,810✔
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,312✔
41	_, exists := find16(c.Data, value)	9,312✔
42	return exists	9,312✔
43	}	9,312✔
44
45	// arrOptimize tries to optimize the container
46	func (c *container) arrOptimize() {	37✔
47	switch {	37✔
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 {	37✔
57	if len(c.Data) < 128 {	58✔
58	return false	21✔
59	}	21✔
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() {	163✔
130	src := c.Data	163✔
131		163✔
132	// Create bitmap data (65536 bits = 8192 bytes = 4096 uint16s)	163✔
133	c.Data = make([]uint16, 4096)	163✔
134	c.Type = typeBitmap	163✔
135	dst := c.bmp()	163✔
136		163✔
137	// Use bulk setting for better performance	163✔
138	for _, value := range src {	8,816✔
139	dst.Set(uint32(value))	8,653✔
140	}	8,653✔
141	}
142
143	// arrMin returns the smallest value in an array container
144	func (c *container) arrMin() (uint16, bool) {	4✔
145	if len(c.Data) == 0 {	5✔
146	return 0, false	1✔
147	}	1✔
148	return c.Data[0], true	3✔
149	}
150
151	// arrMax returns the largest value in an array container
152	func (c *container) arrMax() (uint16, bool) {	4✔
153	if len(c.Data) == 0 {	5✔
154	return 0, false	1✔
155	}	1✔
156	return c.Data[len(c.Data)-1], true	3✔
157	}
158
159	// arrMinZero returns the smallest unset value in an array container
160	func (c *container) arrMinZero() (uint16, bool) {	4✔
161	switch {	4✔
162	case len(c.Data) == 0:	1✔
163	return 0, true	1✔
164	case c.Data[0] != 0:	2✔
165	return 0, true	2✔
166	}
167
168	// Find first gap in the sorted array
169	for i := 0; i < len(c.Data)-1; i++ {	2✔
170	if c.Data[i+1] != c.Data[i]+1 {	2✔
171	return c.Data[i] + 1, true	1✔
172	}	1✔
173	}
174
175	// No gaps found, check if we can increment the last element
NEW 176	if last := c.Data[len(c.Data)-1]; last < 0xFFFF {	×
NEW 177	return last + 1, true	×
NEW 178	}	×
179
NEW 180	return 0, false	×
181	}

kelindar / roaring / 15946630268

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