/** This file contains the design thoughts and details about how we use set theory and more formalized way to design a simple specification language to abstractly describe a sequential data structure. */ 1. Design goals: We should design a specification language that users (developers of data structures) can use to describe the specification of sequential data structures. The language should be as mathematical and precise as possible, while it provides enough expressiveness and usability for users. That's to say, users can learn the language easily and take advantage of it to describe as many data structures as possible, e.g, Lock, Queue, Dequeue, LinkedList, Stack, Vector, Hashtable, and UnorderedPool(maybe). 2. Common data structures: Data structures, to some degree, can be viewed as a collector with specific operation on it. Those operations are done according to the maintained state and pre-defined logic. Set in mathematics has similar characteristics, which contains a collection of elements. However, elements in a set are distint. Order_list, which is a list of elements that have a total order and can duplicate, can be used to complement set. For example, a queue is a container that has a FIFO order on the elements while a stack with a LIFO order. For hashtable, it is a set of pairs (tuples) that has restrictions on the pairs. 3. Potential constructs: a) Set The set here is conceptually similar to the set in Set Theory. We define our set as a collection of unique and unordered elements. Uniqueness here implicates that the set element should provide an internal equality check. The following is some basic manipulations on set: 1) Tuple Every element is an n-dimentional tuple, and each element of a tuple is a tuple. This is basically used to represent the mapping between elements such as a HashMap. Some examples: a or (a) // 1-dimentional tuple, actually any variable is a 1-dimentional tuple (key, value) // 2-dimentional tuple (a, (a, b)) // 2-dimentional tuple, while the second column is a tuple too 1-dimentional tuple is the most basic part, it should have a type, such as integer, boolean, or other templated types. The type of a set can be derived from the tuple too. For example, A, B and C are basic types or templated types, we can have Set<(A)>, Set<(A, B)> or Set<(A, (B, C))> as different types. Set<(A)> contains elements of type A, Set<(A, B)> contains tuples of (A, B) and Set<(A, (B, C))> contains tuples of (A, (B, C)). We can get an 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 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 It takes two sets and return the union of the two sets. Same for the intersection and complement. 3) Cartesian product new_set = prod(s1, s2); // returns the cartisian product of s1 & s2 The result of this operation is that a new set of tuples of s1 and s2. 4) Remove set.remove(elem); 5) Find subset = set.find((key, *)); // use wildcard to find possible subset b) Order_List This is a list of tuples that has an order. It should have the following operations: 1) push_back list.push_back(elem); 2) push_front list.push_front(elem); 3) remove_back elem = list.remove_back(); 4) remove_front 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); }