Commits

Anonymous committed e0627b5

+ set type, + set_list

Comments (0)

Files changed (1)

 (*
 todo:
 
+  #ti{key,val} -> #ti_{key,val}
+
+
   trie:
             - merge с параметром-функцией мержа узлов.
             - fold со свёрткой поддеревьев и, затем, узлов с ними.
+
+  {Sfun.set_{list,tree},Simp.set_{list,tree,hash}}
+
 *)
 
 
 
 (* non-specific types *)
 
+    class type set_ro ['k] =
+      object
+        method mem : 'k -> bool;
+      end
+    ;
+
     (* [map 'k 'v] is a collection of bindings of key of type 'k
        to values of type 'v.  Note that the bindings added with
        [add] method will shadow previous bindings of this key.
       object
         method get_exn : 'k -> 'v;
         method get_opt : 'k -> option 'v;
-        method mem : 'k -> bool;
+        inherit set_ro ['k];
       end
     ;
 
  =
   struct
 
+    class type set_rw ['k] =
+      object
+        inherit set_ro ['k];
+
+        method tikey : ti 'k;
+
+        method empty : set_rw 'k;
+        method is_empty : bool;
+
+        method add : 'k -> set_rw 'k;
+        method remove : 'k -> set_rw 'k;
+
+        (* todo:
+        method merge : set_rw 'k -> set_rw 'k;  ?? продумать семантику,
+          должно быть просто "union" или же (option 'k1 -> option 'k2 -> opt..)
+        *)
+
+      end
+    ;
+
     (* [map_rws] = map readable/writeable with single binding
        (no shadowing, no [add] method, only [replace])
      *)
  =
   struct
 
+    class set_list ['k] ti_key cur =
+      object (self : #Tfun.set_rw 'k)
+
+        method tikey = (ti_key :> ti 'k);
+
+        method mem k = 
+          let eqk = ti_key#eq k in
+          List.exists eqk cur;
+
+        method empty = new set_list ti_key [];
+        method is_empty = (cur = []);
+
+        method add k =
+          if self#mem k
+          then (self :> set_list _)
+          else new set_list ti_key [k :: cur]
+        ;
+
+        method remove k =
+          if self#mem k
+          then
+            new set_list ti_key
+              (let eqk = ti_key#eq k in
+               let neqk x = not (eqk x) in
+               List.filter neqk cur
+              )
+          else (self :> set_list _)
+        ;
+
+      end
+    ;
+
     (* deepest bindings are [add]ed first, top bindings last,
        so you can [add] to or [replace] into any [map_rw*]
        to get desired result. *)