# pyuca - Unicode Collation Algorithm
# Version: 2012-06-21
#
# James Tauber
# http://jtauber.com/

# Copyright (c) 2006-2012 James Tauber and contributors
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.


"""
Preliminary implementation of the Unicode Collation Algorithm.

This only implements the simple parts of the algorithm but I have successfully
tested it using the Default Unicode Collation Element Table (DUCET) to collate
Ancient Greek correctly.

Usage example:

    from pyuca import Collator
    c = Collator("allkeys.txt")

    sorted_words = sorted(words, key=c.sort_key)

allkeys.txt (1 MB) is available at

    http://www.unicode.org/Public/UCA/latest/allkeys.txt

but you can always subset this for just the characters you are dealing with.
"""


class Node:
    
    def __init__(self):
        self.value = None
        self.children = {}


class Trie:
    
    def __init__(self):
        self.root = Node()
    
    def add(self, key, value):
        curr_node = self.root
        for part in key:
            curr_node = curr_node.children.setdefault(part, Node())
        curr_node.value = value
    
    def find_prefix(self, key):
        curr_node = self.root
        remainder = key
        for part in key:
            if part not in curr_node.children:
                break
            curr_node = curr_node.children[part]
            remainder = remainder[1:]
        return (curr_node.value, remainder)


class Collator:

    def __init__(self, filename):

        self.table = Trie()
        self.load(filename)

    def load(self, filename):
        for line in open(filename):
            if line.startswith("#") or line.startswith("%"):
                continue
            if line.strip() == "":
                continue
            line = line[:line.find("#")] + "\n"
            line = line[:line.find("%")] + "\n"
            line = line.strip()
            
            if line.startswith("@"):
                pass
            else:
                semicolon = line.find(";")
                charList = line[:semicolon].strip().split()
                x = line[semicolon:]
                collElements = []
                while True:
                    begin = x.find("[")
                    if begin == -1:
                        break                
                    end = x[begin:].find("]")
                    collElement = x[begin:begin+end+1]
                    x = x[begin + 1:]
                    
                    alt = collElement[1]
                    chars = collElement[2:-1].split(".")
                    
                    collElements.append((alt, chars))
                integer_points = [int(ch, 16) for ch in charList]
                self.table.add(integer_points, collElements)
    
    def sort_key(self, string):
        
        collation_elements = []
        
        lookup_key = [ord(ch) for ch in string]
        while lookup_key:
            value, lookup_key = self.table.find_prefix(lookup_key)
            if not value:
                # Calculate implicit weighting for CJK Ideographs
                # contributed by David Schneider 2009-07-27
                # http://www.unicode.org/reports/tr10/#Implicit_Weights
                value = []
                value.append((".", ["%X" % (0xFB40 + (lookup_key[0] >> 15)), "0020", "0002", "0001"]))
                value.append((".", ["%X" % ((lookup_key[0] & 0x7FFF) | 0x8000), "0000", "0000", "0000"]))
                lookup_key = lookup_key[1:]
            collation_elements.extend(value)
        sort_key = []
        
        for level in range(4):
            if level:
                sort_key.append(0) # level separator
            for element in collation_elements:
                ce_l = int(element[1][level], 16)
                if ce_l:
                    sort_key.append(ce_l)
        
        return tuple(sort_key)