# Circular Vector custom collection

Hi all,

I am currently working in Scala 3 with immutable, finite, small circular collections, meaning that there is no proper beginning or end; unlike a standard `Vector`, each element at index n always has both an element before (even if n is 0) and an element after (even if n is the “last” index).

I wonder if it could be useful for me to create a custom collection to deal with them. So that for instance:

• any index, negative or positive is always valid;
• methods like `sliding` can be modified to behave correctly in a circular fashion;
• methods like `rotateLeft` and `rotateRight` can be added.

I would like to have your suggestions. Something like this exists already? (I haven’t found it) Maybe it is an overkill? Can this be achieved easily by extending and overriding `Vector`?

Mario

Seems a bit specialized – what sort of use cases do you use it for?

In general, it’s the sort of thing where I’d probably recommend starting out by releasing it as a library, and seeing how many people make use of it.

My main concern about it in terms of being a “standard” collection is that I’m not really sure how iteration would behave in a circular object like that, so it’s conceptually a bit different from most…

Hi @jducoeur, thanks for yr reply.

My use case is 2D geometry and graphs, I keep stumbling on circular collections, adjacent angles of a full 360° circle, sides of a perimeter, nodes of a circular path…

So I started thinking if it would be more elegant and sound to have something like `class Perimeter(angles: CircularVector[Double])` instead of `class Perimeter(angles: Vector[Double])`. And to deal at collection level with all the usual methods related to circularity: rotation, symmetries, knowing that after the last element you have the first one…

As for `Iteration` is a good point, I would say I would expect a standard behaviour, ending after the last element, not going into an infinite loop, if this is what you had in mind.

Plus I am not hoping to create something tremendously useful, it would be enough if it makes sense for me. More than happy to share it, of course. I was following in the tracks of Implementing Custom Collections (Scala 2.13) | Scala Documentation where it seems that sometimes creating custom collections (even if not so simple) is the right way to go.

Mario

What you are talking about is known as a circular or ring buffer. I implemented one in Scala many years ago, but I am not currently using it. The one I implemented was based on an Array and was not immutable. The whole thing was 48 lines long, including blank lines, so it’s very easy to implement. I would develop an immutable version if I had a use for it.

Thinking if an intermediate easy solution could be an `extension` that adds to a `Vector` specialized “circular” methods.

Something like:

``````extension[T](circular: Vector[T])
def applyC(index: Int): T =
val size = circular.size
val modulo = Math.abs(index) % size
val indexC =
if index < 0 && modulo != 0 then size - modulo
else modulo
circular(indexC)

def slidingC(size: Int): Iterator[Vector[T]] = ???

def rotate(steps: Int): Vector[T] = ???

val v = Vector(1, 2, 3, 6)
v.applyC(-5) // 6: Int
``````

Hi @jducoeur @Russ and everyone,

I have packed what I think can be a general purpose Scala3 solution in this public repository: GitHub - scala-tessella/ring-vector: Extends Scala3 immutable.Vector with ring (circular) methods

I really would like to have your critical opinion, before considering if it is worth releasing it as a packaged library.

Mario

2 Likes

Hey, you may want to add that to the scala-collection-contrib library so you don’t have to do all the ceremony of publishing a library for a single file.

1 Like

thank you for the tip, that is definitely a possibility as soon as the library accepts Scala 3. I see something is moving in that direction: Compile with Scala 3 by povder · Pull Request #166 · scala/scala-collection-contrib · GitHub

On a different level, I am noticing that all the methods I wrote for `Vector` can be generalized for `Seq`. So I have already tested a more general draft version RingSeq. And now the dumb question: which is in this case the correct way to work with bounds and higher kinds?

I have gone this way and it seems to work:

``````trait RingSeq:

/* for improved readability, a Vector index */
type Index = Int

/* and a RingVector index, any value is valid */
type IndexO = Int

extension[A, B <: Seq[A]](ring: B)

private def index(i: IndexO): Index =
java.lang.Math.floorMod(i, ring.size)

def applyO(i: IndexO): A =
ring(index(i))

def rotateRight(step: Int): B =
if ring.isEmpty then ring
else
val j: Index = ring.size - index(step)
(ring.drop(j) ++ ring.take(j)).asInstanceOf[B]

...
``````

but as soon as I wrote the first `asInstanceOf[B] ` I felt horribly guilty as a student who has not done the proper homework.

Can someone point me in the right direction?

Mario

1 Like

Not sure why you need to wait for Scala 3 just port the code to the old syntax.

About your other question, this is the starting point: Implementing Custom Collections (Scala 2.13) | Scala Documentation

1 Like

A naive (really!) attempt to fix this by shifting the “plugin point” to `SeqOps` for sequence types that always produce their own type as the result of combinator ops:

``````extension[A, B[_] <: SeqOps[A, B, B[A]]](ring: B[A])

// ...

def rotateRight(step: Int): B[A] =
if ring.isEmpty then ring
else
val j: Index = ring.size - index(step)
ring.drop(j) ++ ring.take(j)
``````

This seems to work with `List`, `Vector` and `Queue` at least. However, for a clean and stable solution, it’s probably best to work through the guide @BalmungSan linked to - there also seems to be a page on adding custom operations, which may or may not apply to your use case. (I haven’t ventured into this specific area, yet.)

2 Likes

First of all thank you very much @BalmungSan @sangamon for your feedbacks.

• Scala 3 vs Scala 2: I am sure back porting to Scala 2 must be feasible, I’ll take a look at it once I am confident and happy with the Scala 3 version. Personally after I moved to Scala 3 I try as much as possible to avoid switching codes, not good for my mental health

• Custom Collections vs Scala 3 `extension`: adding to the previous point, Custom Collections has been -as I wrote at the start of the thread- my starting point, but then I shifted to Scala 3 `extension` because most of the `Seq` collections would be exactly the same, instead of overriding 7 methods I can just add their O ring counterpart.

As for RingSeq I have an (at least apparently) perfectly working trait in the `seq` branch at ring-vector/RingSeq.scala at seq · scala-tessella/ring-vector · GitHub
But it relies on 7 `asInstanceOf` calls.

I tried also to implement @sangamon 's suggestion in the `withSeqOps` branch at ring-vector/RingSeq.scala at withSeqOps · scala-tessella/ring-vector · GitHub
Unfortunately it breaks 3 tests, see Using SeqOps as per @sangamon suggestion · scala-tessella/ring-vector@0cdeb9f · GitHub, the underlying error always of type

``````Found:    Any
Required: Int
``````

What I want to add is that I can truly see some merit and usefulness in a working RingSeq and I would like (with some help from the community, since I am not a super expert on these abstractions) to reach a point where it can be safely shared.

Mario

I mean, no need to create a new collection.
Just add extension methods; either with `extension` or `implicit class`

The blog I linked has a section about it, which explain how to use the `IsSeq` and `SeqOps`traits.

Uh, yes. Looks like it always matches to `SeqOps[Any, B, B[Any]]` - which isn’t wrong, as `SeqOps` is covariant in `A`, but I’d have expected the most specific match.

When tinkering with explicit casts, I ran into what looked like a compiler hang/infinite loop:

``````scala> List(1,2,3).rotateRight(1)
-- Info:
[[syntax trees at end of                     typer]] // rs\$line\$2
package repl {
final lazy module val rs\$line\$2: repl.rs\$line\$2 = new repl.rs\$line\$2()
final module class rs\$line\$2() extends Object() { this: repl.rs\$line\$2.type =>
val res0: List[Any] =
RingSeq.rotateRight[Any, List](List.apply[Int]([1,2,3 : Int]*))(1)
}
}

val res0: List[Any] = List(3, 1, 2)

scala> (List(1,2,3): scala.collection.immutable.SeqOps[Int, List, List[Int]]).rotateRight(1)
[warn] In the last 10 seconds, 5.759 (58.3%) were spent in GC. [Heap: 0.01GB free of 1.00GB, max 1.00GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.
Killed
``````

No idea what to make of this, I’m afraid - I’m neither fluent with custom collection extensions nor with in-depth Scala 3 (yet). Perhaps somebody more knowledgeable can chime in?

In the meanwhile, as per @BalmungSan suggestion, I submitted this pull request New circular Seq operations: rotateRight, rotateLeft, startAt by mcallisto · Pull Request #168 · scala/scala-collection-contrib · GitHub to add a first batch of (Scala 2.13) new circular operations to Seq.

Unfortunately I made no real progress in evolving RingSeq in Scala 3 or Scala 2, with `IsSeq` and `SeqOps`, will keep trying.

1 Like

On initial question: I have not found a simple way to return an empty `That` , see SeqDecorator line 84, any suggestion?

I haven’t tested but what about:

``````bf.fromSpecific(coll)(collection.View.Empty)
// Or
bf.fromSpecific(coll)(Seq.empty)
``````

Unfortunately I made no real progress in evolving RingSeq in Scala 3 or Scala 2, with `IsSeq` and `SeqOps`, will keep trying.

Yeah, abstracting over collections is a complex science. I personally have never been able to do something more advanced than just consuming anything that can behave as a collection; every attempt to do something else has ended in failure.
Good luck!

@BalmungSan thank you for the suggestion, I would say that `bf.fromSpecific(coll)(collection.View.Empty)` is correct.

I am really cautious about jumping to any conclusion since I just added a test for an empty `Seq` that is failing in really strange fashion:

``````[error] one error found
[error] /.../scala-collection-contrib/src/test/scala/scala/collection/decorators/SeqDecoratorTest.scala:55:35: diverging implicit expansion for type scala.math.Ordering[T1]
[error] starting with method Tuple9 in object Ordering
[error]     assertEquals(empty.rotateRight(1), empty)
``````

Hi everyone,

I just wanted to give an update on this topic.

In my spare time and thanks also to your feedbacks, the concept has taken the shape of a library, published here RingSeq and here Scaladex.

It works in Scala 3, 2.13 and 2.12 for any generic (immutable or mutable) `Seq`.

Best,

Mario

3 Likes