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 *int,
   N int,
   count int,

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

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

      let i0 u32 = Traits:hash(x) & (self.N - 1);
      let i int = i0;
      do {
         if self.set[i] == 0 {
            ++self.count;
            self.buf->push(Traits:dup(x));
            self.set[i] = self.buf.len;
            return self.buf->lastp();
         } else {
            let x2 = &self.buf.dat[self.set[i] - 1];
            if Traits:eq(*x2, x) {
               return x2;
            }
         }
         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] == 0 {
            return #f;
         } else if Traits:eq(self.buf.dat[self.set[i] - 1], 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);
   }
}