15336754092

Committed 30 May 2025 12:57AM UTC coverage: 94.556% (-0.01%) from 94.569%

Build # 15336754092

Build Type

Pull #324

github

Committed by

jamie-tay

Commit Message

Add tests, make num_offdiagonals an upper bound

Pull Request Pull Request #324: Fix interface tests

Run Details

2 of 2 new or added lines in 1 file covered. (100.0%)

1 existing line in 1 file now uncovered.

6999 of 7402 relevant lines covered (94.56%)

11661769.58 hits per line

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

88.39

/src/BitStringAddresses/sortedparticlelist.jl

"""
    select_int_type(n)

Select unsigned integer type that can hold values up to `n`.
"""
function select_int_type(n)
    if n < 0
        throw(ArgumentError("`n` must be a non-negative integer!"))
    elseif n ≤ typemax(UInt8)
        return UInt8
    elseif n ≤ typemax(UInt16)
        return UInt16
    elseif n ≤ typemax(UInt32)
        return UInt32
    else
        return UInt64
    end
end

"""
    SortedParticleList{N,M,T<:Unsigned}

Type for storing sparse Fock states. Stores the mode number of each particle as an entry
with only its mode stored. The entries are always kept sorted.

Iterating over `SortedParticleList`s yields occupied modes as a tuple of occupation number,
mode number, and position in list.

# Constructors

* `SortedParticleList{N,M,T}(::SVector{N,T})`: unsafe constructor. Does not sort input.

* `SortedParticleList(arr::AbstractVector)`: convert ONR to `SortedParticleList`

"""
struct SortedParticleList{N,M,T<:Unsigned}
    storage::SVector{N,T}
end
function Base.show(io::IO, ss::SortedParticleList{N,M,T}) where {N,M,T}
    print(io, "SortedParticleList{$N,$M,$T}(", Int.(ss.storage), ")")
end

function SortedParticleList{N,M}() where {N,M}
    T = select_int_type(M)
    return SortedParticleList{N,M,T}(ones(SVector{N,T}))
end
function SortedParticleList(onr)
    N = sum(onr)
    M = length(onr)
    T = select_int_type(M)
    eltype(onr) <: Integer || throw(ArgumentError("the onr can only contain integers"))
    any(≥(0), onr) || throw(ArgumentError("all elements of the onr should be positive"))

    return from_onr(SortedParticleList{N,M,T}, onr)
end
function from_onr(::Type{S}, onr) where {N,M,T,S<:SortedParticleList{N,M,T}}
    spl = zeros(MVector{N,T})
    curr = 1
    for (n, v) in enumerate(onr)
        for _ in 1:v
            spl[curr] = n
            curr += 1
        end
    end
    return SortedParticleList{N,M,T}(SVector(spl))
end
function from_onr(::Type{S}, onr::SparseVector) where {N,M,T,S<:SortedParticleList{N,M,T}}
    spl = zeros(MVector{N,T})
    curr = 1
    for (n, v) in zip(rowvals(onr), nonzeros(onr))
        for _ in 1:v
            spl[curr] = n
            curr += 1
        end
    end
    return SortedParticleList{N,M,T}(SVector(spl))
end

function Base.isless(ss1::SortedParticleList, ss2::SortedParticleList)
    return isless(ss1.storage, ss2.storage)
end

num_particles(::Type{<:SortedParticleList{N}}) where {N} = N
num_modes(::Type{<:SortedParticleList{<:Any,M}}) where {M} = M

###
### General functions
###
Base.eltype(::SortedParticleList) = Tuple{Int,Int,Int}

function Base.length(ss::SortedParticleList{<:Any,<:Any,T}) where {T}
    curr = zero(T)
    res = 0
    for i in ss.storage
        res += (i != curr)
        curr = i
    end
    return res
end

function Base.iterate(ss::SortedParticleList{N}, i=1) where {N}
    @inbounds if i > N
        return nothing
    else
        occnum = 1
        mode = ss.storage[i]
        offset = i
        i += 1
        while i ≤ N && ss.storage[i] == mode
            occnum += 1
            i += 1
        end
        return (occnum, Int(mode), i - occnum - 1), i
    end
end

function Base.reverse(ss::SortedParticleList{N,M,T}) where {N,M,T}
    new_storage = map(reverse(ss.storage)) do i
        T(M) - i + one(T)
    end
    return SortedParticleList{N,M,T}(new_storage)
end

# Somehow this is faster than the default method.
Base.hash(ss::SortedParticleList, u::UInt) = hash(ss.storage, u)

# In this case, getting the ONR is the same for bosons and fermions, and assumes the address
# is not malformed.
function onr(ss::SortedParticleList{<:Any,M}) where {M}
    mvec = zeros(MVector{M,Int})
    @inbounds for (occnum, mode, _) in ss
        mvec[mode] = occnum
    end
    return SVector(mvec)
end

# Same as above.
function find_mode(ss::SortedParticleList, n)
    offset = 0
    for (occnum, mode, _) in ss
        if mode == n
            return (occnum, mode, offset)
        elseif mode > n
            return (0, n, offset)
        end
        offset += occnum
    end
    return (0, n, offset)
end

"""
    move_particles(ss::SortedParticleList, dsts, srcs)

Move several particles at once. Moves `srcs[i]` to `dsts[i]`.  `dsts` and `srcs` should be
tuples of [`BoseFSIndex`](@ref) or [`FermiFSIndex`](@ref). The legality of the moves is not
checked - the result of an illegal move is undefined!
"""
function move_particles(ss::SortedParticleList{N,M,T}, dsts, srcs) where {N,M,T}
    new_storage = ss.storage
    for (dst, src) in zip(dsts, srcs)
        src_pos = 1
        @inbounds for i in 1:N
            src_pos = max(src_pos, i * (new_storage[i] == src.mode % T))
        end
        @boundscheck 0 < dst.mode ≤ M || throw(BoundsError(ss, dst.mode))
        new_storage = setindex(new_storage, dst.mode % T, src_pos)
    end
    return SortedParticleList{N,M,T}(sort(new_storage))
end

###
### Bose interface
###
function from_bose_onr(::Type{S}, onr) where{S<:SortedParticleList}
    from_onr(S, onr)
end
to_bose_onr(ss::SortedParticleList, _) = onr(ss)

bose_num_occupied_modes(ss::SortedParticleList) = length(ss)

bose_find_mode(ss::SortedParticleList, n) = find_mode(ss, n)

@inline function bose_excitation(
    ss::SortedParticleList{N,M,T}, creations, destructions
) where {N,M,T}
    creations_rev = reverse(creations)
    value = bose_excitation_value(creations_rev, destructions)
    if iszero(value)
        return ss, 0.0
    else
        return move_particles(ss, creations_rev, destructions), √value
    end
end

Base.length(bom::BoseOccupiedModes{<:Any,<:Any,<:SortedParticleList}) = length(bom.storage)
function Base.iterate(bom::BoseOccupiedModes{<:Any,<:Any,<:SortedParticleList}, i=1)
    it = iterate(bom.storage, i)
    if isnothing(it)
        return nothing
    else
        res, i = it
        return BoseFSIndex(res...), i
    end
end

###
### Fermi interface
###
function from_fermi_onr(::Type{S}, onr) where {S<:SortedParticleList}
    from_onr(S, onr)
end

# Fix offsets and occupation numbers after creation/destruction operator is applied.
# The idea behind these is to allow computing the value from the indices alone.
function _fix_pos_create(c, index)
    index = @set index.offset += (c.mode < index.mode)
    index = @set index.occnum += (c.mode == index.mode)
    return index
end
_fix_pos_create(c) = Base.Fix1(_fix_pos_create, c)
function _fix_pos_destroy(d, index)
    index = @set index.offset -= (d.mode < index.mode)
    index = @set index.occnum -= (d.mode == index.mode)
    return index
end
_fix_pos_destroy(d) = Base.Fix1(_fix_pos_destroy, d)

"""
    fermi_excitation_value_spl(
        creations::NTuple{_,FermiFSIndex}, destructions::NTuple{_,::FermiFSIndex}
    ) -> {-1,0,1}

Compute the value of an excitation from indices. Starts by applying all destruction
operators, and then applying all creation operators. The operators must be given in reverse
order. Will return 0 if move is illegal.

Note that this function only works on indices obtained from a [`SortedParticleList`](@ref).
"""
@inline fermi_excitation_value_spl(::Tuple{}, ::Tuple{}) = 1.0
@inline function fermi_excitation_value_spl((c, cs...), ::Tuple{})
    cs = map(_fix_pos_create(c), cs)
    return fermi_excitation_value_spl(cs, ()) * ifelse(isodd(c.offset), -1, 1) * (c.occnum == 0)
end
@inline function fermi_excitation_value_spl(cs, (d, ds...))
    cs = map(_fix_pos_destroy(d), cs)
    ds = map(_fix_pos_destroy(d), ds)
    return fermi_excitation_value_spl(cs, ds) * ifelse(isodd(d.offset), -1, 1) * (d.occnum == 1)
end

fermi_find_mode(ss::SortedParticleList, n) = FermiFSIndex(find_mode(ss, n))
function fermi_find_mode(ss::SortedParticleList, ns::Tuple)
    # It's OK to do that instead of the fancy method used with bosons, because the
    # assumption is that `N` is small.
    return map(n -> FermiFSIndex(find_mode(ss, n)), ns)
end

@inline function fermi_excitation(
    ss::SortedParticleList{N,M,T}, creations::NTuple{K}, destructions::NTuple{K}
) where {N,M,T,K}
    creations_rev = reverse(creations)
    destructions_rev = reverse(destructions)
    value = fermi_excitation_value_spl(creations_rev, destructions_rev)
    if iszero(value)
        return ss, 0.0
    else
        return move_particles(ss, creations_rev, destructions), float(value)
    end
end

Base.length(fom::FermiOccupiedModes{N,<:SortedParticleList}) where {N} = length(fom.storage)
function Base.iterate(fom::FermiOccupiedModes{<:Any,<:SortedParticleList}, i=1)
    itr = iterate(fom.storage, i)
    if isnothing(itr)
        return nothing
    else
        res, i = itr
        return FermiFSIndex(res...), i
    end
end

1	"""
2	select_int_type(n)
3
4	Select unsigned integer type that can hold values up to `n`.
5	"""
6	function select_int_type(n)	269,990✔
7	if n < 0	269,990✔
8	throw(ArgumentError("`n` must be a non-negative integer!"))	×
9	elseif n ≤ typemax(UInt8)	269,990✔
10	return UInt8	269,989✔
11	elseif n ≤ typemax(UInt16)	1✔
12	return UInt16	1✔
13	elseif n ≤ typemax(UInt32)	×
14	return UInt32	×
15	else
16	return UInt64	×
17	end
18	end
19
20	"""
21	SortedParticleList{N,M,T<:Unsigned}
22
23	Type for storing sparse Fock states. Stores the mode number of each particle as an entry
24	with only its mode stored. The entries are always kept sorted.
25
26	Iterating over `SortedParticleList`s yields occupied modes as a tuple of occupation number,
27	mode number, and position in list.
28
29	# Constructors
30
31	* `SortedParticleList{N,M,T}(::SVector{N,T})`: unsafe constructor. Does not sort input.
32
33	* `SortedParticleList(arr::AbstractVector)`: convert ONR to `SortedParticleList`
34
35	"""
36	struct SortedParticleList{N,M,T<:Unsigned}
37	storage::SVector{N,T}	13,946✔
38	end
39	function Base.show(io::IO, ss::SortedParticleList{N,M,T}) where {N,M,T}	×
40	print(io, "SortedParticleList{$N,$M,$T}(", Int.(ss.storage), ")")	×
41	end
42
43	function SortedParticleList{N,M}() where {N,M}	×
44	T = select_int_type(M)	×
45	return SortedParticleList{N,M,T}(ones(SVector{N,T}))	×
46	end
47	function SortedParticleList(onr)	1✔
48	N = sum(onr)	1✔
49	M = length(onr)	1✔
50	T = select_int_type(M)	1✔
51	eltype(onr) <: Integer \|\| throw(ArgumentError("the onr can only contain integers"))	1✔
52	any(≥(0), onr) \|\| throw(ArgumentError("all elements of the onr should be positive"))	1✔
53
54	return from_onr(SortedParticleList{N,M,T}, onr)	1✔
55	end
56	function from_onr(::Type{S}, onr) where {N,M,T,S<:SortedParticleList{N,M,T}}	6,878✔
57	spl = zeros(MVector{N,T})	6,878✔
58	curr = 1	6,878✔
59	for (n, v) in enumerate(onr)	6,878✔
60	for _ in 1:v	1,374,817✔
61	spl[curr] = n	116,808✔
62	curr += 1	116,808✔
63	end	120,310✔
64	end	2,742,756✔
65	return SortedParticleList{N,M,T}(SVector(spl))	6,878✔
66	end
67	function from_onr(::Type{S}, onr::SparseVector) where {N,M,T,S<:SortedParticleList{N,M,T}}	31✔
68	spl = zeros(MVector{N,T})	31✔
69	curr = 1	31✔
70	for (n, v) in zip(rowvals(onr), nonzeros(onr))	62✔
71	for _ in 1:v	394✔
72	spl[curr] = n	404✔
73	curr += 1	404✔
74	end	414✔
75	end	757✔
76	return SortedParticleList{N,M,T}(SVector(spl))	31✔
77	end
78
79	function Base.isless(ss1::SortedParticleList, ss2::SortedParticleList)	×
80	return isless(ss1.storage, ss2.storage)	×
81	end
82
83	num_particles(::Type{<:SortedParticleList{N}}) where {N} = N	1✔
84	num_modes(::Type{<:SortedParticleList{<:Any,M}}) where {M} = M	1✔
85
86	###
87	### General functions
88	###
89	Base.eltype(::SortedParticleList) = Tuple{Int,Int,Int}	×
90
91	function Base.length(ss::SortedParticleList{<:Any,<:Any,T}) where {T}	130✔
92	curr = zero(T)	130✔
93	res = 0	130✔
94	for i in ss.storage	130✔
95	res += (i != curr)	700✔
96	curr = i	700✔
97	end	1,270✔
98	return res	130✔
99	end
100
101	function Base.iterate(ss::SortedParticleList{N}, i=1) where {N}	13,188,031✔
102	@inbounds if i > N	13,188,031✔
103	return nothing	321,597✔
104	else
105	occnum = 1	12,251,577✔
106	mode = ss.storage[i]	12,251,577✔
107	offset = i	12,251,577✔
108	i += 1	12,251,577✔
109	while i ≤ N && ss.storage[i] == mode	12,414,453✔
110	occnum += 1	162,876✔
111	i += 1	162,876✔
112	end	162,876✔
113	return (occnum, Int(mode), i - occnum - 1), i	12,251,577✔
114	end
115	end
116
117	function Base.reverse(ss::SortedParticleList{N,M,T}) where {N,M,T}	20✔
118	new_storage = map(reverse(ss.storage)) do i	20✔
119	T(M) - i + one(T)	300✔
120	end
121	return SortedParticleList{N,M,T}(new_storage)	20✔
122	end
123
124	# Somehow this is faster than the default method.
125	Base.hash(ss::SortedParticleList, u::UInt) = hash(ss.storage, u)	1,950✔
126
127	# In this case, getting the ONR is the same for bosons and fermions, and assumes the address
128	# is not malformed.
129	function onr(ss::SortedParticleList{<:Any,M}) where {M}	123,337✔
130	mvec = zeros(MVector{M,Int})	123,337✔
131	@inbounds for (occnum, mode, _) in ss	123,337✔
132	mvec[mode] = occnum	2,380,390✔
133	end	4,637,443✔
134	return SVector(mvec)	123,337✔
135	end
136
137	# Same as above.
138	function find_mode(ss::SortedParticleList, n)	491,520✔
139	offset = 0	491,520✔
140	for (occnum, mode, _) in ss	491,520✔
141	if mode == n	3,112,030✔
142	return (occnum, mode, offset)	32,484✔
143	elseif mode > n	3,079,546✔
144	return (0, n, offset)	405,169✔
145	end
146	offset += occnum	2,674,377✔
147	end	5,294,887✔
148	return (0, n, offset)	53,867✔
149	end
150
151	"""
152	move_particles(ss::SortedParticleList, dsts, srcs)
153
154	Move several particles at once. Moves `srcs[i]` to `dsts[i]`. `dsts` and `srcs` should be
155	tuples of [`BoseFSIndex`](@ref) or [`FermiFSIndex`](@ref). The legality of the moves is not
156	checked - the result of an illegal move is undefined!
157	"""
158	function move_particles(ss::SortedParticleList{N,M,T}, dsts, srcs) where {N,M,T}	7,011✔
159	new_storage = ss.storage	7,011✔
160	for (dst, src) in zip(dsts, srcs)	7,011✔
161	src_pos = 1	7,475✔
162	@inbounds for i in 1:N	7,475✔
163	src_pos = max(src_pos, i * (new_storage[i] == src.mode % T))	124,720✔
164	end	241,965✔
165	@boundscheck 0 < dst.mode ≤ M \|\| throw(BoundsError(ss, dst.mode))	7,475✔
166	new_storage = setindex(new_storage, dst.mode % T, src_pos)	7,475✔
167	end	7,939✔
168	return SortedParticleList{N,M,T}(sort(new_storage))	7,011✔
169	end
170
171	###
172	### Bose interface
173	###
174	function from_bose_onr(::Type{S}, onr) where{S<:SortedParticleList}	4,820✔
175	from_onr(S, onr)	4,820✔
176	end
177	to_bose_onr(ss::SortedParticleList, _) = onr(ss)	123,337✔
178
179	bose_num_occupied_modes(ss::SortedParticleList) = length(ss)	700✔
180
181	bose_find_mode(ss::SortedParticleList, n) = find_mode(ss, n)	×
182
183	@inline function bose_excitation(	123,466✔
184	ss::SortedParticleList{N,M,T}, creations, destructions
185	) where {N,M,T}
186	creations_rev = reverse(creations)	123,466✔
187	value = bose_excitation_value(creations_rev, destructions)	123,466✔
188	if iszero(value)	123,466✔
189	return ss, 0.0	118,479✔
190	else
191	return move_particles(ss, creations_rev, destructions), √value	4,987✔
192	end
193	end
194
195	Base.length(bom::BoseOccupiedModes{<:Any,<:Any,<:SortedParticleList}) = length(bom.storage)	×
196	function Base.iterate(bom::BoseOccupiedModes{<:Any,<:Any,<:SortedParticleList}, i=1)	6,043,878✔
197	it = iterate(bom.storage, i)	11,080,323✔
198	if isnothing(it)	10,587,317✔
199	return nothing	21,421✔
200	else
201	res, i = it	5,529,451✔
202	return BoseFSIndex(res...), i	5,529,451✔
203	end
204	end
205
206	###
207	### Fermi interface
208	###
209	function from_fermi_onr(::Type{S}, onr) where {S<:SortedParticleList}	2,088✔
210	from_onr(S, onr)	2,088✔
211	end
212
213	# Fix offsets and occupation numbers after creation/destruction operator is applied.
214	# The idea behind these is to allow computing the value from the indices alone.
215	function _fix_pos_create(c, index)	163,840✔
216	index = @set index.offset += (c.mode < index.mode)	163,840✔
217	index = @set index.occnum += (c.mode == index.mode)	163,840✔
218	return index	163,840✔
219	end
220	_fix_pos_create(c) = Base.Fix1(_fix_pos_create, c)	245,760✔
221	function _fix_pos_destroy(d, index)	737,280✔
222	index = @set index.offset -= (d.mode < index.mode)	737,280✔
223	index = @set index.occnum -= (d.mode == index.mode)	737,280✔
224	return index	737,280✔
225	end
226	_fix_pos_destroy(d) = Base.Fix1(_fix_pos_destroy, d)	491,520✔
227
228	"""
229	fermi_excitation_value_spl(
230	creations::NTuple{_,FermiFSIndex}, destructions::NTuple{_,::FermiFSIndex}
231	) -> {-1,0,1}
232
233	Compute the value of an excitation from indices. Starts by applying all destruction
234	operators, and then applying all creation operators. The operators must be given in reverse
235	order. Will return 0 if move is illegal.
236
237	Note that this function only works on indices obtained from a [`SortedParticleList`](@ref).
238	"""
239	@inline fermi_excitation_value_spl(::Tuple{}, ::Tuple{}) = 1.0	×
240	@inline function fermi_excitation_value_spl((c, cs...), ::Tuple{})	245,760✔
241	cs = map(_fix_pos_create(c), cs)	245,760✔
242	return fermi_excitation_value_spl(cs, ()) * ifelse(isodd(c.offset), -1, 1) * (c.occnum == 0)	245,760✔
243	end
244	@inline function fermi_excitation_value_spl(cs, (d, ds...))	245,760✔
245	cs = map(_fix_pos_destroy(d), cs)	245,760✔
246	ds = map(_fix_pos_destroy(d), ds)	245,760✔
247	return fermi_excitation_value_spl(cs, ds) * ifelse(isodd(d.offset), -1, 1) * (d.occnum == 1)	245,760✔
248	end
249
250	fermi_find_mode(ss::SortedParticleList, n) = FermiFSIndex(find_mode(ss, n))	491,520✔
251	function fermi_find_mode(ss::SortedParticleList, ns::Tuple)	×
252	# It's OK to do that instead of the fancy method used with bosons, because the
253	# assumption is that `N` is small.
254	return map(n -> FermiFSIndex(find_mode(ss, n)), ns)	×
255	end
256
257	@inline function fermi_excitation(	122,880✔
258	ss::SortedParticleList{N,M,T}, creations::NTuple{K}, destructions::NTuple{K}
259	) where {N,M,T,K}
260	creations_rev = reverse(creations)	122,880✔
261	destructions_rev = reverse(destructions)	122,880✔
262	value = fermi_excitation_value_spl(creations_rev, destructions_rev)	122,880✔
263	if iszero(value)	122,880✔
264	return ss, 0.0	120,856✔
265	else
266	return move_particles(ss, creations_rev, destructions), float(value)	2,024✔
267	end
268	end
269
UNCOV 270	Base.length(fom::FermiOccupiedModes{N,<:SortedParticleList}) where {N} = length(fom.storage)	×
271	function Base.iterate(fom::FermiOccupiedModes{<:Any,<:SortedParticleList}, i=1)	1,475,650✔
272	itr = iterate(fom.storage, i)	2,582,384✔
273	if isnothing(itr)	2,459,412✔
274	return nothing	122,972✔
275	else
276	res, i = itr	1,229,706✔
277	return FermiFSIndex(res...), i	1,229,706✔
278	end
279	end

RimuQMC / Rimu.jl / 15336754092

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