16392681431

Committed 19 Jul 2025 08:58PM UTC coverage: 86.561% (-0.08%) from 86.643%

Build # 16392681431

Build Type

push

github

Committed by

web-flow

Commit Message

Make sure restore reads the full slice (#15)

Coverage Stats

1694 of 1957 new or added lines in 12 files covered. (86.56%)

1694 of 1957 relevant lines covered (86.56%)

13865.69 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 {	58,712✔
8	idx, exists := find16(c.Data, value)	58,712✔
9	if exists {	59,618✔
10	return false // Already exists	906✔
11	}	906✔
12
13	// Move elements to the right using bulk copy
14	oldLen := len(c.Data)	57,806✔
15	c.Data = append(c.Data, 0)	57,806✔
16	if idx < oldLen {	62,566✔
17	copy(c.Data[idx+1:], c.Data[idx:])	4,760✔
18	}	4,760✔
19
20	c.Data[idx] = value	57,806✔
21	c.Size++	57,806✔
22	return true	57,806✔
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() {	52✔
47	switch {	52✔
48	case c.arrIsDense():	15✔
49	c.arrToRun()	15✔
50	case c.Size > arrMinSize:	5✔
51	c.arrToBmp()	5✔
52	}
53	}
54
55	// arrIsDense quickly estimates if converting to run container would be beneficial
56	func (c *container) arrIsDense() bool {	52✔
57	if len(c.Data) < 128 {	79✔
58	return false	27✔
59	}	27✔
60
61	lo, hi := c.Data[0], c.Data[len(c.Data)-1]	25✔
62	span := int(hi - lo + 1)	25✔
63	size := len(c.Data)	25✔
64		25✔
65	// Quick density filters	25✔
66	density := float64(size) / float64(span)	25✔
67	switch {	25✔
NEW 68	case density < 0.1: // Very sparse	×
NEW 69	return false	×
70	case density > 0.8: // Very dense	15✔
71	return true	15✔
72	}
73
74	// Estimate number of runs using density
75	runs := size	10✔
76	if gap := float64(span) / float64(size); gap < 2.0 {	12✔
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	10✔
82	sizeAsRun := runs*4 + 2	10✔
83	return sizeAsRun < sizeAsArr*3/4 && runs <= size/3	10✔
84	}
85
86	// arrToRun attempts to convert array to run in a single pass
87	func (c *container) arrToRun() bool {	15✔
88	if len(c.Data) == 0 {	15✔
NEW 89	return false	×
NEW 90	}	×
91
92	// Build runs and count them
93	runsData := make([]uint16, 0, len(c.Data)/2)	15✔
94	i0 := c.Data[0]	15✔
95	i1 := c.Data[0]	15✔
96		15✔
97	for i := 1; i < len(c.Data); i++ {	25,481✔
98	if c.Data[i] == i1+1 {	50,932✔
99	// Continue current run	25,466✔
100	i1 = c.Data[i]	25,466✔
101	} else {	25,466✔
NEW 102	// End current run and start new one	×
NEW 103	runsData = append(runsData, i0, i1)	×
NEW 104	i0 = c.Data[i]	×
NEW 105	i1 = c.Data[i]	×
NEW 106	}	×
107	}
108
109	// Add the final run
110	runsData = append(runsData, i0, i1)	15✔
111		15✔
112	// Check conversion criteria with the actual run count	15✔
113	numRuns := len(runsData) / 2	15✔
114	sizeAsArray := len(c.Data) * 2	15✔
115	sizeAsRun := numRuns*4 + 2 // 2 uint16 per run = 4 bytes	15✔
116		15✔
117	// Only convert if we save at least 25% space and have reasonable compression	15✔
118	shouldConvert := sizeAsRun < sizeAsArray*3/4 && numRuns <= len(c.Data)/3	15✔
119	if shouldConvert {	30✔
120	c.Data = runsData	15✔
121	c.Type = typeRun	15✔
122	return true	15✔
123	}	15✔
124
NEW 125	return false	×
126	}
127
128	// arrToBmp converts this container from array to bitmap
129	func (c *container) arrToBmp() {	166✔
130	src := c.Data	166✔
131		166✔
132	// Create bitmap data (65536 bits = 8192 bytes = 4096 uint16s)	166✔
133	c.Data = make([]uint16, 4096)	166✔
134	c.Type = typeBitmap	166✔
135	dst := c.bmp()	166✔
136		166✔
137	// Use bulk setting for better performance	166✔
138	for _, value := range src {	21,107✔
139	dst.Set(uint32(value))	20,941✔
140	}	20,941✔
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 / 16392681431

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