Spring与枚举参数

1. 前言

使用枚举作为参数类型是非常常见的一种手段,但是枚举传参随着使用方式的不同,也存在的些微的差异。

简单来说分为枚举在作为请求的参数依据传递方式不同可以分为两种情况:

  • GET 请求、POST 表单传递
  • Json 数据格式

两者在做数据类型转换的时候是大不一样的。

2. 实例

首先定义一个枚举类:

  package com.avaloninc.domain;
  
  import com.fasterxml.jackson.annotation.JsonValue;
  
  public enum StatusEnum {
    /**
     * Valid status enum.
     */
    VALID(1, "有效"),
    /**
     * Invalid status enum.
     */
    INVALID(2, "无效");
  
    private final int    code;
    private final String value;
  
    StatusEnum(int code, String value) {
      this.code = code;
      this.value = value;
    }
  }
  

然后我们给出如下简单的 Controller:

  package com.avaloninc;
  
  import com.avaloninc.domain.StatusEnum;
  import lombok.Data;
  import org.springframework.boot.SpringApplication;
  import org.springframework.boot.autoconfigure.SpringBootApplication;
  import org.springframework.web.bind.annotation.GetMapping;
  import org.springframework.web.bind.annotation.PostMapping;
  import org.springframework.web.bind.annotation.RequestBody;
  import org.springframework.web.bind.annotation.RequestMapping;
  import org.springframework.web.bind.annotation.RestController;
  
  @SpringBootApplication
  @RestController
  @RequestMapping("api")
  public class Application {
    public static void main(String[] args) {
      SpringApplication.run(Application.class);
    }
  
    @Data
    public static class ListRequest {
      private StatusEnum status;
    }
  
    @Data
    public static class JsonRequest {
      private StatusEnum status;
    }
  
    @GetMapping
    public StatusEnum list(ListRequest listRequest) {
      return listRequest.getStatus();
    }
  
    @PostMapping
    public StatusEnum post(JsonRequest jsonRequest) {
      return jsonRequest.getStatus();
    }
  
    @PostMapping("json")
    public StatusEnum postJson(@RequestBody JsonRequest jsonRequest) {
      return jsonRequest.getStatus();
    }
  }

然后我们发起一个测试:

  # 1. GET
  curl -X GET 'http://localhost:8080/api?status=VALID'
  
  "VALID"
  
  # 2. POST Form
  curl -X POST  http://localhost:8080/api -F status=VALID
  
  "VALID"
  
  # 3. POST json
  curl -X POST http://localhost:8080/api/json 
    -d '{ "status": "VALID"}'
    
  "VALID"

一切正常!

3. 新的需求

现在添加一个需求:我们希望返回的不只是枚举的字面值,而是真正的中文含义比如有效、无效。

需求实现也很简单,给 StatusEnum 增加一个带有 @JsonValue 注解的方法即可。该注解指定了 Jackson 在序列化对象时使用的方法。

    @JsonValue
    public String toValue() {
      return this.value;
    }

测试结果:

  # 1. GET
  curl -X GET 'http://localhost:8080/api?status=VALID'
  
  "有效"
  
  # 2. POST Form
  curl -X POST  http://localhost:8080/api -F status=VALID
  
  "有效"
  
  # 3. POST json
  curl -X POST http://localhost:8080/api/json 
    -d '{ "status": "VALID"}'
    
  {
      "timestamp": 1520709795581,
      "status": 400,
      "error": "Bad Request",
      "exception": "org.springframework.http.converter.HttpMessageNotReadableException",
      "message": "JSON parse error: Can not deserialize value of type com.avaloninc.domain.StatusEnum from String \"VALID\": value not one of declared Enum instance names: [无效, 有效]; nested exception is com.fasterxml.jackson.databind.exc.InvalidFormatException: Can not deserialize value of type com.avaloninc.domain.StatusEnum from String \"VALID\": value not one of declared Enum instance names: [无效, 有效]\n at [Source: java.io.PushbackInputStream@5ba1fa04; line: 2, column: 12] (through reference chain: com.avaloninc.Application$JsonRequest[\"status\"])",
      "path": "/api/json"
  }

原来以 Json 作为参数的请求出了错误。String \"VALID\": value not one of declared Enum instance names: [无效, 有效] 告诉我们 Json 反序列化为 StatusEnum 时只能用 [无效, 有效] 作为值。奇怪的是没有指定 @JsonCreator@JsonCreator 注解可以指定对象反序列化的方法)为什么没有采用默认的行为,即用枚举字面值反序列化,而采用我们序列化使用的字段呢?查看了 @JsonValue 注解的 javadoc 后有所发现:

  • NOTE: when use for Java <code>enum</code>s, one additional feature is
  • that value returned by annotated method is also considered to be the
  • value to deserialize from, not just JSON String to serialize as.
  • This is possible since set of Enum values is constant and it is possible
  • to define mapping, but can not be done in general for POJO types; as such,
  • this is not used for POJO deserialization.*
  • @see JsonCreator

坑爹啊!对于 @JsonValue 来说枚举是一种特殊的场景,定义了序列化后的值反过来也就被用来反序列化。

解决方法也不难,手动指定一个 @JsonCreator 即可:

    @JsonCreator
    public static StatusEnum fromValue(String str) {
      for (StatusEnum statusEnum : StatusEnum.values()) {
        if (statusEnum.name().equals(str)) {
          return statusEnum;
        }
      }
      throw new IllegalArgumentException("Illegal enum " + str);
    }

于是乎问题也解决了!

4. 进一步思考

进一步思考一下,为什么增加了 @JsonValue 注解后 GET 请求和 POST Form 请求没有变化呢?

答案是参数的绑定机制不同。

通过打断点我们可以发现:GET 请求和 POST Form 请求中的字符串到枚举的转化是通过 org.springframework.core.convert.support.StringToEnumConverterFactory 来实现的,其代码如下:

  /*
   * Copyright 2002-2017 the original author or authors.
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package org.springframework.core.convert.support;
  
  import org.springframework.core.convert.converter.Converter;
  import org.springframework.core.convert.converter.ConverterFactory;
  
  /**
   * Converts from a String to a {@link java.lang.Enum} by calling {@link Enum#valueOf(Class, String)}.
   *
   * @author Keith Donald
   * @author Stephane Nicoll
   * @since 3.0
   */
  @SuppressWarnings({"unchecked", "rawtypes"})
  final class StringToEnumConverterFactory implements ConverterFactory<String, Enum> {
  
      @Override
      public <T extends Enum> Converter<String, T> getConverter(Class<T> targetType) {
          return new StringToEnum(ConversionUtils.getEnumType(targetType));
      }
  
  
      private class StringToEnum<T extends Enum> implements Converter<String, T> {
  
          private final Class<T> enumType;
  
          public StringToEnum(Class<T> enumType) {
              this.enumType = enumType;
          }
  
          @Override
          public T convert(String source) {
              if (source.isEmpty()) {
                  // It's an empty enum identifier: reset the enum value to null.
                  return null;
              }
              return (T) Enum.valueOf(this.enumType, source.trim());
          }
      }
  }

可以发现的是该类实现了接口 ConverterFactory ,通过调用 Enum.valueOf(Class, String) 实现了这个功能。

向下追溯源码可以发现该方法实际上是从一个 Map<String, Enum> 的字典中获取了转换后的实际值,着这个 String 类型的 Key 的获取方式就是 Enum.name() 返回的结果,即枚举的字面值。源码如下:

      /**
       * Returns a map from simple name to enum constant.  This package-private
       * method is used internally by Enum to implement
       * {@code public static <T extends Enum<T>> T valueOf(Class<T>, String)}
       * efficiently.  Note that the map is returned by this method is
       * created lazily on first use.  Typically it won't ever get created.
       */
      Map<String, T> enumConstantDirectory() {
          if (enumConstantDirectory == null) {
              T[] universe = getEnumConstantsShared();
              if (universe == null)
                  throw new IllegalArgumentException(
                      getName() + " is not an enum type");
              Map<String, T> m = new HashMap<>(2 * universe.length);
              for (T constant : universe)
                  m.put(((Enum<?>)constant).name(), constant);
              enumConstantDirectory = m;
          }
          return enumConstantDirectory;
      }
      private volatile transient Map<String, T> enumConstantDirectory = null;

5. 参考文章

Insert Or Update 后续

1. 问题描述

使用 insert … on duplicate key update 语法实现 insertOrUpdate 之后出现了几个新问题,首先给出测试代码:

DROP database if EXISTS test;
CREATE database test;

DROP TABLE if EXISTS test.person;
CREATE table test.person (
    id int not NULL PRIMARY KEY auto_increment,
    name VARCHAR(100) not NULL DEFAULT '' UNIQUE COMMENT '名字',
    age int not NULL DEFAULT 0 COMMENT '年龄',
    gender VARCHAR(20) NOT NULL DEFAULT '' COMMENT '性别',
    addresses text NOT NULL COMMENT '地址'
)ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_bin COMMENT='person';

MyBatis 语句:

<insert id="insertOrUpdate" useGeneratedKeys="true" keyProperty="id">
    insert into test.person
    (id, name, age, gender, addresses)
    VALUES
    <foreach collection="list" item="person" separator=",">
        (id, #{person.name}, #{person.age}, #{person.gender},
        #{person.addresses, typeHandler=com.note4code.test.persistence.typeHandler.GenericMapHandler})
    </foreach>
    on duplicate key update
    age = VALUES(age),
    gender = VALUES(gender),
    addresses = VALUES(addresses)
</insert>

Java 代码:

package com.note4code.test.service;

import com.note4code.test.domain.Address;
import com.note4code.test.domain.Gender;
import com.note4code.test.domain.Person;
import com.note4code.test.domain.Province;
import junit.framework.TestCase;
import org.assertj.core.util.Lists;
import org.assertj.core.util.Maps;
import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.test.context.junit4.SpringRunner;

import java.io.IOException;
import java.util.List;
import java.util.Map;

@RunWith(SpringRunner.class)
@SpringBootTest
public class PersonServiceTest extends TestCase{

  @Autowired
  private PersonService personService;

  private Person me;
  private Person you;
  private Person him;

  @Before
  public void initData() {
    Address address = new Address(Province.BEIJING, "北京", "学院路");
    Map<Province, Address> map = Maps.newHashMap(Province.BEIJING, address);

    this.me = new Person();
    this.me.setName("me");
    this.me.setAge(27);
    this.me.setGender(Gender.MALE);
    this.me.setAddresses(map);

    this.you = new Person();
    this.you.setName("you");
    this.you.setAge(25);
    this.you.setGender(Gender.FEMALE);
    this.you.setAddresses(map);

    this.him = new Person();
    this.him.setName("him");
    this.him.setAge(25);
    this.him.setGender(Gender.MALE);
    this.him.setAddresses(map);
  }

  @Test
  public void testForOnDuplicateKey() {
    personService.addPerson(me);
    int id = me.getId();

    me.setAge(28);
    List<Person> people = Lists.newArrayList(me, you, him);
    personService.addOrUpdate(people);
    assertTrue(id != me.getId());
  }
}

运行测试用例,得到的输出结果是:

people = [Person{id=2, name=’me’, age=28, gender=MALE, addresses={BEIJING=Address{province=BEIJING, city=’北京’, street=’学院路’}}}
, Person{id=0, name=’you’, age=25, gender=FEMALE, addresses={BEIJING=Address{province=BEIJING, city=’北京’, street=’学院路’}}}
, Person{id=0, name=’him’, age=25, gender=MALE, addresses={BEIJING=Address{province=BEIJING, city=’北京’, street=’学院路’}}}
]

另外,查询数据库可以得到:

mysql root@localhost:test> SELECT * from person;
+------+--------+-------+----------+--------------------------------------------------------------------+
|   id | name   |   age | gender   | addresses                                                          |
|------+--------+-------+----------+--------------------------------------------------------------------|
|    1 | me     |    28 | MALE     | {"BEIJING":{"province":"BEIJING","city":"北京","street":"学院路"}} |
|    2 | you    |    25 | FEMALE   | {"BEIJING":{"province":"BEIJING","city":"北京","street":"学院路"}} |
|    3 | him    |    25 | MALE     | {"BEIJING":{"province":"BEIJING","city":"北京","street":"学院路"}} |
+------+--------+-------+----------+--------------------------------------------------------------------+
3 rows in set
Time: 0.002s
mysql root@localhost:test> SELECT LAST_INSERT_ID();
+--------------------+
|   LAST_INSERT_ID() |
|--------------------|
|                 17 |
+--------------------+
1 row in set
Time: 0.001s

从上面的示例可以看出 3 个问题:

  1. 即使使用了 userGeneratedKeys = true 并指定了 keyProperty,只回写了第一行的主键。
  2. 回写的主键与数据库不一致。
  3. LAST_INSERT_ID() 的值发生了跳跃,按理来说应该是 3,但是变成了 17。

2. 疑问

看到这里其实很让人费解:

  1. 为什么只返回了一个主键?
  2. useGeneratedKeys 返回的主键不对那么到底是什么?
  3. 为什么 LAST_INSERT_ID() 发生了跳变?

首先从 userGeneratedKeys 说起:

useGeneratedKeys(仅对 insert 和 update 有用)这会令 MyBatis 使用 JDBC 的 getGeneratedKeys 方法来取出由数据库内部生成的主键(比如:像 MySQL 和 SQL Server 这样的关系数据库管理系统的自动递增字段),默认值:false。

引自 insert, update 和 delete

With older JDBC drivers for MySQL, you could always use a MySQL-specific method on theStatement interface, or issue the query SELECT LAST_INSERT_ID() after issuing an INSERT to a table that had an AUTO_INCREMENT key.

First, we demonstrate the use of the new JDBC 3.0 method getGeneratedKeys() which is now the preferred method to use if you need to retrieve AUTO_INCREMENT keys and have access to JDBC 3.0. The second example shows how you can retrieve the same value using a standard SELECT LAST_INSERT_ID() query. 

引自 Retrieving AUTO_INCREMENT Column Values through JDBC

也就是说 Mybatis 通过 useGeneratedKeys 返回的是 LAST_INSERT_ID()

接着说,那么为什么只回写了一个主键,并且还是错的呢?

If you insert multiple rows using a single INSERT statement, LAST_INSERT_ID() returns the value generated for the first inserted row only.

引自 LAST_INSERT_ID()LAST_INSERT_ID(expr)

按照上文的说法,批量插入只会返回插入的第一条数据的主键。第一次插入 me 这个对象之后 LAST_INSERT_ID() 返回 1。接着在插入 people 时首先是更新了 me 这行记录,而 LAST_INSERT_ID() 没有变。直到插入第二行 you 这个对象,此时 LAST_INSERT_ID() 返回 2,也就是批量插入后回写的主键值。这同时解释了为什么只回写了一个主键并且回写的主键与数据库没有对应上。

最后,关于 LAST_INSERT_ID() 的跳变,我也找到了一些参考资料:

  1. 官方文档:InnoDB AUTO_INCREMENT Lock Modes
  2. 其实这个说的更加简洁清楚:AUTO_INCREMENT 字段的GAP

Insert Or Update

1. MySQL 批量插入

有的时候会有这样的需求:

  1. 批量写入数据,但是数据可能存在主键或者唯一性索引的冲突写到一半就失败了。
  2. 每天批量更新表,新数据插入,旧数据更新。

于是我们不禁想到是否能实现一个 insertOrUpdate 方法呢?事实上,MySQL 给出了标准 SQL 的两种扩展来帮我们实现这种需求。

2. INSERT ... ON DUPLICATE KEY UPDATE

标准 SQL 的扩展,如果插入时遇到主键冲突或者唯一性约束不满足则会执行 update 操作,例如:

INSERT INTO table (a,b,c) VALUES (1,2,3)
  ON DUPLICATE KEY UPDATE c=c+1;

UPDATE table SET c=c+1 WHERE a=1;

支持多行插入:

INSERT INTO table (a,b,c) VALUES (1,2,3),(4,5,6)
  ON DUPLICATE KEY UPDATE c=VALUES(a)+VALUES(b);

ON DUPLICATE KEY UPDATE 子句中的 VALUES(a) 表示的是如果没有冲突将会插入 a 列的值,即 1 或者 4。

ON DUPLICATE KEY UPDATE 子句不适宜在有多个唯一性索引的表上使用。

参考:14.2.5.3 INSERT … ON DUPLICATE KEY UPDATE Syntax

3. Replace

Replace 是标准 SQL 的扩展,等价于 inserts/deletes and inserts

REPLACE [LOW_PRIORITY | DELAYED]
    [INTO] tbl_name
    [PARTITION (partition_name,...)]
    [(col_name,...)]
    {VALUES | VALUE} ({expr | DEFAULT},...),(...),...

REPLACE [LOW_PRIORITY | DELAYED]
    [INTO] tbl_name
    [PARTITION (partition_name,...)]
    SET col_name={expr | DEFAULT}, ...

REPLACE [LOW_PRIORITY | DELAYED]
    [INTO] tbl_name
    [PARTITION (partition_name,...)]
    [(col_name,...)]
    SELECT ...

所有列的值都从 Replace 语句中获取,无法从现有的行中获取值,如果有的列没有指定值那么会给定默认值。如果在指定值的时候使用了 SET col_name = col_name + 1 语句,等价于 SET col_name = DEFAULT(col_name) + 1

Replace 语句的返回值表示影响的行数,影响行数 = 删除的行数 + 插入的行数。对于单行的 Replace 操作,如果返回 1 表示仅仅插入了新的一行,如果大于 1 则表示删除了至少一行并插入了一行。

参考:14.2.8 REPLACE Syntax

3. 异同分析

从文档的说明来看,至少有两点差异:

  1. INSERT … ON DUPLICATE KEY UPDATE 在插入时可以使用现有行的值, Replace 不支持。
    mysql root@localhost:test> create table tb_table (a int not NULL PRIMARY key auto_increment, b int NOT NULL DEFAULT 0, c int NOT NULL DEFAULT 0)
    Query OK, 0 rows affected
    Time: 0.042s
    mysql root@localhost:test> insert into tb_table (a, b, c) VALUES (1,2,3);
    Query OK, 1 row affected
    Time: 0.024s
    mysql root@localhost:test> INSERT INTO tb_table (a, b, c) values (1,5,6) on  DUPLICATE KEY UPDATE b = values(b) + b;
    Query OK, 2 rows affected
    Time: 0.025s
    mysql root@localhost:test> SELECT * from tb_table;
    +-----+-----+-----+
    |   a |   b |   c |
    |-----+-----+-----|
    |   1 |   7 |   3 |
    +-----+-----+-----+
    1 row in set
    Time: 0.001s
    
  2. INSERT … ON DUPLICATE KEY UPDATE 在不满足主键约束或者唯一性约束的时候是更新操作,所以主键不会变。而 Replacedeletes inserts 也就是说老的记录会被删除,如果不指定主键值那么可能会破坏已有的外键关联(比如主键是自增产生,插入的时候不指定主键值)。
    mysql root@localhost:test> create table tb_table (a int not NULL PRIMARY key auto_increment, b int NOT NULL DEFAULT 0 unique, c int NOT NULL DEFAULT 0)
    Query OK, 0 rows affected
    Time: 0.027s
    mysql root@localhost:test> show create table tb_table;
    +----------+----------------+
    | Table    | Create Table   |
    |----------+----------------|
    | tb_table | CREATE TABLE `tb_table` (
     `a` int(11) NOT NULL AUTO_INCREMENT,
     `b` int(11) NOT NULL DEFAULT '0',
     `c` int(11) NOT NULL DEFAULT '0',
     PRIMARY KEY (`a`),
     UNIQUE KEY `b` (`b`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8                |
    +----------+----------------+
    1 row in set
    Time: 0.020s
    mysql root@localhost:test> insert into tb_table (b,c) VALUES (2,3);
    Query OK, 1 row affected
    Time: 0.013s
    mysql root@localhost:test> SELECT * from tb_table;
    +-----+-----+-----+
    |   a |   b |   c |
    |-----+-----+-----|
    |   1 |   2 |   3 |
    +-----+-----+-----+
    1 row in set
    Time: 0.001s
    mysql root@localhost:test> replace into tb_table (b,c) values (2,4);
    Query OK, 2 rows affected
    Time: 0.023s
    mysql root@localhost:test> SELECT * from tb_table;
    +-----+-----+-----+
    |   a |   b |   c |
    |-----+-----+-----|
    |   2 |   2 |   4 |
    +-----+-----+-----+
    1 row in set
    Time: 0.001s
    mysql root@localhost:test> replace into tb_table (b,c) values (2,4),(3,5);
    Query OK, 3 rows affected
    Time: 0.007s
    mysql root@localhost:test> SELECT * from tb_table;
    +-----+-----+-----+
    |   a |   b |   c |
    |-----+-----+-----|
    |   3 |   2 |   4 |
    |   4 |   3 |   5 |
    +-----+-----+-----+
    2 rows in set
    Time: 0.001s
    mysql root@localhost:test> insert into tb_table (b,c) values (2,8) on  DUPLICATE KEY UPDATE c = VALUES(c);
    Query OK, 2 rows affected
    Time: 0.013s
    mysql root@localhost:test> SELECT * from tb_table;
    +-----+-----+-----+
    |   a |   b |   c |
    |-----+-----+-----|
    |   3 |   2 |   8 |
    |   4 |   3 |   5 |
    +-----+-----+-----+
    2 rows in set
    Time: 0.001s
    

Melkman算法

1. 问题描述

给定一组二维坐标的集合,求从这个集合中找出这些二维坐标的外围边界。经过查询,确定了这是一个二维凸包的问题,属于计算几何的范畴。

2. Melkman 算法

经过查询,发现二维凸包的解法有很多种,其中 Melkman 算法是其中比较好的解决方案。Melkman 算法在点排序后可以以 O(n) 的时间复杂度计算凸包。同时 Melkman 还是一种在线的算法,虽然我这里用不到这个特性。

Melkman 算法的大致思想是这样的:首先找出所有点集合中某一个维度上的最大或者最小值,然后按照顺时针或者逆时针的方向逐个遍历集合中剩余的点。要找出集合中最外围的点,有一个不变的特性必须要保持住:

假设 P_i,P_j,P_k 是凸包上逆时针方向上的连续 3 个点,那么它们必然保持一种左转的趋势,即:

    \[\overrightarrow{P_iP_j}\times\overrightarrow{P_jP_k}>0\]

如果用 (x_i,y_i),(x_j,y_j),(x_k,y_k) 来表示这三个点,亦即:

    \[\overrightarrow{P_iP_j}=(x_j-x_i,y_j-y_i)\]

    \[\overrightarrow{P_jP_k}=(x_k-x_j,y_k-y_j)\]

那么根据向量叉积公式必须满足:

    \[(x_j-x_i)<em>(y_k-y_j)-(x_k-x_j)</em>(y_j-y_i)>0\]

3. 算法描述

Melkman 算法使用双端队列来实现这个原理,假设双端队列为 D。所有队列操作可以用入队首、出队首、入队尾、出队尾来描述,实际操作过程可以描述为:

  1. 假设点集合的坐标可以表示为 (x,y),那么首先找出 x 值最小的点记为 P_0

  2. 然后选定一个方向,比如逆时针方向。然后计算所有剩余的每一个点 P_0P_x 形成的向量 \overrightarrow{P_0P_x}y 轴负方向的夹角。根据向量的点积公式计算出夹角之后根据夹角从小到大就行排序得到有序集合 S={P_0,P_1,P_2…P_{n-1}}

  3. 记某一时刻 D 的状态为:P_tP_{t-1}…P_0...P_{b-1}P_b ,对于 S 中的每一个点进行遍历:

    3.1 如果是 P_0 则首先将 P_0 入队尾,如果是 P_1 则入队尾,如果是 P_2 则入队首并且入队尾。

    3.2 假设遍历到当前节点 P_i
    ​ 3.2.1 如果 P_{b-1}P_bP_i 能保持左转特性则继续,否则 P_b 出队尾,如此往复直到 P_{b-m-1}P_{b-m}P_i 能够满足左转特性,P_i 入队尾。

    ​ 3.2.2 如果 P_iP_tP_{t-1} 能保持左转特性则继续,否则 P_t 出队首,如此往复直到 P_iP_{t-n}P_{t-n-1} 能够满足左转特性,P_i 入队首。

  4. 返回 D

4. 算法实现

首先给出数据结构,PointPolygon

Point.java

package com.xxx.dvp.rest.domain.model;

/**
 * User: wuzhiyu.
 * Date: 16/12/21.
 * Time: 15:18.
 */
public class Point {
  private double lng;
  private double lat;

  /* Constructors */

  /* Setters and Getters */
}

Polygon.java

package com.xxx.dvp.rest.domain.model;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * The type Melkman polygon.
 */
public class Polygon {
  private List<Point> points;

  /* Constructors  */

  /* Setter and Getter */

  /**
   * Contains boolean.
   * 源代码来自 .NET Framework。多边形边界上的点不算多边形内
   *
   * @param point the melkman point
   * @return the boolean
   */
  public boolean contains(Point point) {
    int crossings = 0;
    for (int index = 0; index < getPoints().size() - 1; index++) {
      double slope = getPoints().get(index + 1).getSlope(
          getPoints().get(index));
      boolean cond1 = (getPoints().get(index).getLng() <= point.getLng())
          && (point.getLng() < getPoints().get(index + 1).getLng());
      boolean cond2 = (getPoints().get(index + 1).getLng() <= point.getLng())
          && (point.getLng() < getPoints().get(index).getLng());
      boolean above = ((point.getLng() - getPoints().get(index).getLng()) * slope
          + getPoints().get(index).getLat()) > point.getLat();
      if ((cond1 || cond2) && above) {
        crossings++;
      }
    }
    return (crossings % 2 != 0);
  }

  /**
   * On border boolean.
   *
   * @param point the point
   * @return the boolean
   */
  public boolean onBorder(Point point) {
    for (int index = 0; index < getPoints().size() - 1; index++) {
      double slope = getPoints().get(index + 1).getSlope(getPoints().get(index));
      double latOnLine = (point.getLng() - this.points.get(index).getLng()) * slope
          + this.points.get(index).getLat();
      if (latOnLine == point.getLat()) {
        return true;
      }
    }
    return false;
  }

  @Override
  public String toString() {
    return "Polygon{" + "points=" + points + '}';
  }
}

Melkman 算法:

package com.xxx.dvp.rest.domain.service;

import com.xxx.dvp.rest.domain.model.Boundary;
import com.xxx.dvp.rest.domain.model.Point;
import com.xxx.dvp.rest.domain.model.Polygon;
import com.xxx.dvp.rest.infra.persistence.conf.DataExampleConfig;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.geojson.Feature;
import org.geojson.FeatureCollection;

import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Deque;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * User: wuzhiyu.
 * Date: 16/12/26.
 * Time: 10:45.
 */
public class PointService {

  public static void main(String[] argv) throws IOException {
    PointService pointService = new PointService();
    FeatureCollection collection = new FeatureCollection();
    String fileName = "cluster_%d.txt";

    for (int i = 0; i < 8; i++) {
      List<Point> points = DataExampleConfig.getPoints(String.format(fileName, i));
      Polygon polygon = pointService.getConvexHullWithMelkman(points);

      Boundary boundaryOfPolygon = GeoService.getBoundaryOfPolygon(polygon);
      Set<String> gridsOfPolygon = GridService.getGrids(boundaryOfPolygon);

      gridsOfPolygon = GridService.getGridsInPolygon(gridsOfPolygon, polygon);

      List<Point> edgeOfGrids = GridService.getEdgeOfGrids(gridsOfPolygon);

      Polygon newPolygon = new Polygon(edgeOfGrids);

      GridService.outputBoundaryGrids(boundaryOfPolygon);
      GridService.outputPoints(edgeOfGrids);

      Feature polygonFeature = GeoService.getPolygonFeature(newPolygon);

      collection.add(polygonFeature);

      List<Point> errorPoints = points.stream()
          .filter(point -> !polygon.contains(point))
          .filter(point -> !polygon.onBorder(point))
          .collect(Collectors.toList());
      System.out.println("errorPoints = " + errorPoints);
    }

    ObjectMapper objectMapper = new ObjectMapper();
    System.out.println(objectMapper.writeValueAsString(collection));
  }

  public Polygon getConvexHullWithMelkman(List<Point> pointList) {
    if (pointList.size() < 3) {
      return null;
    }

    sortByAngle(pointList);

    Deque<Point> deque = new ArrayDeque<>();

    pointList.forEach(point -> {
      switch (deque.size()) {
        case 0:
        case 1:
          deque.offerLast(point);
          return;
        case 2:
          deque.offerLast(point);
          deque.offerFirst(point);
          return;
        default:
          Point lastRightVertex = deque.pollLast();
          Point lastLeftVertex = deque.pollFirst();

          if (this.isLeftTurn(deque.peekLast(), lastRightVertex, point)
              && this.isLeftTurn(point, lastLeftVertex, deque.peekFirst())) {
            return;
          }

          while (!this.isLeftTurn(deque.peekLast(), lastRightVertex, point)) {
            lastRightVertex = deque.pollLast();
          }
          deque.offerLast(lastRightVertex);
          deque.offerLast(point);

          while (!this.isLeftTurn(point, lastLeftVertex, deque.peekFirst())) {
            lastLeftVertex = deque.pollFirst();
          }
          deque.offerFirst(lastLeftVertex);
          deque.offerFirst(point);
          return;
      }
    });

    return new Polygon(new ArrayList<>(deque));
  }

  private void sortByAngle(List<Point> pointList) {
    Point minLngPoint = pointList.stream()
        .min(Comparator.comparing(Point::getLng)).get();
    pointList.remove(minLngPoint);
    pointList.sort(new Comparator<Point>() {
      @Override
      public int compare(Point o1, Point o2) {
        return Double.compare(angleWithSouth(minLngPoint, o1),
            angleWithSouth(minLngPoint, o2));
      }
    });

    pointList.add(0, minLngPoint);
  }

  public boolean isLeftTurn(Point point1, Point point2, Point point3) {
    return crossProduct(point1, point2, point3) > 0;
  }

  public double crossProduct(Point point1, Point point2, Point point3) {
    double x1 = point2.getLng() - point1.getLng();
    double y1 = point2.getLat() - point1.getLat();
    double x2 = point3.getLng() - point2.getLng();
    double y2 = point3.getLat() - point2.getLat();
    return x1 * y2 - x2 * y1;
  }

  public double dotProduct(Point point1, Point point2, Point point3) {
    double x1 = point2.getLng() - point1.getLng();
    double y1 = point2.getLat() - point1.getLat();
    double x2 = point3.getLng() - point2.getLng();
    double y2 = point3.getLat() - point2.getLat();
    return x1 * x2 + y1 * y2;
  }

  public double angleWithSouth(Point point1, Point point2) {
    Point point = new Point(point1.getLng(), point1.getLat() + 1);
    return Math.acos(this.dotProduct(point, point1, point2)
        / (this.norm(point, point1) * this.norm(point1, point2)));
  }

  public double norm(Point point1, Point point2) {
    double deltaLat = point2.getLat() - point1.getLat();
    double deltaLng = point2.getLng() - point1.getLng();

    return Math.sqrt(deltaLat * deltaLat + deltaLng * deltaLng);
  }
}

上文的代码引用了一个依赖:

<!-- geojson -->
<dependency>
    <groupId>de.grundid.opendatalab</groupId>
    <artifactId>geojson-jackson</artifactId>
    <version>1.7</version>
</dependency>

输出的 json 结果可以在 geojson 做可视化展示。

5. 参考文献

  1. http://maxgoldste.in/melkman/
  2. http://w3.impa.br/~rdcastan/Cgeometry/
  3. 漫话二维凸包

使用 Quartz API

What is Quartz?

Quartz 是一个功能丰富的开源作业调度类库,可以与各种规模的 Java 应用集成。

Instantiating the Scheduler

SchedulerFactory factory = new StdSchedulerFactory();
Scheduler scheduler = factory.getScheduler();
scheduler.start();
JobDetail printJob = JobBuilder.newJob(PrintJob.class)
  .withIdentity("print job", "default group").build();

Trigger trigger = TriggerBuilder.newTrigger().
  withIdentity("print trigger", "default group").startNow().
  withSchedule(SimpleScheduleBuilder.simpleSchedule().
      withIntervalInSeconds(2).
      repeatForever()).build();

scheduler.scheduleJob(printJob,trigger);

Key Interfaces

接口名称 说明
Scheduler 与调度器交互的主要API
Job 调度器执行的组件需要实现的接口
JobDetail 用来定义Job的实例
Trigger 定义给定Job何时执行的组件
JobBuilder 用来定义/构建JobDetail实例
TriggerBuilder 用来定义/构建触发器实例

各种 Builder:

  • org.quartz.JobBuilder
  • org.quartz.SimpleScheduleBuilder
  • org.quartz.CronScheduleBuilder
  • org.quartz.CalenderIntervalScheduleBuilder
  • org.quartz.TriggerBuilder
  • org.quartz.DateBuilder

Jobs and Triggers

一个作业是一个实现 Job 接口的类,该接口只有一个方法:

package org.quartz;
public interface Job {
  public void execute(JobExecutionContext context)
    throws JobExecutionException;
}

当作业的触发器启动,execute 方法被调度器的某个工作线程(worker thread)调用。JobExecutionContext 对象被传递给方法以提供作业实例所在运行时环境的的信息,包括调度器和触发器的句柄、作业的 JobDetail 对象以及其他一些条目。

JobDetail 对象由你的程序在将作业添加到调度器时创建。这个对象包含作业的各种属性设定信息,包括一个被用来存储给定 Job 类实例状态信息的 JobDataMap。

Trigger 对象被用来触发作业的执行。触发器也可以有一个关联到它们的 JobDataMap。JobDataMap 在把作业参数传递给触发器的执行时是很有用的。Quartz 提供一系列不同的触发器类型,最常用的是两个:

  • SimpleTrigger。如果需要你需要“一次性”调用或者在某个给定时间每隔一个时间段 T 触发 N 次,你会觉得它很顺手。
  • CronTrigger。如果你希望像基于日历一样调度作业,它很有用。

Quartz 将作业和触发器分开的设计有很多好处。例如:你可以创建作业并将它们存储在作业调度器中而不关联触发器。这使你能够将许多触发器关联到同一个作业。这种松耦合的另一个好处是能够配置关联触发器已经失效但是仍然驻留在调度器中的作业。这使你能够在随后再次调度它们而不需要重新定义它们。这种设计还允许你在不需要重新定义关联作业的前提下修改和替换触发器。

Identities

作业和触发器在 Quartz 调度器注册时被给予标识键。作业和触发器的键(JobKey 和 TriggerKey)允许它们被放置在组中,便于组织作业和触发器。作业和触发器的键的名字部分必须是组内唯一的。换句话说,作业或者触发器完整的键(或者标识符)由名字和组组成。

解决 Maven 建立的 Spring MVC 项目不支持 EL 表达式的问题

使用 Maven 建立的 Spring MVC 项目默认不支持 EL 表达式,解决方法有两个:

(1)web.xml
将 web.xml 文件的头部默认的:

<!DOCTYPE web-app PUBLIC
 "-//Sun Microsystems, Inc.//DTD Web Application 2.3//EN"
 "http://java.sun.com/dtd/web-app_2_3.dtd" >

<web-app>

替换为:

<web-app xmlns="http://java.sun.com/xml/ns/javaee" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://java.sun.com/xml/ns/javaee
         http://java.sun.com/xml/ns/javaee/web-app_3_0.xsd"
     version="3.0" metadata-complete="true">

(2)JSP 页面设置
在每个 JSP 页面头部添加:

<%@ page isELIgnored="false"%>

Spring MVC 中的 url 问题

这两天在学习 Spring MVC 的时候与到了一个关于 url 的问题让我很困惑,查找资料和同学讨论没找出一个结论。现在先这里 Mark 一下,等找出原因以后再补完这篇文章。

1. 问题描述

首先上一个表单:

<form:form commandName="book" action="book_update" method="post">
<fieldset>
  <legend>Add a book</legend>
  <form:hidden path="id"/>
    <p>
      <label for="category">Category</label>
      <form:select id="category" path="category.id" items="${categories}"
                   itemLabel="name" itemValue="id"></form:select>
    </p>
    <p>
      <label for="title">Title</label>
      <form:input id="title" path="title" />
    </p>
    <p>
      <label for="author">Author</label>
      <form:input id="author" path="author" />
    </p>
    <p>
      <label for="isbn">ISBN</label>
      <form:input id="isbn" path="isbn" />
    </p>
    <p id="buttons">
      <input id="reset" type="reset" tabindex="4" />
      <input id="submit" type="submit" tabindex="5" 
             value="Update Book" />
    </p>
</fieldset>
</form:form>

这个表单在我访问 http://127.0.0.1:8080/book-demo/book_edit/{id} 时会展示。简单来说,这个 url 的格式可以表示为:

http://hostname[:端口号]/context/action/{id}

在这里 hostname[:端口号] 即为 127.0.0.1:8080context 为 webapp 的名字 book-demo,而后面的 action 则使用了路径变量。

从上面的表单代码可以看到表单提交对应的 actionbook_update。这个表单提交的时候,我预期的 url 是:

http://127.0.0.1:8080/book-demo/book_update

但实际表单提交后访问的 action 为:

http://127.0.0.1:8080/book_demo/book_edit/book_update

也就是说程序把 /book_demo/book_edit 作为了 context,把路径变量作为了 action

2. 尝试的解决方案

显然,错误出在访问 action 的时候产生了错误的 url,所以针对这个错误原因我尝试了两种解决方案:

1) action=”/book_update”

我把表单的 action 改了一下,结果产生的 url 是:

http://127.0.0.1:8080/book_update

显然连 url 的 context 都丢了,action 中带了 / 之后有了一点根路径的意思。

2) action=”/book-demo/book_update”

结果正确,获得了我想要的 url 。

3. 思考

a. 关于 url 产生机制

这个问题不禁引人思考 url 路径产生的机制。

之前做过 ruby on rails 的开发,作为对比:tomcat 运行应用的时候都会带上这个应用的名称,也就构成了第一级的上下文。对比 ruby on rails 在运行应用的时候 url 不会带上应用名称。因此,这个表单在 ruby on rails 中使用不会有问题,但是在这里就会有!

从绝对路径与相对路径的角度来看:首先 action=”book_update” 的写法相当于使用相对路径,把 /book_demo/book_edit 当做了上一级路径。而 action=”/book_update” 以及 action=”/book-demo/update” 则属于绝对路径的范畴。

b. 关于 RESTful 的 url

上面的表单其实并不符合 RESTful 的风格(我觉得 rails 提倡的 RESTful 风格的 url 很是优雅,之前做 rails 的时候一直想写写来着)。比如更新一本书的信息,对应的 action 可以叫 update,路径可以映射为 /books/{id}/update。上文的表单是把书本的 id 信息作为一个隐藏域来传递,虽然可行但绝对不是一个良好的风格。这里附一下 RESTful 风格的路由:
Rails:

url HTTP 方法 对应的 action 操作说明
/books GET list 获取所有书籍的信息
/books/new GET new 返回新增书籍的页面
/books POST create 新增一本书籍
/books/{id} GET show 显示某特定id书本的详细信息
/books/{id}/edit GET edit 返回编辑书本信息的页面
/books/{id} PUT/PATCH update 更新书本信息
/books/{id} DELETE destroy 删除书本信息

Rails 的 HTTP 方法使用了一些小技巧来实现 PUT/PATCH 和 DELETE 方法。通过在表单内增加一个隐藏域来实现:

<input type="hidden" name="_method" value="put">

对应地,我们可以借鉴并稍作修改在 Spring MVC 中应用:

url HTTP 方法 对应的 action 操作说明
/books GET list 获取所有书籍的信息
/books/new GET new 返回新增书籍的页面
/books/create POST create 新增一本书籍
/books/{id} GET show 显示某特定id书本的详细信息
/books/{id}/edit GET edit 返回编辑书本信息的页面
/books/{id}/update POST update 更新书本信息
/books/{id}/destroy POST destroy 删除书本信息