Merging upstream version 1.44.3.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 210 insertions, 0 deletions

diff --git a/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_abstract.h b/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_abstract.h
new file mode 100644
index 000000000..942b4e3c2
--- /dev/null
+++ b/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_abstract.h
@@ -0,0 +1,210 @@
+// Copyright (C) 2004  Davis E. King (davis@dlib.net)
+// License: Boost Software License   See LICENSE.txt for the full license.
+#undef DLIB_LZ77_BUFFER_KERNEl_ABSTRACT_
+#ifdef DLIB_LZ77_BUFFER_KERNEl_ABSTRACT_
+
+#include "../algs.h"
+
+namespace dlib
+{
+
+    class lz77_buffer 
+    {
+        /*!
+            INITIAL VALUE
+                get_history_buffer_limit() == defined by constructor arguments
+                get_lookahead_buffer_limit() == defined by constructor arguments
+                get_history_buffer_size() == 0
+                get_lookahead_buffer_size() == 0
+
+
+            WHAT THIS OBJECT REPRESENTS
+                This object represents a pair of buffers (history and lookahead buffers) 
+                used during lz77 style compression.
+
+                It's main function is to search the history buffer for long strings which
+                match the contents (or a part of the contents) of the lookahead buffer.
+                
+
+            HISTORY AND LOOKAHEAD BUFFERS
+                The buffers have the following structure:
+                | history buffer | lookahead buffer |  <-- contents of buffers
+                |  ...9876543210 | 0123456789...    |  <-- index numbers
+
+                So this means that history_buffer(0) == 'r', history_buffer(1) == 'e'
+                and so on.  And lookahead_buffer(0) == 'l', lookahead_buffer(1) == 'o'
+                and so on.
+
+
+                What shift_buffers() does in english:
+                    This function just means that the buffers have their contents shifted
+                    left by N elements and that elements shifted out of the lookahead buffer 
+                    go into the history buffer.   An example will make it clearer.
+
+                    Suppose that we have the following buffers before we apply shift_buffers()
+                        history_buffer() == "hey" and
+                        lookahead_buffer() == "lookahead buffer"
+                    And in the same format as the above diagram it would be
+                        | hey | lookahead buffer |  <-- contents of buffers
+                        | 210 | 0123456789...    |  <-- index numbers
+
+                    Applying shift_buffers(4) will give
+                        lookahead_buffer() == "ahead buffer"
+                        history_buffer() == "heylook" or "eylook" or "ylook" or "look"
+
+                    You might be wondering why the history_buffer can resize itself in 
+                    such a nondeterministic way.  It is just to allow a lot of freedom in the 
+                    implementations of this object.                                  
+        !*/
+
+    public:
+
+        lz77_buffer (
+            unsigned long total_limit,
+            unsigned long lookahead_limit            
+        );
+        /*!
+            requires
+                - 6 < total_limit < 32
+                - 15 < lookahead_limit <= 2^(total_limit-2)
+            ensures                
+                - #*this is properly initialized
+                - #get_history_buffer_limit() == 2^total_limit  - lookahead_limit
+                - #get_lookahead_buffer_limit() == lookahead_limit
+            throws
+                - std::bad_alloc
+        !*/
+
+        virtual ~lz77_buffer (
+        );
+        /*!
+            ensures
+                - any resources associated with *this have been released
+        !*/
+
+        void clear(
+        );
+        /*!
+            ensures
+                - #*this has its initial value
+            throws
+                - std::bad_alloc
+                    if this exception is thrown then #*this is unusable 
+                    until clear() is called and succeeds
+        !*/
+
+        void shift_buffers (
+            unsigned long N
+        );
+        /*!
+            requires
+                - N <= get_lookahead_buffer_size()
+            ensures
+                - #get_lookahead_buffer_size() == get_lookahead_buffer_size() - N
+                - #get_history_buffer_size() >= N
+                - #get_history_buffer_size() <= get_history_buffer_size()+N
+                - #get_history_buffer_size() <= get_history_buffer_limit()
+                - for all i where 0 <= i < N:
+                    #history_buffer(N-1-i) == lookahead_buffer(i)
+                - for all i where 0 <= i < #get_history_buffer_size()-N:
+                    #history_buffer(N+i) == history_buffer(i)
+                - for all i where 0 <= i < #get_lookahead_buffer_size()
+                    #lookahead_buffer(i) == lookahead_buffer(N+i)            
+        !*/
+
+        void add (
+            unsigned char symbol
+        );
+        /*!
+            ensures
+                - if (get_lookahead_buffer_size() == get_lookahead_buffer_limit()) then
+                    - performs shift_buffers(1)
+                    - #lookahead_buffer(get_lookahead_buffer_limit()-1) == symbol
+                    - #get_lookahead_buffer_size() == get_lookahead_buffer_size()
+                - else
+                    - #lookahead_buffer(get_lookahead_buffer_size()) == symbol
+                    - #get_lookahead_buffer_size() == get_lookahead_buffer_size() + 1                                    
+            throws
+                - std::bad_alloc
+                    if this exception is thrown then #*this is unusable 
+                    until clear() is called and succeeds
+        !*/
+
+        void find_match (
+            unsigned long& index,
+            unsigned long& length,
+            unsigned long min_match_length
+        );
+        /*!
+            ensures
+                - if (#length != 0) then
+                    - #length >= min_match_length
+                    - for all i where 0 <= i < #length:
+                      history_buffer(#index-i) == lookahead_buffer(i)
+                    - performs shift_buffers(#length)
+            throws
+                - std::bad_alloc
+                    if this exception is thrown then #*this is unusable 
+                    until clear() is called and succeeds
+        !*/
+
+        unsigned long get_history_buffer_limit (
+        ) const;
+        /*!
+            ensures
+                - returns the max number of symbols that can fit in the history buffer
+        !*/
+
+        unsigned long get_lookahead_buffer_limit (
+        ) const;
+        /*!
+            ensures
+                - returns the max number of symbols that can fit in the lookahead buffer
+        !*/
+
+        unsigned long get_history_buffer_size (
+        ) const;
+        /*!
+            ensures
+                - returns the number of symbols currently in the history buffer
+        !*/
+
+        unsigned long get_lookahead_buffer_size (
+        ) const;
+        /*!
+            ensures
+                - returns the number of symbols currently in the lookahead buffer
+        !*/
+
+        unsigned char lookahead_buffer (
+            unsigned long index
+        ) const;
+        /*!
+            requires
+                - index < get_lookahead_buffer_size()
+            ensures
+                - returns the symbol in the lookahead buffer at location index
+        !*/
+
+        unsigned char history_buffer (
+            unsigned long index
+        ) const;
+        /*!
+            requires
+                - index < get_history_buffer_size()
+            ensures
+                - returns the symbol in the history buffer at location index
+        !*/
+
+
+    private:
+
+        // restricted functions
+        lz77_buffer(lz77_buffer&);        // copy constructor
+        lz77_buffer& operator=(lz77_buffer&);    // assignment operator
+
+    };      
+}
+
+#endif // DLIB_LZ77_BUFFER_KERNEl_ABSTRACT_
+