Revert Sequence class; start redisigning syncing

6 files changed, 629 insertions, 87 deletions

diff --git a/active_document/__init__.py b/active_document/__init__.py
index 376f5d3..2ff1ea4 100644
--- a/active_document/__init__.py
+++ b/active_document/__init__.py
@@ -17,10 +17,9 @@ from active_document.document import Document
 
 from active_document.env import ACCESS_CREATE, ACCESS_WRITE, ACCESS_READ, \
         ACCESS_DELETE, ACCESS_AUTHOR, ACCESS_AUTH, ACCESS_PUBLIC, \
-        ACCESS_LEVELS, ACCESS_SYSTEM, ACCESS_LOCAL, ACCESS_REMOTE, \
-        index_flush_timeout, index_flush_threshold, \
-        index_write_queue, \
-        BadRequest, NotFound, Forbidden, Seqno, DEFAULT_LANG, \
+        ACCESS_LEVELS, ACCESS_SYSTEM, ACCESS_LOCAL, ACCESS_REMOTE, MAX_LIMIT, \
+        index_flush_timeout, index_flush_threshold, index_write_queue, \
+        BadRequest, NotFound, Forbidden, Seqno, Sequence, DEFAULT_LANG, \
         uuid, default_lang, gettext
 
 from active_document.metadata import Metadata, PropertyMeta, Property, \
@@ -35,6 +34,3 @@ from active_document.commands import to_int, to_list, \
         Request, Response, CommandsProcessor, CommandNotFound
 
 from active_document.volume import SingleVolume, VolumeCommands
-
-
-MAX_LIMIT = 2147483648
diff --git a/active_document/directory.py b/active_document/directory.py
index b2306a0..75044cb 100644
--- a/active_document/directory.py
+++ b/active_document/directory.py
@@ -264,61 +264,41 @@ class Directory(object):
             self.commit()
             self._notify({'event': 'populate'})
 
-    def diff(self, accept_range, limit):
-        """Return documents' properties for specified times range.
-
-        :param accept_range:
-            seqno sequence to accept documents
-        :param limit:
-            number of documents to return at once
-        :returns:
-            a tuple of ((`left-seqno`, `right-seqno`), [(`guid`, `patch`)]),
-            where `patch` is a resulting dictionary from `Document.diff()`
-            for corresponding `guid`
-
-        """
-        if not accept_range:
-            return
-
-        # To make fetching more reliable, avoid using intermediate
-        # find's offsets (documents can be changed and offset will point
-        # to different document).
-        if hasattr(accept_range, 'first'):
-            seqno = accept_range.first
+    def diff(self, in_seq, out_seq, **kwargs):
+        if 'group_by' in kwargs:
+            # Pickup only most recent change
+            kwargs['order_by'] = '-seqno'
         else:
-            seqno = accept_range[0]
+            kwargs['order_by'] = 'seqno'
+        # TODO On big requests, xapian can raise an exception on edits
+        kwargs['limit'] = env.MAX_LIMIT
+        kwargs['no_cache'] = True
 
-        query = {'limit': limit,
-                 'no_cache': True,
-                 'reply': ['guid'],
-                 'order_by': 'seqno',
-                 }
-
-        while True:
-            documents, total = self.find(query='seqno:%s..' % seqno, **query)
-            if not total:
-                break
+        for start, end in in_seq:
+            query = 'seqno:%s..' % start
+            if end:
+                query += str(end)
+            documents, __ = self.find(query=query, **kwargs)
 
             for doc in documents:
-                seqno = doc.get('seqno')
-                if seqno not in accept_range:
-                    continue
-
                 diff = {}
+                diff_seq = env.Sequence()
                 for name in self.metadata.keys():
                     if name == 'seqno':
                         continue
                     meta = doc.meta(name)
-                    if meta is None or meta['seqno'] not in accept_range:
+                    if meta is None:
+                        continue
+                    seqno = meta.get('seqno')
+                    if seqno not in in_seq:
                         continue
                     prop = diff[name] = {'mtime': meta['mtime']}
                     for i in ('value', 'mime_type', 'digest', 'path', 'url'):
                         if i in meta:
                             prop[i] = meta[i]
-
-                yield doc.guid, seqno, diff
-
-            seqno += 1
+                    diff_seq.include(seqno, seqno)
+                yield doc.guid, diff
+                out_seq.include(diff_seq)
 
     def merge(self, guid, diff, increment_seqno=True):
         """Apply changes for documents."""
diff --git a/active_document/env.py b/active_document/env.py
index f5e2d9c..e63da72 100644
--- a/active_document/env.py
+++ b/active_document/env.py
@@ -16,11 +16,12 @@
 import os
 import locale
 import logging
+import collections
 from uuid import uuid1
 from os.path import exists
 
 from active_toolkit.options import Option
-from active_toolkit import util
+from active_toolkit import util, enforce
 
 
 _logger = logging.getLogger('active_document')
@@ -56,6 +57,8 @@ ACCESS_NAMES = {
         ACCESS_DELETE: 'Delete',
         }
 
+MAX_LIMIT = 2147483648
+
 
 index_flush_timeout = Option(
         'flush index index after specified seconds since the last change',
@@ -243,3 +246,157 @@ class Seqno(object):
             os.fsync(f.fileno())
         self._orig_value = self._value
         return True
+
+
+class Sequence(list):
+    """List of sorted and non-overlapping ranges.
+
+    List items are ranges, [`start`, `stop']. If `start` or `stop`
+    is `None`, it means the beginning or ending of the entire scale.
+
+    """
+
+    def __init__(self, value=None, empty_value=None):
+        """
+        :param value:
+            default value to initialize range
+        :param empty_value:
+            if not `None`, the initial value for empty range
+
+        """
+        if empty_value is None:
+            self._empty_value = []
+        else:
+            self._empty_value = [empty_value]
+
+        if value:
+            self.extend(value)
+        else:
+            self.clear()
+
+    def __contains__(self, value):
+        for start, end in self:
+            if value >= start and (end is None or value <= end):
+                return True
+        else:
+            return False
+
+    @property
+    def first(self):
+        if self:
+            return self[0][0]
+        else:
+            return 0
+
+    @property
+    def last(self):
+        if self:
+            return self[-1][-1]
+
+    @property
+    def empty(self):
+        """Is timeline in the initial state."""
+        return self == self._empty_value
+
+    def clear(self):
+        """Reset range to the initial value."""
+        self[:] = self._empty_value
+
+    def include(self, start, end=None):
+        """Include specified range.
+
+        :param start:
+            either including range start or a list of
+            (`start`, `end`) pairs
+        :param end:
+            including range end
+
+        """
+        if issubclass(type(start), collections.Iterable):
+            for range_start, range_end in start:
+                self._include(range_start, range_end)
+        elif start is not None:
+            self._include(start, end)
+
+    def exclude(self, start, end=None):
+        """Exclude specified range.
+
+        :param start:
+            either excluding range start or a list of
+            (`start`, `end`) pairs
+        :param end:
+            excluding range end
+
+        """
+        if issubclass(type(start), collections.Iterable):
+            for range_start, range_end in start:
+                self._exclude(range_start, range_end)
+        else:
+            enforce(end is not None)
+            self._exclude(start, end)
+
+    def _include(self, range_start, range_end):
+        if range_start is None:
+            range_start = 1
+
+        range_start_new = None
+        range_start_i = 0
+
+        for range_start_i, (start, end) in enumerate(self):
+            if range_end is not None and start - 1 > range_end:
+                break
+            if (range_end is None or start - 1 <= range_end) and \
+                    (end is None or end + 1 >= range_start):
+                range_start_new = min(start, range_start)
+                break
+        else:
+            range_start_i += 1
+
+        if range_start_new is None:
+            self.insert(range_start_i, [range_start, range_end])
+            return
+
+        range_end_new = range_end
+        range_end_i = range_start_i
+        for i, (start, end) in enumerate(self[range_start_i:]):
+            if range_end is not None and start - 1 > range_end:
+                break
+            if range_end is None or end is None:
+                range_end_new = None
+            else:
+                range_end_new = max(end, range_end)
+            range_end_i = range_start_i + i
+
+        del self[range_start_i:range_end_i]
+        self[range_start_i] = [range_start_new, range_end_new]
+
+    def _exclude(self, range_start, range_end):
+        if range_start is None:
+            range_start = 1
+        enforce(range_end is not None)
+        enforce(range_start <= range_end and range_start > 0,
+                'Start value %r is less than 0 or not less than %r',
+                range_start, range_end)
+
+        for i, interval in enumerate(self):
+            start, end = interval
+            if end is not None and end < range_start:
+                # Current `interval` is below than new one
+                continue
+
+            if end is None or end > range_end:
+                # Current `interval` will exist after changing
+                self[i] = [range_end + 1, end]
+                if start < range_start:
+                    self.insert(i, [start, range_start - 1])
+            else:
+                if start < range_start:
+                    self[i] = [start, range_start - 1]
+                else:
+                    del self[i]
+
+            if end is not None:
+                range_start = end + 1
+                if range_start < range_end:
+                    self.exclude(range_start, range_end)
+            break
diff --git a/tests/units/document.py b/tests/units/document.py
index 6ccd0f0..cd480eb 100755
--- a/tests/units/document.py
+++ b/tests/units/document.py
@@ -448,32 +448,35 @@ class DocumentTest(tests.Test):
         for i in os.listdir('3/3'):
             os.utime('3/3/%s' % i, (3, 3))
 
+        out_seq = env.Sequence()
         self.assertEqual([
-            ('1', 2, {
+            ('1', {
                 'guid': {'value': '1', 'mtime': 1},
                 'ctime': {'value': 1, 'mtime': 1},
                 'prop': {'value': '1', 'mtime': 1},
                 'mtime': {'value': 1, 'mtime': 1},
                 'blob': {'mtime': 1, 'digest': hashlib.sha1('1').hexdigest(), 'mime_type': 'application/octet-stream', 'path': tests.tmpdir + '/1/1/blob.blob'},
                 }),
-            ('2', 4, {
+            ('2', {
                 'guid': {'value': '2', 'mtime': 2},
                 'ctime': {'value': 2, 'mtime': 2},
                 'prop': {'value': '2', 'mtime': 2},
                 'mtime': {'value': 2, 'mtime': 2},
                 'blob': {'mtime': 2, 'digest': hashlib.sha1('2').hexdigest(), 'mime_type': 'application/octet-stream', 'path': tests.tmpdir + '/2/2/blob.blob'},
                 }),
-            ('3', 5, {
+            ('3', {
                 'guid': {'value': '3', 'mtime': 3},
                 'ctime': {'value': 3, 'mtime': 3},
                 'prop': {'value': '3', 'mtime': 3},
                 'mtime': {'value': 3, 'mtime': 3},
                 }),
             ],
-            read_diff(directory, xrange(100), 2))
+            [i for i in directory.diff(env.Sequence([[0, None]]), out_seq)])
+        self.assertEqual([[1, 5]], out_seq)
 
+        out_seq = env.Sequence()
         self.assertEqual([
-            ('2', 4, {
+            ('2', {
                 'guid': {'value': '2', 'mtime': 2},
                 'ctime': {'value': 2, 'mtime': 2},
                 'prop': {'value': '2', 'mtime': 2},
@@ -481,22 +484,61 @@ class DocumentTest(tests.Test):
                 'blob': {'mtime': 2, 'digest': hashlib.sha1('2').hexdigest(), 'mime_type': 'application/octet-stream', 'path': tests.tmpdir + '/2/2/blob.blob'},
                 }),
             ],
-            read_diff(directory, [3, 4], 2))
+            [i for i in directory.diff(env.Sequence([[3, 4]]), out_seq)])
+        self.assertEqual([[3, 4]], out_seq)
 
+        out_seq = env.Sequence()
         self.assertEqual([
             ],
-            read_diff(directory, [3], 2))
+            [i for i in directory.diff(env.Sequence([[3, 3]]), out_seq)])
+        self.assertEqual([], out_seq)
 
+        out_seq = env.Sequence()
         self.assertEqual([
             ],
-            read_diff(directory, xrange(6, 100), 2))
+            [i for i in directory.diff(env.Sequence([[6, 100]]), out_seq)])
+        self.assertEqual([], out_seq)
         directory.update(guid='2', prop='22')
         self.assertEqual([
-            ('2', 6, {
+            ('2', {
                 'prop': {'value': '22', 'mtime': os.stat('2/2/prop').st_mtime},
                 }),
             ],
-            read_diff(directory, xrange(6, 100), 2))
+            [i for i in directory.diff(env.Sequence([[6, 100]]), out_seq)])
+        self.assertEqual([[6, 6]], out_seq)
+
+    def test_diff_Partial(self):
+
+        class Document(document.Document):
+
+            @active_property(slot=1)
+            def prop(self, value):
+                return value
+
+        directory = Directory(tests.tmpdir, Document, IndexWriter)
+        directory.create(guid='1', prop='1', ctime=1, mtime=1)
+        for i in os.listdir('1/1'):
+            os.utime('1/1/%s' % i, (1, 1))
+        directory.create(guid='2', prop='2', ctime=2, mtime=2)
+        for i in os.listdir('2/2'):
+            os.utime('2/2/%s' % i, (2, 2))
+
+        out_seq = env.Sequence()
+        for guid, diff in directory.diff(env.Sequence([[0, None]]), out_seq):
+            self.assertEqual('1', guid)
+            break
+        self.assertEqual([], out_seq)
+
+        out_seq = env.Sequence()
+        for guid, diff in directory.diff(env.Sequence([[0, None]]), out_seq):
+            if guid == '2':
+                break
+        self.assertEqual([[1, 1]], out_seq)
+
+        out_seq = env.Sequence()
+        for guid, diff in directory.diff(env.Sequence([[0, None]]), out_seq):
+            pass
+        self.assertEqual([[1, 2]], out_seq)
 
     def test_diff_WithBlobsSetByUrl(self):
 
@@ -513,15 +555,73 @@ class DocumentTest(tests.Test):
         for i in os.listdir('1/1'):
             os.utime('1/1/%s' % i, (1, 1))
 
+        out_seq = env.Sequence()
         self.assertEqual([
-            ('1', 2, {
+            ('1', {
                 'guid': {'value': '1', 'mtime': 1},
                 'ctime': {'value': 1, 'mtime': 1},
                 'mtime': {'value': 1, 'mtime': 1},
                 'blob': {'mtime': 1, 'mime_type': 'application/octet-stream', 'url': 'http://sugarlabs.org'},
                 }),
             ],
-            read_diff(directory, xrange(100), 2))
+            [i for i in directory.diff(env.Sequence([[0, None]]), out_seq)])
+        self.assertEqual([[1, 2]], out_seq)
+
+    def test_diff_Filter(self):
+
+        class Document(document.Document):
+
+            @active_property(prefix='P')
+            def prop(self, value):
+                return value
+
+        directory = Directory(tests.tmpdir, Document, IndexWriter)
+
+        directory.create(guid='1', ctime=1, mtime=1, prop='1')
+        directory.create(guid='2', ctime=2, mtime=2, prop='2')
+        for i in os.listdir('2/2'):
+            os.utime('2/2/%s' % i, (2, 2))
+
+        out_seq = env.Sequence()
+        self.assertEqual([
+            ('2', {
+                'guid': {'value': '2', 'mtime': 2},
+                'ctime': {'value': 2, 'mtime': 2},
+                'mtime': {'value': 2, 'mtime': 2},
+                'prop': {'value': '2', 'mtime': 2},
+                }),
+            ],
+            [i for i in directory.diff(env.Sequence([[0, None]]), out_seq, prop='2')])
+        self.assertEqual([[2, 2]], out_seq)
+
+    def test_diff_GroupBy(self):
+
+        class Document(document.Document):
+
+            @active_property(slot=1, prefix='P')
+            def prop(self, value):
+                return value
+
+        directory = Directory(tests.tmpdir, Document, IndexWriter)
+
+        directory.create(guid='1', ctime=1, mtime=1, prop='0')
+        for i in os.listdir('1/1'):
+            os.utime('1/1/%s' % i, (1, 1))
+        directory.create(guid='2', ctime=2, mtime=2, prop='0')
+        for i in os.listdir('2/2'):
+            os.utime('2/2/%s' % i, (2, 2))
+
+        out_seq = env.Sequence()
+        self.assertEqual([
+            ('2', {
+                'guid': {'value': '2', 'mtime': 2},
+                'ctime': {'value': 2, 'mtime': 2},
+                'mtime': {'value': 2, 'mtime': 2},
+                'prop': {'value': '0', 'mtime': 2},
+                }),
+            ],
+            [i for i in directory.diff(env.Sequence([[0, None]]), out_seq, group_by='prop')])
+        self.assertEqual([[2, 2]], out_seq)
 
     def test_merge_New(self):
 
@@ -552,7 +652,7 @@ class DocumentTest(tests.Test):
             os.utime('document1/3/3/%s' % i, (3, 3))
 
         directory2 = Directory('document2', Document, IndexWriter)
-        for guid, seqno, diff in directory1.diff(xrange(100), 2):
+        for guid, diff in directory1.diff(env.Sequence([[0, None]]), env.Sequence()):
             directory2.merge(guid, diff)
 
         self.assertEqual(
@@ -619,7 +719,7 @@ class DocumentTest(tests.Test):
         self.assertEqual(2, doc.meta('blob')['mtime'])
         self.assertEqual('2', file('document2/gu/guid/blob.blob').read())
 
-        for guid, seqno, diff in directory1.diff(xrange(100), 2):
+        for guid, diff in directory1.diff(env.Sequence([[0, None]]), env.Sequence()):
             directory2.merge(guid, diff)
 
         self.assertEqual(
@@ -634,7 +734,7 @@ class DocumentTest(tests.Test):
         self.assertEqual('2', file('document2/gu/guid/blob.blob').read())
 
         os.utime('document1/gu/guid/mtime', (3, 3))
-        for guid, seqno, diff in directory1.diff(xrange(100), 2):
+        for guid, diff in directory1.diff(env.Sequence([[0, None]]), env.Sequence()):
             directory2.merge(guid, diff)
 
         self.assertEqual(
@@ -649,7 +749,7 @@ class DocumentTest(tests.Test):
         self.assertEqual('2', file('document2/gu/guid/blob.blob').read())
 
         os.utime('document1/gu/guid/blob', (4, 4))
-        for guid, seqno, diff in directory1.diff(xrange(100), 2):
+        for guid, diff in directory1.diff(env.Sequence([[0, None]]), env.Sequence()):
             directory2.merge(guid, diff)
 
         self.assertEqual(
@@ -675,7 +775,7 @@ class DocumentTest(tests.Test):
         directory1.create(guid='1', prop='1', ctime=1, mtime=1)
 
         directory2 = Directory('document2', Document, IndexWriter)
-        for guid, seqno, diff in directory1.diff(xrange(100), 2):
+        for guid, diff in directory1.diff(env.Sequence([[0, None]]), env.Sequence()):
             directory2.merge(guid, diff, increment_seqno=False)
         self.assertEqual(
                 [(1, 1, '1', '1')],
@@ -686,7 +786,7 @@ class DocumentTest(tests.Test):
         self.assertEqual(0, doc.meta('prop')['seqno'])
 
         directory3 = Directory('document3', Document, IndexWriter)
-        for guid, seqno, diff in directory1.diff(xrange(100), 2):
+        for guid, diff in directory1.diff(env.Sequence([[0, None]]), env.Sequence()):
             directory3.merge(guid, diff=diff)
         self.assertEqual(
                 [(1, 1, '1', '1')],
@@ -698,7 +798,7 @@ class DocumentTest(tests.Test):
 
         directory1.update(guid='1', prop='2', ctime=2, mtime=2)
 
-        for guid, seqno, diff in directory1.diff(xrange(100), 2):
+        for guid, diff in directory1.diff(env.Sequence([[0, None]]), env.Sequence()):
             directory3.merge(guid, diff, increment_seqno=False)
         self.assertEqual(
                 [(2, 2, '1', '2')],
@@ -711,7 +811,7 @@ class DocumentTest(tests.Test):
         time.sleep(1)
         directory1.update(guid='1', prop='3', ctime=3, mtime=3)
 
-        for guid, seqno, diff in directory1.diff(xrange(100), 2):
+        for guid, diff in directory1.diff(env.Sequence([[0, None]]), env.Sequence()):
             directory3.merge(guid, diff)
         self.assertEqual(
                 [(3, 3, '1', '3')],
@@ -735,7 +835,7 @@ class DocumentTest(tests.Test):
             os.utime('document1/gu/guid/%s' % i, (1, 1))
 
         directory2 = Directory('document2', Document, IndexWriter)
-        for guid, seqno, diff in directory1.diff(xrange(100), 2):
+        for guid, diff in directory1.diff(env.Sequence([[0, None]]), env.Sequence()):
             directory2.merge(guid, diff)
 
         doc = directory2.get('guid')
@@ -904,15 +1004,5 @@ class DocumentTest(tests.Test):
                 db._find(query='prop:=1', order_by='prop')[0])
 
 
-def read_diff(directory, *args, **kwargs):
-    result = []
-    for guid, seqno, data in directory.diff(*args, **kwargs):
-        if hasattr(data, 'read'):
-            result.append((guid, seqno, data.read()))
-        else:
-            result.append((guid, seqno, data))
-    return result
-
-
 if __name__ == '__main__':
     tests.main()
diff --git a/tests/units/env.py b/tests/units/env.py
index c5f0b56..18a2b7d 100755
--- a/tests/units/env.py
+++ b/tests/units/env.py
@@ -1,11 +1,13 @@
 #!/usr/bin/env python
 # sugar-lint: disable
 
+import copy
 from os.path import exists
 
 from __init__ import tests
 
 from active_document import env
+from active_document.env import Sequence
 
 
 class EnvTest(tests.Test):
@@ -49,6 +51,316 @@ class EnvTest(tests.Test):
         self.assertEqual('bar', env.gettext({'1-a': 'foo', '1': 'bar', 'default': 'default'}, '1-b'))
         self.assertEqual('foo', env.gettext({'1-a': 'foo', '2': 'bar', 'default': 'default'}, '1-b'))
 
+    def test_Sequence_empty(self):
+        scale = Sequence(empty_value=[1, None])
+        self.assertEqual(
+                [[1, None]],
+                scale)
+        assert scale.empty
+        scale.exclude(1, 1)
+        assert not scale.empty
+
+        scale = Sequence()
+        self.assertEqual(
+                [],
+                scale)
+        assert scale.empty
+        scale.include(1, None)
+        assert not scale.empty
+
+    def test_Sequence_exclude(self):
+        scale = Sequence(empty_value=[1, None])
+        scale.exclude(1, 10)
+        self.assertEqual(
+                [[11, None]],
+                scale)
+
+        scale = Sequence(empty_value=[1, None])
+        scale.exclude(5, 10)
+        self.assertEqual(
+                [[1, 4], [11, None]],
+                scale)
+
+        scale.exclude(2, 2)
+        self.assertEqual(
+                [[1, 1], [3, 4], [11, None]],
+                scale)
+
+        scale.exclude(1, 1)
+        self.assertEqual(
+                [[3, 4], [11, None]],
+                scale)
+
+        scale.exclude(3, 3)
+        self.assertEqual(
+                [[4, 4], [11, None]],
+                scale)
+
+        scale.exclude(1, 20)
+        self.assertEqual(
+                [[21, None]],
+                scale)
+
+        scale.exclude(21, 21)
+        self.assertEqual(
+                [[22, None]],
+                scale)
+
+    def test_Sequence_include_JoinExistingItems(self):
+        scale = Sequence()
+
+        scale.include(1, None)
+        self.assertEqual(
+                [[1, None]],
+                scale)
+
+        scale.include(2, None)
+        self.assertEqual(
+                [[1, None]],
+                scale)
+
+        scale.include(4, 5)
+        self.assertEqual(
+                [[1, None]],
+                scale)
+
+        scale.exclude(2, 2)
+        scale.exclude(4, 4)
+        scale.exclude(6, 6)
+        scale.exclude(9, 9)
+        self.assertEqual(
+                [[1, 1],
+                    [3, 3],
+                    [5, 5],
+                    [7, 8],
+                    [10, None]],
+                scale)
+
+        scale.include(10, 20)
+        self.assertEqual(
+                [[1, 1],
+                    [3, 3],
+                    [5, 5],
+                    [7, 8],
+                    [10, None]],
+                scale)
+
+        scale.include(8, 20)
+        self.assertEqual(
+                [[1, 1],
+                    [3, 3],
+                    [5, 5],
+                    [7, None]],
+                scale)
+
+        scale.include(5, None)
+        self.assertEqual(
+                [[1, 1],
+                    [3, 3],
+                    [5, None]],
+                scale)
+
+        scale.include(1, None)
+        self.assertEqual(
+                [[1, None]],
+                scale)
+
+    def test_Sequence_include_InsertNewItems(self):
+        scale = Sequence()
+
+        scale.include(8, 10)
+        scale.include(3, 3)
+        self.assertEqual(
+                [[3, 3],
+                    [8, 10]],
+                scale)
+
+        scale.include(9, 11)
+        self.assertEqual(
+                [[3, 3],
+                    [8, 11]],
+                scale)
+
+        scale.include(7, 12)
+        self.assertEqual(
+                [[3, 3],
+                    [7, 12]],
+                scale)
+
+        scale.include(5, 5)
+        self.assertEqual(
+                [[3, 3],
+                    [5, 5],
+                    [7, 12]],
+                scale)
+
+        scale.include(4, 4)
+        self.assertEqual(
+                [[3, 5],
+                    [7, 12]],
+                scale)
+
+        scale.include(1, 1)
+        self.assertEqual(
+                [[1, 1],
+                    [3, 5],
+                    [7, 12]],
+                scale)
+
+        scale.include(2, None)
+        self.assertEqual(
+                [[1, None]],
+                scale)
+
+    def teste_Sequence_Invert(self):
+        scale_1 = Sequence(empty_value=[1, None])
+        scale_1.exclude(2, 2)
+        scale_1.exclude(5, 10)
+
+        scale_2 = copy.deepcopy(scale_1[:])
+        scale_2[-1][1] = 20
+
+        self.assertEqual(
+                [
+                    [1, 1],
+                    [3, 4],
+                    [11, None],
+                    ],
+                scale_1)
+        scale_1.exclude(scale_2)
+        self.assertEqual(
+                [[21, None]],
+                scale_1)
+
+    def test_Sequence_contains(self):
+        scale = Sequence(empty_value=[1, None])
+        scale.exclude(2, 2)
+        scale.exclude(5, 10)
+
+        assert 1 in scale
+        assert 2 not in scale
+        assert 3 in scale
+        assert 5 not in scale
+        assert 10 not in scale
+        assert 11 in scale
+
+    def test_Sequence_first(self):
+        scale = Sequence()
+        self.assertEqual(0, scale.first)
+
+        scale = Sequence(empty_value=[1, None])
+        self.assertEqual(1, scale.first)
+        scale.exclude(1, 3)
+        self.assertEqual(4, scale.first)
+
+    def test_Sequence_include(self):
+        rng = Sequence()
+        rng.include(2, 2)
+        self.assertEqual(
+                [[2, 2]],
+                rng)
+        rng.include(7, 10)
+        self.assertEqual(
+                [[2, 2], [7, 10]],
+                rng)
+        rng.include(5, 5)
+        self.assertEqual(
+                [[2, 2], [5, 5], [7, 10]],
+                rng)
+        rng.include(15, None)
+        self.assertEqual(
+                [[2, 2], [5, 5], [7, 10], [15, None]],
+                rng)
+        rng.include(3, 5)
+        self.assertEqual(
+                [[2, 5], [7, 10], [15, None]],
+                rng)
+        rng.include(11, 14)
+        self.assertEqual(
+                [[2, 5], [7, None]],
+                rng)
+
+        rng = Sequence()
+        rng.include(10, None)
+        self.assertEqual(
+                [[10, None]],
+                rng)
+        rng.include(7, 8)
+        self.assertEqual(
+                [[7, 8], [10, None]],
+                rng)
+        rng.include(2, 2)
+        self.assertEqual(
+                [[2, 2], [7, 8], [10, None]],
+                rng)
+
+    def test_Sequence_Union(self):
+        seq_1 = Sequence()
+        seq_1.include(1, 2)
+        seq_2 = Sequence()
+        seq_2.include(3, 4)
+        seq_1.include(seq_2)
+        self.assertEqual(
+                [[1, 4]],
+                seq_1)
+
+        seq_1 = Sequence()
+        seq_1.include(1, None)
+        seq_2 = Sequence()
+        seq_2.include(3, 4)
+        seq_1.include(seq_2)
+        self.assertEqual(
+                [[1, None]],
+                seq_1)
+
+        seq_2 = Sequence()
+        seq_2.include(1, None)
+        seq_1 = Sequence()
+        seq_1.include(3, 4)
+        seq_1.include(seq_2)
+        self.assertEqual(
+                [[1, None]],
+                seq_1)
+
+        seq_1 = Sequence()
+        seq_1.include(1, None)
+        seq_2 = Sequence()
+        seq_2.include(2, None)
+        seq_1.include(seq_2)
+        self.assertEqual(
+                [[1, None]],
+                seq_1)
+
+        seq_1 = Sequence()
+        seq_2 = Sequence()
+        seq_2.include(seq_1)
+        self.assertEqual([], seq_2)
+
+        seq_1 = Sequence()
+        seq_2 = Sequence()
+        seq_2.include(1, None)
+        seq_2.include(seq_1)
+        self.assertEqual([[1, None]], seq_2)
+
+        seq = Sequence()
+        seq.include(10, 11)
+        seq.include(None)
+        self.assertEqual([[10, 11]], seq)
+
+    def test_Sequence_last(self):
+        seq = Sequence()
+        self.assertEqual(None, seq.last)
+
+        seq = Sequence()
+        seq.include(10, None)
+        self.assertEqual(None, seq.last)
+
+        seq = Sequence()
+        seq.include(1, 1)
+        seq.include(3, 5)
+        seq.include(10, 11)
+        self.assertEqual(11, seq.last)
+
 
 if __name__ == '__main__':
     tests.main()
diff --git a/tests/units/index.py b/tests/units/index.py
index d110fda..f7f1859 100755
--- a/tests/units/index.py
+++ b/tests/units/index.py
@@ -314,18 +314,25 @@ class IndexTest(tests.Test):
             'var_1': ActiveProperty('var_1', 1, 'A'),
             'var_2': ActiveProperty('var_2', 2, 'B'),
             'var_3': ActiveProperty('var_3', 3, 'C'),
+            'var_4': ActiveProperty('var_4', 4, 'D'),
             })
 
-        db.store('1', {'var_1': '1', 'var_2': '1', 'var_3': '3'}, True)
-        db.store('2', {'var_1': '2', 'var_2': '1', 'var_3': '4'}, True)
-        db.store('3', {'var_1': '3', 'var_2': '2', 'var_3': '4'}, True)
+        db.store('1', {'var_1': '1', 'var_2': '1', 'var_3': '3', 'var_4': 0}, True)
+        db.store('2', {'var_1': '2', 'var_2': '1', 'var_3': '4', 'var_4': 0}, True)
+        db.store('3', {'var_1': '3', 'var_2': '2', 'var_3': '4', 'var_4': 0}, True)
 
         self.assertEqual(
-                ([{'guid': '1', 'var_1': '1'}, {'guid': '3', 'var_1': '3'}], 2),
-                db._find(reply=['var_1'], group_by='var_2'))
+                [{'guid': '1', 'var_1': '1'}, {'guid': '3', 'var_1': '3'}],
+                db._find(reply=['var_1'], group_by='var_2')[0])
         self.assertEqual(
-                ([{'guid': '1', 'var_1': '1'}, {'guid': '2', 'var_1': '2'}], 2),
-                db._find(reply=['var_1'], group_by='var_3'))
+                [{'guid': '1', 'var_1': '1'}, {'guid': '2', 'var_1': '2'}],
+                db._find(reply=['var_1'], group_by='var_3')[0])
+        self.assertEqual(
+                [{'guid': '1'}],
+                db._find(reply=['guid'], group_by='var_4', order_by='var_1')[0])
+        self.assertEqual(
+                [{'guid': '3'}],
+                db._find(reply=['guid'], group_by='var_4', order_by='-var_1')[0])
 
     def test_MultipleValues(self):
         db = Index({