# What data structure do I need? (and is it implemented in Julia?)
**URL:** https://discourse.julialang.org/t/what-data-structure-do-i-need-and-is-it-implemented-in-julia/82378
**Category:** General Usage
**Tags:** question, data\_structures
**Created:** [June 7, 2022, 3:53pm UTC](https://discourse.julialang.org/t/what-data-structure-do-i-need-and-is-it-implemented-in-julia/82378 "2022-06-07T15:53:10Z")
**Posts on this page:** 6
**Page:** 1
### Author:  [@JAgho](https://discourse.julialang.org/u/JAgho)
#### Post date: [June 7, 2022, 3:53pm UTC](https://discourse.julialang.org/t/what-data-structure-do-i-need-and-is-it-implemented-in-julia/82378/1 "2022-06-07T15:53:10Z")
I have a collection of coordinates which is a fixed set. I collect these into groups using some arbitrary clustering scheme. Consequently I now hold some collection of arrays. I need to be able to merge groups together, or split groups into smaller groups.
Obviously this is `Dict` like behaviour. I require that keys are integers which count from `1 -> n`, with no gaps. Splits or merges may happen many, many times, so if a split occurs, I can’t simply delete a key and replace it with two new (higher valued) keys, as this will lead to a growing maximum value of a key, and consequently an eventual overflow.
What data structure has this property? Essentially each time I merge groups I want to permit a gap in the sequence of keys to form, and each time I split a group I want to preferentially fill any existing gaps before creating new key(s). Obviously I can implement this with a queue to which deleted keys are added, and drawn from preferentially before generating new keys, but this is both clumsy and probably reinventing the wheel.
Any advice would be hugely helpful, as the last thing I need is some weird custom behaviour happening behind the scenes.
---
### Author:  [@cjdoris](https://discourse.julialang.org/u/cjdoris)
#### Post date: [June 7, 2022, 4:27pm UTC](https://discourse.julialang.org/t/what-data-structure-do-i-need-and-is-it-implemented-in-julia/82378/2 "2022-06-07T16:27:00Z")
How about you have your `groups::Dict{Int,Whatever}` but also have an `unused_keys::Vector{Int}`. When you do a merge, `push!` the result onto `unused_keys`. When you do a split, `pop!` a key if `unused_keys` is not empty. I’m not sure if there’s a data structure like this already implemented.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [June 7, 2022, 4:35pm UTC](https://discourse.julialang.org/t/what-data-structure-do-i-need-and-is-it-implemented-in-julia/82378/3 "2022-06-07T16:35:19Z")
Are your coordinates of some given dimensionality e.g. 2D, 3D, 4D, or is the dimensionality always one of some few e.g. 2D or 3D?
Are the values of each coordinate always of some type or some supertype e.g. Ints, Floats32s, Int64s and Float64s or wider e.g. Complex, Quaternion?
---
### Author:  [@JAgho](https://discourse.julialang.org/u/JAgho)
#### Post date: [June 7, 2022, 4:39pm UTC](https://discourse.julialang.org/t/what-data-structure-do-i-need-and-is-it-implemented-in-julia/82378/4 "2022-06-07T16:39:52Z")
Coordinates are always fixed in dimensionality for a given data structure. This is usually 2D or 3D but I guess it’s generalisable to kD. Elsewhere I’m representing these with `SVectors`, but it seems the payload is secondary to the question?
---
### Author:  [@sbuercklin](https://discourse.julialang.org/u/sbuercklin)
#### Post date: [June 7, 2022, 4:45pm UTC](https://discourse.julialang.org/t/what-data-structure-do-i-need-and-is-it-implemented-in-julia/82378/5 "2022-06-07T16:45:06Z")
There may be a particular structure that solves this, but a `Vector{MyGroupType}` in conjunction with an `unused_keys` queue like cjdoris suggested is my intuition. `Vector` gives you `Dict`-like behavior for the “keys” as indices, and you can extend the vector as needed with `resize!`.
---
### Author:  [@JAgho](https://discourse.julialang.org/u/JAgho)
#### Post date: [June 7, 2022, 7:43pm UTC](https://discourse.julialang.org/t/what-data-structure-do-i-need-and-is-it-implemented-in-julia/82378/6 "2022-06-07T19:43:46Z")
This was the solution I hoped to avoid, but I guess it’s the sensible solution after all. With a little bit of tinkering, I ended up with:
```julia
function merge!(groups, unused, candidates)
min = minimum(candidates)
sd = setdiff(candidates, min)
for c in sd
append!(groups[min], groups[c])
empty!(groups[c])
end
append!(unused, sd)
end
#split! could use an array of coordinates :newgroup to describe the new split clusters
#logic is a bit yikes
function split!(groups, unused, candidate, newgroup)
len = length(newgroup)
ulen = length(unused)
if isempty(unused)
k = length(groups)
for i in len
groups[k+i] = newgroup[i]
end
elseif len < ulen
push!(unused, candidate)
foreach(((k, v), ) -> groups[k] = v, zip(unused, newgroup))
splice!(unused, ulen-len+1:ulen+1)
elseif len == ulen
push!(unused, candidate)
foreach(((k, v), ) -> groups[k] = v, zip(unused, newgroup))
empty!(unused)
else
push!(unused, candidate)
foreach(((k, v), ) -> groups[k] = v, zip(unused, newgroup))
empty!(unused)
k = length(groups)
for i in len
groups[k+i] = newgroup[i]
end
end
end
clusts #Dict{Int64, Vector{SVector{2, Int64}}}
uk = Int[]
#merge cluster 3 into 2, add key 3 to :uk
merge!(clusts, uk, (2,3))
# split clusts[10] to contain the values from clusts[5] and clusts[6]
# this will prefrentially write to clusts[3] as it was freed by the
# prior operation, with the second cluster written to the candidate clust[10]
split!(clusts, uk, 10, (clusts[5], clusts[6])) #dummy values
```
Needs a bit of testing and maybe a performance pass, but that seems to be the idea everyone suggested. Any e.g. type stability improving suggestions very welcome.
Edit: After some trimming to simplify the big messy `split!` function, we get this, which seems to behave for arbitrary collections.
```julia
function merge!(groups, unused, candidates)
min = minimum(candidates)
sd = setdiff(candidates, min)
for c in sd
append!(groups[min], groups[c])
empty!(groups[c])
end
append!(unused, sd)
end
function split!(groups, unused, candidate, newgroup)
len = length(newgroup)
push!(unused, candidate)
ulen = length(unused)
foreach(((k, v), ) -> groups[k] = v, zip(unused, Base.Iterators.take(newgroup, ulen)))
splice!(unused, max(ulen-len+1,1):ulen)
if len > ulen
k = length(groups)
for i in ulen+1:len
groups[k+i] = newgroup[i]
end
end
end
```