On Sep 21, 3:05 am, Philippe Marschall <philippe.marsch...@gmail.com>
wrote:
>
> But long is crappy abstraction. Sometimes you need two decimal places,
> sometimes three, sometimes six, sometimes "as many as there are".
> That's all quite cumbersome to do with a long alone. String seems like
> the easier way to go.
>
Well, in case anyone is interested, below I have included the code for
a class that can lexicographically encode BigDecimals as strings (and
I have included JUnit test class).
This class encodes numbers as strings in such a way that the
lexicographic order of the encoded strings is the same as the natural
order of the original numbers.
The length of an encoded number is only slightly larger than the
length of its original number.
Unlike other schemes, there is no limit to the size of numbers which
may be encoded.
This encoding lets you store BigDecimals as Strings and still be able
to do proper range searches in queries.
This code was based on ideas in this paper: www.zanopha.com/docs/elen.ps
, but there are some minor differences.
Feel free to use this code as you wish.
----------------------------------------------------------------------------
package net.sf.contrail.core.impl;
import java.math.BigDecimal;
import java.text.ParseException;
import net.sf.contrail.core.ContrailException;
/**
* Encodes numbers as strings in such a way that the lexicographic
order of the
* encoded strings is the same as the natural order of the original
numbers.
* The length of an encoded number is only slightly larger than the
length
* of its original number.
* Unlike other schemes, there is no limit to the size of numbers
which may be encoded.
*
* @author ted stockwell
*
*/
public class StorageNumberCodec {
public static final String decode(String input) {
try
{
if (input == null)
return null;
if (input.length() <= 0)
return "";
return new Decoder(input)._output;
}
catch (ParseException e) {
throw new ContrailException("Failed to decode
number:"+input, e);
}
}
public static final BigDecimal decodeAsBigDecimal(String input) {
try
{
if (input == null)
return null;
if (input.length() <= 0)
throw new ContrailException("Internal Error:
Cannot decode an
empty String");
return new BigDecimal(new Decoder(input)._output);
}
catch (ParseException e) {
throw new ContrailException("Failed to decode
number:"+input, e);
}
}
public static final String encode(String input) {
try
{
if (input == null)
return null;
if (input.length() <= 0)
return "";
return new Encoder(input)._output;
}
catch (ParseException e)
{
throw new ContrailException("Failed to parse
number:"+input, e);
}
}
public static final String encode(BigDecimal decimal) {
if (decimal == null)
return null;
return encode(decimal.toPlainString());
}
static public class Encoder {
private String _input;
private int _position= 0;
private int _end;
private String _output= "";
private boolean _isNegative= false;
private Encoder(String input) throws ParseException {
_input= input;
_end= _input.length();
char c= _input.charAt(_position);
if (c == '-') {
_input.charAt(_position++);
_isNegative= true;
}
readNumberBeforeDecimal();
if (readDecimalPoint()) {
readNumber(_end - _position);
}
_output+= _isNegative ? '?' : '*';
}
private boolean readDecimalPoint() throws ParseException {
if (_end <= _position)
return false;
char c= _input.charAt(_position++);
if (c != '.')
throwParseException("Expected decimal point");
if (_end <= _position)
return false;
_output+= _isNegative ? ':' : '.';
return true;
}
private void readNumberBeforeDecimal() throws ParseException {
char[] buffer= new char[_input.length()];
// read number until decimal point reached or end
int i= 0;
while(_end > _position) {
char c= _input.charAt(_position++);
if ('0' <= c && c <= '9') {
buffer[i++]= (char)(_isNegative ?
'0'+('9'-c) : c);
}
else if (c == '.') {
_position--;
break;
}
}
// now figure out needed prefixes
String prefix= "";
int l= i;
String unaryPrefix= _isNegative ? "*" : "?";
while (1 < l) {
unaryPrefix+= _isNegative ? '*' : '?';
String s= Integer.toString(l);
if (_isNegative) {
char[] cs= s.toCharArray();
for (int j= 0; j < cs.length; j++)
cs[j]= (char)('0'+ '9'-cs[j]);
s= new String(cs);
}
prefix= s+prefix;
l= s.length();
}
_output+= unaryPrefix; // output unary prefix count
_output+= prefix; // output prefixes
_output+= new String(buffer, 0, i); // now output
actual number
}
private void readNumber(int length) {
if (_isNegative) {
while (0 < length--) {
_output+=
(char)('0'+('9'-_input.charAt(_position++)));
}
}
else {
_output+= _input.substring(_position,
_position+length);
_position+= length;
}
}
private void throwParseException(String message) throws
ParseException {
throw new ParseException(message, _position);
}
}
static public class Decoder {
private String _input;
private int _position= 0;
private int _end;
private String _output= "";
private boolean _isNegative= false;
private Decoder(String input) throws ParseException {
_input= input;
_end= _input.length();
int lastChar= _input.charAt(_end-1);
while (lastChar == '*' || lastChar== '?' || lastChar ==
':' ||
lastChar == '.')
lastChar= _input.charAt((--_end)-1);
char c= _input.charAt(_position);
if (c == '*') {
_output+= '-';
_isNegative= true;
}
else if (c != '?')
throw new ParseException("All encoded numbers
must begin with
either '?' or '*'", _position);
readSequence();
if (readDecimalPoint()) {
readNumber(_end - _position);
}
}
private boolean readDecimalPoint() throws ParseException {
if (_end <= _position)
return false;
char c= _input.charAt(_position++);
if (c != (_isNegative ? ':' : '.'))
throw new ParseException("Expected decimal
point", _position);
if (_end <= _position)
return false;
_output+= '.';
return true;
}
private void readSequence() throws ParseException {
int sequenceCount= 0;
while(true) {
int c= _input.charAt(_position++);
if (c == '*' || c == '?') {
sequenceCount++;
}
else {
_position--;
break;
}
}
readNumberSequence(sequenceCount);
}
private void readNumberSequence(int sequenceCount) {
int prefixLength= 1;
while (1 < sequenceCount--) {
prefixLength= readPrefix(prefixLength);
}
readNumber(prefixLength);
}
private int readPrefix(int length) {
String s;
if (_isNegative) {
char[] cs= new char[length];
int i= 0;
while (0 < length--) {
cs[i++]=
(char)('0'+('9'-_input.charAt(_position++)));
}
s= new String(cs);
}
else {
s= _input.substring(_position,
_position+length);
_position+= length;
}
return Integer.parseInt(s);
}
private void readNumber(int length) {
if (_isNegative) {
while (0 < length--) {
_output+=
(char)('0'+('9'-_input.charAt(_position++)));
}
}
else {
_output+= _input.substring(_position,
_position+length);
_position+= length;
}
}
}
}
---------------------------------------------------------------
package net.sf.contrail.tests;
import java.text.ParseException;
import java.util.ArrayList;
import java.util.Collections;
import junit.framework.TestCase;
import net.sf.contrail.core.impl.StorageNumberCodec;
/**
* Tests the number encoding scheme
* @author ted stockwell
*/
public class NumberDecoderTest extends TestCase {
public void testNumberDecoder() throws ParseException {
String[] tokens= new String[] {
"-100.5", "**6899:4?",
"-10.5", "**789:4?",
"-3.145", "*6:854?",
"-3.14", "*6:85?",
"-1.01", "*8:98?",
"-1", "*8?",
"-0.0001233", "*9:9998766?",
"-0.000123", "*9:999876?",
"0", "?0*",
"0.000123", "?0.000123*",
"0.0001233", "?0.0001233*",
"1", "?1*",
"1.01", "?1.01*",
"3.14", "?3.14*",
"3.145", "?3.145*",
"10.5", "??210.5*",
"100.5", "??3100.5*"
};
// test the ordering of the characters used in the encoding
// if characters are not ordered in correct manner then encoding
fails
assertTrue('*' < '.');
assertTrue('.' < '0');
assertTrue('0' < '1');
assertTrue('1' < '2');
assertTrue('2' < '3');
assertTrue('3' < '4');
assertTrue('4' < '5');
assertTrue('5' < '6');
assertTrue('6' < '7');
assertTrue('7' < '8');
assertTrue('8' < '9');
assertTrue('9' < ':');
assertTrue(':' < '?');
ArrayList<String> encoded= new ArrayList<String>();
// test that the above encoded numbers are actually in lexical
order
like we think they are
for (int i= 0; i < tokens.length; i= i+2)
encoded.add(tokens[i+1]);
Collections.sort(encoded);
System.out.print(encoded);
for (int i= 0, j= 0; i < tokens.length; i= i+2)
assertEquals(tokens[i+1], encoded.get(j++));
// test that we decode correctly
for (int i= 0; i < tokens.length; i= i+2)
assertEquals(tokens[i],
StorageNumberCodec.decode(tokens[i+1]));
// test that we encode correctly
for (int i= 0; i < tokens.length; i= i+2)
assertEquals(tokens[i+1],
StorageNumberCodec.encode(tokens[i]));
}
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Google App Engine for Java" group.
To post to this group, send email to google-appengine-java@googlegroups.com
To unsubscribe from this group, send email to
google-appengine-java+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/google-appengine-java?hl=en
-~----------~----~----~----~------~----~------~--~---
