2 This file contains the design thoughts and details about how we use set
3 theory and more formalized way to design a simple specification language to
4 abstractly describe a sequential data structure.
8 We should design a specification language that users (developers of data
9 structures) can use to describe the specification of sequential data
10 structures. The language should be as mathematical and precise as possible,
11 while it provides enough expressiveness and usability for users. That's to
12 say, users can learn the language easily and take advantage of it to describe
13 as many data structures as possible, e.g, Lock, Queue, Dequeue, LinkedList,
14 Stack, Vector, Hashtable, and UnorderedPool(maybe).
16 2. Common data structures:
17 Data structures, to some degree, can be viewed as a collector with specific
18 operation on it. Those operations are done according to the maintained state
19 and pre-defined logic. Set in mathematics has similar characteristics, which
20 contains a collection of elements. However, elements in a set are distint.
21 Order_list, which is a list of elements that have a total order and can
22 duplicate, can be used to complement set. For example, a queue is a container
23 that has a FIFO order on the elements while a stack with a LIFO order. For
24 hashtable, it is a set of pairs (tuples) that has restrictions on the pairs.
26 3. Potential constructs:
28 The set here is conceptually similar to the set in Set Theory. We define our
29 set as a collection of unique and unordered elements. Uniqueness here
30 implicates that the set element should provide an internal equality check.
31 The following is some basic manipulations on set:
33 Every element is an n-dimentional tuple, and each element of a tuple is a
34 tuple. This is basically used to represent the mapping between elements such
35 as a HashMap. Some examples:
36 a or (a) // 1-dimentional tuple, actually any variable is a 1-dimentional tuple
37 (key, value) // 2-dimentional tuple
38 (a, (a, b)) // 2-dimentional tuple, while the second column is a tuple too
39 1-dimentional tuple is the most basic part, it should have a type, such as
40 integer, boolean, or other templated types. The type of a set can be derived
41 from the tuple too. For example, A, B and C are basic types or templated
42 types, we can have Set<(A)>, Set<(A, B)> or Set<(A, (B, C))> as different
43 types. Set<(A)> contains elements of type A, Set<(A, B)> contains tuples of
44 (A, B) and Set<(A, (B, C))> contains tuples of (A, (B, C)). We can get an
45 instance of tuple in a way like (key, value).
46 The tuple has its basic operation dimention(n), which returns the tuple of
48 2) Union, intersection, and remove.
49 new_set = union(s1, s2); // returns a new set
51 s1.union(s2); // s1 becomes the union of s1 and s2, and it returns the new s1
52 It takes two sets and return the union of the two sets. Same for the
53 intersection and complement.
55 new_set = prod(s1, s2); // returns the cartisian product of s1 & s2
56 The result of this operation is that a new set of tuples of s1 and s2.
60 subset = set.find((key, *)); // use wildcard to find possible subset
62 This is a list of tuples that has an order. It should have the following
67 list.push_front(elem);
69 elem = list.remove_back();
71 elem = list.remove_front();
73 elem = list.find(elem);
75 index = list.indexOf(elem);
76 index = list.indexOf(elem, 1);
80 list.pushAfterElem(target, elem, 10); // find the first matched target from index 10,
81 // insert elem after target
88 Set<(Key, Value)> table;
90 void Put((Key) key, (Value) value) {
91 table.remove(table.find((key, *))).union((key,value));
94 (Value) Get((Key) key) {
95 return table.find((key, *));
100 Order_List<(Type)> stack;
102 void Push((Type) elem) {
103 stack.push_back(elem);
107 return stack.remove_back();
111 // Suppose we store the pointer and they are unique??
113 Order_List<(Type)> list;
115 void add((Type) target, (Type) elem) {
116 assert(list.find(elem).size() == 1);
117 list.insertAfterElem(target, elem);
120 void remove((Type) target) {
125 // A possible data structure, basically returns an element only once
127 Order_List<(Type)> pool;
129 void insert((Type) elem) {
130 pool.push_back(elem);
133 // Check if elem is possible to be removed; if yes, remove it & return true,
134 // otherwise return false.
135 bool remove((Type) elem) {
136 return pool.removeIfExists(elem);