Circular array in Julia

Specific Domains Geo
1

Is the a simple way in Julia to define circular array, e.g., if I have:

x=zeros(4,4)

I would like that:

x[1,5] = x[1,1]
x[1,6] = x[1,2]
…

and

x[5,1] = x[1,1]
x[6,1] = x[2,1]
…

I would like to define a more complex grid topology so simple solution like adding the reminder operator:

x[1%4,5%4]

will not help

1 Like
2

Welcome to Julia’s Discourse forum!, about your question, you can define your own array type, defining the necessary interfaces (see this link). for example, a starting base can be this (supposing the circular size is the size of the data):

struct CircularArray{T,N} <: AbstractArray{T,N}
    x::AbstractArray{T,N}
end

the next step would be defining the basic operations: size, getindex and setindex!. here i have some trouble, if someone can help, it can be appreciated.

size(A::CircularArray) = size(A.x)

anyway, if this is made, it can be a nice adition to DataStructures.jl

3

Also, related post from discourse can help:

4

The question is not super-clear, but I am under the impression that @udistr may just be looking for a function that makes this array, and may be fine with a Matrix. In that case, a loop should be fine.

5

Thanks longemen3000,

Defining a new array type was my direction also. But I am still not sure how to implement the basic operations getindex and setindex!. This is so far what I was able to come up with:

struct CircularArray
    x
end

function (getindex::CircularArray)(i,j)

  x=getindex.x
  S=size(x);
  nx=S[1];ny=S[2];
  
  if (i>0 && i<=nx) && (j>0 && j<=ny)  
    return x[i,j]
  else     
    if i<1
      i1 = nx+i
      j1 = j
      return getindex(i1,j1)
    end
    if i>nx
      i1 = i-nx
      j1 = j     
      return getindex(i1,j1)
    end
    if j<1
      i1 = i
      j1 = ny+j
      return getindex(i1,j1)
    end
    if j>ny
      i1 = i
      j1 = j-ny
      return getindex(i1,j1)
    end
  end
end

x=reshape(collect(0:15).%4 .+1,(4,4));
y=x'

x1=CircularArray(x)
y1=CircularArray(y)

i=0;j=1;
x1(i,j),y1(i,j)

What should I do in order to be able to get the index with square brackets - x1[5,1] and how to set values, e.g., x[5,1]=1 ?

I do plan to use this for finite difference calculations but for some operations, such as box mean, it is not enough to have only the halo.

6

so, you need negative implementations?, lets see what can i do

7

There is a typo there, it should be:

i1 = nx+i
8

try this, the implementation is multidimentional

struct CircularArray{T,N} <: AbstractArray{T,N} #inherits from AbstractArray
    x::AbstractArray{T,N}
    function CircularArray(x::AbstractArray{T,N}) where {T,N} 
#creates the type only with a vector x
        return new{T,N}(x)
    end
end

Base.size(A::CircularArray) = size(A.x) #important: use of Base.function

Base.length(A::CircularArray)=length(A.x)

function Base.getindex(A::CircularArray, I::Vararg{Int, N}) where N # implements A[I]
    I2 = size(A)
    return Base.getindex(A.x,(mod.(I .- 1,I2) .+ 1)...) #this is the magic operation
end

Base.getindex(A::CircularArray, I) = (A[i] for i in I) #A[1:5], for example

function Base.setindex!(A,value,I::Vararg{Int, N}) where N # A[I] = value
    return Base.setindex!(A.x,value,(mod.(I .- 1,I2) .+ 1)...)
end

Base.IndexStyle(::Type{CircularArray}) = IndexCartesian()

example code:

x=reshape(collect(0:15).%4 .+1,(4,4));
y=x'

x1=CircularArray(x)
y1=CircularArray(y)

i=0;j=1;
x1[i,j],y1[i,j]

this works in N dimensions:

#1-dimentional example
z = 1:15
z2 = CircularArray(z)
z2[16] # 1
z3 = collect(z2[14:16]) #[14,15,1]
9

When implementing a circular array, doesn’t it make much more sense to use 0-based indexing?

2 Likes
10

maybe, my toughts were to preserve the 1-based indexing of julia, and preserve the equality circular_x[i,j] == x[i,j]

3 Likes
11

There exists an implementation in ShiftedArrays: https://github.com/piever/ShiftedArrays.jl/blob/master/src/circshiftedarray.jl

If you need something more complex but along these lines, hopefully it can serve as a starting point to write your own custom array type.

1 Like
12

And there is the mod1 function to avoid all this shifting indices manually:

julia> mod1(5,5)
5

julia> mod1(6,5)
1
3 Likes
13

Thanks again longemen3000 (and others)! This do what I want except this:

julia> x1[:,0]
ERROR: BoundsError: attempt to access 4×4 CircularArray{Int64,2} at index [Base.Slice(Base.OneTo(4)), 0]
Stacktrace:
 [1] throw_boundserror(::CircularArray{Int64,2}, ::Tuple{Base.Slice{Base.OneTo{Int64}},Int64}) at ./abstractarray.jl:484
 [2] checkbounds at ./abstractarray.jl:449 [inlined]
 [3] _getindex(::IndexCartesian, ::CircularArray{Int64,2}, ::Base.Slice{Base.OneTo{Int64}}, ::Int64) at ./multidimensional.jl:641
 [4] getindex(::CircularArray{Int64,2}, ::Function, ::Int64) at ./abstractarray.jl:927
 [5] top-level scope at none:0

x[1,0] and x[:,1] work so it is only a problem dealing with ranges outside array boundaries. Any ideas how to solve this?

1 Like
14

That’s just a matter of defining the appropriate checkbounds specialization. In fact, I think you can simply turn off bounds checks entirely:

Base.checkbounds(A::CircularArray, I...) = nothing
3 Likes
15

This is material for a small compact package!

2 Likes
16

Is there a package with this circular array type available and well-tested already?

2 Likes
17

Perhaps https://github.com/Vexatos/CircularArrays.jl ?

5 Likes
18

Maybe this one can help:

https://github.com/udistr/CyclicArrays.jl

4 Likes
19

@udistr can you comment on the difference between CyclicArrays.jl and CircularArrays.jl? Aren’t they equivalent?

20

CyclicArrays.jl is aimed at handling more complex multi-face array topologies. For example, a cubed-sphere grid with 6 faces, in which the faces are interconnected in a non-trivial manner.

1 Like