balanced_ternary/lib.rs
1//! A [balanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary) data structure.
2//!
3//! A `Ternary` object in this module represents a number in the balanced ternary numeral system.
4//! Balanced ternary is a non-standard positional numeral system that uses three digits: {-1, 0, +1}
5//! represented here as `Neg` for -1, `Zero` for 0, and `Pos` for +1. It is useful in some domains
6//! of computer science and mathematics due to its arithmetic properties and representation
7//! symmetry.
8//!
9//! # Data Structures
10//!
11//! - **`Digit` Enum**:
12//! Represents a single digit for balanced ternary values, with possible values:
13//! - `Neg` for -1
14//! - `Zero` for 0
15//! - `Pos` for +1
16//!
17//! - **`Ternary` Struct**:
18//! Represents a balanced ternary number as a collection of `Digit`s.
19//! Provides utility functions for conversion, parsing, and manipulation.
20//!
21//! # Examples
22//!
23//! ## Converting between representations:
24//! ```rust
25//! use balanced_ternary::*;
26//!
27//! let ternary = Ternary::from_dec(5);
28//! assert_eq!(ternary.to_string(), "+--");
29//! assert_eq!(ternary.to_dec(), 5);
30//!
31//! let parsed = Ternary::parse("+--");
32//! assert_eq!(parsed.to_string(), "+--");
33//! assert_eq!(parsed.to_dec(), 5);
34//! ```
35//!
36//! ## Negative numbers:
37//! ```rust
38//! use balanced_ternary::*;
39//!
40//! let neg_five = Ternary::from_dec(-5);
41//! assert_eq!(neg_five.to_string(), "-++");
42//! assert_eq!(neg_five.to_dec(), -5);
43//!
44//! let negated = -&neg_five;
45//! assert_eq!(negated.to_string(), "+--");
46//! assert_eq!(negated.to_dec(), 5);
47//! ```
48//!
49//! ## Larger numbers:
50//! ```rust
51//! use balanced_ternary::*;
52//!
53//! let big = Ternary::from_dec(121);
54//! assert_eq!(big.to_string(), "+++++");
55//! assert_eq!(big.to_dec(), 121);
56//!
57//! let neg_big = Ternary::from_dec(-121);
58//! assert_eq!(neg_big.to_string(), "-----");
59//! assert_eq!(neg_big.to_dec(), -121);
60//! ```
61//!
62//! ## Operations
63//! ```
64//! use balanced_ternary::Ternary;
65//!
66//! let repr9 = Ternary::parse("+00");
67//! let repr4 = Ternary::parse("++");
68//! let repr13 = &repr9 + &repr4;
69//! let repr17 = &repr13 + &repr4;
70//! let repr34 = &repr17 + &repr17;
71//!
72//! assert_eq!(repr13.to_string(), "+++");
73//! assert_eq!(repr17.to_string(), "+-0-");
74//! assert_eq!(repr34.to_string(), "++-+");
75//!
76//! let repr30 = &repr34 - &repr4;
77//! assert_eq!(repr30.to_dec(), 30);
78//! assert_eq!(repr30.to_string(), "+0+0");
79//! ```
80//!
81#![no_std]
82extern crate alloc;
83
84use alloc::string::{String, ToString};
85use alloc::vec;
86use alloc::vec::Vec;
87use core::fmt::{Display, Formatter};
88use core::str::FromStr;
89
90/// Represents a digit in the balanced ternary numeral system.
91///
92/// A digit can have one of three values:
93/// - `Neg` (-1): Represents the value -1 in the balanced ternary system.
94/// - `Zero` (0): Represents the value 0 in the balanced ternary system.
95/// - `Pos` (+1): Represents the value +1 in the balanced ternary system.
96///
97/// Provides utility functions for converting to/from characters, integers, and negation.
98#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
99pub enum Digit {
100 /// Represents -1
101 Neg,
102 /// Represents 0
103 Zero,
104 /// Represents +1
105 Pos,
106}
107
108/// Provides helper functions for formatting integers in a given radix.
109///
110/// Used internally to convert decimal numbers into their ternary representation.
111/// - `x`: The number to be formatted.
112/// - `radix`: The base of the numeral system.
113///
114/// Returns a string representation of the number in the specified base.
115fn format_radix(mut x: u32, radix: u32) -> String {
116 let mut result = vec![];
117
118 loop {
119 let m = x % radix;
120 x /= radix;
121 result.push(core::char::from_digit(m, radix).unwrap());
122 if x == 0 {
123 break;
124 }
125 }
126 result.into_iter().rev().collect()
127}
128
129impl Digit {
130 /// Converts the `Digit` into its character representation.
131 ///
132 /// - Returns:
133 /// - `-` for `Digit::Neg`
134 /// - `0` for `Digit::Zero`
135 /// - `+` for `Digit::Pos`
136 pub fn to_char(&self) -> char {
137 match self {
138 Digit::Neg => '-',
139 Digit::Zero => '0',
140 Digit::Pos => '+',
141 }
142 }
143
144 /// Creates a `Digit` from its character representation.
145 ///
146 /// - Accepts:
147 /// - `-` for `Digit::Neg`
148 /// - `0` for `Digit::Zero`
149 /// - `+` for `Digit::Pos`
150 /// - Panics if the input character is invalid.
151 pub fn from_char(c: char) -> Digit {
152 match c {
153 '-' => Digit::Neg,
154 '0' => Digit::Zero,
155 '+' => Digit::Pos,
156 _ => panic!("Invalid value. A Ternary must be either -, 0 or +."),
157 }
158 }
159
160 /// Converts the `Digit` into its integer representation.
161 ///
162 /// - Returns:
163 /// - -1 for `Digit::Neg`
164 /// - 0 for `Digit::Zero`
165 /// - 1 for `Digit::Pos`
166 pub fn to_i8(&self) -> i8 {
167 match self {
168 Digit::Neg => -1,
169 Digit::Zero => 0,
170 Digit::Pos => 1,
171 }
172 }
173
174 /// Creates a `Digit` from its integer representation.
175 ///
176 /// - Accepts:
177 /// - -1 for `Digit::Neg`
178 /// - 0 for `Digit::Zero`
179 /// - 1 for `Digit::Pos`
180 /// - Panics if the input integer is invalid.
181 pub fn from_i8(i: i8) -> Digit {
182 match i {
183 -1 => Digit::Neg,
184 0 => Digit::Zero,
185 1 => Digit::Pos,
186 _ => panic!("Invalid value. A Ternary must be either -1, 0 or +1."),
187 }
188 }
189}
190
191/// Represents a balanced ternary number using a sequence of `Digit`s.
192///
193/// Provides functions for creating, parsing, converting, and manipulating balanced ternary numbers.
194#[derive(Debug, Clone, PartialEq, Eq, Hash)]
195pub struct Ternary {
196 digits: Vec<Digit>,
197}
198
199impl Ternary {
200 /// Creates a new balanced ternary number from a vector of `Digit`s.
201 pub fn new(digits: Vec<Digit>) -> Ternary {
202 Ternary { digits }
203 }
204
205 /// Returns the number of digits (length) of the balanced ternary number.
206 pub fn log(&self) -> usize {
207 self.digits.len()
208 }
209
210 /// Returns a reference to the [Digit] indexed by `index` if it exists.
211 ///
212 /// Digits are indexed **from the right**:
213 /// ```
214 /// use balanced_ternary::Ternary;
215 ///
216 /// // Indexes :
217 /// // 32
218 /// // 4||1
219 /// // 5||||0
220 /// // ||||||
221 /// // vvvvvv
222 /// let ternary = Ternary::parse("+++--+");
223 /// assert_eq!(ternary.get_digit(1).unwrap().to_char(), '-')
224 /// ```
225 pub fn get_digit(&self, index: usize) -> Option<&Digit> {
226 self.digits.iter().rev().nth(index)
227 }
228
229 /// Parses a string representation of a balanced ternary number into a `Ternary` object.
230 ///
231 /// Each character in the string must be one of `+`, `0`, or `-`.
232 pub fn parse(str: &str) -> Self {
233 let mut repr = Ternary::new(vec![]);
234 for c in str.chars() {
235 repr.digits.push(Digit::from_char(c));
236 }
237 repr
238 }
239
240 /// Converts the `Ternary` object to its integer (decimal) representation.
241 ///
242 /// Calculates the sum of each digit's value multiplied by the appropriate power of 3.
243 pub fn to_dec(&self) -> i64 {
244 let mut dec = 0;
245 for (rank, digit) in self.digits.iter().rev().enumerate() {
246 dec += digit.to_i8() as i64 * 3_i64.pow(rank as u32);
247 }
248 dec
249 }
250
251 /// Creates a balanced ternary number from a decimal integer.
252 ///
253 /// The input number is converted into its balanced ternary representation,
254 /// with digits represented as `Digit`s.
255 pub fn from_dec(dec: i64) -> Self {
256 let sign = dec.signum();
257 let str = format_radix(dec.abs() as u32, 3);
258 let mut next = 0u8;
259 let mut repr = Ternary::new(vec![]);
260 for digit in str.chars().rev() {
261 let digit = u8::from_str(&digit.to_string()).unwrap() + next;
262 if digit < 2 {
263 repr.digits.push(Digit::from_i8(digit as i8));
264 next = 0;
265 } else if digit == 2 {
266 repr.digits.push(Digit::from_i8(-1));
267 next = 1;
268 } else if digit == 3 {
269 repr.digits.push(Digit::from_i8(0));
270 next = 1;
271 }
272 }
273 if next == 1 {
274 repr.digits.push(Digit::from_i8(1));
275 }
276 repr.digits.reverse();
277 if sign == -1 {
278 -&repr
279 } else {
280 repr
281 }
282 }
283}
284
285impl Display for Ternary {
286 fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
287 let mut str = String::new();
288 for digit in self.digits.iter() {
289 str.push(digit.to_char());
290 }
291 write!(f, "{}", str)
292 }
293}
294
295pub mod operations;
296
297#[cfg(feature = "tryte")]
298pub mod tryte;
299
300#[cfg(test)]
301mod tests {
302 use super::*;
303 #[test]
304 fn test_ternary() {
305 let repr5 = Ternary::new(vec![Digit::Pos, Digit::Neg, Digit::Neg]);
306 assert_eq!(repr5.to_dec(), 5);
307 let repr5 = Ternary::from_dec(5);
308 assert_eq!(repr5.to_dec(), 5);
309
310 let repr13 = Ternary::new(vec![Digit::Pos, Digit::Pos, Digit::Pos]);
311 assert_eq!(repr13.to_dec(), 13);
312
313 let repr14 = Ternary::parse("+---");
314 let repr15 = Ternary::parse("+--0");
315 assert_eq!(repr14.to_dec(), 14);
316 assert_eq!(repr15.to_dec(), 15);
317 assert_eq!(repr14.to_string(), "+---");
318 assert_eq!(repr15.to_string(), "+--0");
319
320 let repr120 = Ternary::from_dec(120);
321 assert_eq!(repr120.to_dec(), 120);
322 assert_eq!(repr120.to_string(), "++++0");
323 let repr121 = Ternary::from_dec(121);
324 assert_eq!(repr121.to_dec(), 121);
325 assert_eq!(repr121.to_string(), "+++++");
326
327 let repr_neg_5 = Ternary::parse("-++");
328 assert_eq!(repr_neg_5.to_dec(), -5);
329 assert_eq!(repr_neg_5.to_string(), "-++");
330
331 let repr_neg_5 = Ternary::from_dec(-5);
332 assert_eq!(repr_neg_5.to_dec(), -5);
333 assert_eq!(repr_neg_5.to_string(), "-++");
334
335 let repr_neg_121 = Ternary::from_dec(-121);
336 assert_eq!(repr_neg_121.to_dec(), -121);
337 assert_eq!(repr_neg_121.to_string(), "-----");
338
339 let test = Ternary::from_dec(18887455);
340 assert_eq!(test.to_dec(), 18887455);
341 assert_eq!(test.to_string(), "++00--0--+-0++0+");
342 }
343}