代码之家 › 专栏 › 技术社区 › Sixthpoint

从树构建JPA规范

jpa-criteria spring-data-jpa algorithm java

13

Sixthpoint · 技术社区 · 6 年前

我创建了一个API,允许用户使用树构建查询。这棵树是用 SearchOperationRequest 班级。

@Data
@ApiModel(value = "SearchOperationRequest", description = "Condition for the query")
public class SearchOperationRequest {

    @ApiModelProperty(value = "Conditional statement for the where clause", allowableValues = "EQUALS, NOT_EQUALS, GREATER_THAN, LESS_THAN, LIKE, STARTS_WITH, ENDS_WITH, CONTAINS")
    private SearchConditionOperation condition;

    @ApiModelProperty(value = "Column name to be searched on")
    private String column;

    @ApiModelProperty(value = "Value of column")
    private Object value;

    @ApiModelProperty(value = "Value of OR / AND")
    private SearchComparator comparator;

    @ApiModelProperty(value = "Left node of comparator condition")
    private SearchOperationRequest left;

    @ApiModelProperty(value = "Right node of comparator condition")
    private SearchOperationRequest right;

    public boolean isTreeLeaf() {
        return left == null && right == null;
    }

    public boolean isComparator() {
        return comparator != null;
    }
}

因此,通过这个例子,我可以创建一个 搜索操作请求 要求所有的 其中hidden=false,x=88

"searchOperation": {
    "left": {
        "column": "Hidden",
        "condition": "EQUALS",
        "value": false
    },
    "comparator": "AND",
    "right": {
        "left": {
            "column": "X",
            "condition": "EQUALS",
            "value": 88
        },
        "comparator": "AND"
    }
}

此请求使用通用规范生成器构建到规范中。

public class GenericSpecificationsBuilder<U> {

    public Specification<U> buildSpecificationFromSearchOperationRequest(SearchOperationRequest root, Function<SpecificationSearchCriteria, Specification<U>> converter) {

        Stack<SearchOperationRequest> stack = new Stack<>();

        Stack<SearchOperationRequest> comparatorStack = new Stack<>();
        Deque<Specification<U>> specStack = new LinkedList<>();

        SearchOperationRequest pointer = root;

        while (pointer != null || !stack.empty()) {

            if (pointer.isTreeLeaf()) {
                specStack.push(converter.apply(new SpecificationSearchCriteria(pointer.getColumn(), pointer.getCondition(), pointer.getValue())));
            }

            if (pointer.isComparator()) {
                comparatorStack.push(pointer);
            }

            if (pointer.getRight() != null) {
                stack.push(pointer.getRight());
            }

            if (pointer.getLeft() != null) {
                pointer.setRight(pointer.getLeft());
                pointer.setLeft(null);
            } else if (!stack.empty()) {
                SearchOperationRequest temp = stack.pop();
                pointer.setRight(temp);
            }

            pointer = pointer.getRight();
        }


        while (specStack.size() <= comparatorStack.size()) {
            comparatorStack.pop();
        }

        while (!comparatorStack.empty()) {

            SearchOperationRequest searchOperationRequest = comparatorStack.pop();

            Specification<U> operand1 = specStack.pop();
            Specification<U> operand2 = specStack.pop();
            if (searchOperationRequest.getComparator().equals(SearchComparator.AND)) {
                specStack.push(Specification.where(operand1)
                        .and(operand2));
            } else if (searchOperationRequest.getComparator().equals(SearchComparator.OR)) {
                specStack.push(Specification.where(operand1)
                        .or(operand2));
            }
        }


        return specStack.pop();
    }
}

我的电流对右重树很有用。表示如下查询:

WHERE X = 6 AND X = 9
WHERE Z = 5 OR T=9
WHERE Z = 5 OR T=9 OR H=6

但它不适用于构建更复杂的树,因为大括号中的条件应该优先并首先执行。

WHERE (X = 6 OR Z = 9) AND (T=6 OR H=8)

这个更复杂的模型 搜索操作请求 将是:

"searchOperation": {
    "left": {
        "left": {
            "column": "X",
            "condition": "EQUALS",
            "value": 6
        },
        "comparator": "AND",
        "right": {
            "column": "Z",
            "condition": "EQUALS",
            "value": 9
        }
    },
    "comparator": "AND",
    "right": {
        "left": {
            "column": "T",
            "condition": "EQUALS",
            "value": 6
        },
        "comparator": "AND",
        "right": {
            "column": "H",
            "condition": "EQUALS",
            "value": 8
        }
    }
}

如何修改我的 GenericSpecificationsBuilder 能够处理更复杂的 搜索操作请求 树?

1 回复 | 直到 6 年前

1

6

ingen 6 年前

让我们使用示例树来遵循执行流程。

和
/ \
左或右或
/\/\
X=6 Z=9 T=6 H=8
< /代码> 

当我们退出第一个whileloop时,我们的堆栈如下:


stack=
ComparatorStack=和,Leftor,Rightor
specstack=x=6,z=9,t=6,h=8_
< /代码> 

相同的状态进入最终状态whileloop.


while(!ComparatorStack.Empty()){

searchOperationRequest searchOperationRequest=comparatorstack.pop();

规格<u>operand1=specstack.pop();
规格<U>operand2=specstack.pop();
if(searchOperationRequest.getComparator().equals(searchComparator.and))。{
specstack.push(规范.where(operand1)
.和(操作2));
}否则,如果(searchOperationRequest.getComparator().equals(searchComparator.or))。{
specstack.push(规范.where(operand1)
或(操作数2);
}
}
< /代码> 

这里的问题是您将结果推回到specstack。因此,在第二次迭代时,您将弹出第一次迭代的结果(therightor),以及z=9,并将leftorlogic应用到它。


分解树


让我们后退一步,看看你是如何分解树的,更具体地说:

if(pointer.getLeft()!{NULL){
pointer.setright(pointer.getleft());
pointer.setleft(空);
否则,(如果)!stack.empty()){
searchOperationRequest temp=stack.pop();
指针。设置正确(温度);
}
< /代码> 

此代码的问题在于您正在更改树中的节点。在第一个示例中,我们的指针一次指向节点:

z=9
/ \
零右位
< /代码> 

看起来不太对劲。不要使用堆栈(depth first search)来分解树,您可以使用队列(width first search)并获取您在进行免费订购后的订单。




这是否解决了将每个逻辑运算符(comparator)应用于正确操作数的问题?不完全如此,为了能够解决下面的两种布局,我们可以在不同的工作流中分解运算符和操作数,而不是将它们全部分解在一起。


and rootand
/\|/\
左或右或左或右或
/\/\|/\/\
X=6 Z=9 T=6 H=8_X=6 Z=9 H=8
|/\
| t=6 y=3
< /代码> 

解决方案


本文中第一个类似JSON的表示有一个不合逻辑的布局,因为逻辑运算符需要同时操作左操作数和右操作数。相反,你有:

“right”:。{
“左”:{
“列”:“X”,
“condition”:“等于”,
“价值”:88
}
“comparator”:“和”
}
< /代码> 

让我们考虑对称表示的解决方案,其中每个逻辑运算符都有左操作数和右操作数。


首先,我们对树进行逐级处理。同时,我们将每个comparator放在一个堆栈上,这样我们在第二个whileloop中首先得到最后一个。


在第二个循环中,当我们返回到根目录时,我们使用一个新的队列来存储我们的“in between results”。


queue<searchOperationRequest>queue=new linkedList<gt;();
deque<searchOperationRequest>comparatorStack=新建链接列表<>();

如果(根==空!root.iscomparator())返回;
queue.add(根);
而(!)queue.isEmpty()){
searchOperationRequest节点=queue.poll();
comparatorstack.push(节点);
如果(没有)离开!=空&&node.left.iscomparator())queue.add(node.left);
如果(没错)!=空&node.right.iscomparator())queue.add(node.right);
}

queue<规范>specqueue=new linkedList<>();
而(!)comparatorstack.isEmpty()){
searchOperationRequest comparator=comparatorstack.pop();
//颠倒操作数顺序,以便正确轮询已计算的值
规范操作2;
searchOperationRequest指针=comparator.getRight();
if(pointer.istreeeaf()){
operand2=converter.apply(new specificationsearchcriteria(pointer.getColumn(),pointer.getCondition(),pointer.getValue());
}否则{
operand2=specqueue.poll();
}
规范操作1;
指针=comparator.getLeft();
if(pointer.istreeeaf()){
operand1=converter.apply(new specificationsearchcriteria(pointer.getColumn(),pointer.getCondition(),pointer.getValue());
}否则{
operand1=specqueue.poll();
}
if(comparator.equals(searchcomparator.and))。{
specqueue.add(specification.where(operand1).and(operand2));
}否则,如果(comparator.equals(searchcomparator.or))。{




while

stack = {}
comparatorStack = { AND, leftOR, rightOR }
specStack = { X=6, Z=9, T=6, H=8 }




while (!comparatorStack.empty()) {

    SearchOperationRequest searchOperationRequest = comparatorStack.pop();

    Specification<U> operand1 = specStack.pop();
    Specification<U> operand2 = specStack.pop();
    if (searchOperationRequest.getComparator().equals(SearchComparator.AND)) {
        specStack.push(Specification.where(operand1)
                .and(operand2));
    } else if (searchOperationRequest.getComparator().equals(SearchComparator.OR)) {
        specStack.push(Specification.where(operand1)
                .or(operand2));
    }
}


specStackrightORZ=9leftOr





if (pointer.getLeft() != null) {
    pointer.setRight(pointer.getLeft());
    pointer.setLeft(null);
} else if (!stack.empty()) {
    SearchOperationRequest temp = stack.pop();
    pointer.setRight(temp);
}




    Z=9      
  /     \ 
null   rightOR


Depth First SearchBreadth First Search



comparator

         AND                    |                    rootAND                 
      /       \                 |                  /         \    
  leftOR     rightOR            |              leftOR       rightOR  
  /    \     /    \             |              /    \       /    \   
X=6   Z=9  T=6   H=8            |            X=6    AND    Z=9   H=8   
                                |                 /    \      
                                |               T=6   Y=3 






"right": {
    "left": {
        "column": "X",
        "condition": "EQUALS",
        "value": 88
    },
    "comparator": "AND"
}






Queue

Queue<SearchOperationRequest> queue = new LinkedList<>();
Deque<SearchOperationRequest> comparatorStack = new LinkedList<>();

if (root == null || !root.isComparator()) return;
queue.add(root);
while(!queue.isEmpty()){
    SearchOperationRequest node = queue.poll();
    comparatorStack.push(node);
    if(node.left != null && node.left.isComparator()) queue.add(node.left);
    if(node.right != null && node.right.isComparator()) queue.add(node.right);
}

Queue<Specification> specQueue = new LinkedList<>();
while(!comparatorStack.isEmpty()){
    SearchOperationRequest comparator = comparatorStack.pop();
    // reverse operand order so already computed values are polled correctly
    Specification operand2; 
    SearchOperationRequest pointer = comparator.getRight();
    if(pointer.isTreeLeaf()) {
        operand2 = converter.apply(new SpecificationSearchCriteria(pointer.getColumn(), pointer.getCondition(), pointer.getValue()));
    } else {
        operand2 = specQueue.poll();
    }
    Specification operand1; 
    pointer = comparator.getLeft();
    if(pointer.isTreeLeaf()) {
        operand1 = converter.apply(new SpecificationSearchCriteria(pointer.getColumn(), pointer.getCondition(), pointer.getValue()));
    } else {
        operand1 = specQueue.poll();
    }
    if (comparator.equals(SearchComparator.AND)) {
        specQueue.add(Specification.where(operand1).and(operand2));
    } else if (comparator.equals(SearchComparator.OR)) {
        specQueue.add(Specification.where(operand1).or(operand2));
    }
} 

return specQueue.poll();