Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Z曲線とかどうなの?
package com.ashigeru.appengine.query.tiling.controller.zorder;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import net.arnx.jsonic.JSON;
import org.slim3.controller.Controller;
import org.slim3.controller.Navigation;
import org.slim3.datastore.Datastore;
import com.ashigeru.appengine.query.tiling.meta.ZOrderVectorMeta;
import com.ashigeru.appengine.query.tiling.model.DistanceComparator;
import com.ashigeru.appengine.query.tiling.model.ZOrderVector;
import com.google.appengine.api.datastore.Query.FilterOperator;
import com.google.appengine.api.datastore.Query.SortDirection;
public class AddController extends Controller {
private static final int CANDIDATES = 10;
@Override
public Navigation run() throws Exception {
String name = asString("name");
Integer d1 = asInteger("d1");
Integer d2 = asInteger("d2");
Integer d3 = asInteger("d3");
Integer d4 = asInteger("d4");
if (name == null || d1 == null || d2 == null || d3 == null || d4 == null) {
return null;
}
ZOrderVector vector = new ZOrderVector(d1, d2, d3, d4);
vector.setName(name);
ZOrderVectorMeta m = ZOrderVectorMeta.get();
// Z-Orderingの前後を取得
List<ZOrderVector> front = Datastore.query(m)
.filter("ordering", FilterOperator.LESS_THAN_OR_EQUAL, vector.getOrdering())
.limit(CANDIDATES + 1)
.sort("ordering", SortDirection.DESCENDING)
.asList();
List<ZOrderVector> back = Datastore.query(m)
.filter("ordering", FilterOperator.GREATER_THAN, vector.getOrdering())
.limit(CANDIDATES)
.sort("ordering", SortDirection.ASCENDING)
.asList();
// ユークリッド距離で並べなおす
List<ZOrderVector> candidates = new ArrayList<ZOrderVector>();
candidates.addAll(front);
candidates.addAll(back);
Collections.sort(candidates, new DistanceComparator(vector));
// ついでに自分も保存しておく
Datastore.put(vector);
List<Map<String, Object>> results = new ArrayList<Map<String, Object>>();
for (int i = 0, n = Math.min(candidates.size(), 3); i < n; i++) {
Map<String, Object> entry = new HashMap<String, Object>();
ZOrderVector found = candidates.get(i);
entry.put("name", found.getKey().getName());
entry.put("vector", found.getVector());
entry.put("distance", vector.distanceTo(found));
results.add(entry);
}
JSON.encode(results, response.getWriter(), true);
return null;
}
}
package com.ashigeru.appengine.query.tiling.model;
/**
* バイト配列を操作する。
* @author ashigeru
*/
public class ByteArrayBuilder {
private byte[] bytes;
public ByteArrayBuilder(int numberOfBytes) {
bytes = new byte[numberOfBytes];
}
public static ByteArrayBuilder fromDouble(double value) {
ByteArrayBuilder result = new ByteArrayBuilder(8);
long bits = Double.doubleToRawLongBits(value);
for (int b = 0; b < 8; b++) {
result.bytes[b] = (byte) (bits >>> (Double.SIZE - (b + 1) * 8));
}
return result;
}
public static ByteArrayBuilder fromInt(int value) {
ByteArrayBuilder result = new ByteArrayBuilder(4);
for (int b = 0; b < 4; b++) {
result.bytes[b] = (byte) (value >>> (Integer.SIZE - (b + 1) * 8));
}
return result;
}
public void set(int offset, boolean value) {
int byteOffset = offset / 8;
int bitOffset = offset % 8;
byte mask = (byte) (0x80 >>> bitOffset);
if (value) {
bytes[byteOffset] |= mask;
}
else {
bytes[byteOffset] &= ~mask;
}
}
public boolean get(int offset) {
int byteOffset = offset / 8;
int bitOffset = offset % 8;
byte mask = (byte) (0x80 >>> bitOffset);
return (bytes[byteOffset] & mask) != 0;
}
public byte[] getBytes() {
return this.bytes;
}
}
package com.ashigeru.appengine.query.tiling.model;
import java.util.Comparator;
/**
* 基点からの距離を基にした比較。
* @author ashigeru
*/
public class DistanceComparator implements Comparator<ZOrderVector> {
private ZOrderVector origin;
public DistanceComparator(ZOrderVector origin) {
this.origin = origin;
}
public int compare(ZOrderVector o1, ZOrderVector o2) {
double d1 = origin.distanceTo(o1);
double d2 = origin.distanceTo(o2);
return Double.compare(d1, d2);
}
}
package com.ashigeru.appengine.query.tiling.model;
import java.util.Arrays;
import org.slim3.datastore.Attribute;
import org.slim3.datastore.Datastore;
import org.slim3.datastore.Model;
import com.google.appengine.api.datastore.Key;
import com.google.appengine.api.datastore.ShortBlob;
/**
* Z曲線用のビット列を持つ多次元ベクトル。
* @author ashigeru
*/
@Model
public class ZOrderVector {
@Attribute(primaryKey = true)
private Key key;
@Attribute(lob = true)
private int[] vector;
private ShortBlob ordering;
public ZOrderVector() {
return;
}
public ZOrderVector(int...vector) {
this.vector = vector;
ordering = new ShortBlob(computeOrder(vector));
}
private static byte[] computeOrder(int[] vector) {
int dimensions = vector.length;
ByteArrayBuilder results = new ByteArrayBuilder(dimensions * 8);
for (int i = 0; i < dimensions; i++) {
ByteArrayBuilder bits = ByteArrayBuilder.fromInt(vector[i]);
for (int offset = 0; offset < Integer.SIZE; offset++) {
results.set(offset * dimensions + i, bits.get(offset));
}
}
return results.getBytes();
}
public double distanceTo(ZOrderVector other) {
int[] v1 = vector;
int[] v2 = other.vector;
if (v1.length != v2.length) {
return Double.NaN;
}
double sum = 0.0;
for (int i = 0; i < v1.length; i++) {
double diff = v1[i] - v2[i];
sum += diff * diff;
}
return Math.sqrt(sum);
}
@Override
public String toString() {
return Arrays.toString(vector);
}
public Key getKey() {
return this.key;
}
public void setKey(Key key) {
this.key = key;
}
public int[] getVector() {
return this.vector;
}
public void setVector(int[] vector) {
this.vector = vector;
}
public ShortBlob getOrdering() {
return this.ordering;
}
public void setOrdering(ShortBlob order) {
this.ordering = order;
}
public void setName(String name) {
this.key = Datastore.createKey(ZOrderVector.class, name);
}
}
@ashigeru

This comment has been minimized.

Copy link
Owner Author

ashigeru commented May 12, 2010

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.