commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From pste...@apache.org
Subject svn commit: r289992 - in /jakarta/commons/sandbox/id/trunk: project.xml src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
Date Sun, 18 Sep 2005 22:31:52 GMT
Author: psteitz
Date: Sun Sep 18 15:31:47 2005
New Revision: 289992

URL: http://svn.apache.org/viewcvs?rev=289992&view=rev
Log:
Added TimeBasedAlphanumericIdentifierGenerator
PR# 36683
Contributed by Jorg Schaible

Added:
    jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
  (with props)
    jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
  (with props)
Modified:
    jakarta/commons/sandbox/id/trunk/project.xml

Modified: jakarta/commons/sandbox/id/trunk/project.xml
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/id/trunk/project.xml?rev=289992&r1=289991&r2=289992&view=diff
==============================================================================
--- jakarta/commons/sandbox/id/trunk/project.xml (original)
+++ jakarta/commons/sandbox/id/trunk/project.xml Sun Sep 18 15:31:47 2005
@@ -119,6 +119,9 @@
 	  	<email>rwinston@eircom.net</email>
 	  	<organization></organization>
   	  </contributor>
+          <contributor>
+	  	<name>Jörg Schaible</name>
+  	  </contributor>
   	  <contributor>
 	  	<name>Jukka Zitting</name>
   	  </contributor>

Added: jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java?rev=289992&view=auto
==============================================================================
--- jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
(added)
+++ jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
Sun Sep 18 15:31:47 2005
@@ -0,0 +1,172 @@
+/*
+ * Copyright 2005 The Apache Software Foundation.
+ *
+ * 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.apache.commons.id.serial;
+
+import java.util.Arrays;
+import java.util.Calendar;
+import java.util.TimeZone;
+
+import org.apache.commons.id.AbstractStringIdentifierGenerator;
+
+
+/**
+ * <p>
+ * <code>TimeBasedAlphanumericIdentifierGenerator</code> is an Identifier Generator
that generates an alphanumeric
+ * identifier in base 36 as a String object from the current UTC time and an internal counter.
+ * </p>
+ * <p>
+ * The generator guarantees that all generated ids have an increasing natural sort order
(even if the time internally
+ * has an overflow). The implementation additionally guarantees, that all instances within
the same process do generate
+ * unique ids. All generated ids have the same length (padding with 0's on the left), which
is determined by the maximum
+ * size of a long value and the <code>postfixSize</code> parameter passed to
the constructor.
+ * </p>
+ * <p>
+ * Note: To ensure unique ids that are created within the same millisecond (or maximum time
resolution of the system),
+ * the implementation uses an internal counter. The maximum value of this counter is determined
by the
+ * <code>postfixSize</code> parameter i.e. the largest value that can be represented
in base 36. If the counter
+ * exceeds this value, an IllegalStateException is thrown.
+ * </p>
+ * <p>
+ * Note: The uniqueness of the generated ids cannot be guaranteed if the system performs
time shifts, that affect the
+ * running processes.
+ * </p>
+ * @author Commons-Id team
+ * @version $Id$
+ */
+public class TimeBasedAlphanumericIdentifierGenerator extends AbstractStringIdentifierGenerator
{
+
+    final private static char[] padding;
+    static {
+        padding = new char[MAX_LONG_ALPHANUMERIC_VALUE_LENGTH];
+        Arrays.fill(padding, '0');
+    }
+    final private static TimeZone UTC = TimeZone.getTimeZone("UTC");
+    private static long last = 0;
+    private static long counter = 0;
+    final private int postfixSize;
+    private final long offset;
+
+    /**
+     * Construct a TimeBasedAlphanumericIdentifierGenerator with a defined size of the postfix
and an offset for the
+     * time value. The offset can be used to manipulate the representation of the time value
in the generated id. If a
+     * TimeBasedAlphanumericIdentifierGenerator is constructed with an offset of the current
number of milliseconds
+     * since 1st Jan 1970 the first generated id in the same millisecond will have an id
consisting of a sequence of '0'
+     * characters.
+     * @param postfixSize the size of the postfix
+     * @param offset the offset taken into account for the time value
+     * @throws IllegalArgumentException if <code>postfixSize</code> is negative
or exceeds the maximum size for
+     *             representing {@link Long#MAX_VALUE} in base 36
+     */
+    public TimeBasedAlphanumericIdentifierGenerator(final int postfixSize, final long offset)
{
+        if (postfixSize < 0 || postfixSize > MAX_LONG_ALPHANUMERIC_VALUE_LENGTH) {
+            throw new IllegalArgumentException("Invalid size for postfix");
+        }
+        this.postfixSize = postfixSize;
+        this.offset = offset;
+    }
+
+    /**
+     * Construct a TimeBasedAlphanumericIdentifierGenerator with a defined size of the postfix.
+     * @param postfixSize the size of the postfix defining the maximum number of possible
ids generated within the same
+     *            millisecond (depending on the time resolution of the running system)
+     * @throws IllegalArgumentException if <code>postfixSize</code> is negative
or exceeds the maximum size for
+     *             representing {@link Long#MAX_VALUE} in base 36
+     */
+    public TimeBasedAlphanumericIdentifierGenerator(final int postfixSize) {
+        this(postfixSize, 0);
+    }
+
+    /**
+     * Construct a TimeBasedAlphanumericIdentifierGenerator with a default size of the postfix
of 3.
+     */
+    public TimeBasedAlphanumericIdentifierGenerator() {
+        this(3);
+    }
+
+    public long maxLength() {
+        return MAX_LONG_ALPHANUMERIC_VALUE_LENGTH + postfixSize;
+    }
+
+    public long minLength() {
+        return maxLength();
+    }
+
+    public String nextStringIdentifier() {
+        final long now;
+        synchronized (this) {
+            now = Calendar.getInstance(UTC).getTime().getTime(); // JDK 1.3 compatibility
+            if (now != last) {
+                last = now;
+                counter = 0;
+            } else {
+                ++counter;
+            }
+        }
+        final String postfix = counter > 0 ? Long.toString(counter, ALPHA_NUMERIC_CHARSET_SIZE)
: "";
+        if (postfix.length() > postfixSize) {
+            throw new IllegalStateException("The maximum number of identifiers in this millisecond
has been reached");
+        }
+        // ensure, that no negative value is used and values stay increasing
+        long base = now - offset;
+        long value = base < 0 ? base + Long.MAX_VALUE + 1 : base;
+        final String time = Long.toString(value, ALPHA_NUMERIC_CHARSET_SIZE);
+        final char[] buffer = new char[MAX_LONG_ALPHANUMERIC_VALUE_LENGTH + postfixSize];
+        int i = 0;
+        int maxPad = MAX_LONG_ALPHANUMERIC_VALUE_LENGTH - time.length();
+        if (maxPad > 0) {
+            System.arraycopy(padding, 0, buffer, 0, maxPad);
+        }
+        System.arraycopy(time.toCharArray(), 0, buffer, maxPad, time.length());
+        if (base < 0) {
+            // Representation of Long.MAX_VALUE starts with '1', negative 'base' means higher
value in time
+            buffer[0] += 2;
+        }
+        i += time.length() + maxPad;
+        if (postfixSize > 0) {
+            maxPad = postfixSize - postfix.length();
+            if (maxPad > 0) {
+                System.arraycopy(padding, 0, buffer, i, maxPad);
+                i += maxPad;
+            }
+            System.arraycopy(postfix.toCharArray(), 0, buffer, i, postfix.length());
+        }
+        return new String(buffer);
+    }
+
+    /**
+     * Retrieve the number of milliseconds since 1st Jan 1970 that were the base for the
given id.
+     * @param id the id to use
+     * @param offset the offset used to create the id
+     * @return the number of milliseconds
+     * @throws IllegalArgumentException if <code>id</code> is not a valid id
from this type of generator
+     */
+    public long getMillisecondsFromId(final Object id, final long offset) {
+        if (id instanceof String && id.toString().length() >= MAX_LONG_ALPHANUMERIC_VALUE_LENGTH)
{
+            final char[] buffer = new char[MAX_LONG_ALPHANUMERIC_VALUE_LENGTH];
+            System.arraycopy(id.toString().toCharArray(), 0, buffer, 0, MAX_LONG_ALPHANUMERIC_VALUE_LENGTH);
+            final boolean overflow = buffer[0] > '1';
+            if (overflow) {
+                buffer[0] -= 2;
+            }
+            long value = Long.parseLong(new String(buffer), ALPHA_NUMERIC_CHARSET_SIZE);
+            if (overflow) {
+                value -= Long.MAX_VALUE + 1;
+            }
+            return value + offset;
+        }
+        throw new IllegalArgumentException("'" + id + "' is not an id from this generator");
+    }
+}

Propchange: jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java?rev=289992&view=auto
==============================================================================
--- jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
(added)
+++ jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
Sun Sep 18 15:31:47 2005
@@ -0,0 +1,218 @@
+/*
+ * Copyright 2005 The Apache Software Foundation.
+ *
+ * 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.apache.commons.id.serial;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Calendar;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.TimeZone;
+
+import org.apache.commons.id.IdentifierGenerator;
+import org.apache.commons.id.StringIdentifierGenerator;
+
+import junit.framework.TestCase;
+
+
+/**
+ * @author J&ouml;rg Schaible
+ */
+public class TimeBasedAlphanumericIdentifierGeneratorTest extends TestCase {
+
+    protected void setUp() throws Exception {
+        super.setUp();
+        Thread.sleep(50); // Ensure no side-effect with previous tests (depends on timer
resolution)
+    }
+
+    /**
+     * Test constant size of generated identifier.
+     */
+    public void testIdentifierSizeIsConstant() {
+        final int maxSize = Long.toString(Long.MAX_VALUE, 36).length();
+        StringIdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(0);
+        assertEquals(maxSize, idGenerator.nextStringIdentifier().length());
+        assertEquals(maxSize, idGenerator.maxLength());
+        assertEquals(maxSize, idGenerator.minLength());
+        idGenerator = new TimeBasedAlphanumericIdentifierGenerator(1);
+        assertEquals(maxSize + 1, idGenerator.nextStringIdentifier().length());
+        assertEquals(maxSize + 1, idGenerator.maxLength());
+        assertEquals(maxSize + 1, idGenerator.minLength());
+        idGenerator = new TimeBasedAlphanumericIdentifierGenerator(10);
+        assertEquals(maxSize + 10, idGenerator.nextStringIdentifier().length());
+        assertEquals(maxSize + 10, idGenerator.maxLength());
+        assertEquals(maxSize + 10, idGenerator.minLength());
+    }
+
+    /**
+     * Test illegal values for the postfix size.
+     */
+    public void testIllegalPostfixSize() {
+        try {
+            new TimeBasedAlphanumericIdentifierGenerator(-1);
+            fail("Thrown " + IllegalArgumentException.class.getName() + " expected");
+        } catch (final IllegalArgumentException e) {
+            // OK
+        }
+        final int maxSize = Long.toString(Long.MAX_VALUE, 36).length();
+        try {
+            new TimeBasedAlphanumericIdentifierGenerator(maxSize + 1);
+            fail("Thrown " + IllegalArgumentException.class.getName() + " expected");
+        } catch (final IllegalArgumentException e) {
+            // OK
+        }
+    }
+
+    /**
+     * Test that an IllegalStateException is thrown if no more unique identifiers can be
generated.
+     */
+    public void testIllegalStateWhenTooManyIdentifiersGenerated() {
+        final IdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(0);
+        idGenerator.nextIdentifier();
+        try {
+            idGenerator.nextIdentifier();
+            // ensure exception even if a new time slice has been started between the last
two calls
+            idGenerator.nextIdentifier();
+            fail("Thrown " + IllegalStateException.class.getName() + " expected");
+        } catch (final IllegalStateException e) {
+            // OK
+        }
+    }
+
+    /**
+     * Test that the generator can be tweaked to start with '0'.
+     */
+    public void testMayStartWithIdentifierOfZeros() {
+        final int maxSize = Long.toString(Long.MAX_VALUE, 36).length();
+        final char[] zeros = new char[maxSize];
+        Arrays.fill(zeros, '0');
+
+        // synchronize with current time slice ...
+        final long waitForNextPeriod = System.currentTimeMillis();
+        long next = waitForNextPeriod;
+        while (next == waitForNextPeriod) {
+            next = System.currentTimeMillis();
+        }
+
+        // ... next id should be in same time slice if it is used as current offset
+        final StringIdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(0,
next);
+
+        assertEquals(new String(zeros), idGenerator.nextStringIdentifier());
+    }
+
+    /**
+     * Ensure that the default postfix size is big enough for a lot faster computers.
+     */
+    public void testDefaultPostfixSizeIsGoodEnough() {
+        final List idList = new ArrayList();
+
+        final IdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator();
+
+        // synchronize with current time slice ...
+        long waitForNextPeriod = System.currentTimeMillis();
+        long next = waitForNextPeriod;
+        while (next == waitForNextPeriod) {
+            next = System.currentTimeMillis();
+        }
+
+        // ... and now generate in the current one as much as possible
+        waitForNextPeriod = next;
+        while (next == waitForNextPeriod) {
+            idList.add(idGenerator.nextIdentifier());
+            next = System.currentTimeMillis();
+        }
+
+        // should not exceed the 10th number of possible values
+        assertTrue(idList.size() < (36 * 36 * 36) / 10);
+    }
+
+    /**
+     * Test if generator can handle an internal overflow as it may happen for time values
and still delivers increasing
+     * ids.
+     */
+    public void testInternalOverflowStillIncreasesIds() {
+        final List idList = new ArrayList();
+        final TimeZone utc = TimeZone.getTimeZone("UTC");
+        final long first = Calendar.getInstance(utc).getTime().getTime();
+        final long offset = first < 0 ? 0 : -(Long.MAX_VALUE - first - 100); // 100 ms
before internal overflow
+        final IdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(3,
offset);
+        while (Calendar.getInstance(utc).getTime().getTime() - first < 200) {
+            idList.add(idGenerator.nextIdentifier());
+        }
+        final List sorted = new ArrayList(idList);
+        Collections.sort(sorted);
+        assertEquals(idList, sorted);
+    }
+
+    /**
+     * Test ensures, that generator can recalculate the time from the id if internally no
overflow had happened.
+     */
+    public void testCanRetrieveTimeFromIdWithoutInternalOverflow() {
+        // synchronize with current time slice ...
+        final long waitForNextPeriod = System.currentTimeMillis();
+        final TimeBasedAlphanumericIdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(
+                4, waitForNextPeriod - 1000);
+
+        long next = waitForNextPeriod;
+        while (next == waitForNextPeriod) {
+            next = System.currentTimeMillis();
+        }
+
+        final String id = idGenerator.nextStringIdentifier();
+        assertEquals(next, idGenerator.getMillisecondsFromId(id, waitForNextPeriod - 1000));
+    }
+
+    /**
+     * Test ensures, that generator can recalculate the time from the id even if internally
an overflow had happened.
+     */
+    public void testCanRetrieveTimeFromIdWithInternalOverflow() {
+        // synchronize with current time slice ...
+        final long waitForNextPeriod = System.currentTimeMillis();
+        final TimeBasedAlphanumericIdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(
+                4, waitForNextPeriod + 1000);
+
+        long next = waitForNextPeriod;
+        while (next == waitForNextPeriod) {
+            next = System.currentTimeMillis();
+        }
+
+        final String id = idGenerator.nextStringIdentifier();
+        assertEquals(next, idGenerator.getMillisecondsFromId(id, waitForNextPeriod + 1000));
+    }
+
+    /**
+     * Test if different instances of the generator still deliver unique ids.
+     */
+    public void testDifferentGeneratorInstancesWillProduceStillUniqueIds() {
+        final IdentifierGenerator idGenerators[] = new IdentifierGenerator[] {
+                new TimeBasedAlphanumericIdentifierGenerator(),
+                new TimeBasedAlphanumericIdentifierGenerator(),
+                new TimeBasedAlphanumericIdentifierGenerator(),
+        };
+
+        final int loop = 1000;
+        final List idList = new ArrayList();
+        for(int i = loop; i-- > 0; ) {
+            for (int j = 0; j < idGenerators.length; ++j) {
+                idList.add(idGenerators[j].nextIdentifier());
+            }
+        }
+
+        assertEquals(loop * idGenerators.length, idList.size());
+        assertEquals(loop * idGenerators.length, new HashSet(idList).size());
+    }
+}

Propchange: jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain



---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message