more notes
authorPeizhao Ou <peizhaoo@uci.edu>
Fri, 8 Nov 2013 06:53:55 +0000 (22:53 -0800)
committerPeizhao Ou <peizhaoo@uci.edu>
Fri, 8 Nov 2013 06:53:55 +0000 (22:53 -0800)
notes/sequential_spec.txt

index 6cdf5b8..73e85cc 100644 (file)
@@ -45,7 +45,7 @@
    instance of tuple in a way like (key, value).
       The tuple has its basic operation dimention(n), which returns the tuple of
          its nth column.
-   2) Union, intersection, and complement.
+   2) Union, intersection, and remove.
    new_set = union(s1, s2); // returns a new set
    or
    s1.union(s2); // s1 becomes the union of s1 and s2, and it returns the new s1
    elem = list.remove_front();
    5) Find
    elem = list.find(elem);
+   6) IndexOf
+   index = list.indexOf(elem);
+   index = list.indexOf(elem, 1);
+   7) PushAtIndex
+   list.pushAtIdex(1);
+   8) PushAfterElem
+   list.pushAfterElem(target, elem, 10); // find the first matched target from index 10,
+                                         // insert elem after target
+   9) RemoveIfExists
+   RemoveIfExists(elem)
+
+4. Examples:
+   1) Hashtable
+   @Declare:
+     Set<(Key, Value)> table;
+   @Manipulation:
+     void Put((Key) key, (Value) value) {
+       table.remove(table.find((key, *))).union((key,value));
+        }
+     
+        (Value) Get((Key) key) {
+       return table.find((key, *));
+        }
+
+   2) Stack
+   @Declare:
+     Order_List<(Type)> stack;
+   @Manipulation:
+     void Push((Type) elem) {
+       stack.push_back(elem);
+        }
+
+        (Type) Pop() {
+       return stack.remove_back();
+        }
+
+   3) LinkedList
+   // Suppose we store the pointer and they are unique??
+   @Declare:
+     Order_List<(Type)> list;
+   @Manipulation:
+     void add((Type) target, (Type) elem) {
+       assert(list.find(elem).size() == 1);
+          list.insertAfterElem(target, elem);
+        }
+
+        void remove((Type) target) {
+       list.remove(target);
+        }
+
+   4) UnorderPool
+   // A possible data structure, basically returns an element only once
+   @Declare:
+     Order_List<(Type)> pool;
+   @Manipulation:
+     void insert((Type) elem) {
+       pool.push_back(elem);
+        }
+
+     // Check if elem is possible to be removed; if yes, remove it & return true,
+        // otherwise return false.
+        bool remove((Type) elem) {
+       return pool.removeIfExists(elem);
+        }