Author: Planet Debian Spanish

filter(lambda x: x.startsWith(prefix), word_list)

>>> tree = HintSearchTree()
>>> tree.put("nacho")
>>> tree.put("nachos")
>>> tree.put("nachete")
>>> tree.get_hints("nach")
['nachete', 'nacho', 'nachos']
>>> tree.get_hints("nacho")
['nacho', 'nachos']
>>> tree.delete("nacho")
>>> tree.get_hints("nacho")
['nachos']
>>> tree.count_words()
2
>>> tree.get_hints("n")
['nachete', 'nachos']
>>> tree.is_indexed("nachete")
True
>>> tree.is_indexed("nach")
False
>>> tree.empty()
False

class HintSearchTreeNode(object):
class HintSearchTreeNode(object):
  def __init__(self, parent=None, terminal=False):
    self._children = {}
    self._terminal = terminal
    self._parent = parent
 
  @property
  def children(self):
    return self._children
 
  @property
  def terminal(self):
    return self._terminal
 
  @terminal.setter
  def terminal(self, value):
    self._terminal = value
 
  @property
  def parent(self):
    return self._parent
 
class HintSearchTree(object):
  def __init__(self):
    self._root = HintSearchTreeNode()
 
  def put(self, word):
    """Adds a word to the tree."""
    # TODO: Sanitize 'word'
    if len(word) > 0:
      self._put(self._root, word)
 
  def count_words(self):
    """Retrieves the number of indexed words in the tree."""
    return self._count_words(self._root)
 
  def is_indexed(self, word):
    """Returns True if 'word' is indexed."""
    node = self._find(self._root, word)
    return node is not None and node.terminal is True
 
  def get_hints(self, prefix):
    """Returns a list of words prefixed by 'prefix'."""
    return self._match_prefix(self._root, prefix)
 
  def delete(self, word):
    """Deletes 'word' (if exists) from the tree."""
    terminal = self._find(self._root, word)
    if terminal is not None:
      terminal.terminal = False
      self._prune(terminal.parent, word)
 
  def empty(self):
    """Returns True if the tree contains no elements."""
    return len(self._root.children) == 0
 
  def _put(self, node, word, depth=0):
    next_node = node.children.get(word[depth])
    if next_node is None:
      next_node = HintSearchTreeNode(parent=node)
      node.children[word[depth]] = next_node
    if len(word)-1 == depth:
      next_node.terminal = True
    else:
      self._put(next_node, word, depth+1)
 
  def _count_words(self, node):
    words = 1 if node.terminal is True else 0
    for k in node.children:
      words += self._count_words(node.children[k])
    return words
 
  def _match_prefix(self, node, prefix):
    terminal = self._find(node, prefix)
    if terminal is not None:
      return self._harvest_node(terminal, prefix)
    else:
      return []
 
  def _harvest_node(self, node, prefix, path=""):
    hints = []
    if node.terminal is True:
      hints.append(prefix + path)
    for k in node.children:
      hints.extend(self._harvest_node(node.children[k], prefix, path+k))
    return hints
 
  def _find(self, node, word, depth=0):
    if depth == len(word):
      return node
    else:
      child = node.children.get(word[depth])
      if child is not None:
        return self._find(child, word, depth+1)
      else:
        return None
 
  def _prune(self, node, word):
    if self._count_words(node.children[word[-1]]) == 0:
      del node.children[word[-1]]
      if len(node.children) == 0 and node.parent is not None \
          and node.terminal is not True:
        self._prune(node.parent, word[:-1])

use warnings;
use threads;
 
use Thread::Queue;
use POSIX;
 
use IO::Socket::INET;
use HTTP::Request;
use HTTP::Status qw(:constants status_message);
 
use Getopt::Long;
use DateTime::Format::HTTP;
use Data::Validate::URI qw(is_http_uri);
use Log::Log4perl qw(:easy);
 
use constant MAX_THREADS => 10;
use constant MAX_LEN_HEADERS_BUFFER => 8*1024;
use constant DEFAULT_REDIRECT_URI => "http://www.example.org";
use constant DEFAULT_PORT => 80;
use constant DEFAULT_POOL_SIZE => 3;
 
my $redir_uri = DEFAULT_REDIRECT_URI;
my $server_port = DEFAULT_PORT;
my $thread_pool_size = DEFAULT_POOL_SIZE;
my $verbose;
 
GetOptions('url=s' => \$redir_uri, 
           'port=i' => \$server_port,
           'threads=i' => \$thread_pool_size,
           'verbose'  => \$verbose) or exit -1;
 
die "Invalid redirect URI (e.g. http://www.example.org)\n" unless is_http_uri($redir_uri);
die "Invalid port (e.g. 8080)\n" unless 0 < $server_port && $server_port < 2**16;
die "Invalid pool size (should be in [1..".MAX_THREADS."])\n" 
            unless 0 < $thread_pool_size && $thread_pool_size <= MAX_THREADS;
 
Log::Log4perl->easy_init( level => $verbose? $DEBUG : $INFO );
 
my $pending = Thread::Queue->new(); 
 
my $lsock = IO::Socket::INET->new( LocalPort => $server_port,
                                   Proto => 'tcp',
                                   Listen => 1,
                                   Reuse => 1 ) or die "Couldn't bind listening socket ($!)\n"; 
 
INFO("Listening on port $server_port\n");
INFO("Redirecting HTTP requests to: '$redir_uri'\n");
 
my @workers = ();
for (1..$thread_pool_size) {
    if ($thread = threads->create("worker")) {
        push(@workers, $thread);
    }
}
 
DEBUG(sprintf("%d thread(s) working under the hood\n", $#workers+1));
 
# Set a tidy shutdown just in case an external agent SIG{INT,TERM}s the process
$SIG{'INT'} = $SIG{'TERM'} = sub {
    # Dirty hack. threads->kill() does not wake up the thread :(
    for (1..@workers) {
        $pending->enqueue(-1);
    }
    for (@workers) {
        DEBUG(sprintf("Worker %d terminated: %d clients served\n", $_->tid, $_->join())); 
    }
    close($lsock); 
    exit 0; 
};
 
while(1) {
    my $csock = $lsock->accept() or next;
    $pending->enqueue(POSIX::dup(fileno $csock));
    DEBUG(sprintf("New client enqueued: %s:%s\n", $csock->peerhost, $csock->peerport));
    close($csock);
}
 
sub worker {
    my $clients_served = 0;
    while(my $fd = $pending->dequeue) { # API promises thread safety :-)
        if ($fd == -1) {
            return $clients_served;
        }
 
        my $sock = IO::Socket::INET->new_from_fd($fd, "r+");
        DEBUG(sprintf("Dequeued client %s:%d by worker %d.\n", $sock->peerhost,
                            $sock->peerport, threads->tid()));
 
        my $buf = "";
        while(<$sock>) {
            # CAUTION: there isn't any self protection against very long lines
            last if /^\r\n$/;
            $buf .= $_;
            goto BYE if length $buf > MAX_LEN_HEADERS_BUFFER;
        }
 
        if (my $request = HTTP::Request->parse($buf)) {
            INFO(sprintf("[%s] %s {%s}\n", $request->method, $request->uri, $sock->peerhost));
        }
 
        printf $sock "HTTP/1.1 %d %s\r\n", 
            HTTP_MOVED_PERMANENTLY, status_message(HTTP_MOVED_PERMANENTLY);
        printf $sock "Date: %s\r\n", DateTime::Format::HTTP->format_datetime;
        print $sock "Location: $redir_uri\r\n";
        print $sock "Server: Simple HTTP Redirection/0.1 ($^O)\r\n";
        print $sock "Connection: close\r\n";
        print $sock "\r\n";
 
BYE:  
        $clients_served++;
        close($sock);
    }
}

while [ 1 ]; 
 do echo -e "HTTP/1.1 301 Moved Permanently\r\nLocation: http://31337.pl\r\n\r\n" | nc -l 7070; 
done