Faster pagination / model object seeking (10x faster infact :o) for larger datasets (500k +)

"""
    ModelPagination
    Designed and Coded by Cal Leeming
    Many thanks to Harry Roberts for giving us a heads up on how to do this properly!

    You may also notice the class is almost exactly the same as the django pagination, give or take :)
    http://docs.djangoproject.com/en/dev/topics/pagination/?from=olddocs
    So this means, in most cases, you can use this as a drop in replacement.
    Although, if you are looking at using this, you would probably not just "drop it in" lol.

    ----------------------------------------------------------------------------

    This is a super optimized way of paginating datasets over 1 million records.
    It uses MAX() rather then COUNT(), because this is super faster.

    EXAMPLE:
    >>> _t = time.time(); x = Post.objects.aggregate(Max('id')); "Took %ss"%(time.time() - _t )
    'Took 0.00103402137756s'
    >>> _t = time.time(); x = Post.objects.aggregate(Count('id')); "Took %ss"%(time.time() - _t )
    'Took 0.92404794693s'
    >>>

    This does mean that if you go deleting things, then the IDs won't be accurate,
    so if you delete 50 rows, you're exact count() isn't going to match, but this is
    okay for pagination, because for SEO, we want items to stay on the original page
    they were scanned on. If you go deleting items, then the items shift backwards
    through the pages, so you end up with inconsistent SEO on archive pages. If this
    doesn't make sense, go figure it out for yourself, its 2am in the morning ffs ;p

    Now, the next thing we do, is use id seeking, rather then OFFSET, because again,
    this is a shitton faster:

    EXAMPLE:
    >>> _t = time.time(); x = map(lambda x: x, Post.objects.filter(id__gte=400000, id__lt=400500).all()); print "Took %ss"%(time.time() - _t)
    Took 0.0467309951782s
    >>> _t = time.time(); _res = map(lambda x: x, Post.objects.all()[400000:400500]); print "Took %ss"%(time.time() - _t)
    Took 1.05785298347s
    >>>

    By using this seeking method (which btw, can be implemented on anything, not just pagination)
    on a table with 5 million rows, we are saving 0.92s on row count, and 1.01s on item grabbing.
    This may not seem like much, but if you have 1024 concurrent users, this will make a huge
    difference.

    If you have any questions or problems, feel free to contact me on
    cal.leeming [at] simplicitymedialtd.co.uk

"""
from django.core.paginator import Paginator, InvalidPage, EmptyPage
from django.db.models import Max,Count,Q,F

class ModelPagination:
    model = None
    items_per_page = None
    count = None
    page_range = []

    def __init__(self, model, items_per_page):
        self.model = model
        self.items_per_page = items_per_page
        self.count = self.model.aggregate(Max('id'))['id__max']
        self.num_pages = divmod(self.count, self.items_per_page)[0]+1

        for i in range(self.num_pages):
            self.page_range.append(i+1)

    def page(self, page_number):
        if page_number > self.num_pages:
            raise EmptyPage, "That page contains no results"

        if page_number <= 0:
            raise EmptyPage, "That page number is less than 1"

        start = self.items_per_page * (page_number-1)
        end = self.items_per_page * page_number

        object_list = self.model.filter(id__gte=start, id__lt=end)
        return ModelPaginationPage(object_list, page_number, self.count, start, end, self)

class ModelPaginationPage:
    object_list = None
    number = None
    count = None
    start = None
    end = None
    paginator = None

    def __unicode__(self):
        return "<Page %s of %s>"%(self.number, self.count)

    def __init__(self, object_list, number, count, start, end, paginator):
        self.number = number
        self.count = count
        self.object_list = object_list
        self.start = start
        self.end = end
        self.paginator = paginator

    def has_next(self):
        return False if self.number >= self.count else True

    def has_previous(self):
        return False if self.number <= 1 else True

    def has_other_pages(self):
        return True if self.has_next or self.has_previous else False

    def next_number(self):
        return self.number + 1

    def previous_number(self):
        return self.number + 1

    def start_index(self):
        return self.start

    def end_index(self):
        return self.end

###############################################################################
# OUR EXAMPLE USAGE
###############################################################################
def archive(request, *args, **kwargs):
    _t = time.time()

    # 4chan
    if kwargs.get('feed') == '4chan':
        ret = Post.objects
        url = '/archive/4chan-page-'

    else:
        raise Exception, "Invalid feed specified"

    # calculate what page we are on
    page_num = int(args[0]) if args and args[0] else 1

    # create the pagination object
    _items_per_page = 1000
    pagination = ModelPagination(Post.objects, 1000)
    
    # extract the items from the page
    page = pagination.page(page_num)

    items = map(lambda x: {
        'id' : x.get('id'),
        'username' : x.get('username'),
        'title' : make_title(x.get('message'), x.get('image_filename'), x.get('username')),
        'url' : "/fcp/%s-%s.html"%(make_title(x.get('message'), x.get('image_filename'), x.get('username')), x.get('id')),
        'partial_message' : x.get('message')[:256] if x.get('message') else None,
        'created': x.get('created'),
        'image_url' : x.get('image_url')

    }, page.object_list.values('id', 'username', 'message', 'image_filename', 'created', 'image_url'))

    context = RequestContext(request, {
        'url' : url,
        'page_num' : page_num,
        'loading_time' : time.time() - _t,
        'page' : page,
        'items' : items,
        'pagination' : pagination
    })

    return render_to_response('lazylittlegirl/archive/results.html', context_instance=context)


"""
<!-- Here is some example usage in a template, again this is just a copy and paste out of one of our projects, and not intended as a unit test or w/e -->
    <div id="content">
        <ol>
            {% for item in items %}
                <li class="li1">
                    <div class="box1">
                        <a href="{{item.url}}" alt="{{item.title}}" title="{{item.title}}" target="_blank">Post #{{item.id}}</a> - {{item.created}} by {{item.username}} 
                    </div>
                </li>
            {% endfor %}
        </ol>

   <br />
   <hr />
   
    <div id="pagenumbers"><b>Pages :</b>
        {% for xpage in pagination.page_range %}
            {% if page.number == xpage %}
                [<b>{{xpage}}</b>]
            {% else %}
                <a title="Page {{xpage}} of {{pagination.num_pages}}" alt="Page {{xpage}} of {{pagination.num_pages}}" href="{{url}}{{xpage}}.html">{{xpage}}</a>
            {% endif %}
        {% endfor %}
    </div>
"""