Hi ted. If you want to package this up in an open source project, I'll be happy to add it to the open source projects page: http://groups.google.com/group/google-appengine/web/google-app-engine-open-source-projects
<http://groups.google.com/group/google-appengine/web/google-app-engine-open-source-projects>- Jason On Mon, Sep 21, 2009 at 8:07 AM, ted stockwell <[email protected]> wrote: > > > > On Sep 21, 3:05 am, Philippe Marschall <[email protected]> > 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 [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-appengine-java?hl=en -~----------~----~----~----~------~----~------~--~---
