アルゴリズムの練習 in Scala

ChainedHashTable.scala

import scala.collection.mutable
import scala.util.Random

case class ChainedHashTable[A](private var t: Array[mutable.ListBuffer[A]],
                               private var d: Int,
                               private var n: Int = 0,
                               private var z: Int)
    extends USet[A] {

  private[this] lazy val w: Int = 32

  override def size: Int = this.n

  override def add(a: A): Boolean = {
    find(a).fold {
      if (n + 1 > t.length) {
        resize()
      }
      t(hash(a)) += a
      n = n + 1
      true
    } (_ => false)
  }

  override def remove(a: A): Option[A] = {
    var it = t(hash(a)).iterator
    while (it.hasNext) {
      val b = Some(it.next()) // hasNext を通しているので常にある
      if (b.contains(a)) {
        val index = it.indexOf(b.get)
        it = it.drop(index)
        n = n - 1
        return b
      }
    }
    None
  }

  override def find(a: A): Option[A] = {
    t(hash(a)).find(_ == a)
  }

  override def clear(): Unit = {
    d = 1
    t = allocTable(1 << d)
    n = 0
  }

  override def iterator: Iterator[A] = {
    class InnerIterator(private var i: Int,
                        private var j: Int,
                        private var ilast: Int = 0,
                        private var jlast: Int = 0)
        extends Iterator[A] {
      override def hasNext: Boolean = i < t.length
      override def next(): A = {
        ilast = i
        jlast = j

        val x = t(i)(j)
        j = j + 1

        while (i < t.length && j + 1 > t(i).size) {
          j = 0
          i = i + 1
        }

        x
      }
    }

    locally {
      var i = 0
      val j = 0
      while (i < t.length && t(i).isEmpty) {
        i = i + 1
      }

      new InnerIterator(i, j)
    }
  }

  private def resize(): Unit = {
    d = 1

    while (1 << d <= n) {
      d = d + 1
    }

    n = 0

    val oldTable = t
    t = allocTable(1 << d)
    oldTable.foreach(lb => lb.foreach(x => add(x)))
  }

  private def hash(a: Any): Int = (z * a.hashCode()) >>> (w - d)

  private def allocTable(s: Int): Array[mutable.ListBuffer[A]] =
    ChainedHashTable.allocTable(s)
}

object ChainedHashTable {

  def create[A](): ChainedHashTable[A] = {
    val d = 1
    val t = allocTable[A](1 << d)
    val z = {
      val r = Random
      r.nextInt() | 1
    }

    ChainedHashTable(t = t, d = d, z = z)
  }

  private def allocTable[A](s: Int): Array[mutable.ListBuffer[A]] = {
    val tab: Array[mutable.ListBuffer[A]] = new Array[mutable.ListBuffer[A]](s)
    (0 until s).foreach(i => tab.update(i, mutable.ListBuffer[A]()))
    tab
  }
}

object Main extends App {
  val chainedHashTable = ChainedHashTable.create[Int]()
  (1 to 10000).foreach(i => chainedHashTable.add(i))
  println(chainedHashTable.size) // 10000

  (1 to 10000).foreach(i => chainedHashTable.remove(i))
  println(chainedHashTable.size) // 0
}

LinearHashTable.scala

case class LinearHashTable[A](private var t: Array[Option[A]],
                              private var del: A,
                              private var n: Int = 0,
                              private var d: Int,
                              private var q: Int = 0)
    extends USet[A] {

  private[this] lazy val w: Int = 32

  override def add(a: A): Boolean =
    find(a).fold {
      if (2 * q + 1 > t.length) {
        resize()
      }

      var i = hash(a)

      while (!t(i).contains(del)) {
        i = if (i == t.length - 1) {
          0
        } else {
          i + 1
        }
      }

      if (t(i).isEmpty) {
        q = q + 1
      }

      n = n + 1

      t.update(i, Option(a))

      true
    }(_ => false)

  override def remove(a: A): Option[A] = {
    var i = hash(a)

    while (t(i).isDefined) {
      val y = t(i)
      if (!y.contains(del) && y.contains(a)) {
        t(i) = Option(del)
        n = n - 1
        if (8 * n < t.length) {
          resize()
        }
        return y
      }

      i = if (i == t.length - 1) {
        0
      } else {
        i + 1
      }
    }

    None
  }

  override def find(a: A): Option[A] = {
    var i = hash(a)

    while (t(i).isDefined) {
      if (!t(i).contains(del) && t(i).contains(a)) {
        return t(i)
      }

      i = if (i == t.length - 1) {
        0
      } else {
        i + 1
      }
    }

    None
  }

  override def clear(): Unit = {
    n = 0
    q = 0
    d = 1
    t = new Array(1 << d)
  }

  override def iterator: Iterator[A] = {
    class InnerIterator(private var i: Int, private var iprev: Int)
        extends Iterator[A] {
      override def hasNext: Boolean = i < t.length
      override def next(): A = {
        val x = t(i)
        iprev = i
        while (i < t.length && (t(i).isEmpty || t(i).contains(del))) {
          i = i + 1
        }
        x.get
      }
      // remove がない？？
    }

    new InnerIterator(i = {
      var n = 0
      while (n < t.length && (t(n).isEmpty || t(n).contains(del))) {
        n = n + 1
      }
      n
    }, -1)
  }

  private def hash(a: A): Int = {
    import utils.TabularHashing._
    val h = a.hashCode()
    tab(0)(h & 0xff) ^ tab(1)((h >>> 8) & 0xff) ^ tab(2)((h >>> 16) & 0xff) ^ tab(
      3)((h >>> 24) & 0xff) >>> (w - d)
  }

  private def resize(): Unit = {
    d = 1

    while ((1 << d) < 3 * n) {
      d = d + 1
    }

    val told = t
    t = new Array(1 << d)
    q = n

    told.zipWithIndex.foreach(element => {
      val k = element._2
      if (told(k).isDefined && told(k).contains(del)) {
        var i = hash(told(k).get)
        while (t(i).isDefined) {
          i = if (i == t.length - 1) {
            0
          } else {
            i + 1
          }
        }
        t.update(i, told(k))
      }
    })
  }
}

object LinearHashTable {

  def create[A](del: A): LinearHashTable[A] = {
    val d = 1
    val t = new Array[Option[A]](1 << d) // TODO 初期化してくれない気がする
    LinearHashTable(d = d, del = del, t = t)
  }
}

TabularHashing.scala

package utils

object TabularHashing {
  lazy val tab: Array[Array[Int]] = Array(
    Array(0x0069aeff, 0x6ac0719e, 0x384cd7ee, 0xcba78313, 0x133ef89a,
      0xb37979e6, 0xa4c4e09c, 0x911c738b, 0xc7fe9194, 0xba8e5dc7, 0xe610718c,
      0x48460ac5, 0x6b4d9d43, 0x73afeeab, 0x051264cb, 0x4b3dba93, 0x28837665,
      0xfb80a52b, 0xad1c14af, 0xb2baf17f, 0x35e311a5, 0xf7fa2905, 0xa973c315,
      0x00885f47, 0x8842622b, 0x0445a92c, 0x701ba3a0, 0xef608902, 0x176099ad,
      0xd240f938, 0xb32d83c6, 0xb341afb8, 0xc3a978fb, 0x55ed1f0c, 0xb581286e,
      0x8ff6938e, 0x9f11c1c5, 0x4d083bd6, 0x1aacc2a4, 0xdf13f00a, 0x1e282712,
      0x772d354b, 0x21e3a7fd, 0x4bc932dc, 0xe1deb7ba, 0x5e868b8a, 0xc9331cc6,
      0xaa931bbf, 0xff92aba6, 0xe3efc69f, 0xda3b8e2a, 0xf9b21ec1, 0x2fb89674,
      0x61c87462, 0xa553c2f9, 0xca01e279, 0x35999337, 0xf44c4fd3, 0x136a2773,
      0x812607a8, 0xbfcd9bbf, 0x0b1d15cd, 0xc2a0038b, 0x029ab4f7, 0xcd7c58f9,
      0xed3821c4, 0x325457c6, 0x1dc6b295, 0x876dcb83, 0x52df45fc, 0xa01c9fba,
      0xc938ff66, 0x19e52c87, 0x03ae67f9, 0x7db39e51, 0x74f31686, 0x5f10e5a3,
      0x74108d8a, 0x64e63104, 0xd86a38d6, 0x65be2fbb, 0xef06049e, 0x9bca1dbd,
      0x06c63e73, 0xe97bd103, 0xfed3c22c, 0x09d10fc6, 0xb92633a3, 0x21378ebf,
      0xe37fa54e, 0x893c7910, 0xc1c74a5a, 0x6c23c029, 0x4d4b6187, 0xd72bb8fb,
      0x0dbe1118, 0x5e0f4188, 0xce0d2dc8, 0x8dd83231, 0x0466ab90, 0x814bc11a,
      0xef688b9b, 0x0a03c851, 0xca3c984f, 0x6df87ca4, 0x6b34d1b2, 0x2bad5c75,
      0xaed1b6d8, 0x8c73f8b4, 0x4577d798, 0x5c953767, 0xe7da2d51, 0x2b9279a0,
      0x418d9b51, 0x8c47ec3d, 0x894e6119, 0xa0ca769d, 0x1c3b16a4, 0xa1621b5b,
      0xa695da53, 0x22462819, 0xf4b878cf, 0x72b4d648, 0x1faf4267, 0x4ba16750,
      0x08a9d645, 0x6bfb829c, 0xe051295f, 0x6dd5cd97, 0x2e9d1baf, 0x6ed6231d,
      0x6f84cb25, 0x9ae60c95, 0xbcee55ca, 0x6831cd97, 0x2ccdbc99, 0x9f8a0a81,
      0xa0b2c08f, 0xe957c36b, 0x9cb797b5, 0x107c6362, 0x48dacf5d, 0x6e16f569,
      0x39be78c3, 0x6445637f, 0xed445ee5, 0x8ec45004, 0x9ef8a405, 0xb5796a45,
      0x049d5143, 0xb3c1d852, 0xc36d9b44, 0xab0da981, 0xff5226b3, 0x19169b4c,
      0x9a49194d, 0xba218b42, 0xab98c8ee, 0x4db02645, 0x6faca3c8, 0x12c60d2d,
      0xaf67b750, 0xf0f6a855, 0xead566d9, 0x42d0cccd, 0x76a532bb, 0x82a6dc35,
      0xc1c23d0e, 0x83d45bd2, 0xd7024912, 0x97888901, 0x2b7cdd2c, 0x523742a5,
      0xecb96b3b, 0xd800d833, 0x7b4d0c91, 0x95c7dd86, 0x88880aad, 0xf0ce0990,
      0x7e292a90, 0x79ac4437, 0x8a9f59cc, 0x818444d1, 0xae4e735d, 0xa529db95,
      0x58b35661, 0xa909a7de, 0x9273beaa, 0xfe94332c, 0x259b88e4, 0xc88f4f6a,
      0x2a9d33ef, 0x4b5d106d, 0xdc3a9fca, 0xa8061cad, 0x7679422c, 0xaf72ad02,
      0xc5799ea5, 0x306d694d, 0x620aad10, 0xd188b9dd, 0xeff6ad87, 0x6b890354,
      0xb5907cd3, 0x733290fc, 0x4b6c0733, 0x0bad0ebd, 0xa049d3ad, 0xc9d0cdae,
      0x9c144d6f, 0x5990b63b, 0xfa33d8e2, 0x9ebeb5a0, 0xbc7c5c92, 0xd3edd2e6,
      0x54ae1af6, 0xd6ada4bd, 0x14094c5a, 0x0e3c5adf, 0xf1ab60f1, 0x74456a66,
      0x0f3a675a, 0x87445d0d, 0xa81adc2e, 0x0f47a1a5, 0x4eedb844, 0x9c9cb0ce,
      0x8bb3d330, 0x02df93e6, 0x86e3ad51, 0x1c1072b9, 0xacf3001b, 0xbd08c487,
      0xc2667a11, 0xdd5ef664, 0xd47b67fb, 0x959cca45, 0xa7da8e68, 0xb75b1e18,
      0x75201924, 0xe689ab8b, 0x0f5e6b0a, 0x75205923, 0xbba35593, 0xd24dab24,
      0x0288caeb, 0xcbf022a9, 0x392d7ee5, 0x16fe493a, 0xb6bcadfd, 0x9813ec72,
      0x9aa3d37c, 0xee88a59e, 0x6cdbad4e, 0x6b96aabf, 0xcb54d5e5),
    Array(0x116fc403, 0x260d7e7b, 0xdef689e7, 0xa5b3d49a, 0x921f3594,
      0xb24c8cba, 0x1bdefb3f, 0x6519e846, 0x24b37253, 0x1cc6b12b, 0x6f48f06e,
      0xca90b0db, 0x8e20570b, 0xda75ed0f, 0x1b515143, 0x0990a659, 0xdcedb6b3,
      0xec22de79, 0xdd56f7a9, 0x901194a6, 0x4bf3db02, 0x5d31787d, 0xd24da2ca,
      0x9fc9bc14, 0x9aa38ac9, 0xe95972ba, 0x8233a732, 0xb9d4317e, 0x51f9b329,
      0x94f12c56, 0x1ace26e4, 0xecda5183, 0x1353e547, 0x39b99ab3, 0x6413ac97,
      0xeb6b5334, 0xdd94ed2b, 0x298e9d2c, 0xd38abc91, 0x3f17ee4e, 0x99f8931d,
      0x88bae7da, 0xb5506a36, 0x2d7baf6d, 0x42a98d2b, 0xbb9b94b9, 0x58820083,
      0x521bba4c, 0x76699597, 0x137b86be, 0x8533888e, 0xb37316dd, 0x284c3de4,
      0xfe60e3e6, 0x94edaa40, 0x919c85cd, 0x24cb6f23, 0x6b446fbd, 0xbe933c15,
      0x2a43951a, 0x791a9f90, 0x47977c04, 0xa6350eec, 0x95e817a5, 0xffc82e8c,
      0xad379229, 0x6ec9531a, 0x8cab29f9, 0xb2f18402, 0xd0ebdac1, 0xd7b559b4,
      0x7ad30e7c, 0xe1d1adb7, 0x58a66f9c, 0x7a26636a, 0x8c865f92, 0x65363517,
      0x732b87db, 0x64a1ad52, 0x72e87c39, 0x0b943e4d, 0x532d3593, 0xedcf9975,
      0x44b5bec1, 0x13ac91f8, 0x6e6f3a76, 0x36ac3c6d, 0x528a3ecf, 0xf3d8cd75,
      0x8facd64c, 0xdb4d13d5, 0x80d49a67, 0xaa7061d3, 0x9486ba8d, 0x7454a65b,
      0x18e7b707, 0xd9cc05b9, 0x44eb014d, 0x28ba26d8, 0xa8852791, 0xf8dc3053,
      0xabe46b52, 0x9e261d1f, 0x768f83dd, 0x1c888838, 0x6d9b9ce6, 0x69e82575,
      0x2959538f, 0xd0ff9685, 0x92b4540c, 0x7c93035b, 0x7cad90ad, 0x49aaa908,
      0x3981f4b8, 0x191f4339, 0xd0971bfc, 0xa7209692, 0x0e253cad, 0x40e2ee61,
      0xc5c63486, 0xdf4f238b, 0x2d3cb89a, 0x3b5704b2, 0xcc14c2cb, 0xb1698d38,
      0x079c3b9b, 0xbb3867e4, 0x9f01e223, 0x35e69012, 0x5c87d888, 0x2cea4193,
      0xee088da5, 0x0ea4d5ab, 0x8a4906e8, 0xf6e5e283, 0xee87fa18, 0x9f96c751,
      0x947252c0, 0x9b50b97e, 0x05952521, 0x9440f5ae, 0xa0642786, 0xebcc62be,
      0xadccf011, 0x00b863e6, 0x1c3ab5b3, 0x7c701e4b, 0xa9565792, 0xb1ad459c,
      0x833ba164, 0x89544ae3, 0x35540c75, 0x198d0fec, 0xbe93bf33, 0xc28444b3,
      0xbc3add48, 0xb4300c14, 0xee0ed408, 0xca08ada3, 0x0be06480, 0xc4dd8ce2,
      0x61195564, 0x5b10a111, 0x65cd2b3b, 0xcbeb06ae, 0xfce70080, 0xef40b102,
      0xfc0bfe6f, 0x8111bf20, 0xfb166db1, 0x3598b2ef, 0x1e0e04de, 0x1bf7cf2d,
      0x0de7eaf1, 0x829457e0, 0xe8865341, 0x826272ad, 0xb57db2a4, 0x7413e6e7,
      0x416323ff, 0x8e08d503, 0x1da4dfac, 0x983b9a78, 0x0fab5fe0, 0x585e7a90,
      0x038cf73c, 0xecf90d31, 0x046055c8, 0x59926d71, 0x06959f1f, 0x3b8290b7,
      0x0bb834d9, 0xa0dc5bec, 0xec9ae604, 0x6ebfd59d, 0xfeccbab5, 0x240bd4ba,
      0x2df2b232, 0xe14e0383, 0xd86526ec, 0xe3d974fc, 0x940662b5, 0x81abf5d4,
      0x8010e6eb, 0x700d9849, 0x040d0c42, 0xc980417b, 0x95fa374a, 0x724b1448,
      0x217205ec, 0x0153b4bb, 0xea55ea92, 0x2049d5a1, 0x82576f06, 0x586fcfeb,
      0xa975e489, 0x14c862e9, 0xacb8b52c, 0x2f3fb91e, 0xce273650, 0x66608f4a,
      0x24f81bb7, 0x0382dc34, 0x07bdc163, 0xc42ad034, 0xe63cf998, 0x1a61f233,
      0xd5754ebe, 0x37275214, 0x2322de2a, 0x3a53b9b4, 0xab9c6963, 0x2f3a51be,
      0x5066e7c7, 0x941bda97, 0x75fadceb, 0xd05ad081, 0xf77d5daf, 0xd9879250,
      0xebf8bf97, 0x65be4a70, 0x388eda48, 0x728173fb, 0x05975bfa, 0x314dad8a,
      0x2cb4909f, 0xc736b716, 0x9007296d, 0x4fd61551, 0xd4378ccf, 0x649aac3e,
      0xd9ca1a9d, 0x16ff16ae, 0x8090f1c5, 0xfe0c4703, 0xc4152307),
    Array(0xf07e5e34, 0x62114ba6, 0xf45ffe22, 0xbaa48702, 0xe27e48a4,
      0xc43b4779, 0x549a4566, 0x93bc4836, 0x3b2e8d46, 0x3f8a77ae, 0x71e2d944,
      0xc09c5dce, 0xebfbfd4f, 0x7f8e1c40, 0x3c310a69, 0x52f62f09, 0xb7fd11bb,
      0xa9d055a7, 0xe3bd4654, 0x9696ae10, 0xdf953225, 0x42fd2380, 0x69756e5c,
      0x9d950bc4, 0xe2beea59, 0xd33daa07, 0xe97d31ce, 0xd9fb0a49, 0x553a27f2,
      0x7166586f, 0xeb04d48c, 0x72adb63a, 0x340ab99e, 0x459b4609, 0x481421b7,
      0x7db83c71, 0x192f6c22, 0x711852a8, 0xc6bd6562, 0xb91be2c8, 0xefe89dbf,
      0xc404eb9b, 0x9ebc1bc7, 0x8dc7eed2, 0x4d84efd7, 0x0783d7e5, 0x3b5ca2f2,
      0x9997e51c, 0x89b432c9, 0x72ae9672, 0x61d522d9, 0xa639fd45, 0xa7da3b46,
      0x696e73ec, 0x89581a95, 0x4aa25f94, 0xd0eb2a48, 0x04865f68, 0x1cbd651a,
      0xd6b2afd9, 0xd401b965, 0xd20aa5a7, 0xc0aa1b15, 0xfb4ce7af, 0x159974c5,
      0x15d0841d, 0x6b2836b4, 0xef3b3edf, 0xaf2db0b3, 0x13106fb6, 0xff41d7f9,
      0xab2a698d, 0x68e04dc9, 0xe5ee0099, 0xe50d4017, 0x5ea78d6d, 0x2e18fb07,
      0xfe22b9ff, 0x544c05f1, 0xc2e10853, 0x8d151bd6, 0x17ee763a, 0xa663ce31,
      0x4a4b5e33, 0x298b13c1, 0xd3b40c89, 0x121b6b4e, 0x59cf0429, 0x3d0bab9d,
      0xd24c5dfe, 0x5bb7349f, 0xac5dbfe9, 0x7eca5ebb, 0xadb8b3e3, 0x71ab540b,
      0xc8e3dc0d, 0x12e6cd3f, 0x8197f22c, 0x5ff77265, 0xe5641dbc, 0x818ab24c,
      0x627b98f7, 0xdd84e1d6, 0x531c2346, 0xec2f4e3c, 0x4a3cb318, 0x70cb24fe,
      0x35c17bfe, 0xec91fd18, 0x6efb3c18, 0x16908369, 0x41732188, 0x449e658b,
      0x2e9931cb, 0x67cd066e, 0x883ca306, 0xf66aecac, 0x979bf015, 0x8e85e27d,
      0x0560372b, 0x987995d6, 0xaff98ed7, 0x552ee87b, 0x21a53787, 0x3d3cfd45,
      0xa084dae0, 0x8c91be2f, 0xac4c3550, 0xa7db63ff, 0x124b2f23, 0x95d05d4e,
      0xb983db13, 0xa929a3c1, 0x111cd0a0, 0xf59ded9a, 0xce677ae3, 0xfa949e59,
      0xd673e658, 0xf8c8e27b, 0x3c60fc3d, 0x59a4f230, 0xf54a5e87, 0x08cff440,
      0xd4bbb1ee, 0x6a0c7db0, 0xecbaa99d, 0xec61dcaf, 0xf1056e2b, 0x54236899,
      0xadad347c, 0xc9885bc9, 0x2fe2a4ec, 0x01ba2b86, 0x6b23f604, 0xb354ef08,
      0x6a3dc5e2, 0xab61da36, 0x7543925a, 0x0a558940, 0x48d4d8f3, 0xd84f2f6f,
      0x6ac5311c, 0xcd1b660e, 0x51293d3d, 0xa0f15790, 0xd629cd78, 0x89201fa5,
      0x46005119, 0x9617fa14, 0xc375a68b, 0x7ccb519b, 0x6420a714, 0xb736d2ce,
      0x154fcf4a, 0x71cad2f5, 0xacb150d7, 0x97bc8e36, 0xc5506d0a, 0xa9facc35,
      0x1a9630db, 0xbd3d72ee, 0x58cdf27c, 0x17f3e1f9, 0x41598836, 0xd6adac30,
      0x309a5b3f, 0x3bd3aa32, 0x40f08f50, 0xf37cbd6c, 0xcbdb8aef, 0xe0819189,
      0x5a9b663b, 0x6932a448, 0xb1b3e866, 0xc50ee24d, 0xad999126, 0xafb04056,
      0xc95974e5, 0x636a64fa, 0x0bb12dd9, 0x78caa164, 0xd26a7ec8, 0x451a0b53,
      0x6d00aac6, 0x484d1d9d, 0x39728dd4, 0xfbfec2ea, 0xa6d5aaf9, 0x91c4f6ea,
      0x31cab009, 0x9b6ba4e8, 0xe271ed67, 0x4c87a84d, 0x8a1a4567, 0x93749497,
      0xc566edcc, 0xc8229554, 0x927925fd, 0xad1caced, 0xdc24f7ed, 0xc92b9220,
      0x936cd037, 0xbd2d0256, 0x5c92409b, 0xa3aa2682, 0x4da97646, 0xbcfdec81,
      0x25d5b61d, 0x20e1660d, 0x4b5214ed, 0x91aa596a, 0xb241415c, 0x88ec91a1,
      0x2375e939, 0x981ad627, 0x4a54ee18, 0x13d98660, 0x9375c64d, 0x538d3b28,
      0x4bf37ca7, 0x192b351e, 0x3cacf215, 0x3ecf3565, 0x50f5c0fc, 0xaafe3d4e,
      0x6351b4f5, 0x1b800d4f, 0xfad73cdf, 0xe300e1d8, 0xb2cb5b04, 0xfb019702,
      0xfb647f85, 0x375a7b74, 0xed6a6760, 0x45c54e76, 0x06524d79),
    Array(0x48722ec4, 0x8a2694db, 0x3cf80478, 0xf9bc47ba, 0x76b258fb,
      0xf71a1ec6, 0x841189df, 0x1a866461, 0x72b5488c, 0x71663983, 0xbda59407,
      0xa2b68f85, 0x62dbd0aa, 0xe4966aa3, 0x32e0efaa, 0x71bb3699, 0x2eda14a6,
      0x53f8917c, 0x874974ce, 0xe680bcca, 0x96a9c462, 0x399ca451, 0xc46616f5,
      0xeee71114, 0x5878e472, 0x3a83c559, 0x54862a18, 0x82aea480, 0x492d0019,
      0xd62a7027, 0x36655f50, 0xce412fdf, 0xc8136871, 0xd6cfe1d8, 0x121c9c91,
      0x13abbf51, 0x3aaa7037, 0x9f6e7cb6, 0xae82c4c4, 0x55fdce32, 0xd8dd6bda,
      0xd6ec4938, 0x6a5aee52, 0x52c8a764, 0xa6a85297, 0x5131de9e, 0x396a6599,
      0xe27b1100, 0xe68588d3, 0x7b89a612, 0xad48a7a4, 0xfd205673, 0x81807089,
      0x239d2d38, 0x39518df3, 0x256f3f14, 0x5c65e7b8, 0x64caebdc, 0xd8d694b6,
      0xb4a87da3, 0xa651881e, 0xca1d252d, 0x993a3ddc, 0x14f9a54d, 0x6b14d2ff,
      0xbbed03bb, 0x8d12bc03, 0x6cce455d, 0x613d6487, 0x6d04ce6a, 0xc2f4c84c,
      0x306d8ff2, 0x584a9847, 0x68902fc5, 0x70af1a4f, 0x3ab4cb98, 0xe8be4453,
      0x7e95d355, 0x84b0f371, 0x4c5ccb52, 0xdd6d029c, 0xafa47124, 0x71aabf91,
      0xd3407f95, 0xe7fa3a9c, 0x4f634405, 0x0cbf2cb7, 0x0192ff17, 0x296959dd,
      0x9e4d34d5, 0xfd9a4286, 0xac7b6933, 0x4650f585, 0x168af40d, 0x73816119,
      0x5542d96d, 0x99047276, 0x1b5bbe67, 0x01a8209e, 0x6f9db32e, 0xd762bbd1,
      0x299a3804, 0x87abe66d, 0xd479eeaa, 0x79928f4e, 0x3937ffbc, 0x3c8e83ca,
      0x2a8f9347, 0x4d2324d3, 0xf0183dda, 0x9fbedb15, 0xac365889, 0xf1be552c,
      0xa4b32d5a, 0xdc77fff3, 0x9d516da8, 0x7f3c347c, 0x39e8479f, 0x9e869687,
      0x6a160347, 0x49ab7403, 0x830d31c7, 0x11311354, 0x79e6cc69, 0x35b25caa,
      0x398af9aa, 0x02ef4356, 0xb5ecba53, 0x666d6c8b, 0x8836b3ae, 0x23b9fc98,
      0x0cc8e3d0, 0x3ad594e1, 0xb124529d, 0xe059c1de, 0xfa88e0d9, 0xba117846,
      0x1782a65a, 0xee9f80f9, 0xbc9aec55, 0x88aec1d4, 0x9c3907fa, 0x92b7b5bf,
      0x464acbf4, 0xbbbd04a8, 0xf0e966bf, 0x14c5f971, 0x83018d49, 0xfaf4fc0a,
      0x3b4639b2, 0x6b7e297d, 0xc0e9a807, 0x418713d3, 0x1a2b2361, 0x80850d90,
      0xd515816e, 0x3deb48ea, 0x6bfe6aa1, 0x3680036c, 0x228e76ae, 0x78f16c87,
      0xff4d85ea, 0x7d831974, 0xba962d6b, 0x4bae0b1d, 0xc0db431a, 0x04b46400,
      0xcf427175, 0x244e321d, 0x1c8b1fc9, 0x63a2b794, 0x1939d9c6, 0xc92a530e,
      0x21a8e5ad, 0x28050194, 0x3b106223, 0xb21e2ce1, 0x7ae71fe4, 0x7f7759f0,
      0x0329c8f4, 0xd09f6b37, 0x897e12a5, 0x4103c4b1, 0x56520dae, 0x5d7391aa,
      0x7ac9f12d, 0xeac6b834, 0x99f8f6a8, 0x2867867a, 0xff6f3343, 0x3167097a,
      0x38432d1d, 0x108377f8, 0xfd8e0d5f, 0x25e15692, 0xf00d40f9, 0x1f1276f3,
      0xb748c8cd, 0x6dbb9d9c, 0x99ab7ceb, 0xa4a9784f, 0xcb4b2535, 0xb3eb5ca7,
      0xd3a09e75, 0x90f3ee7e, 0x28ef2a57, 0xbdb643a2, 0x1112ab10, 0x546b1af2,
      0x8c41e90d, 0x0f5fcd88, 0x6f259f40, 0x34b33966, 0x5f3558d7, 0xfff36f0b,
      0xa3459449, 0xdcecbce1, 0x69ff2bf7, 0x7525e1da, 0x24c9de72, 0xea9626b1,
      0x87c7385d, 0x15e4211e, 0x9f7ef269, 0xfed018d1, 0x7632076c, 0x8d4f0157,
      0x10c1205a, 0x65db0e00, 0x813f0e8b, 0xbafea255, 0xb47e6663, 0x2a0eba78,
      0xf66b3783, 0xfff1db48, 0x47997f03, 0x3a49e877, 0x4536a0b5, 0x89b0738f,
      0xf5758b5e, 0x1d277388, 0xf5db28e8, 0xb4ef0add, 0x776fed12, 0x045b614a,
      0xc95f47ae, 0x13a1d602, 0x217d6338, 0xc509d080, 0x006789de, 0xd891cccc,
      0xb02f9980, 0x67f00301, 0xafc87999, 0x043d8fbd, 0xb32d6061)
  )
}

USet.scala

trait USet[A] extends Iterable[A] {
  def size: Int
  def add(a: A): Boolean
  def remove(a: A): Option[A]
  def find(a: A): Option[A]
  def clear(): Unit
}