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?

Thank you in advance,

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.

Thank you in advance.

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

Hi @BalmungSan

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?

Thank you in advance,

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 :slight_smile:

  • 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 SeqOpstraits.

Uh, yes. :confused: 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 :slight_smile: 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)