Large commit; many features

4 files changed, 162 insertions, 0 deletions

diff --git a/pkg/query/data_structures.go b/pkg/query/data_structures.go
new file mode 100644
index 0000000..c48ecde
--- /dev/null
+++ b/pkg/query/data_structures.go
@@ -0,0 +1,81 @@
+package query
+
+import "errors"
+
+// not threadsafe implementation of stack
+type nodeStack struct {
+	buf []*Node
+}
+
+func (s nodeStack) Push(n *Node) {
+	s.buf = append(s.buf, n)
+}
+func (s nodeStack) Pop() *Node {
+	last_index := len(s.buf) - 1
+	n := s.buf[last_index]
+	s.buf = s.buf[:last_index]
+	return n
+}
+func (s nodeStack) Peek() *Node {
+	return s.buf[len(s.buf)-1]
+}
+func (s nodeStack) IsEmpty() bool {
+	return len(s.buf) == 0
+}
+
+type nodeQueue struct {
+	buf  []*Node
+	head int
+	tail int
+}
+
+func makeNodeQueue(initial *Node, cap int) nodeQueue {
+	if cap < 1 {
+		panic("Invalid nodeQueue Capacity")
+	}
+
+	q := nodeQueue{
+		buf:  make([]*Node, 0, cap),
+		head: 0,
+		tail: 1,
+	}
+	q.buf[0] = initial
+
+	return q
+}
+
+func (q nodeQueue) Enqueue(n *Node) error {
+
+	q.buf[q.tail] = n
+	new_tail := (q.tail + 1) % len(q.buf)
+	if new_tail == q.head {
+		return errors.New("Queue out of capacity")
+	}
+
+	q.tail = new_tail
+	return nil
+}
+func (q nodeQueue) Dequeue() (*Node, error) {
+	if q.head == q.tail {
+		return nil, errors.New("Empty Queue")
+	}
+
+	n := q.buf[q.head]
+	q.head = (q.head + 1) % len(q.buf)
+	return n, nil
+}
+func (q nodeQueue) PeekHead() (*Node, error) {
+	if q.head == q.tail {
+		return nil, errors.New("Empty queue")
+	}
+	return q.buf[q.head], nil
+}
+func (q nodeQueue) PeekTail() (*Node, error) {
+	if q.head == q.tail {
+		return nil, errors.New("Empty Queue")
+	}
+	return q.buf[q.tail-1], nil
+}
+func (q nodeQueue) IsEmpty() bool {
+	return q.head == q.tail
+}
diff --git a/pkg/query/lang.md b/pkg/query/lang.md
new file mode 100644
index 0000000..a399cb8
--- /dev/null
+++ b/pkg/query/lang.md
@@ -0,0 +1,12 @@
+# Query Language Spec
+
+```
+<expr_list> := <expr> | <expr> <expr_list>
+
+<expr> := <statment> <bin_op> <statment>
+<statment> := <statement_start> {strings} <statment_end>
+<statment_start := 
+<statment_end> :=
+
+<bin_op> := "and" | "or" | "not" | "similar"
+```
diff --git a/pkg/query/parser.go b/pkg/query/parser.go
new file mode 100644
index 0000000..355b18c
--- /dev/null
+++ b/pkg/query/parser.go
@@ -0,0 +1,19 @@
+package query
+
+type TokenType uint64
+
+const (
+    TOKEN_ERROR TokenType = iota
+    TOKEN_EOF
+	TOKEN_AND
+	TOKEN_OR
+	TOKEN_NOT
+	TOKEN_SIMILAR
+	TOKEN_STATEMENT
+	// TODO: consider adding regex token
+)
+
+type Token struct {
+	Type    TokenType
+	Content string
+}
diff --git a/pkg/query/query.go b/pkg/query/query.go
new file mode 100644
index 0000000..b712370
--- /dev/null
+++ b/pkg/query/query.go
@@ -0,0 +1,50 @@
+package query
+
+
+type Node struct {
+	Parent   *Node
+	Children []*Node
+	Token
+}
+
+type AST struct {
+	root Node
+	size uint64
+}
+
+// Walk an ast depth first
+func (T AST) dfWalk() func() (*Node, bool) {
+	stack := nodeStack{make([]*Node, 0, T.size)}
+	stack.Push(&T.root)
+
+	return func() (*Node, bool) {
+		n := stack.Pop()
+		for _, child := range n.Children {
+			stack.Push(child)
+		}
+
+		if stack.IsEmpty() {
+			return n, false
+		}
+		return n, true
+	}
+}
+
+// Walk an ast breadth first
+func (T AST) bfWalk() func() (*Node, bool) {
+	queue := nodeQueue{}
+	queue.buf = make([]*Node, 0, T.size)
+	queue.Enqueue(&T.root)
+
+	return func() (*Node, bool) {
+		n, err := queue.Dequeue()
+		if err != nil {
+			return nil, false
+		}
+
+		for _, child := range n.Children {
+			queue.Enqueue(child)
+		}
+		return n, true
+	}
+}