import "vec.hff";
import "all.hff";

// KTraits:
//        :hash(K) u32
//        :eq(T, T) bool
//        :dup(T) T
struct Set<T, Traits> {
   buf Vec<T>,
   set **const T,
   N int,
   count int,

   fn intern(self *Set, x T) *const T {
      if self.set == #null {
         self.set = xcalloc(self.N = 16, sizeof *T);
      }

      if self.count == self.N / 2 {
         free(self.set);
         self.set = xcalloc(self.N *= 2, sizeof *T);
         vec_each(p, i, self.buf,
            let i = Traits:hash(p) & (self.N - 1);
            for ;; {
               if self.set[i] == #null {
                  self.set[i] = &self.buf.dat[i];
                  break;
               }
               i = (i + 1) & (self.N - 1);
            }
         )
      }

      let i0 u32 = Traits:hash(x) & (self.N - 1);
      let i int = i0;
      do {
         if self.set[i] == #null {
            ++self.count;
            self.buf->push(Traits:dup(x));
            return self.set[i] = &self.buf.dat[self.buf.len - 1];
         } else if Traits:eq(*self.set[i], x) {
            return self.set[i];
         }
         i = (i + 1) & (self.N - 1);
      } while i != i0;
      assert(#f, "unreachable");
   }
   
   fn contains(self *Set, x T) bool {
      let i0 u32 = Traits:hash(x) & (self.N - 1);
      let i int = i0;
      do {
         if self.set[i] == #null {
            return #f;
         } else if Traits:eq(*self.set[i], x) {
            return #t;
         }
         i = (i + 1) & (self.N - 1);
      } while i != i0;
      assert(#f, "unreachable");
   }

   fn put(self *Set, x T) void {
      self->intern(x);
   }
}