X-Git-Url: http://plrg.eecs.uci.edu/git/?p=cdsspec-compiler.git;a=blobdiff_plain;f=notes%2Fsequential_spec.txt;h=ef3bafff351ba008abe7ce8cccef3c7dc29ac1e1;hp=6cdf5b87f2faf3bf824eae3c388652f2d74e242f;hb=d1da7bb66eab25dfab97f46d9e2c34cdbf380a31;hpb=b0734b902e9ecdbecac89a0182b86dcf1ec5c9fe diff --git a/notes/sequential_spec.txt b/notes/sequential_spec.txt index 6cdf5b8..ef3baff 100644 --- a/notes/sequential_spec.txt +++ b/notes/sequential_spec.txt @@ -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 @@ -71,3 +71,67 @@ elem = list.remove_front(); 5) Find elem = list.find(elem); + 6) IndexOf + index = list.indexOf(elem); + index = list.indexOf(elem, 1); + 7) PushAtIndex + list.pushAtIndex(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); + }