import "vec.hff";

#{
Traits:hash(K) u32 
      :eq(T, T) bool
      :dup(T) T // useful to strdup strings before interning them
}
struct Set<T, Traits> {
   buf Vec<T>,
   set *int,
   N int,
   count int,

   fn _nexthash(h *u32) u32 {
      // return *h = (*h * 1664525) + 1013904223u; // double hashing
      return ++*h; // linear probing
   }

   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 h = Traits:hash(p);
            let j = h & (self.N - 1);
            for ;; {
               if self.set[j] == 0 {
                  self.set[j] = i + 1;
                  break;
               }
               j = _nexthash(&h) & (self.N - 1);
            }
         }
      }

      let h u32 = Traits:hash(x);
      let i = h & (self.N - 1);
      let n = 0;
      for ;; {
         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;
            }
         }
         ++n;
         i = _nexthash(&h) & (self.N - 1);
      }
   }
   
   fn contains(self *Set, x T) bool {
      if self.N == 0 { return #f; }
      let h u32 = Traits:hash(x);
      let i = h & (self.N - 1);
      for ;; {
         if self.set[i] == 0 {
            return #f;
         } else if Traits:eq(self.buf.dat[self.set[i] - 1], x) {
            return #t;
         }
         i = _nexthash(&h) & (self.N - 1);
      }
   }

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

   fn clear(self *Set) void {
      self.buf->clear();
      free(self.set);
      *self = {};
   }
}

defmacro set_each(v, Set, &body) [
   let $s = (Set);
   for let $i = 0; $i < $s.N; ++$i {
      let $idx = $s.set[$i];
      if $idx > 0 {
         let v = $s.buf.dat[$idx - 1];
         body;
      }
   }
]