Bags

Bags are sets which allow repeated elements.

import es.weso.collection._

val bag = Bag("a","b","a")
// bag: Bag[String] = BagSortedMap(Map("a" -> 2, "b" -> 1))

RBE - Regular Bag Expressions

Regular Bag Expressions (RBE) are regular expressions where the order of the elements is not significant.

Example usage

The following line declares rbe as a regular bag expressions that matches between 1 or 3 as and 1 b:

import es.weso.rbe._

val rbe = And(Symbol("a",1,3), Symbol("b",1,1))
// rbe: And[String] = And(
//   Symbol("a", 1, IntLimit(3)),
//   Symbol("b", 1, IntLimit(1))
// )

There are 2 algorithms to check if a bag matches a rbe.

The interval algorithm is in PTime but only works if the rbe doesn't have repeated symbols.

Example:

import es.weso.rbe.interval._

val checker = IntervalChecker(rbe)
// checker: IntervalChecker[String] = IntervalChecker(
//   And(Symbol("a", 1, IntLimit(3)), Symbol("b", 1, IntLimit(1)))
// )

val check = checker.check(bag, false)
// check: checker.Matched[Bag[String]] = Right(
//   BagSortedMap(Map("a" -> 2, "b" -> 1))
// )